Fixed cost, cost for waiting time, reducing vans used

I’m currently working through how to reduce vehicles used.

  • Capacity isn’t constrained.
  • Fixed cost per vehicle is HIGH
  • FIXED_COST_PARAM is HIGH
  • Maximum time per vehicle is 8 hours

Problem

Deliveries 274
Vehicles 3
Time 11:05:00
Service Time 09:08:00
Driving Time 01:57:00
Distance (km) 65.47

There is enough time to only use 2 vehicles, but it is using 3. The 3rd simply does 1 delivery and heads back to depot.
There are previous discussions around getting the lowest amount of vehicles required, but I don’t think there is a guaranteed solution.

Is there a method to use waiting time cost?
eg. If a vehicle is used it has to sit out the remaining time it has, in this case for the full 8 hours?
This would mean if a vehicle is used for 1 delivery, then it has 7+ hours of wait time.

Anyone have any ideas on this?

I’m not sure how to include your waiting time idea. But in order to reduce the number of vehicles you could experiment with the “FIXED_COST_PARAM” and set it to a higher value.

Another more complex option would be to implement a hierarchical objective function, where for a certain number of iterations the fleet is minimized. Then the minimal feasible number of vehicles is fixed and the cost are optimized. However, this does not guarantee that the solution with fewer vehicles has lower costs.

Hiya,

I tried to set that fixed_cost_param to 999999 but no matter what I would not get a reliable reduction in vehicles to the bare minimum requirement. I need to invest more time and learn a lot more to find a good solution to this.
I understand that jsprit tries to minimize the cost but in reality it is more feasible in the real world to reduce the number of vehicles used even if there was a slight increase in route cost.

I thought of maybe adding a dynamic job based on vehicle numbers right next to the depot with a time window where it has to deliver right at the end. It would be a fake delivery for each vehicle with a skill specific to each vehicle used.

I found that if I run with INFINITE fleet size the solution is solved faster where I have 1000+ deliveries instead of having a FINITE fleet size.

If you want a hierarchical objective function where the fleet is minimized first you can implement one of the fleet minimization approaches from literature. For example the article from Christiaens and Vanden Berghe (20202) (https://doi.org/10.1287/trsc.2019.0914) has some approach.

For example, before starting the first iteration, a fleet minimization runs on the initial solution for a couple of iterations and iteratively tries to reduce the number of vehicles. After the maximum number of iterations is reached, the solution with the lowest feasible number vehicles is used as the initial solution. In addition, you then also have to adjust the number vehicles available to avoid the use of more vehicles again.

1 Like