运筹系列92：vrp算法包VROOM

1. 介绍

VROOM is an open-source optimization engine written in C++20 that aim at providing good solutions to various real-life vehicle routing problems (VRP) within a small computing time.
可以解决如下问题：
TSP (travelling salesman problem)
CVRP (capacitated VRP)
VRPTW (VRP with time windows)
MDHVRPTW (multi-depot heterogeneous vehicle VRPTW)
PDPTW (pickup-and-delivery problem with TW)

2. 入门

安装：pip install pyvroom
注意vroom目前在mac m系列上还无法编译通过。

2.1 基本样例

基础用法样例，需要输入：

1. 距离矩阵
2. 车辆清单
3. 工作清单

import vroom
problem_instance = vroom.Input()
problem_instance.set_durations_matrix(profile="car",matrix_input=[[0, 2104, 197, 1299],[2103, 0, 2255, 3152],[197, 2256, 0, 1102],[1299, 3153, 1102, 0]],)
problem_instance.add_vehicle([vroom.Vehicle(47, start=0, end=0),vroom.Vehicle(48, start=2, end=2)])
problem_instance.add_job([vroom.Job(1414, location=0), vroom.Job(1515, location=1),vroom.Job(1616, location=2),vroom.Job(1717, location=3)])
solution = problem_instance.solve(exploration_level=5, nb_threads=4)
solution.routes[["vehicle_id", "type", "arrival", "location_index", "id"]]

输出为

其中id为job的编号，location index为地点的编号。

2.2 文件输入

也可以通过json文件输入：

{ "vehicles": [{"id":0, "start_index":0, "end_index":3} ],"jobs": [{"id":1414,"location_index":1},{ "id":1515,"location_index":2}],"matrices": { "car": {"durations": [ [0,2104,197,1299],[2103,0,2255,3152],[197,2256,0,1102],[1299,3153,1102,0]]}}
}

然后使用命令行：
vroom -i test2.json
结果如下：

2.3 调用引擎

VROOM可以通过下面几个引擎来计算距离：OSRM,Openrouteservice,Valhalla。在Input中指定servers和router即可，基础用法样例：

import vroom
problem_instance = vroom.Input(servers={"auto": "valhalla1.openstreetmap.de:443"},router=vroom._vroom.ROUTER.VALHALLA)
problem_instance.add_vehicle(vroom.Vehicle(1, start=(2.44, 48.81), profile="auto"))
problem_instance.add_job([vroom.Job(1, location=(2.44, 48.81)),vroom.Job(2, location=(2.46, 48.7)),vroom.Job(3, location=(2.42, 48.6)),])
sol = problem_instance.solve(exploration_level=5, nb_threads=4)
print(sol.summary.duration)

The only difference is no need to define the duration/distance matrix.

3. 详细介绍

详见：https://github.com/VROOM-Project/vroom/blob/master/docs/API.md
需要定义

1. resources (vehicles)
2. single-location pickup and/or delivery tasks (jobs/shipments)
3. 如果没有指定经纬度和地图server的话，则需要定义matrices

3.1 jobs/shipments

最基础的版本需要定义id和location。location可以是编号（如果已经给了matrix），也可以是坐标，也可以是封装了坐标的vroom.Location。
剩下的顾名思义：1）如果有时间窗约束的话，需要定义timewindows，可选setup，service；2）如果是pickup&delivery问题的话，可以定义pickup和delivery的数量；3）可以用skills约束车辆和路径的匹配关系；4）可以用priority提升或降低任务的优先级。

    id:Job identifier number. Two jobs can not have the sameidentifier.location:Location of the job. If interger, value interpreted as an thecolumn in duration matrix. If pair of numbers, valueinterpreted as longitude and latitude coordinates respectively.setup:The cost of preparing the vehicle before actually going out fora job.service:The time (in secondes) it takes to pick up/deliver shipmentwhen at customer.delivery:The amount of how much is being carried to customer.pickup:The amount of how much is being carried back from customer.skills:Skills required to perform job. Only vehicles which satisfiesall required skills (i.e. has at minimum all skills valuesrequired) are allowed to perform this job.priority:The job priority level, where 0 is the lowest priorityand 100 is the highest priority.time_windows:Windows for where service is allowed to begin.Defaults to have not restraints.

shipments其实和job没有太大差别，可用于定义dial-a-ride类型的问题。
首先定义shipmentStep，字段包括：

    id:Job identifier number. Two jobs can not have the sameidentifier.location:Location of the job. If interger, value interpreted as an thecolumn in duration matrix. If pair of numbers, valueinterpreted as longitude and latitude coordinates respectively.setup:The cost of preparing the vehicle before actually going out fora job.service:The time (in secondes) it takes to pick up/deliver shipmentwhen at customer.time_windows:Windows for where service is allowed to begin.Defaults to have not restraints.description:Optional string descriping the job.

然后定义shipment：

    pickup:Description of the pickup part of the shipment.delivery:Description of the delivery part of the shipment.amount:An interger representation of how much is being carried backfrom customer.skills:Skills required to perform job. Only vehicles which satisfiesall required skills (i.e. has at minimum all skills valuesrequired) are allowed to perform this job.priority:The job priority level, where 0 is the lowest priorityand 100 is the highest priority.

3.2 vehicles

定义vehicle一定要配置id，start和end。其他可配属性如下：

    id:Vehicle idenfifier number. Two vehicle can not have the sameidentifier.start:The location where the vehicle starts at before any jobs are done.If omitted, the vehicle will start at the first task it will beassigned. If interger, value interpreted as an the column induration matrix. If pair of numbers, value interpreted as longitudeand latitude coordinates respectively.end:The location where the vehicle should end up after all jobs arecompleted. If omitted, the vehicle will end at the last task itwill be assigned. If interger, value interpreted as an the columnin duration matrix. If pair of numbers, value interpreted aslongitude and latitude coordinates respectively.profile:The name of the profile this vehicle falls under.capacity:Array of intergers representing the capacity to carry differentgoods.skills:Skills provided by this vehilcle needed to perform various tasks.time_window:The time window for when this vehicle is available for usage.breaks:Breaks this vehicle should take.description:Optional string descriping the vehicle.speed_factor:The speed factor for which this vehicle runs faster or slower thanthe default.max_tasks:The maximum number of tasks this vehicle can perform.steps:Set of custom steps this vehicle should take.

如果我们需要指定一辆车的已分配工作，可以用VehicleStep类指定：

    step_type:The type of step in question. Choose from: `start`, `end`, `break`,`single`, `pickup`, and `delivery`.id:Reference to the job/break the step is associated with.Not used for `step_type == "start"` and `step_type == "end"`.service_at:Hard constraint that the step in question should be performedat a give time point.service_after:Hard constraint that the step in question should be performedafter a give time point.service_before:Hard constraint that the step in question should be performedbefore a give time point.

3.3 其他

vroom.break:指定午休时间等

    id:Job identifier number. Two jobs can not have thesame identifier.time_windows:Time windows for where breaks is allowed to begin.Defaults to have not restraints.service:The time duration of the break.description:A string describing this break

4. 输出

输出包括：
code：status code
error：error message (present iff code is different from 0)
summary：object summarizing solution indicators
unassigned：array of objects describing unassigned tasks with their id, type, and if provided, description, location and location_index
routes：array of route objects

4.1 code

4.2 summary

提供汇总信息，字段包括：

4.3 routes

展示具体路径，包括如下字段

routes中的每一行都是一个step类型：

其中violation对应的字段含义为：