Plan employee transportation
This tutorial presents a vehicle routing problem revolving around optimization of employee transportation operations using Tour Planning. The scenario involves a company operating a fleet of vehicles with varying capacities and cost structures. The goal is to pick up employees from multiple locations and transport them to a central destination before 8:00 AM while minimizing costs and adhering to time constraints. This approach can also be applied to school transportation, ensuring that students are picked up from various locations and arrive at school on time while keeping costs low.
Tip
For another people transportation use case that considers the requirement for a single person to be driven by the same driver on both the commute to and from their target location, such as from home to school and back, see Flexible groups.
Problem
The following sections provide a breakdown of the fleet and tour plan configuration for the purpose of this case study.
Fleet configuration
Two types of vehicles are available: car_a and van_a. Each vehicle type has specific cost structures, capacities, and shift times. The following table provides an overview of the vehicle types in the fleet, allowing for easy comparison of their costs, capacity, and quantity available:
| Vehicle Type | Costs (Fixed) | Capacity | Amount | Shift Start | Shift End |
|---|---|---|---|---|---|
car_a | $25.00 | 4 | 3 | 06:30:00 | 08:00:00 |
van_a | $20.00 | 7 | 2 | 06:30:00 | 08:00:00 |
Even though the van vehicle is more spacious, it is assigned a lower fixed cost to encourage its more frequent use to carry people. This means the cost of running the vehicle is spread out over more trips or items, making each trip cheaper.
The following snippet puts the fleet settings in the context of a problem JSON:
{
"fleet": {
"types": [
{
"id": "car_a",
"profile": "car",
"costs": {
"fixed": 25,
"distance": 0.005,
"time": 0.005
},
"capacity": [
4
],
"amount": 3
},
{
"id": "van_a",
"profile": "car",
"costs": {
"fixed": 20,
"distance": 0.005,
"time": 0.005
},
"capacity": [
7
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
}
}Tour plan
The tour plan in this vehicle routing problem consists of 12 job tasks for each employee to pick up, as shown in the following snippet:
{
"id": "Employee_1",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.56182,
"lng": 13.497167
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
}Each job is configured to last 60 seconds through the duration property and specifies the maximum time an employee can spend in a vehicle to 3600 seconds (one hour) through the maxTimeOnVehicle property. The specification of maxTimeOnVehicle places a soft constraint on both tour duration and capacity of each vehicle:
-
Tour Duration: The
maxTimeOnVehicleparameter ensures that each employee spends no more than the specified time (3600seconds or one hour) in the vehicle. This constraint influences the total time a vehicle can spend picking up and dropping off employees, effectively limiting the duration of the tour from the moment the first employee is picked up to the last drop-off. -
Capacity: While
maxTimeOnVehicleprimarily constrains tour duration, it indirectly affects vehicle capacity. Since a vehicle must complete its tour within one hour, it might not be able to pick up as many employees if they are spread out over a large area or if the travel times between pickup points are long.
The following section contains the full problem JSON file:
Click to expand/collapse the sample JSON
{
"fleet": {
"types": [
{
"id": "car_a",
"profile": "car",
"costs": {
"fixed": 25,
"distance": 0.005,
"time": 0.005
},
"shifts": [
{
"start": {
"time": "2023-05-28T06:30:00Z"
},
"end": {
"time": "2023-05-28T08:00:00Z",
"location": {
"lat": 52.508884,
"lng": 13.386738
}
}
}
],
"capacity": [
4
],
"amount": 3
},
{
"id": "van_a",
"profile": "car",
"costs": {
"fixed": 20,
"distance": 0.005,
"time": 0.005
},
"shifts": [
{
"start": {
"time": "2023-05-28T06:30:00Z"
},
"end": {
"time": "2023-05-28T08:00:00Z",
"location": {
"lat": 52.508884,
"lng": 13.386738
}
}
}
],
"capacity": [
7
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
},
"plan": {
"jobs": [
{
"id": "Employee_1",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.56182,
"lng": 13.497167
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_2",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.534553,
"lng": 13.519429
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_3",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.482275,
"lng": 13.502456
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_4",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.473537,
"lng": 13.505414
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_5",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.463341,
"lng": 13.49061
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_6",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.434003,
"lng": 13.466142
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_7",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.447476,
"lng": 13.433062
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_8",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.458414,
"lng": 13.392079
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_9",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.446407,
"lng": 13.36047
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_10",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.440807,
"lng": 13.351399
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_11",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.441913,
"lng": 13.339028
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Employee_12",
"maxTimeOnVehicle": 3600,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.458232,
"lng": 13.338698
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
}
]
}
}Solution
The following figure shows the solution visualization:
The following table breaks down the tour statistics for each vehicle assigned a job:
| Vehicle ID | Vehicle Type | Total Cost | Total Distance | Total Duration | Driving Time (s) | Driving Time (min) | Serving Time (s) | Number of Stops | Employees Picked Up |
|---|---|---|---|---|---|---|---|---|---|
| van_a_2 | van_a | $159.19 | 24,889 m | 2,949 s | 2,529 s | 42.15 min | 420 s | 7 | Employee_6, Employee_7, Employee_8, Employee_9, Employee_10, Employee_11, Employee_12 |
| van_a_1 | van_a | $169.98 | 26,867 m | 3,129 s | 2,829 s | 47.15 min | 300 s | 5 | Employee_1, Employee_2, Employee_3, Employee_4, Employee_5 |
As the solution indicates, the optimization algorithm selected only vehicles of type van_a for the job, for the following reasons:
van_awas selected due to its lower fixed cost, making it a more cost-efficient option compared tocar_a.- With its higher capacity than
car_a,van_awas able to serve all jobs by using only 2 vehicles, meeting the time constraints. The use of only two vans highlights the effectiveness of the optimization algorithm in reducing the fleet size. In addition, fewer vehicles on the road might lead to reduced emissions and environmental impact. - Each vehicle met the maximum time on vehicle constraint of
3600seconds (one hour), ensuring timely arrival of all employees to their destination. By ensuring timely pickup and drop-off within the specified time limits, the solution contributes to employee satisfaction and punctuality.
The following section contains the full solution JSON file:
Click to expand/collapse the sample JSON
{
"statistic": {
"cost": 329.17,
"distance": 51756,
"duration": 6078,
"times": {
"driving": 5358,
"serving": 720,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "van_a_2",
"typeId": "van_a",
"stops": [
{
"time": {
"arrival": "2023-05-28T06:30:00Z",
"departure": "2023-05-28T06:31:00Z"
},
"load": [
1
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.434003,
"lng": 13.466142
},
"time": {
"start": "2023-05-28T06:30:00Z",
"end": "2023-05-28T06:30:00Z"
}
},
{
"jobId": "Employee_6",
"type": "pickup",
"location": {
"lat": 52.434003,
"lng": 13.466142
},
"time": {
"start": "2023-05-28T06:30:00Z",
"end": "2023-05-28T06:31:00Z"
}
}
],
"location": {
"lat": 52.434003,
"lng": 13.466142
},
"distance": 0
},
{
"time": {
"arrival": "2023-05-28T06:36:50Z",
"departure": "2023-05-28T06:37:50Z"
},
"load": [
2
],
"activities": [
{
"jobId": "Employee_7",
"type": "pickup",
"location": {
"lat": 52.447476,
"lng": 13.433062
},
"time": {
"start": "2023-05-28T06:36:50Z",
"end": "2023-05-28T06:37:50Z"
}
}
],
"location": {
"lat": 52.447476,
"lng": 13.433062
},
"distance": 3529
},
{
"time": {
"arrival": "2023-05-28T06:44:17Z",
"departure": "2023-05-28T06:45:17Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Employee_8",
"type": "pickup",
"location": {
"lat": 52.458414,
"lng": 13.392079
},
"time": {
"start": "2023-05-28T06:44:17Z",
"end": "2023-05-28T06:45:17Z"
}
}
],
"location": {
"lat": 52.458414,
"lng": 13.392079
},
"distance": 7553
},
{
"time": {
"arrival": "2023-05-28T06:50:32Z",
"departure": "2023-05-28T06:51:32Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Employee_9",
"type": "pickup",
"location": {
"lat": 52.446407,
"lng": 13.36047
},
"time": {
"start": "2023-05-28T06:50:32Z",
"end": "2023-05-28T06:51:32Z"
}
}
],
"location": {
"lat": 52.446407,
"lng": 13.36047
},
"distance": 10367
},
{
"time": {
"arrival": "2023-05-28T06:55:02Z",
"departure": "2023-05-28T06:56:02Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Employee_10",
"type": "pickup",
"location": {
"lat": 52.440807,
"lng": 13.351399
},
"time": {
"start": "2023-05-28T06:55:02Z",
"end": "2023-05-28T06:56:02Z"
}
}
],
"location": {
"lat": 52.440807,
"lng": 13.351399
},
"distance": 11951
},
{
"time": {
"arrival": "2023-05-28T06:59:23Z",
"departure": "2023-05-28T07:00:23Z"
},
"load": [
6
],
"activities": [
{
"jobId": "Employee_11",
"type": "pickup",
"location": {
"lat": 52.441913,
"lng": 13.339028
},
"time": {
"start": "2023-05-28T06:59:23Z",
"end": "2023-05-28T07:00:23Z"
}
}
],
"location": {
"lat": 52.441913,
"lng": 13.339028
},
"distance": 13550
},
{
"time": {
"arrival": "2023-05-28T07:04:36Z",
"departure": "2023-05-28T07:05:36Z"
},
"load": [
7
],
"activities": [
{
"jobId": "Employee_12",
"type": "pickup",
"location": {
"lat": 52.458232,
"lng": 13.338698
},
"time": {
"start": "2023-05-28T07:04:36Z",
"end": "2023-05-28T07:05:36Z"
}
}
],
"location": {
"lat": 52.458232,
"lng": 13.338698
},
"distance": 15677
},
{
"time": {
"arrival": "2023-05-28T07:19:09Z",
"departure": "2023-05-28T07:19:09Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 52.508884,
"lng": 13.386738
},
"time": {
"start": "2023-05-28T07:19:09Z",
"end": "2023-05-28T07:19:09Z"
}
}
],
"location": {
"lat": 52.508884,
"lng": 13.386738
},
"distance": 24889
}
],
"statistic": {
"cost": 159.19,
"distance": 24889,
"duration": 2949,
"times": {
"driving": 2529,
"serving": 420,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
},
{
"vehicleId": "van_a_1",
"typeId": "van_a",
"stops": [
{
"time": {
"arrival": "2023-05-28T06:30:00Z",
"departure": "2023-05-28T06:31:00Z"
},
"load": [
1
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.56182,
"lng": 13.497167
},
"time": {
"start": "2023-05-28T06:30:00Z",
"end": "2023-05-28T06:30:00Z"
}
},
{
"jobId": "Employee_1",
"type": "pickup",
"location": {
"lat": 52.56182,
"lng": 13.497167
},
"time": {
"start": "2023-05-28T06:30:00Z",
"end": "2023-05-28T06:31:00Z"
}
}
],
"location": {
"lat": 52.56182,
"lng": 13.497167
},
"distance": 0
},
{
"time": {
"arrival": "2023-05-28T06:37:37Z",
"departure": "2023-05-28T06:38:37Z"
},
"load": [
2
],
"activities": [
{
"jobId": "Employee_2",
"type": "pickup",
"location": {
"lat": 52.534553,
"lng": 13.519429
},
"time": {
"start": "2023-05-28T06:37:37Z",
"end": "2023-05-28T06:38:37Z"
}
}
],
"location": {
"lat": 52.534553,
"lng": 13.519429
},
"distance": 3749
},
{
"time": {
"arrival": "2023-05-28T06:52:39Z",
"departure": "2023-05-28T06:53:39Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Employee_3",
"type": "pickup",
"location": {
"lat": 52.482275,
"lng": 13.502456
},
"time": {
"start": "2023-05-28T06:52:39Z",
"end": "2023-05-28T06:53:39Z"
}
}
],
"location": {
"lat": 52.482275,
"lng": 13.502456
},
"distance": 12529
},
{
"time": {
"arrival": "2023-05-28T06:55:29Z",
"departure": "2023-05-28T06:56:29Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Employee_4",
"type": "pickup",
"location": {
"lat": 52.473537,
"lng": 13.505414
},
"time": {
"start": "2023-05-28T06:55:29Z",
"end": "2023-05-28T06:56:29Z"
}
}
],
"location": {
"lat": 52.473537,
"lng": 13.505414
},
"distance": 13815
},
{
"time": {
"arrival": "2023-05-28T07:02:29Z",
"departure": "2023-05-28T07:03:29Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Employee_5",
"type": "pickup",
"location": {
"lat": 52.463341,
"lng": 13.49061
},
"time": {
"start": "2023-05-28T07:02:29Z",
"end": "2023-05-28T07:03:29Z"
}
}
],
"location": {
"lat": 52.463341,
"lng": 13.49061
},
"distance": 16756
},
{
"time": {
"arrival": "2023-05-28T07:22:09Z",
"departure": "2023-05-28T07:22:09Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 52.508884,
"lng": 13.386738
},
"time": {
"start": "2023-05-28T07:22:09Z",
"end": "2023-05-28T07:22:09Z"
}
}
],
"location": {
"lat": 52.508884,
"lng": 13.386738
},
"distance": 26867
}
],
"statistic": {
"cost": 169.98000000000002,
"distance": 26867,
"duration": 3129,
"times": {
"driving": 2829,
"serving": 300,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}Next steps
- For more information on the maxTimeOnVehicle property, see Problem
- For an in-depth exploration of the HERE Tour Planning API methods, endpoints, and parameters, see the API Reference.
Updated 29 days ago