VRP工具or-tools调研 王羚宇 2017.03.10

OUTLINE TSP问题与VRP问题 or-tools 工具包介绍 求解VRP问题示例 TSP问题 VRP问题 关键变量、函数

TSP问题 旅行推销员问题（Travelling salesman problem, TSP）是 这样一个问题：给定一系列 城市和每对城市之间的距离， 求解访问每一座城市一次并 回到起始城市的最短回路。 它是组合优化中的一个NP 困难问题，在运筹学和理论 计算机科学中非常重要。 尽管问题在计算上很困难，但已经有了大量的启发式和精确方法。，因此可以完全求解城市数量上万的实例，并且甚至能在误差1%范围内估计上百万个城市的问题

TSP问题-问题定义 问题定义如下：给定若干城市与城市间的距离集 合，求经过所有城市恰好一次的最短回路。即： 给定图G=(V, E, W)，其中V为顶点集合，|V|=n， E为边集合，W为边权函数，求集合{1, 2, …, n}的 一个排列π 使得下式最小。

TSP问题-整数规划问题 问题同样可以用整数线性规划问题来形式化，我们用数字1,…,𝑛标 记这些城市，并定义 x 𝑖𝑗 = 1 路径选择从i到j 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 并选择优化： 第一组等式要求每个城市都能另一个城市前来，而第二组等式要求每个城市都能出发。最后的约束迫使覆盖所有城市的路径只有一条，而不是两条或者多条分散的路径在一起覆盖的。 证明可行解中的每个子回路经过1号城市（注意到等式保证了只有一条这样的路径），就能证明所有可行解只包含一个封闭城市序列。对于若我们对所有xij=1 对应的不等式求和的话，对 k 步不经过1号城市的任何子回路，我们得到：nk≤(n−1)k, 矛盾。

VRP问题 TSP问题考虑一辆车依次遍历每一个节点一次，求满足条 件的遍历方法的最小代价。 What about 多辆车，每个节点有不同的需求？ 车辆路线问题(VRP)：一定数量的客户，各自有不同数量 的货物需求，配送中心向客户提供货物，由一个车队负 责分送货物，组织适当的行车路线，目标是使得客户的 需求得到满足，并能在一定的约束下，达到诸如路程最 短、成本最小、耗费时间最少等目的。

VRP问题-问题定义 设有一场站，共有M 辆货车，车辆容量为Q，有 N位顾客，每位顾客有其需求量D。车辆从场站 出发对客户进行配送服务最后返回场站，要求所 有顾客都被配送，每位顾客一次配送完成，且不 能违反车辆容量的限制，目的是所有车辆路线的 总距离最小。

VRP问题-整数规划问题 问题同样可以用整数线性规划问题来形式化，我们用数字1,…,𝑛标 记这些城市，并定义 x 𝑖𝑗 = 1 路径选择从i到j 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 并选择优化： 其中r(s)是服务集合S中各节点所需的最少车辆数目。

VRP问题变种(1) 与一般的VR问题相比，变种的VRP问题通常增加了一些额外的 限制，这些限制通常包括:装卸货的顺序，时间（时间窗），是 否要求回到场点，容量限制等。 有时间窗车辆路径问题（VRPTW，VRP with Time Windows） 考虑需求点对于车辆到达的时间有所要求之下，在车辆途程 问题之中加入时窗的限制，在VRPTW问题中，除了行驶成本 之外, 成本函数还要包括由于早到某个客户而引起的等待时间 和客户需要的服务时间。 与一般的VR问题相比，变种的VRP问题通常增加了一些额外的限制，这些限制通常包括:装卸货的顺序，时间（时间窗），是否要求回到场点，容量限制等。以下是几种比较常见的变种VRP问题： 在VRPTW中，车辆除了要满足VRP问题的限制之外，还必须要满足需求点的时窗限制，而需求点的时窗限制可以分为两种，一种是硬时窗（Hard Time Window），硬时窗要求车辆必须要在时窗内到达，早到必须等待，而迟到则拒收；另一种是软时窗（Soft Time Window），不一定要在时窗内到达，但是在时窗之外到达必须要处罚，以处罚替代等待与拒收是软时窗与硬时窗最大的不同。

VRP问题变种(2) 接送货物的车辆路径问题（VRPPD，Vehicle Routing Problem with Pickup and Delivery） 按序接送货物的车辆路径问题（Vehicle Routing Problem with LIFO） 问题要求最近接收的货物需要最早的被运送、卸货。 开放的车辆路径问题（OVRP，Open Vehicle Routing Problem） 车辆在运送货物后并不需要返回场点。

OUTLINE TSP问题与VRP问题 or-tools 工具包介绍 求解VRP问题示例 TSP问题 VRP问题 关键变量、函数

or-tools介绍（1） or-tools 是 Google 的优化搜索工具。优化工具包括： 约束编程解决方案(N-皇后问题，数字谜问题) 背包算法 图算法 (最短路径，线性和分配，最小费用流，最大流) 路径规划问题(TSP,VRP) 为线性规划和混合整数规划解决方案提供简单统一接口 Constraint programming is the name given to identifying feasible solutions out of a very large set of candidates, where the problem can be modeled in terms of arbitrary constraints.

or-tools介绍（2）-主要特性 开源免费 持续维护，改进和开发 详细的文档，提供 C++, Python, Java 和 C# 示例 便捷，可以在以下平台编译： Ubuntu 14.04 and 16.04 up (64-bit). Mac OS X El Capitan with Xcode 7.x (64 bit). Microsoft Windows with Visual Studio 2013 and 2015 (64-bit) 高效，用户友好 良好测试

or-tools 代码结构 FlatZinc, a solver input language that is understood by a wide range of solvers.

OUTLINE TSP问题与VRP问题 or-tools 工具包介绍 求解VRP问题示例 TSP问题 VRP问题 关键变量、函数

使用到的相关代码 求解TSP问题的直接依赖在 base graph constraint_solver utils 文件夹中

关键变量 求解相关 routing_first_solution： default : select the first node with an unbound successor and connect it to the first available node GlobalCheapestArc LocalCheapestArc PathCheapestArc GlobalCheapestArc :iteratively connect two nodes which produce the cheapest route segment LocalCheapestArc:select the first node with an unbound successor and connect it to the node which produces the cheapest route segment PathCheapestArc :starting from a route “start” node, connect it to the node which produces the cheapest route segment, then extend the route by iterating on the last node added to the route

关键变量 搜索过程 Meta-heuristics启发式算法策略 routing_guided_local_search (default: false): activates guided local search Generally the most efficient metaheuristic for vehicle routing routing_simulated_annealing (default: false): activates simulated annealing routing_tabu_search (default: false): activates tabu search 模拟退火： 模拟退火算法新解的产生和接受可分为如下四个步骤： 第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。 第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。 第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropolis准则: 若Δt′<0则接受S′作为新的当前解S，否则以概率exp(-Δt′/kT)接受S′作为新的当前解S。 第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。 模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。 禁忌算法： 它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向， 当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best so far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。

关键变量搜索相关 Local search neighborhoods routing_no_lns (default: false): 使用LNS，可能会找到更好的解 法，不过通常比较慢 routing_no_TSP (default: true): 在求解当前模型时不使用精确 算法求解“子”TSP问题 searching for solution  routing_solution_limit (default: kint64max) 在找到若干次更好的 解后停止 routing_time_limit (default: kint64max) 在查找若干时间后停止

Routing相关 路径相关的变量 Dimension相关的变量 next(i)：i节点的直接后继的节点号（可以通过 IndexToNode()得到该节点） vehicle(i)：返回该节点属于车辆路径的编号 Dimension相关的变量 dimension变量 cumul(i, d) 节点i的累积值 transit(i, d) 节点i的delta值 if j == next(i), cumul(j) = cumul(i) + transit(i) + slack(i)

关键API RoutingModel RoutingModel (int nodes, int vehicles, NodeIndex depot) : 构造VRP问题 const Assignment* RoutingModel :: SolveWithParameters (const RoutingSearchParameters& search_parameters)： 求解VRP问题 void SetArcCostEvaluatorOfAllVehicles(NodeEvaluator2* evaluator)：定义最小化变量问题 ResultCallback2<int64, NodeIndex, NodeIndex>

关键API AddDimension(): bool AddDimension(NodeEvaluator2* evaluator, evaluator: 加入限制变量的callback函数 相关的两个变量： cumul(累加变量) transit(站点变量) if j == next(i), cumul(j) = cumul(i) + transit(i) + slack(i) capacity: cumul变量的最大值 fix_start_cumul_to_zero:开始时是否置为0 bool AddDimension(NodeEvaluator2* evaluator, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string& name );

关键API VRP问题：加入若干节点属于同一辆车的约束： 示例：solver->AddSoftSameVehicleConstraint(); 标注数组中的节点应该分到同一辆车上，如果没在同一辆 车上，每多一个特例，总成本函数增加cost. // Adds a soft contraint to force a set of nodes to be on the same vehicle. // If all nodes are not on the same vehicle, each extra vehicle used adds // 'cost' to the cost function.

关键API VRP问题：加入两个节点存在接送关系： 满足：1. node1,node2由同一辆车服务； 示例: https://github.com/google/or-tools/blob/c11c96f1dce24893de5357e7c643aa6958496ada/src/constraint_solver/routing.h line 580. // Notifies that node1 and node2 form a pair of nodes which should belong // to the same route. This methods helps the search find better solutions, // especially in the local search phase. // It should be called each time you have an equality constraint linking // the vehicle variables of two node (including for instance pickup and // delivery problems): // Solver* const solver = routing.solver(); // solver->AddConstraint(solver->MakeEquality( // routing.VehicleVar(routing.NodeToIndex(node1)), // routing.VehicleVar(routing.NodeToIndex(node2)))); // solver->AddPickupAndDelivery(node1, node2); // // TODO(user): Remove this when model introspection detects linked nodes. void AddPickupAndDelivery(NodeIndex node1, NodeIndex node2) { pickup_delivery_pairs_.push_back( {{NodeToIndex(node1)}, {NodeToIndex(node2)}}); }

关键API 自定义条件：在constraint_solver中加入constraint 示例： 表示需要满足left <= right. 还有很多这样的API： https://github.com/google/or-tools/blob/master/src/constraint_solver/constraint_solver.h line 1200+-

关键API 自定义条件 https://github.com/google/or-tools/blob/master/src/constraint_solver/constraint_solver.h line 1200+-

TSP问题示例 准备数据 构造求解器 准备callback函数 调用求解器

TSP问题示例 准备数据--给定若干个城市和他们之间的距离

TSP问题示例 构造求解器

TSP问题示例 构造求解器

TSP问题示例 准备callback函数 callback: a function that takes any pair of nodes in the graph for the problem and returns the distance between them — and then passes it to the solver

TSP问题示例 调用求解器 输出示例

VRP问题示例 与TSP相比，示例VRP程序加入了车辆的容量限制，同时调度 多辆车完成规划问题。 准备数据：生成每个站点的位置跟其货物需求；定义距离调 用函数

VRP问题示例 Callback函数

VRP问题示例 准备demand的调用函数

VRP问题示例 AddDimension(): bool AddDimension(NodeEvaluator2* evaluator, evaluator: 加入限制变量的callback函数 相关的两个变量： cumul(累加变量) transit(站点变量) if j == next(i), cumul(j) = cumul(i) + transit(i) + slack(i) capacity: cumul变量的最大值 fix_start_cumul_to_zero:开始时是否置为0 bool AddDimension(NodeEvaluator2* evaluator, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string& name );

VRP问题示例 加入约束

VRP问题示例 示例输出

VRPTW示例 问题说明： VRP + Time Windows. 在这个例子中，我们定义总的时间为服务时间+路 上花费的时间，其中服务时间与每个站点所需货 物量成正比，路上花费的时间跟站点间的距离成 正比。

VRPTW示例 准备数据： VRP + Time Windows.在这个例子中，我们定义 总的时间为服务时间+路上花费的时间，其中服务 时间与每个站点所需货物量成正比，路上花费的 时间跟站点间的距离成正比。

VRPTW示例 定义callback函数: 服务时间与每个站点所需货物量成正比

VRPTW示例 定义callback函数 路上花费的时间跟站点间的距离成正比。

VRPTW示例 定义callback函数 总时间=服务时间+路程时间

VRPTW示例 加入时间维度

VRPTW示例 加入时间维度限制： 获取该dimension 为其中的每个站点设置开始、结束时间值，加 入约束

Q&A?

reference https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Vehicle_routing_problem https://developers.google.com/optimization/reference/constraint_solver/routing/ https://acrogenesis.com/or- tools/documentation/documentation_hub.html#user_manual https://developers.google.com/optimization/ https://developers.google.com/optimization/routing/TSP/TSP https://developers.google.com/optimization/routing/TSP/vehicle_routing_time_w indows https://github.com/google/or-tools/blob/master/src/constraint_solver/routing.h