0

我正在使用 Optaplanner 解决以下具有许多要求的复杂 vrp 问题。除了以下两个方面，我能够处理其中的大部分。

  1. 仅在 DropOffs 前取件
  2. 在接送客户的路上强制执行特定路径。

目标是吸引一群前往靠近的目的地并将他们放在同一辆车中的客户。

提前致谢！感谢您的帮助！

该问题与示例 VRP TimeWindow 示例非常相似，但有以下更改。

  • 客户将在固定地点（在电路中）被接走
  • 每个接送客户都有一个下车目的地（
    赛道外）
  • 车辆不会前往下车处，然后再次返回取货处。（一旦车辆离开赛道，它所做的就是在设定的位置下客）
  • 在电路中移动的车辆必须在特定路径上移动（想象一条单向街道）

计划使用道路距离以及每个皮卡之间的分数是已知的。Pickup -> Drop-Off 未知（计划使用 Air）。

我很难强制执行，在离开赛道让客户下车后，车辆可能不会回来接更多的客户，并且在车辆可以在赛道上行驶的固定路径上进行这项工作。

我的主要想法是执行以下操作。

  • 为客户添加了 TYPE 属性以区分取货和客户
  • 向客户类添加了一个变量侦听器，该侦听器跟踪当前车辆到达时的所有 DropOffIds，以便只有在有乘客前往该地点时才会转到 dropOffLocation。当车辆到达 dropOff 时，它会从列表中删除该项目。（本质上用作堆栈）。
  • 从理论上讲，问题在于，如果客户位置相对较近，这不是从一辆汽车停下来接一个客户，然后再接另一个客户。
  • 还很难执行车辆必须在电路中采用的固定路线，计划使用成本矩阵来使用软约束来强制执行路线隐含性（车辆不会倒退或跳过一个点，因为成本太高），但没有按应有的方式工作。
4

1 回答 1

0

我可能会考虑这样的域模型：

@PlanningEntity
class Pickup implements PickupOrVehicle {
    Customer customer;

    @PlanningVariable
    PickupOrVehicle previousPickup;

    @PlanningVariable
    int dropOffPriority;

}
@PlanningEntity // Shadow entity
class Vehicle implements PickupOrVehicle {
    ...

    @ShadowVariable(based on dropOffPriority and previousPickup)
    List<Customer> dropOffOrderList;

    // For consistency we might also add pickUpOrderList
}

这dropOffPriority应该是全局唯一的（通过唯一地初始化它并且只为该变量配置 SwapMoves。

否则，VariableListener 应该只dropOffPriority通过客户的 id 订购 2 个相同的分配（因为订购必须是确定性的！）。

不确定它是否会运作良好。如果您确实尝试过，请在此处告诉我们它是否有效。

于 2016-06-24T07:33:47.883 回答