AI导哈

多快递员路径规划工具

该工具提供三种优化模型（CP、SMT、MIP）来解决多快递员路径规划问题，旨在最小化任何快递员的最大行驶距离，确保工作负载的公平分配。

  • by davide-leone
  • Python
  • 本地部署
  • 更新于
在 GitHub 查看 davide-leone/cdmo-mcp

使用说明

多快递员问题的建模与求解

问题描述

这 多快递员计划（MCP）问题 定义如下：

  • 我们有 m快递员 负责分发 n≥m个项目 不同的客户地点。

  • 每位快递员 我 具有最大负载能力 lᵢ.

  • 每一项 j 有：

    • 交货地点 j.
    • 大小 sⱼ （例如重量或体积）。

  • 快递员必须在一个共同的地方开始和结束他们的旅行 原点o.

  • 物品的分配必须尊重每个快递员的装载能力。

目标：尽量减少 任何快递员旅行的最大距离，确保公平分配工作量。

解决方案概述

该项目提供 三种优化模型 为了解决MCP：

  1. 约束规划（CP）

    • 使用 巨人旅行社（GTR） 代表前任与继任者的关系。
    • 与旅行矩阵方法相比，提高了可扩展性，特别是在大型实例上。

  2. 满意模理论（SMT）

    • 基于3D二进制“旅行”矩阵编码快递到位置的转换。

  3. 混合整数规划（MIP）

    • 还使用旅行矩阵公式，类似于经典公式 容量受限车辆路径问题（CVRP） 模型。

通过在一个通用框架下统一CP、SMT和MIP方法，该存储库允许对不同的优化范式进行基准测试和比较。

安装与执行

该解决方案通过以下方式完全容器化 码头工人. 从项目根目录运行提供的PowerShell脚本：

.\run.ps1 -ArgsToPass <arguments>
  • 这 -ArgsToPass 参数取Python脚本名称(launcher.py)以及其他选项。

参数

共同

  • --model {CP, SMT, MIP} → 选择要运行的模型。如果省略，则按顺序运行。
  • --inst <int> → 选择实例编号。如果省略，则测试所有实例。

CP特定

  • -c, --chuffed → 仅使用 哈哈大笑 求解器（禁用Gecode）。

    注意：Gecode可能无法在Windows上运行；CP测试在Linux上运行。

SMT专用

  • -p, --prune → 启用修剪。
  • --n_sol <int> → 考虑用于修剪的启发式解决方案的数量（默认值：10）。
  • -l, --load_heuristics → 从文件加载启发式算法（确保可重复性）。
  • -d, --debug → 启用调试输出。

MIP特定

  • -g, --gurobi → 启用Gurobi求解器（需要有效的许可证）。
  • -s, --skip → 跳过超过超时的实例。
  • -l, --load_heuristics → 从文件加载启发式算法（确保可重复性）。
  • -d, --debug → 启用调试输出。

使用示例

  1. 在所有实例上运行所有模型 （配置与报告结果相同）：

    .\run.ps1 -ArgsToPass "launcher.py", "-l", "-p", "-g", "-s"

  2. 仅在实例1上运行MIP模型:

    .\run.ps1 -ArgsToPass "launcher.py", "-l", "-p", "-g", "-s", "--model", "MIP", "--inst", "1"

  3. 运行解决方案检查器:

    .\run.ps1 -ArgsToPass "check_solution.py", "DAT", "res/"

相关 MCP