GraphHopper.com | Forum | GitHub | Maps | Blog

Balancing jobs to all vehicles / split routes / min-max


#1

I want to share all jobs to all vehicles.
How could I do that?


#2

Have a look into the min-max objective where you can achieve a rather ‘equal spread’ but as stated in the docs: this usually comes with higher transport costs


#3

Thanks @karussell

When I tried in editor, min-max objective assign jobs to all vehicles. But it’s only up to some no of vehicles. First i use min objective of completion_time with 12 vehicles, 7 vehicles are used to finish all jobs. When optimize same jobs and vehicles with min-max objective, only 11 vehicles are used and one vehicle is still available.
When I check min-max objective result, jobs assigned to each vehicle still can be shared to others.


#4

The algorithms tries not to produce too high transportation costs at the same time, so the remaining vehicle might not be worth it. Would you mind sending us the JSON? (via private message here or via email)


#5

min-max minimizes the maximum of each routes’ completion time. Usually this yields more balanced routes. However, if the maximum cannot be further reduced by employing another vehicle, it does not use another idle vehicle.


#6

If you want to employ all vehicles, you might achieve this by continuously reducing the number of max. shipments that can be transported by your vehicles. What if you start with a cap. dimension of no.shipments/no.vehicles*1.1. If routes are not balanced enought you might reduce this to no.shipments/no.vehicles … Would this be a viable approach for you?
Still, we (at GraphHopper) can think about how to balance automatically. However, we need to find out first, what to balance best. No. stopps? Load in terms of weight?


#7

Thanks @stefan

I don’t get clearly what you want me to try.
total dimension of shipments / total vehicles * 1.1?
Please, could you explain me your suggested approach?

I want to optimize to use all vehicles as much as all services or shipments are finished by vehicles.
To balance no. of stops or weight is an another scenario to consider.

I sent my optimized data through forum email.
I got any reply concerned with this email.


#8

total dimension of shipments / total vehicles * 1.1?

I meant to reduce the capacity (one cap dimension) such that all vehicles will be employed. Currently, it seems that only a subset of your vehicles are employed. If you add further “reasonable” constraints, you might enforce all vehicles to be employed.
For example: If you have 100 services and 10 vehicles, a specification without any (cap) constraints might yield a solution with one vehicle (serving all 100 services). If you divide your number of services by the number of vehicles (100 / 10 = 10) and add another capacity dimension “max-services” and set it to 10 such that your vehicles can only load 10 services, all your 10 vehicles will be employed.


#9

Thanks @stefan

Now I know balancing jobs to vehicles. But sorry as I don’t know about ‘max-services’.
I only use Optimization API, and there is no property like ‘max-services’ in vehicle capacity. Is it new property which is not in documentation?


#10

Thanks @stefan
Now i can balance routes by no of locations. There are some vehicles (one or two) not getting assigned sometimes. How could I force to use all vehicles?


#11

Hi @stefan,

In balancing jobs (locations) to all vehicles, I found out today it’s not working by adding average job locations as new capacity in vehicle type. It’s working before. I still couldn’t find why it’s not working now. I can provide data if you want to check.

Thanks


#12

Hello @myominlin, if you provide your example (per mail), I can have a look.
Best, Stefan


#13

Thanks @stefan

I provided data as the following:

{
“objectives”: [
{
“type”: “min”,
“value”: “completion_time”
}
],
“vehicles”: [
{
“vehicle_id”: “vehicle0”,
“start_address”: {
“location_id”: “v0_start”,
“lon”: 101.6408893,
“lat”: 3.1249302
},
“return_to_depot”: true,
“type_id”: “vehicle_type_0”,
“skills”: [
“CD6”,
“Zone A”,
“East KL”
],
“end_address”: {
“location_id”: “v0_end”,
“lon”: 101.6300431,
“lat”: 3.1077034
},
“earliest_start”: 28800,
“latest_end”: 61200,
“max_distance”: 2147483647,
“break”: null
},
{
“vehicle_id”: “vehicle1”,
“start_address”: {
“location_id”: “v1_start”,
“lon”: 101.6408635,
“lat”: 3.1249221
},
“return_to_depot”: false,
“type_id”: “vehicle_type_1”,
“skills”: [
“Fuso”,
“Zone A”
],
“end_address”: null,
“earliest_start”: 28800,
“latest_end”: 61200,
“max_distance”: 2147483647,
“break”: null
},
{
“vehicle_id”: “vehicle2”,
“start_address”: {
“location_id”: “v2_start”,
“lon”: 101.6408893,
“lat”: 3.1249302
},
“return_to_depot”: true,
“type_id”: “vehicle_type_2”,
“skills”: [
“CD6”,
“Zone A”,
“Central KL”
],
“end_address”: null,
“earliest_start”: 28800,
“latest_end”: 61200,
“max_distance”: 2147483647,
“break”: null
}
],
“vehicle_types”: [
{
“type_id”: “vehicle_type_0”,
“profile”: “small_truck”,
“speed_factor”: 0.8,
“service_time_factor”: 1,
“capacity”: [
1400,
700,
5
]
},
{
“type_id”: “vehicle_type_1”,
“profile”: “small_truck”,
“speed_factor”: 1,
“service_time_factor”: 1,
“capacity”: [
1300,
600,
5
]
},
{
“type_id”: “vehicle_type_2”,
“profile”: “small_truck”,
“speed_factor”: 1,
“service_time_factor”: 1,
“capacity”: [
1600,
800,
5
]
}
],
“services”: [],
“shipments”: [
{
“pickup”: {
“address”: {
“location_id”: “jsp0”,
“lon”: 101.6894842,
“lat”: 3.1466952
},
“time_windows”: null,
“duration”: 1200
},
“delivery”: {
“address”: {
“location_id”: “jsd0”,
“lon”: 101.6428008,
“lat”: 3.1270277
},
“time_windows”: null,
“duration”: 2100
},
“id”: “ADM-101017-00001”,
“name”: “Test”,
“size”: [
580,
300,
2
],
“required_skills”: [],
“allowed_vehicles”: [],
“priority”: 2
},
{
“pickup”: {
“address”: {
“location_id”: “jsp0”,
“lon”: 101.6894842,
“lat”: 3.1466952
},
“time_windows”: null,
“duration”: 1800
},
“delivery”: {
“address”: {
“location_id”: “jsd1”,
“lon”: 101.718651,
“lat”: 3.1578882
},
“time_windows”: null,
“duration”: 1800
},
“id”: “ADM-101017-00002”,
“name”: “Test”,
“size”: [
380,
200,
2
],
“required_skills”: [],
“allowed_vehicles”: [],
“priority”: 2
},
{
“pickup”: {
“address”: {
“location_id”: “jsp0”,
“lon”: 101.6894842,
“lat”: 3.1466952
},
“time_windows”: null,
“duration”: 1500
},
“delivery”: {
“address”: {
“location_id”: “jsd2”,
“lon”: 101.6872575,
“lat”: 3.1731189
},
“time_windows”: null,
“duration”: 2100
},
“id”: “ADM-101017-00003”,
“name”: “Test”,
“size”: [
1019,
500,
2
],
“required_skills”: [],
“allowed_vehicles”: [],
“priority”: 2
},
{
“pickup”: {
“address”: {
“location_id”: “jsp0”,
“lon”: 101.6894842,
“lat”: 3.1466952
},
“time_windows”: null,
“duration”: 1500
},
“delivery”: {
“address”: {
“location_id”: “jsd3”,
“lon”: 101.7123004,
“lat”: 3.1457828
},
“time_windows”: null,
“duration”: 2100
},
“id”: “ADM-101017-00004”,
“name”: “Test”,
“size”: [
1019,
500,
2
],
“required_skills”: [],
“allowed_vehicles”: [],
“priority”: 2
},
{
“pickup”: {
“address”: {
“location_id”: “jsp0”,
“lon”: 101.6894842,
“lat”: 3.1466952
},
“time_windows”: null,
“duration”: 1500
},
“delivery”: {
“address”: {
“location_id”: “jsd4”,
“lon”: 101.7291794,
“lat”: 3.1291716
},
“time_windows”: null,
“duration”: 2100
},
“id”: “ADM-101017-00005”,
“name”: “Test”,
“size”: [
1019,
500,
2
],
“required_skills”: [],
“allowed_vehicles”: [],
“priority”: 2
},
{
“pickup”: {
“address”: {
“location_id”: “jsp0”,
“lon”: 101.6894842,
“lat”: 3.1466952
},
“time_windows”: null,
“duration”: 1500
},
“delivery”: {
“address”: {
“location_id”: “jsd5”,
“lon”: 101.6854985,
“lat”: 3.0914975
},
“time_windows”: null,
“duration”: 2100
},
“id”: “ADM-101017-00006”,
“name”: “Test”,
“size”: [
1019,
500,
2
],
“required_skills”: [],
“allowed_vehicles”: [],
“priority”: 2
},
{
“pickup”: {
“address”: {
“location_id”: “jsp6”,
“lon”: 101.6907961,
“lat”: 3.1460845
},
“time_windows”: null,
“duration”: 1500
},
“delivery”: {
“address”: {
“location_id”: “jsd6”,
“lon”: 101.6857739,
“lat”: 3.1101967
},
“time_windows”: null,
“duration”: 2100
},
“id”: “ADM-101017-00007”,
“name”: “Test”,
“size”: [
1019,
500,
2
],
“required_skills”: [],
“allowed_vehicles”: [],
“priority”: 2
}
],
“relations”: []
}


#14

Hi @myominlin,
You are correct. When dealing with shipments, it does not work. Since the third capacity dimension you introduced can be interpreted as max. number of shipments that can be loaded at the same time. If you unload a shipment, another shipment can be loaded of course which in turn breaks your assumption of max. number of shipments per vehicle (in total). If you change your objective to min-max, it helps a bit.
Would it help, if we introduced another field in vehicle called “max_jobs” to restrict the number jobs that vehicle can load?

Best,
Stefan


#15

@stefan

Thanks for quick reply.
When I try with min-max, it’s working for now to share all job locations to all vehicles.
Actually, I also want to balance jobs to all vehicles by time or distance if API can provide.
Please let me know if there is an alternative way can do that.


#16

Not sure it is helpful as this is a bit late, but did you find the parameters max_distance and max_driving_time?


#17

This New feature: balance stops might be interesting here as well.