GraphHopper.com | Forum | GitHub | Maps | Blog

Minimum routes per route


#1

I’m being asked if there is a way to constraint routes from being to small. I’m trying to create a constraint that invalidates if a route has too few jobs. Since the routes grow on each iteration of constraints it leaves all my routes empty and jobs unassigned at the end.

As a business standard at my job, all jobs must be handled but the routes must not have only one job, otherwise is not profitable.

Any help with this is appreciated. Thanks in advance.


#2

I don’t think currently there is an easy way to impose a hard constraint on the minimum number of jobs (or activities) in a route.

On a side note, @stefan implemented a min-max vrp quite a while ago where the algo tried to evenly distribute the jobs among the routes to minimize the maximum route distance (or cost? I don’t quite remember, sorry).


#3

I’m not sure ho feasible it is but you can try following.

1: Do a constraint check before ruin step
2: Check if a route has enough number of nodes, if not do not ruin that route
3: If yes, set value of alpha so that number of nodes after ruin is greater than or equal to minimum number of nodes required.


#4

@jie31best that sounds about right, is there a link to such implementation or can I look for it in Github and the like? Thanks btw.

@Bhoumik_Shah, how can I specify when is a constraint run? In this case before the ruin step. Is is the same as the hard/soft route/activity constraints?


#5

Note that the implementation was quite a while back so I assume quite a bit of codes would be out of date. You could just focus on the state updater, the objective function and the soft constraint.


#6

Hi,

I would like to implement something similar and I was wondering if now there is a better or easier suggestion for doing so?

The constraint that I want to impose is that a route shouldn’t be acceptable if the total number of deliveries and pickups is less than a given value. The fleet that I want to use is finite and the acceptable solution would be less vehicles used but with enough deliveries and pickups.

I have thought the following which is different from your suggestions.

First, I have implemented SolutionCostCalculator which checks for the number of activities per route for the given solution and if the condition isn’t met then an extra cost is introduced. With that I try to achieve that solutions honoring the constraint will be picked.

Then, when the algorithm ends I check again if the found solutions honor the condition and if not I re-run the algorithm but I set the number of the vehicles to one less, until I find an acceptable solution.

However, I am not very satisfied from the above process and I was wondering if I should stop pursuing this and trying some other approach. What do you think?

Thanks in advance!

Update: I tried using a SolutionAcceptor instead of a SolutionCostCalculator and I find the results more satisfying. However, any suggestions or comments are more than welcome!


#7

It depends on your use case, but I’ve found two ways to approach this problem:

  1. Adding a fixed cost. This will cause the solver to attempt to use less vehicles. Even if the distance-optimal solution sends 1 package per vehicle, setting a high-enough fixed cost per vehicle will override this, and produce a solution with less vehicles serving multiple packages (while still optimizing the route for the lesser number of vehicles).

  2. Adding a fixed time cost. For my use case, I required that a vehicle, if used, would be “booked” for a certain amount of time. For example, a driver must be paid 5 hours of wage time regardless of how much time he is actually asked to work during his route (in some countries, laws produce this sort of weird constraint).

In the case of #2, I also had to add a “phantom cost” of distance. Remember that if you set these “medium” constraints/costs, you still have to differentiate between solutions. For example, in the case of #2, if I have 2 solutions both solving the issue in under 5 hours and thus producing the same cost, the solution that has a longer driving distance is penalized.