Google ORtool工具求解Vehicle Routing问题

官方文档链接：https://developers.google.com/optimization/routing

本翻译文档所有code（Apache 2.0 License）及图片来自ortool官方文档（Creative Commons Attribution 4.0 License），仅供学习使用，侵删。

示例1：旅行商问题（提供点与点之间的距离矩阵）

创造数据（目标点之间的距离矩阵）-> 创建路径规划模型 -> 创建距离回调函数 -> 设置旅行cost -> 设置搜索参数 -> 求解 -> 输出结果

示例一完整代码：点此看代码

示例二：电子板打孔（仅提供点的坐标，使用函数计算欧拉距离）

创造数据（目标点坐标）-> 计算距离矩阵 -> 创建路径规划模型 -> 创建距离回调函数 -> 设置旅行cost -> 设置搜索参数 -> 求解 -> 输出结果

示例二完整代码：电子板打孔代码

结果：（提供了两种搜索策略）

示例三：车辆路径规划问题（VRP）

四辆车从起点0出发，需遍历所有点，求解使得四辆车中路径最长的那辆车长度最短。

创造数据（距离矩阵 + 车辆数量 + 起点）-> 创建路径规划模型 ->  创建距离回调函数 ->  添加距离维度 -> 设置旅行cost -> 设置搜索参数 -> 求解 -> 输出结果

示例三完整代码：VRP代码

示例四：带容量限制的车辆路径规划问题(CVRP)

在示例三的基础上，四辆车有装载容量限制，需要将放置在各个点的货物运回0号点，同样是求解使得四辆车中路径最长的那辆车长度最短。

创造数据（距离矩阵 + 车辆数量 + 起点 + 车辆容量限制 + 每个点的货物数量）-> 创建路径规划模型 ->  创建距离回调函数 ->  添加需求回调函数和容量限制 -> 设置旅行cost -> 设置搜索参数 -> 求解 -> 输出结果

CVRP代码：CVRP代码

结果：

示例五：货物运输的车辆路径规划问题

需要规划车辆路径，使得车辆能够将某地的货物运输到另一个地方，同样是求解使得四辆车中路径最长的那辆车长度最短。

创造数据（距离矩阵 + 车辆数量 + 起点 + 运输计划）-> 创建路径规划模型 ->  创建距离回调函数 -> 设置旅行cost ->  添加距离维度限制 -> 添加运输计划 -> 设置搜索参数 -> 求解 -> 输出结果

完整代码：pickup and delivery

示例六：VRPTW 有时间窗口限制的VRP问题

访问的地点有时间窗口限制，时间窗口外的时间不可访问

创造数据（旅行时间矩阵 + 车辆数量 + 起点 + 时间窗）-> 创建路径规划模型 ->  创建旅行时间回调函数 -> 设置旅行cost ->  添加时间窗口限制  -> 设置搜索参数 -> 求解 -> 输出结果

完整代码：VRPTW