2019-04-03派森学习第135天
2019-04-03 本文已影响0人
每日派森
今天继续处理智能派工的程序。
上午做了进一步的思考之后，发现和车辆路径问题（VRP，vehicle routing problem）很相似，那么先来学习一下VRP问题。
1. 问题模型
VRP问题是车辆路径问题的缩写。问题是：有N辆车，都从原点出发，每辆车访问一些点后回到原点，要求所有的点都要被访问到，求最短的车辆行驶距离或最少需要的车辆数或最小化最长行驶距离。
常见的限制要求包括：车辆容量限制、时间窗限制、点访问顺序要求等。
对于VRP问题可以使用ortools库的RoutingModel模型。
首先为车添加用于进行优化的dimension：
1
然后使用GetDimensionOrDie方法获取dimension，并设置优化目标。注意在VRP问题中，路径上给点赋的index和点实际的index不一样，需要使用IndexToNode方法进行转换才能得到实际的index。
2 实例
下图中各点距离用曼哈顿距离，目标函数是最小化各车辆行驶距离的差别。可以对dimension使用SetGlobalSpanCostCoefficient方法可以获得目标函数。global_span_cost = coefficient * (Max(dimension end value) - Min(dimension start value)).
2
3 程序实现
3
