标签: vehicle-routing

我已经使用 or-tools 几个月了，但最近遇到了以下问题：

模型：

• 2辆车，每辆车都有一个开始位置s0, s1和一个结束位置t0, t1。
• 2 个参观地点x0, x1。

时间窗口：

[[5400, 5820], [9000, 9420], [5520, 39719], [6420, 43319], [5521, 39720], [6421, 43320]]

持续时间矩阵：

[
   x0: [0, horizon, horizon, horizon, 5400, 5400], 
   x1: [horizon, 0, horizon, horizon, 1800, 1800], 
   s0: [0, 0, horizon, horizon, 0, horizon], 
   s1: [0, 0, horizon, horizon, horizon, 0], 
   t0: [horizon, horizon, horizon, horizon, horizon, horizon],
   t1: [horizon, horizon, horizon, horizon, horizon, horizon]
]

哪里horizon = 86760- 这只是一个很大的价值来驳回这个潜在的任务。 …

对于 or-tools 中的 VRP，有没有办法让车辆在某些固定位置开始，但允许任意结束位置？

文档https://developers.google.com/optimization/routing/routing_tasks#setting-start-and-end-locations-for-routes和https://developers.google.com/optimization/routing/routing_tasks#allowing-任意开始和结束位置显示如何分别设置自定义或任意开始/结束位置。

我的问题是我们可以将它们结合起来吗？即自定义开始位置和任意结束位置（反之亦然）？

谢谢

我正在使用 Google OR-Tools 在几天内优化单个车辆的路线。

我在尝试着：

• 能够指定优化路由的天数。
• 能够指定每天的开始位置和结束位置。
• 能够指定每天的开始时间和结束时间。

我有一组 40 个位置。对于我想包含在我的优化天数范围内的每一天，我将开始和结束位置添加到矩阵中。所以如果我想优化一天，我的矩阵中总共会有 42 个位置。如果我想优化两天，我的矩阵中总共会有 44 个位置。等等。模式是这样的：

1 Day:
Matrix = [[start day 1], [end day 1], [location], [location], ... ]

2 Days:
Matrix = [[start day 1], [end day 1], [start day 2], [end day 2], [location], [location], ... ]

3 Days:
Matrix = [[start day 1], [end day 1], [start day 2], [end day 2], [start day 3], [end day 3], [location], [location], ... ]

我希望允许删除位置以实现可行的解决方案，并且只允许在指定的时间窗口内访问位置，我相信我已经成功实施了这两个选项。

我当前的实现可在此处以及GitHub 上找到。 …

我正在尝试开发一种算法来解决我无法分类的问题，我公开了主题：

您有一张地图，分为多个部分，这些部分具有特定的区域和一定数量的人居住的地方。

该问题包括找到面积不超过特定值的连接部分的集合，从而最大化所选居民的数量。

目前我可以想到两种方法：

• 将问题视为具有正自然值的无向图中的全对最短路径问题，其中不满足最大选定区域约束的解将被丢弃。为此，您可以使用 Floyd-Warshall 算法、适用于所有对的 Dijkstra 算法或 Thorup 算法（可以在时间 V * E 内完成，其中这些是图的顶点和边）。
• 将其视为具有利润的开放车辆路径问题，其中每辆车可以在其想要的任何地方开始和结束（具有利润的开放车辆路径问题或 OVRPP）。
• 另一种方法

此外，根据特定问题的组合，在某些情况下可以使用遗传算法和禁忌搜索，但这仅适用于不允许找到最佳解决方案的情况。

更清楚地说，所寻求的是获得面积之和不超过总面积的连接部分的选择。要最大化的参数是所选部分的总体总和。目标是找到最优解决方案。

例如，这是最大面积为 6（红色区域）的最佳选择

谢谢大家！

I am currently evaluating googles or-tools and just noticed that it's not really a solver on its own but mainly an interface to other solvers. What I'd like to know is which solvers this framework uses for constraint and routing problems.

I have already looked thoroughly through https://developers.google.com/optimization/, but only found that

• for linear optimization Google's "in-house, open-source GLOP" is used
• for network flow optimization an own solver seems to be used ("OR-Tools provides several solvers for network flow …

我有一个使用 Google 的 OR Tools python 库实现的有效车辆路由问题（带时间窗口）解决方案。我有一个包含 15 个位置的时间矩阵以及每个位置的时间窗口。我还将访问每个地点的持续时间纳入每次访问的费用中。所有值均以秒为单位。我有意只用一辆车来解决这个问题（本质上是解决旅行推销员问题）。

如果位置阻止创建有效的解决方案，我不会尝试添加从解决方案中删除位置的功能。现在，如果我将每次访问的持续时间设置为 3600 秒，则无法访问所有 15 个位置。但是，如果我将每次访问的持续时间设置为 900 秒，那么所有 15 个位置都可以找到解决方案。我想添加一个析取项，以允许在这些较长的持续时间内创建解决方案，并且只需从解决方案中删除一个位置即可避免失败。

我不想从解决方案中删除一些位置，因此我给了它们极大的惩罚以确保它们不会被删除，而其他位置我则指定为零的惩罚。但现在，所有其他地点都被放弃，因为它们的罚款为零 - 我认为这是因为罚款小于交通成本，但我不完全确定这是否确实是原因。我应该如何允许从解决方案中删除位置，但防止其他位置可删除？

现在我添加的唯一代码是：

# Allow to drop nodes.
for node in range(1, len(Penalties)):
  routing.AddDisjunction([manager.NodeToIndex(node)], Penalties[node])

来源

from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

Matrix = [
  [0, 557, 763, 813, 618, 822, 700, 1527, 112, 1011, 734, 551, 604, 1156, 732],             # Depot
  [523, 0, 598, 934, 607, 658, 535, 1529, 589, 857, 424, 475, …

我们当前的方法是多次运行求解器。我想知道是否有更好的方法。

一些解释：

多行程车辆路径问题（VRPMT）：车辆可以执行多条路线。