Solve open vehicle routing problems
The Open VRP is a variation of the vehicle routing problem (VRP) that has a distinctive characteristic: its open path format. This means that vehicles are not required to return to the depot after completing all tasks; instead, the key vehicle shift constraints for these problems are pickup and delivery locations and the times.
It is a common scenario for delivery companies that use vehicles that are not company-owned, meaning that these vehicles may not be required to return to the depot or any specific location after serving the last customer. The Open VRP (Vehicle Routing Problem) is encountered in real-world scenarios such as home delivery of various products or services, food delivery, and other similar operations.
HERE Tour planning offers the ability to create an open tour, which is a tour without a defined starting or ending location. Therefore, depending on the problem definition, the tour can begin or end at any of the task locations, including pickup and delivery points. The following variations of Open VRP are supported:
- Problem without shift end (shift end time, as well as location, is not specified)
- Problem without shift end location
- Problem without shift start location
- Problem without shift start and end locations
In this tutorial, we'll discuss a couple of examples.
Problem without shift end
In this variation, the shift end is completely omitted.
Consider a scenario where you, as a delivery company, hire a vehicle to deliver goods to customers. The vehicle may need to start from a specified location, such as a depot or warehouse, to pick up the goods for delivery.
Therefore, that depot/warehouse location will serve as the starting point for the vehicle. Given that once the assigned tasks are completed, the vehicle is free to conclude the tour without needing to return to the depot/warehouse. Additionally, we can establish shiftTime limits for the vehicles to manage the drivers' working hours.
In this case, it is crucial to note that you cannot employ multiple open shifts (shifts without an end time) for a vehicle within the same tour to prevent shifts from overlapping. If you need to assign more than one shift to a vehicle, only the final shift for that vehicle can lack an end time; otherwise, a validation error will occur.
The following is one example when shift start (with location) is defined while shift end is not defined:
{
"fleet": {
"types": [
{
"id": "048d43e6e61c",
"profile": "car_1",
"costs": {
"fixed": 10.0,
"distance": 0.002,
"time": 0.01
},
"shifts": [
{
"start": {
"time": "2021-07-13T08:20:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
100
],
"limits": {
"shiftTime": 43200
},
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.513365341037485,
"lng": 13.325000854641972
},
"duration": 780
}
],
"demand": [
40
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"duration": 120
}
],
"demand": [
5
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"duration": 360
}
],
"demand": [
10
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.55783238016377,
"lng": 13.304436007504957
},
"duration": 720
}
],
"demand": [
10
]
}
]
}
},
{
"id": "job_5",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.60592698633012,
"lng": 13.360660447014226
},
"duration": 240
}
],
"demand": [
5
]
}
]
}
},
{
"id": "job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.547429320898374,
"lng": 13.303190999428224
},
"duration": 780
}
],
"demand": [
15
]
}
]
}
}
]
}
}Solution
The solution for such a problem will look as follows:
{
"statistic": {
"cost": 252.23600000000002,
"distance": 71323,
"duration": 9959,
"times": {
"driving": 6959,
"serving": 3000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "048d43e6e61c_2",
"typeId": "048d43e6e61c",
"stops": [
{
"time": {
"arrival": "2021-07-13T08:20:00Z",
"departure": "2021-07-13T08:20:00Z"
},
"load": [
35
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"start": "2021-07-13T08:20:00Z",
"end": "2021-07-13T08:20:00Z"
}
}
],
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"distance": 0
},
{
"time": {
"arrival": "2021-07-13T08:43:06Z",
"departure": "2021-07-13T08:49:06Z"
},
"load": [
45
],
"activities": [
{
"jobId": "job_3",
"type": "pickup",
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"time": {
"start": "2021-07-13T08:43:06Z",
"end": "2021-07-13T08:49:06Z"
}
}
],
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"distance": 14796
},
{
"time": {
"arrival": "2021-07-13T09:11:11Z",
"departure": "2021-07-13T09:24:11Z"
},
"load": [
85
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"location": {
"lat": 52.513365341037485,
"lng": 13.325000854641972
},
"time": {
"start": "2021-07-13T09:11:11Z",
"end": "2021-07-13T09:24:11Z"
}
}
],
"location": {
"lat": 52.513365341037485,
"lng": 13.325000854641972
},
"distance": 30106
},
{
"time": {
"arrival": "2021-07-13T09:39:28Z",
"departure": "2021-07-13T09:52:28Z"
},
"load": [
70
],
"activities": [
{
"jobId": "job_6",
"type": "delivery",
"location": {
"lat": 52.547429320898374,
"lng": 13.303190999428224
},
"time": {
"start": "2021-07-13T09:39:28Z",
"end": "2021-07-13T09:52:28Z"
}
}
],
"location": {
"lat": 52.547429320898374,
"lng": 13.303190999428224
},
"distance": 36717
},
{
"time": {
"arrival": "2021-07-13T10:02:13Z",
"departure": "2021-07-13T10:14:13Z"
},
"load": [
60
],
"activities": [
{
"jobId": "job_4",
"type": "delivery",
"location": {
"lat": 52.55783238016377,
"lng": 13.304436007504956
},
"time": {
"start": "2021-07-13T10:02:13Z",
"end": "2021-07-13T10:14:13Z"
}
}
],
"location": {
"lat": 52.55783238016377,
"lng": 13.304436007504956
},
"distance": 39363
},
{
"time": {
"arrival": "2021-07-13T10:28:13Z",
"departure": "2021-07-13T10:32:13Z"
},
"load": [
55
],
"activities": [
{
"jobId": "job_5",
"type": "delivery",
"location": {
"lat": 52.60592698633012,
"lng": 13.360660447014226
},
"time": {
"start": "2021-07-13T10:28:13Z",
"end": "2021-07-13T10:32:13Z"
}
}
],
"location": {
"lat": 52.60592698633012,
"lng": 13.360660447014226
},
"distance": 47447
},
{
"time": {
"arrival": "2021-07-13T11:03:59Z",
"departure": "2021-07-13T11:05:59Z"
},
"load": [
50
],
"activities": [
{
"jobId": "job_2",
"type": "delivery",
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"time": {
"start": "2021-07-13T11:03:59Z",
"end": "2021-07-13T11:05:59Z"
}
}
],
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"distance": 71323
}
],
"statistic": {
"cost": 252.23600000000002,
"distance": 71323,
"duration": 9959,
"times": {
"driving": 6959,
"serving": 3000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}From this solution, we can see the statistic of the vehicle's tour, including the total cost, duration, distance, and time spent for driving and serving with all the locations visited regarding the constraints. Note that the vehicle's last activity time and location are the last time and location in the tour.
Problem without shift start and end locations
Here is an example where neither the shift start location nor the shift end location is defined, while only the shift start and end times are specified.
This variant of Open VRP can also be applied in a multi-shift context, provided that the shift times across the shifts do not overlap.
This use case is quite common when fleet operators engage external fleet suppliers. In such instances, they typically create the tour without knowing the exact location from which the supplier's fleet will commence or conclude the tour. Consequently, the tour is generated for all the given tasks, and the fleet supplier executes the tour.
{
"fleet": {
"types": [
{
"id": "048d43e6e61c",
"profile": "car_1",
"costs": {
"fixed": 10.0,
"distance": 0.002,
"time": 0.01
},
"shifts": [
{
"start": {
"time": "2021-07-13T08:20:00Z"
},
"end": {
"time": "2021-07-13T14:20:00Z"
}
}
],
"capacity": [
100
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.513365341037485,
"lng": 13.325000854641972
},
"duration": 780
}
],
"demand": [
40
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"duration": 120
}
],
"demand": [
5
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"duration": 360
}
],
"demand": [
10
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.55783238016377,
"lng": 13.304436007504957
},
"duration": 720
}
],
"demand": [
10
]
}
]
}
},
{
"id": "job_5",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.60592698633012,
"lng": 13.360660447014226
},
"duration": 240
}
],
"demand": [
5
]
}
]
}
},
{
"id": "job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.547429320898374,
"lng": 13.303190999428224
},
"duration": 780
}
],
"demand": [
15
]
}
]
}
}
]
}
}Solution
The solution for such a problem will look as follows:
{
"statistic": {
"cost": 207.94,
"distance": 56495,
"duration": 8495,
"times": {
"driving": 5495,
"serving": 3000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "048d43e6e61c_2",
"typeId": "048d43e6e61c",
"stops": [
{
"time": {
"arrival": "2021-07-13T08:20:00Z",
"departure": "2021-07-13T08:22:00Z"
},
"load": [
30
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"time": {
"start": "2021-07-13T08:20:00Z",
"end": "2021-07-13T08:20:00Z"
}
},
{
"jobId": "job_2",
"type": "delivery",
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"time": {
"start": "2021-07-13T08:20:00Z",
"end": "2021-07-13T08:22:00Z"
}
}
],
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"distance": 0
},
{
"time": {
"arrival": "2021-07-13T08:53:11Z",
"departure": "2021-07-13T08:57:11Z"
},
"load": [
25
],
"activities": [
{
"jobId": "job_5",
"type": "delivery",
"location": {
"lat": 52.60592698633012,
"lng": 13.360660447014226
},
"time": {
"start": "2021-07-13T08:53:11Z",
"end": "2021-07-13T08:57:11Z"
}
}
],
"location": {
"lat": 52.60592698633012,
"lng": 13.360660447014226
},
"distance": 23646
},
{
"time": {
"arrival": "2021-07-13T09:10:40Z",
"departure": "2021-07-13T09:22:40Z"
},
"load": [
15
],
"activities": [
{
"jobId": "job_4",
"type": "delivery",
"location": {
"lat": 52.55783238016377,
"lng": 13.304436007504956
},
"time": {
"start": "2021-07-13T09:10:40Z",
"end": "2021-07-13T09:22:40Z"
}
}
],
"location": {
"lat": 52.55783238016377,
"lng": 13.304436007504956
},
"distance": 31705
},
{
"time": {
"arrival": "2021-07-13T09:31:36Z",
"departure": "2021-07-13T09:44:36Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_6",
"type": "delivery",
"location": {
"lat": 52.547429320898374,
"lng": 13.303190999428224
},
"time": {
"start": "2021-07-13T09:31:36Z",
"end": "2021-07-13T09:44:36Z"
}
}
],
"location": {
"lat": 52.547429320898374,
"lng": 13.303190999428224
},
"distance": 34750
},
{
"time": {
"arrival": "2021-07-13T10:01:37Z",
"departure": "2021-07-13T10:14:37Z"
},
"load": [
40
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"location": {
"lat": 52.513365341037485,
"lng": 13.325000854641972
},
"time": {
"start": "2021-07-13T10:01:37Z",
"end": "2021-07-13T10:14:37Z"
}
}
],
"location": {
"lat": 52.513365341037485,
"lng": 13.325000854641972
},
"distance": 41184
},
{
"time": {
"arrival": "2021-07-13T10:35:35Z",
"departure": "2021-07-13T10:41:35Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_3",
"type": "pickup",
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"time": {
"start": "2021-07-13T10:35:35Z",
"end": "2021-07-13T10:41:35Z"
}
},
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"time": {
"start": "2021-07-13T10:41:35Z",
"end": "2021-07-13T10:41:35Z"
}
}
],
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"distance": 56495
}
],
"statistic": {
"cost": 207.94,
"distance": 56495,
"duration": 8495,
"times": {
"driving": 5495,
"serving": 3000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}In this solution, the vehicle's tour begins at one of the delivery points, and it concludes at the stop where the last delivery is made.
Next steps
For more information, see:
Updated 29 days ago