Single Day Vehicle Routing
Input
An input for a solve request for a VRP problem requires several data:
- locations
- orders
- vehicles
Locations
Define the list of locations.
| Property | Description | Type |
|---|---|---|
name |
Unique identifier for location name | string |
latitude |
Latitude in WSG84 | number |
longitude |
Longitude in WSG84 | number |
Orders
| Property | Description | Type |
|---|---|---|
name | The unique name of the order | string |
location | The name of the location where this order is located. (refers to location list) | string |
duration | Duration of the service (in minutes) | integer |
type | Type restriction. Only vehicles with the same type string can perform the orders for which this type is present. | string |
demand | Demand for capacity type 1. Can be in volumetric measures. | integer |
windows | Time windows that restrict the time at which this order is scheduled. | array of Window |
allowedVehicles | List of vehicle id's that are allowed to process this order. | array of string |
disallowedVehicles | List of vehicle id's that are NOT allowed to process this order. | array of string |
Fleet
The fleet consists of your vehicles, that you want to allocate the orders to. Each vehicle is defined by a starting and ending location (referencing a location on the network), and the shift start and end times.
| Property | Description | Type |
|---|---|---|
name | Unique identifier for vehicle name | string |
startlocation | The name of the location where the vehicle starts | string |
endlocation | The name of the location where the vehicle ends | string |
shiftstart | Starting time of the shift in minutes (0-1439) | integer |
shiftend | End time of the shift in minutes (0-1439) | integer |
capacity | Capacity available in the vehicle. | integer |
type | Type restrictions. These should match with the type requirements of an Order. | array of string |
overtime | Checks whether this vehicle can go into overtime. | boolean |
breaks | Break definitions | Break object |
The end location is optional and may be omitted. This may be useful in cases when you care less about total distance traveled, and instead would like to prioritize your visits closeby to be done as soon as possible. The reason why this works is because Solvice OnRoute minimizes total travel time, and may leave closeby visits for on the way back.
Optionally, you may define the capacity of the vehicle (using the same unit as the "weight" for your orders). The algorithm will make sure that this capacity will not be exceeded. You can define 2 types of capacity: e.g. one for weight (in pounds, kilos, tons) and one for volume (square meters, cube meters)
If you are using type restrictions on your visits, make sure you also define the same types for your vehicles in the type parameter. This value is an array of strings for multiple types. Vehicles without any type will still be able to serve the visits that have no type restrictions. Examples of type restrictions: "Technician", "Maintenance", ...
If a vehicle can do overtime, then the shift end constraint is not seen as hard and then it is possible that some orders are scheduled after shift end. overtime_end determines the maximum of overtime.
Breaks
A break can be scheduled between a certain break interval (breakstart and breakend) and can take a pre-defined amount of time (breakduration).
| Parameter | Description | Type |
|---|---|---|
breakstart | Earliest starting time of a break | integer |
breakend | Latest ending time of a break | integer |
breakduration | Duration of a break | integer |
Introducing breaks will require more computation time, as they are seen as visits in the solution.
Options
Specific options can be added to guide the solving process.
| Property | Description | Type |
|---|---|---|
traffic | Traffic modifier. Default at 1.0. All travel times get multiplied with the traffic parameter. | double |
overconstrained | Indicates to not plan all orders, but only the feasible ones. | boolean |
minimize_driver_wait_time | Wait time should be minimized. | boolean |
minimize_vehicle_use | The least number of vehicles should be used. | boolean |
Output
After checking that the status is solved, you can fetch the solution in the solution endpoint. The solution endpoint will return a list of visits per vehicle. Additionally, the score function will be presented as well as the unresolved constraints.
Score
Scoring an optimisation solution is done by dividing between soft and hard constraints.
Hard constraints are required constraints, while soft constraints force the solution in a certain direction as objective functions. For more information, see the section on What is Optimisation?
In the following example, the score is given for a simple optimisation question where you can see that there is no hard constraint violation (resulting in a hard score of 0) and the soft score results in 59 score points while aiming to reach to zero. This means that the solution is feasible according to the constraints.
{
"score": {
"hardScore": 0,
"softScore": -59,
"feasible": true
}
}
Unresolved constraints
Some constraints cannot be resolved and are left violated. In the unresolved section in the solution, we show the constraints that are violated in a list with their respective score value.
"unresolved": [
{
"name": "Vehicle Capacity",
"value": -4,
"level": "HARD"
}
]
Solution
The actual solution is a map of a list of visits to the vehicle name.
{
"solution ": {
"driver1": [
{
"location ": "loc0 ",
"order ": null,
"arrival ": 510,
"finish ": 510,
"wait ": 0,
"drive ": 0,
"distance ": 0
},
{
"location ": "loc1 ",
"order ": "order1 ",
"arrival ": 504,
"finish ": 534,
"wait ": 0,
"drive ": 24,
"distance ": 24
}
]
}
}
Visit object
| Property | Description | Type |
|---|---|---|
location | The location name of the visit | string |
order | The order name of the visit. | string |
arrival | The arrival time of that visit in minutes starting from midnight. | integer |
finish | The finish time of that visit in minutes starting from midnight. >= arrival | integer |
wait | The waiting time at that visit, if applicable in minutes. | integer |
drive | The driving / travel time from this visit to the next visit in minutes | integer |
distance | The travel distance from this visit to the next visit in minutes. | integer |
Example
{
"solver": "VRP",
"locations": [
{
"name": "loc0",
"latitude": 51.12317420299715,
"longitude": 5.281797793554478
},
{
"name": "loc1",
"latitude": 50.65329310557439,
"longitude": 4.517600740757033
},
{
"name": "loc2",
"latitude": 51.20586951408341,
"longitude": 5.050825570502835
},
{
"name": "loc3",
"latitude": 51.116048511299724,
"longitude": 3.4438340449873435
}
],
"fleet": [
{
"name": "drive John",
"startlocation": "loc0",
"shiftstart": 500,
"shiftend": 1439,
"type": [
"Technician"
]
},
{
"name": "driver Joe",
"startlocation": "loc2",
"endlocation": "loc1",
"shiftstart": 500,
"shiftend": 900,
"type": [
"Maintenance"
]
}
],
"orders": [
{
"name": "order0",
"location": "loc2",
"windows": [
{
"starttime": 480,
"endtime": 720,
"hard": true
},
{
"starttime": 780,
"endtime": 1020,
"hard": true
}
],
"duration": 30,
"type": [
"Technician"
]
},
{
"name": "order1",
"location": "loc1",
"duration": 30
},
{
"name": "order2",
"location": "loc0",
"demand": 2,
"duration": 30
},
{
"name": "order3",
"location": "loc1",
"demand": 2,
"duration": 5
}
]
}
{
"score": {
"initScore": 0,
"hardScore": -4,
"mediumScore": 0,
"softScore": -125,
"feasible": false,
"solutionInitialized": true,
"zero": false
},
"unresolved": [
{
"name": "Travel Time",
"value": -125,
"level": "SOFT",
"notZero": true
},
{
"name": "Vehicle Capacity",
"value": -4,
"level": "HARD",
"notZero": true
}
],
"status": "SOLVED",
"solver": "VRP",
"weights": {},
"locations": [
{
"name": "loc0",
"latitude": 51.12317420299715,
"longitude": 5.281797793554478
},
{
"name": "loc1",
"latitude": 50.65329310557439,
"longitude": 4.517600740757033
},
{
"name": "loc2",
"latitude": 51.20586951408341,
"longitude": 5.050825570502835
},
{
"name": "loc3",
"latitude": 51.116048511299724,
"longitude": 3.4438340449873435
}
],
"fleet": [
{
"name": "drive John",
"startlocation": "loc0",
"visits": [
{
"location": "loc0",
"arrival": 500,
"finish": 500,
"wait": 0,
"drive": 0,
"distance": 0,
"service": 0,
"demand": 0,
"demand2": 0,
"coords": {
"address": "loc0",
"latitude": 51.12317420299715,
"longitude": 5.281797793554478
}
},
{
"location": "loc0",
"order": "order2",
"nextLocation": "loc2",
"arrival": 500,
"finish": 530,
"wait": 0,
"drive": 0,
"distance": 0,
"service": 30,
"demand": 2,
"demand2": 0,
"coords": {
"address": "loc0",
"latitude": 51.12317420299715,
"longitude": 5.281797793554478
}
},
{
"location": "loc2",
"order": "order0",
"arrival": 557,
"finish": 587,
"wait": 0,
"drive": 27,
"distance": 20383,
"service": 30,
"demand": 0,
"demand2": 0,
"coords": {
"address": "loc2",
"latitude": 51.20586951408341,
"longitude": 5.050825570502835
}
}
],
"shiftstart": 500,
"shiftend": 1439,
"type": [
"Technician"
]
},
{
"name": "driver Joe",
"startlocation": "loc2",
"endlocation": "loc1",
"visits": [
{
"location": "loc2",
"arrival": 500,
"finish": 500,
"wait": 0,
"drive": 0,
"distance": 0,
"service": 0,
"demand": 0,
"demand2": 0,
"coords": {
"address": "loc2",
"latitude": 51.20586951408341,
"longitude": 5.050825570502835
}
},
{
"location": "loc1",
"order": "order3",
"nextLocation": "loc1",
"arrival": 598,
"finish": 603,
"wait": 0,
"drive": 98,
"distance": 100266,
"service": 5,
"demand": 2,
"demand2": 0,
"coords": {
"address": "loc1",
"latitude": 50.65329310557439,
"longitude": 4.517600740757033
}
},
{
"location": "loc1",
"order": "order1",
"arrival": 603,
"finish": 633,
"wait": 0,
"drive": 0,
"distance": 0,
"service": 30,
"demand": 0,
"demand2": 0,
"coords": {
"address": "loc1",
"latitude": 50.65329310557439,
"longitude": 4.517600740757033
}
},
{
"location": "loc1",
"arrival": 633,
"finish": 633,
"wait": 0,
"drive": 0,
"distance": 0,
"service": 0,
"demand": 0,
"demand2": 0,
"coords": {
"address": "loc1",
"latitude": 50.65329310557439,
"longitude": 4.517600740757033
}
}
],
"shiftstart": 500,
"shiftend": 900,
"type": [
"Maintenance"
]
}
],
"orders": [
{
"name": "order0",
"location": "loc2",
"windows": [
{
"starttime": 480,
"endtime": 720,
"hard": true
},
{
"starttime": 780,
"endtime": 1020,
"hard": true
}
],
"arrivalTime": 557,
"duration": 30,
"type": [
"Technician"
]
},
{
"name": "order1",
"location": "loc1",
"arrivalTime": 603,
"duration": 30
},
{
"name": "order2",
"location": "loc0",
"demand": 2,
"arrivalTime": 500,
"duration": 30
},
{
"name": "order3",
"location": "loc1",
"demand": 2,
"arrivalTime": 598,
"duration": 5
}
],
"solution": {
"drive John": [
{
"location": "loc0",
"arrival": 500,
"finish": 500,
"wait": 0,
"drive": 0,
"distance": 0,
"service": 0,
"demand": 0,
"demand2": 0,
"coords": {
"address": "loc0",
"latitude": 51.12317420299715,
"longitude": 5.281797793554478
}
},
{
"location": "loc0",
"order": "order2",
"nextLocation": "loc2",
"arrival": 500,
"finish": 530,
"wait": 0,
"drive": 0,
"distance": 0,
"service": 30,
"demand": 2,
"demand2": 0,
"coords": {
"address": "loc0",
"latitude": 51.12317420299715,
"longitude": 5.281797793554478
}
},
{
"location": "loc2",
"order": "order0",
"arrival": 557,
"finish": 587,
"wait": 0,
"drive": 27,
"distance": 20383,
"service": 30,
"demand": 0,
"demand2": 0,
"coords": {
"address": "loc2",
"latitude": 51.20586951408341,
"longitude": 5.050825570502835
}
}
],
"driver Joe": [
{
"location": "loc2",
"arrival": 500,
"finish": 500,
"wait": 0,
"drive": 0,
"distance": 0,
"service": 0,
"demand": 0,
"demand2": 0,
"coords": {
"address": "loc2",
"latitude": 51.20586951408341,
"longitude": 5.050825570502835
}
},
{
"location": "loc1",
"order": "order3",
"nextLocation": "loc1",
"arrival": 598,
"finish": 603,
"wait": 0,
"drive": 98,
"distance": 100266,
"service": 5,
"demand": 2,
"demand2": 0,
"coords": {
"address": "loc1",
"latitude": 50.65329310557439,
"longitude": 4.517600740757033
}
},
{
"location": "loc1",
"order": "order1",
"arrival": 603,
"finish": 633,
"wait": 0,
"drive": 0,
"distance": 0,
"service": 30,
"demand": 0,
"demand2": 0,
"coords": {
"address": "loc1",
"latitude": 50.65329310557439,
"longitude": 4.517600740757033
}
},
{
"location": "loc1",
"arrival": 633,
"finish": 633,
"wait": 0,
"drive": 0,
"distance": 0,
"service": 0,
"demand": 0,
"demand2": 0,
"coords": {
"address": "loc1",
"latitude": 50.65329310557439,
"longitude": 4.517600740757033
}
}
]
}
}
Updated about 1 year ago