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對應的字段含義為：