A way to force a fixed number of vehicles

[matthewrudy]

We are looking for a way to force the number of vehicles.

Namely, we have 20 waypoints, and 5 vehicles,
we want to optimise the routes to use all of the 5 vehicles.

I think given the existing library, the best way to do this is to have a negative fixed cost for each vehicle.

ie. it should increase the cost function to not use all vehicles.

But currently that function isn't supported,

if (fixedCost < 0.0) throw new IllegalStateException("fixed costs cannot be smaller than zero")

and forking the library to remove this line doesn't seem to work correctly.

(I guess negative fixedCosts are ignored somewhere internally?)

[oblonski]

You need to redefine the objective function. It is a min-max problem where you want to reduce the overall makespan by employing all your available resources. Unfortunately, this is not open source yet. What you can try is to implement a two step approach. In the first step, you would try to reduce the operation time of your drivers so that you can just serve all your jobs. Given the max operation time of the drivers, you would redefine your problem incorporating this max time. Then you would minimize transport costs.

[matthewrudy]

Thanks @oblonski we managed to hack it by doing the following

we add a massive negative fixed cost for each vehicle
(we had to fork the repo to allow this)

val vehicleType = VehicleTypeImpl.Builder.newInstance("vehicle")
  .setFixedCost(-1000000.0) //Workaround to force using all vehicles
  .setMaxVelocity(13.0) //~ 50km/h
  .build()

Then we make sure it uses the fixed cost

val algorithm = Jsprit.Builder.newInstance(problem)
  .setProperty(Jsprit.Parameter.FAST_REGRET, "true")
  .setProperty(Jsprit.Parameter.THREADS, "5")
  .setProperty(Jsprit.Parameter.FIXED_COST_PARAM, "1.") //Increase weight of the fixed cost to enable the force all vehicle workaround
  .buildAlgorithm()

[roganjoshp]

Hi @matthewrudy I am interested in this feature. I have made the changes you have suggested and removed the error. However, with 4 available vehicles and 23 jobs, it's only assigning two drivers. All vehicles start in the same location and could all carry the items. The route cost is correctly reflecting the disproportionate negative cost. Does this implementation really work for you consistently or is there something else going on to keep vehicle numbers down?

[roganjoshp]

Actually, it seems the setup of the algorithm is important. By ensuring there is regret in the Strategy, it will then use all of the vehicles as you suggested. It is hacky though and it shows; the extra two vehicles are simply grabbing one item each (closest to the warehouse) after which they become an unnecessary additional cost. I can't think of a reasonable way to define the problem to make them behave more naturally without fundamental changes to the objective function.

I suppose this could be because the warehouse in this case is not located centrally in the service catchment area, they're all heading in the same direction initially. Perhaps if you have something more evenly distributed then you get better solutions.

[matthewrudy]

@mcrnotts it will depend on how the algorithm generates new solutions, yes.

Our business requirement is give the customer the exact number of vehicles they request
even if it would be more efficient and cheaper not to.

But... that's business requirements for you
:)

[PGWelch]

It may be more reliable to actually modify the insertion and ruin heuristics a bit. Assuming you want n vehicles, for the initial solution construction, randomly choose n jobs, assigning one per vehicle and then apply cheapest or regret based construction to assign all other jobs and finish building the first solution. For subsequent ruin-and-recreate iterations, use a modified ruin which leaves at least a single job in place on each route (where the job is randomly chosen each time).

This kind of strategy would force the algorithm to always use n vehicles, but still allow it to optimise them.

[atmikev]

Was this functionality ever added into the master branch?

[lfreneda]

Same question: Was this functionality ever added into the master branch?

[nkaragiannis]

It may be more reliable to actually modify the insertion and ruin heuristics a bit. Assuming you want n vehicles, for the initial solution construction, randomly choose n jobs, assigning one per vehicle and then apply cheapest or regret based construction to assign all other jobs and finish building the first solution. For subsequent ruin-and-recreate iterations, use a modified ruin which leaves at least a single job in place on each route (where the job is randomly chosen each time).

This kind of strategy would force the algorithm to always use n vehicles, but still allow it to optimise them.

Hi! Can you please help me to code the above strategy?

Thanks