- Products ProductsLocation Services
Solve complex location problems from geofencing to custom routing
PlatformCloud environments for location-centric solution development, data exchange and visualization
Tracking & PositioningFast and accurate tracking and positioning of people and devices, indoors or outdoors
APIs & SDKsEasy to use, scaleable and flexible tools to get going quickly
Developer EcosystemsAccess Location Services on your favorite developer platform ecosystem
- Documentation DocumentationOverview OverviewServices ServicesApplications ApplicationsDevelopment Enablers Development EnablersContent ContentHERE Studio HERE StudioHERE Workspace HERE WorkspaceHERE Marketplace HERE MarketplacePlatform Foundation and Policy Documents Platform Foundation and Policy Documents
- Pricing
- Resources ResourcesTutorials TutorialsExamples ExamplesBlog & Release Announcements Blog & Release AnnouncementsChangelog ChangelogDeveloper Newsletter Developer NewsletterKnowledge Base Knowledge BaseFeature List Feature ListSupport Plans Support PlansSystem Status System StatusLocation Services Coverage Information Location Services Coverage InformationSample Map Data for Students Sample Map Data for Students
- Help
Open VRP
It occurs very often when delivery companies use vehicles that are not on the company staff which implies that those vehicles may not return to the depot, or may work on their specific shifts as contractors. Such a type of problem is called Open VRP. In the Open VRP, contractors who are not employees of the delivery company use their own vehicles and do not return to the depot after servicing the last customer. The Open VRP may be encountered in real-life as home delivery of any products or services, food delivery, etc.
The Open VRP is a variant of the vehicle routing problem that has a unique character which is its open path form. This means that the vehicles are not required to return to the depot after completing all tasks, therefore the key constraints for such problems are pickup and delivery locations and the vehicles' time shifts.
Basically, to build an Open VRP we should add a shift start time and location to the desired vehicle, without adding any shift end time and location, to allow the vehicle finish its tour at the last served job location.
Note that you can not use several open shifts (shift without end time) for a vehicle in one tour to prevent shifts overlapping. If you need to set more than one shift to a vehicle, then only the last shift of a vehicle is allowed not to have a shift end time, otherwise, a validation error will be returned.
Let’s consider a situation when a delivery company hires two vehicles for delivering any products to the customers. Those vehicles do not belong to the company and the drivers are contractors. The company does not even have a depot where those vehicles start their route, but it has a warehouse where they need to pick up the goods that they will need to deliver.
Thus, that warehouse location will be the starting location for both vehicles. Considering that after executing the last delivery the vehicles don’t need to return to the depot, then they will end their tours on the last delivery. Also in this situation, we will need to set the shiftTime for the vehicles’ limits to control the drivers working time.
Problem
With all the constraints above, the problem for this specific open VRP will look as follows:
{
"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": 267.092,
"distance": 73626,
"duration": 10984,
"times": {
"driving": 7984,
"serving": 3000,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "048d43e6e61c_2",
"typeId": "048d43e6e61c",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-07-13T08:20:00Z",
"departure": "2021-07-13T08:20:00Z"
},
"load": [
35
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.44003237354213,
"lng": 13.422125667246638
},
"time": {
"arrival": "2021-07-13T08:48:16Z",
"departure": "2021-07-13T08:54:16Z"
},
"load": [
45
],
"activities": [
{
"jobId": "job_3",
"type": "pickup"
}
],
"distance": 14798
},
{
"location": {
"lat": 52.513365341037485,
"lng": 13.325000854641972
},
"time": {
"arrival": "2021-07-13T09:19:01Z",
"departure": "2021-07-13T09:32:01Z"
},
"load": [
85
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
],
"distance": 31507
},
{
"location": {
"lat": 52.547429320898374,
"lng": 13.303190999428224
},
"time": {
"arrival": "2021-07-13T09:48:41Z",
"departure": "2021-07-13T10:01:41Z"
},
"load": [
70
],
"activities": [
{
"jobId": "job_6",
"type": "delivery"
}
],
"distance": 38124
},
{
"location": {
"lat": 52.55783238016377,
"lng": 13.304436007504956
},
"time": {
"arrival": "2021-07-13T10:11:56Z",
"departure": "2021-07-13T10:23:56Z"
},
"load": [
60
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
],
"distance": 40768
},
{
"location": {
"lat": 52.60592698633012,
"lng": 13.360660447014226
},
"time": {
"arrival": "2021-07-13T10:40:28Z",
"departure": "2021-07-13T10:44:28Z"
},
"load": [
55
],
"activities": [
{
"jobId": "job_5",
"type": "delivery"
}
],
"distance": 48850
},
{
"location": {
"lat": 52.7478839710114,
"lng": 13.44595304182502
},
"time": {
"arrival": "2021-07-13T11:21:04Z",
"departure": "2021-07-13T11:23:04Z"
},
"load": [
50
],
"activities": [
{
"jobId": "job_2",
"type": "delivery"
}
],
"distance": 72722
}
],
"statistic": {
"cost": 267.092,
"distance": 73626,
"duration": 10984,
"times": {
"driving": 7984,
"serving": 3000,
"waiting": 0,
"break": 0
}
}
}
]
}
From this solution, we can see the statistic of the vehicles' tours, including the total cost, duration, distance, and time spent for driving and serving with all the locations visited regarding the constraints. Note that the vehicles' last activity time and location are the last time and location in the tour.
