VRPTW分支定界算法求解器

基于Gurobi的VRPTW（带时间窗的车辆路径问题）分支定界算法求解器。

快速开始

安装依赖

pip install gurobipy matplotlib

基本使用

# 求解小型实例（25个客户）
python main.py --data "data/C101.txt" --limit 25

# 完整求解（100个客户，10分钟时间限制）
python main.py --data "data/C101.txt" --limit 100 --time 600

# 生成路线可视化图
python main.py --data "data/C101.txt" --limit 25 --plot --plot_path "routes.png"

常用参数

python main.py \
    --data "data/C101.txt" \           # Solomon数据文件
    --limit 50 \                       # 客户数量（不含仓库）
    --time 300 \                       # 求解时间限制（秒）
    --gap 0.01 \                       # 精度要求（1%）
    --F 1000 \                         # 车辆固定成本
    --P 1 \                            # 超时罚金
    --plot \                           # 生成可视化图
    --plot_use_orig_id                 # 使用原始客户编号

数据集

• C类实例: data/C101.txt - data/C109.txt (聚类分布)
• R类实例: data/R101.txt - data/R211.txt (随机分布)
• RC类实例: data/RC101.txt - data/RC208.txt (混合分布)

输出说明

========== 基本信息 ==========
实例: C101
客户数: 100
容量Q: 200.0
车数上限K: 25

========== 求解结果 ==========
状态码: 2                    # 2=最优解
解数量: 3
目标值: 10828.94            # 总行驶距离
用车数: 10

========== 路线 ==========
Route 1: 0 -> 5 -> 3 -> 7 -> 8 -> 10 -> 11 -> 9 -> 6 -> 4 -> 2 -> 1 -> 75 -> 0
Route 2: 0 -> 13 -> 17 -> 18 -> 19 -> 15 -> 16 -> 14 -> 12 -> 0
...

求解建议

• 测试阶段: 使用 --limit 10-25 快速验证
• 完整求解: 根据计算资源调整 --limit 和 --time
• 精度要求:
  • 快速求解：--gap 0.05
  • 平衡求解：--gap 0.01
  • 高精度：--gap 0.001

常见问题

Q: 求解时间过长？ A: 增加 --gap 参数或减少 --limit 客户数量

Q: 无可行解？ A: 检查时间窗设置或尝试更小的客户子集

Q: Gurobi许可证？ A: 需要有效的Gurobi许可证，请访问官网获取

参数说明

参数	说明	默认值
--data	Solomon数据文件路径	必需
--limit	客户数量（不含仓库）	无限制
--time	求解时间限制（秒）	300
--gap	MIPGap精度	0.01
--F	车辆固定成本	0
--P	超时罚金系数	0
--plot	生成路线图	关闭
--plot_use_orig_id	使用原始客户编号	关闭

许可证

需要有效的Gurobi许可证。