PDPTW-BCP-Java-CPLEX

基于 Java 和 IBM ILOG CPLEX 的带时间窗取送货问题（Pickup and Delivery Problem with Time Windows, PDPTW）分支切割定价求解器。

项目围绕 Gschwind、Irnich、Rothenbaecher 和 Tilk（2018）的双向标签列生成算法 进行实现与复现，包含可穷尽的 elementary pricing、割平面、分支定价以及用于论文配置 的统一运行入口。

当前仓库是研究型实现。算法机制及代表性算例已经得到较完整验证，但不把论文全部 benchmark 表格的逐项重现作为完成标准。详细实现记录、证据和剩余性能问题见 Work.md。

已实现内容

• 基于集合覆盖模型的受限主问题（RMP）。
• CPLEX 主问题求解，以及用于小规模验证的自研两阶段单纯形后端。
• 前向、后向和双向标签定价。
• 静态与动态 half-way point，SS/SW dominance。
• Arc-reduced 启发式定价及 unrestricted exact fallback。
• Elementary route、资源扩展、双向标签合并和路线 replay 校验。
• Subset-Row、rounded-capacity 和随机化 2-path cuts。
• Vehicle-count 与 set-outflow 分支规则。
• Branch-Cut-and-Price、Phase-I/Phase-II 人工变量和精确定价证书传播。
• RC、RC+、Li & Lim 及 reverse 实例组配置。
• Tiny pricing oracle 和端到端回归验证入口。

环境要求

• Windows PowerShell。
• JDK 21 或更高版本。
• IBM ILOG CPLEX Optimization Studio。

批处理脚本默认从以下目录加载 CPLEX：

D:\Application_install\Cplex

如果安装位置不同，请先设置 CPLEX_STUDIO_DIR：

$env:CPLEX_STUDIO_DIR = 'C:\Program Files\IBM\ILOG\CPLEX_Studio2211'

CPLEX 是商业软件，不包含在本仓库中。运行前需要自行安装并确保许可证可用。

快速开始

git clone https://github.com/nitrazepam01/PDPTW-BCP-Java-CPLEX.git
Set-Location .\PDPTW-BCP-Java-CPLEX

.\build.bat
.\run.bat .\PDPTW_instances\RC\AA30_12.ll --paper-exact --time=120

求解完成后，程序会在实例旁生成 <instance>.solution.txt。这些结果文件已被 .gitignore 排除。

对于文件名无法自动识别论文实例组的算例，可以显式指定分组：

.\run.bat .\PDPTW_instances\RC\b_AA50_20.ll `
  --paper-exact --paper-group=RC --time=600

常用参数

参数	说明
--paper-exact	启用面向论文复现的 elementary Branch-Cut-and-Price 配置
--paper-group=<group>	指定 RC、RC_PLUS、LL 或对应 reverse 分组
--bp	启用 Branch-and-Price
--nocuts	禁用 Subset-Row cuts；不能与 --paper-exact 同用
--robust	启用 robust-cut separation
--nong	禁用 NG-route relaxation
--pricing=<mode>	选择 static、static-sw、dynamic、dynamic-sw、forward 或 backward
--nodes=<n>	设置最大分支节点数
--time=<sec>	设置总时间限制
--depth-first	使用深度优先节点选择
--best-bound	使用最小 LP 下界节点选择

--paper-exact 默认使用动态双向定价、TAILORED SR dominance、SR/robust cuts、 depth-first Branch-and-Price，并关闭 NG-route relaxation。启发式定价不能独立提供最优性 证明；程序只有在 unrestricted exact pricing 完成并满足证书条件后才报告精确下界。

验证

验证单个实例：

.\verify.bat .\PDPTW_instances\RC\AA30_12.ll

运行仓库内的代表性回归集合：

.\verify-all.bat

pdp.Verify 还包含 tiny exhaustive pricing oracle、定价策略交叉验证、cut/branch 继承和 Phase-I/II 等专项检查。完整验证命令和当前证据清单记录在 Work.md。

项目结构

src/main/java/pdp/
  branching/    Branch-and-Price 节点、分支规则和树管理
  colgen/       主问题、列生成和路线列
  cuts/         SR、RCI、2-path 等割平面
  data/         实例、节点和数据模型
  labeling/     标签、资源扩展、dominance 和双向定价
  solver/       求解流程、解对象和状态传播
  Main.java     命令行入口
  SolverConfig.java
  Verify.java   回归与独立验证入口

PDPTW_instances/  随仓库提供的测试实例
Work.md           详细复现记录和开发交接文档

论文

Timo Gschwind, Stefan Irnich, Ann-Kathrin Rothenbaecher, Christian Tilk, "Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems", European Journal of Operational Research, 266(2), 521-530, 2018.

License

本项目采用 Apache License 2.0。