车辆路线

注意 ：虽然 Google OR-Tools 中的路由求解器是免费的，但需要工业级服务的用户可以使用 Cloud Fleet Route。查看示例 Web 应用的源代码。

最常见的优化任务之一是车辆路线，其目标是为前往一组地点的车队找到最佳路线。通常，“最佳”是指总距离或费用最少的路线。 以下是路由问题的一些示例：

• 一家包裹配送服务公司想要为司机指定送货路线。
• 一家有线电视公司希望为技术人员分配用于拨打住宅服务电话的路由。
• 一家拼车公司想要为司机分配上车和下车路线。

其中最著名的路线问题是旅行推销员问题 (TSP)：对于需要探访不同营业地点的客户并返回出发地的销售人员，找出最短的路线。TSP 可以用图表示，其中节点对应位置，而边（或弧形）表示位置之间的直接行程。例如，下图显示了一个仅有四个位置（分别标记为 A、B、C 和 D）的 TSP。任意两个位置之间的距离由连接这两个位置的边旁边的数字指定。

通过计算所有可能路线的距离，可以看到最短路线是 ACDBA，总距离为 35 + 30 + 15 + 10 = 90。

地点越多，问题就越严重。上面的示例中只有六条路线。但如果有 10 个位置（不计算起点），则路由数量为 362880。如果是 20 个营业地点，此数量会跳到 2432902008176640000。 详尽搜索所有可能的路线可以保证找到最短路径，但这对于除一小部分位置以外的所有位置来说很难计算。对于更大的问题，需要使用优化技术智能搜索解决方案空间，并找到最佳（或接近优化）的解决方案。

更通用的 TSP 版本是车辆路线问题 (VRP)，其中有多辆车辆。在大多数情况下，VRP 都有限制：例如，车辆可能具有承载最大重量或最大体积的物品容量，或者驾驶员可能需要在客户要求的指定时间范围内造访某些地点。

OR-Tools 可以解决多种类型的 VRP 问题，包括：

• 旅行销售人员问题，即只有一辆车的典型路线问题。
• 车辆路线问题，是对多辆车辆的 TSP 的泛化。
• 具有容量限制的 VRP，即车辆可携带商品的最大容量。
• 设有时间范围的 VRP：车辆必须按照指定的时间间隔到访地点。
• 具有资源限制的 VRP，例如在仓库（路线的起点）装卸车辆的空间或人员。
• 存在访问量下降的 VRP。在这种情况下，车辆并非必须造访所有地点，但必须针对每次访问丢失而支付罚金。

解决车辆路线问题的限制

车辆路线问题从本质上说是难以解决的：解决问题所需的时间会随着问题规模成倍增长。对于足够大的问题，OR-Tools（或任何其他路由软件）可能需要数年时间才能找到最佳解决方案。因此，OR-Tools 有时会返回良好的解决方案，但并非最佳解决方案。如需找到更好的解决方案，请更改求解器的搜索选项。如需查看示例，请参阅更改搜索策略。

注意 ：我们还应该补充一点，还有一些其他求解器，例如 Concorde，专用于求解非常大的 TSP 以获得最优性，这些求解器在这方面超过了 OR-Tools。但是，OR-Tools 提供了一个更好的平台，用于解决更宽泛的路由问题，这些问题包含的限制超出纯 TSP 的限制。