- 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
VRP with Heterogeneous Fleet
It’s a well-known constraint for a VRP when a fleet of vehicles is characterized by different capacities, costs or vehicle types. For example, a fleet can consist of Car, Truck, Pedestrian, Scooter, or Bicycle with different shift hours, capacities, distance/duration, and cost. This is called a Heterogeneous fleet VRP and it requires some specific settings in terms of vehicles to be solved. Let’s consider a solution for such a problem with some specific constraints.
Let’s say we have a fleet of two different types of vehicles - a car and a truck. They have different shift times, capacity, max distance and cost. Moreover, both vehicles start their shifts at the same location, but the car finishes its tour at another depot, which means its end location is different from the start location. Taking into account those different constraints for both vehicles, we will have to specify all of them separately for car_1 and truck_1.
Regarding the jobs that we are going to assign for the tour, there will be no specific constraints as the algorithm will consider all the constraints specified for the vehicles and calculate the route taking that into account. So for the jobs we specify the routine data - jobs ID, time, location, demand and priority (if needed), etc. The key constraints in this very problem will be the vehicles’ type and capacity, start and end location, the shift time, and jobs' demand. With the car's capacity of 10 and the truck's capacity of 40, we are going to execute 4 jobs with the demand of 2, 2, 6, and 40 respectively. Regarding all mentioned above, the problem for the Heterogeneous fleet VRP would look as follows:
Problem
{
"fleet": {
"types": [
{
"id": "6d1dc02e19d6",
"profile": "car_1",
"costs": {
"fixed": 8.0,
"distance": 0.002,
"time": 0.009
},
"shifts": [
{
"start": {
"time": "2021-08-27T06:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T13:03:00Z",
"location": {
"lat": 52.529953,
"lng": 13.314877
}
}
}
],
"capacity": [
10
],
"amount": 1
},
{
"id": "b47bb0d26e4c",
"profile": "truck_1",
"costs": {
"fixed": 13.0,
"distance": 0.002,
"time": 0.006
},
"shifts": [
{
"start": {
"time": "2021-08-27T14:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T19:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
40
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
},
{
"type": "truck",
"name": "truck_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T09:03:00Z",
"2021-08-27T15:03:00Z"
]
],
"location": {
"lat": 52.46274034612159,
"lng": 13.381744271815766
},
"duration": 780
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T09:03:00Z",
"2021-08-27T15:03:00Z"
]
],
"location": {
"lat": 52.495709703500346,
"lng": 13.383026814092966
},
"duration": 840
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T10:03:00Z",
"2021-08-27T18:03:00Z"
]
],
"location": {
"lat": 52.489639267111066,
"lng": 13.305679494421426
},
"duration": 540
}
],
"demand": [
6
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-08-27T10:03:00Z",
"2021-08-27T19:03:00Z"
]
],
"location": {
"lat": 52.60353049998964,
"lng": 13.42085512158312
},
"duration": 1080
}
],
"demand": [
40
]
}
]
}
}
]
}
}
Solution
The solution for this problem will look as follows:
{
"statistic": {
"cost": 184.654,
"distance": 48104,
"duration": 8949,
"times": {
"driving": 5709,
"serving": 3240,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "6d1dc02e19d6_1",
"typeId": "6d1dc02e19d6",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T06:03:00Z",
"departure": "2021-08-27T09:06:45Z"
},
"load": [
10
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.495709703500346,
"lng": 13.383026814092966
},
"time": {
"arrival": "2021-08-27T09:17:02Z",
"departure": "2021-08-27T09:31:02Z"
},
"load": [
8
],
"activities": [
{
"jobId": "job_2",
"type": "delivery"
}
],
"distance": 5299
},
{
"location": {
"lat": 52.46274034612159,
"lng": 13.381744271815766
},
"time": {
"arrival": "2021-08-27T09:39:50Z",
"departure": "2021-08-27T09:52:50Z"
},
"load": [
6
],
"activities": [
{
"jobId": "job_1",
"type": "delivery"
}
],
"distance": 9504
},
{
"location": {
"lat": 52.489639267111066,
"lng": 13.305679494421426
},
"time": {
"arrival": "2021-08-27T10:03:00Z",
"departure": "2021-08-27T10:12:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
],
"distance": 16674
},
{
"location": {
"lat": 52.529953,
"lng": 13.314877
},
"time": {
"arrival": "2021-08-27T10:23:09Z",
"departure": "2021-08-27T10:23:09Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 25453
}
],
"statistic": {
"cost": 100.082,
"distance": 25413,
"duration": 4584,
"times": {
"driving": 2424,
"serving": 2160,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "b47bb0d26e4c_1",
"typeId": "b47bb0d26e4c",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T14:03:00Z",
"departure": "2021-08-27T14:03:00Z"
},
"load": [
40
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.60353049998964,
"lng": 13.42085512158312
},
"time": {
"arrival": "2021-08-27T14:32:08Z",
"departure": "2021-08-27T14:50:08Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
],
"distance": 11280
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T15:15:45Z",
"departure": "2021-08-27T15:15:45Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 22692
}
],
"statistic": {
"cost": 84.572,
"distance": 22691,
"duration": 4365,
"times": {
"driving": 3285,
"serving": 1080,
"waiting": 0,
"break": 0
}
}
}
]
}
From this solution we can see the common statistics of the tour like total cost, distance and duration, total driving, serving, and waiting time as well as the detailed statistics of each vehicle’s tour separately, as they had different constraints which is typical for the Heterogeneous fleet.
