Vehicle Routing Problem - Use All Vehicles

[Robert Robbins]

I've played around with the original Python sample code for a Vehicle Routing Problem which finds routes for 4 vehicles. However, if you specify 6 vehicles it still only finds 4 routes for four vehicles. In other words, it only finds as many routes as are needed and leaves some vehicles not utilized.

I would like to add a constraint that all vehicles must be used. Does this make sense? Can that be done?

[blind.line]

I recall a number of approaches discussed on this mailing list, many looking at how to achieve some optimal balance of work between vehicles, all else being equal. 

If you just want a fairly easy to implement solution, just limit the max pickups (aka node visits) of each vehicle be about equal to the Ave number of nodes per vehicle, rounding up. So with 6 vehicles, 10 nodes to visit, constraint is max 2 nodes per veh. 

To do this, set up a dimension that counts nodes, incrementing by one with each visit.  Hopefully that makes sense. 

This approach should get all the vehicles in the game, but it certainly won’t balance length of routes or anything like that. 

James

On Mar 26, 2019, at 16:37, Robert Robbins <robbi...@gmail.com> wrote:

I've played around with the original Python sample code for a Vehicle Routing Problem which finds routes for 4 vehicles. However, if you specify 6 vehicles it still only finds 4 routes for four vehicles. In other words, it only finds as many routes as are needed and leaves some vehicles not utilized.

I would like to add a constraint that all vehicles must be used. Does this make sense? Can that be done?

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[in...@bobvoorneveld.nl]

James, we're looking at the same problem.

Another solution we're trying to implement is to make de difference between total travel time (or distance, based on needs) of every vehicle as small as possible.

But we still don't know how to implement that path and how that interferes with SetArcCostEvaluatorOfAllVehicles.

Any suggestions?

[blind.lin...@gmail.com]

That is a difficult one, and hopefully someone else will share how
they've solved it.

For me, my approach is to accept that the solution won't be optimal,
and then to implement a hack that gets me close enough. For the one
real-world problem for which I needed to address this sort of problem,
the pickup and delivery points were scattered fairly uniformly, so it
was good enough to keep the number of passengers served roughly equal
(limit the total number of pickup nodes visited). The other leavening
factor in my application was that the client was okay with having some
vehicles with excess capacity, as they could be used to handle new
requests and broken schedules due to passenger no-shows.

I'm also using python.

I think if I needed to *really* tackle this sort of problem, trying to
make all vehicles have roughly the same distance or time spent
traveling, I would stop being lazy and learn C++ again, so that you
can use the method "add dimension with dependent dimension". With
that kind of a dimension, it might be possible to increase the cost of
adding more distance to a vehicle exponentially (guessing---maybe a
power law would work?), such that the solver would find a cheaper
solution by spreading the distance traveled around. In other words,
make the cost of adding additional distance to a vehicle *worse* that
assigning a slightly longer total trip length to two or more vehicles.

Without turning to C++, it might be possible to do a two-stage
solution? Run one solver process, get an "optimal" result and a
total distance value for the solution, compute the ideal ave distance
per vehicle using this value, then re-run the solver but this
time with a constraint that vehicles can't exceed the ideal distance
per vehicle, plus say 2% to allow for the fact that the new solution
will likely be a little bit longer.

Actually, looking at V7.0, it *might* be the case that this function
is now exposed to Python? I don't see any IF DEF guards around
https://github.com/google/or-tools/blob/v7.0/ortools/constraint_solver/routing.h#L459
That would be super cool if true.

Ah, hopes dashed: https://github.com/google/or-tools/blob/v7.0/ortools/constraint_solver/python/routing.i#L71
I think. Although maybe not, as the %include routing.h comes after
the above line. (Obv. I need to relearn C++...)

Maybe someone else will chime in with an actual solution?

Regards,
James

> --
> You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

--

James E. Marca

[christoph...@ksb.com]

I'm using OR Tools to do other types of problems, but wouldn't changing the optimization goal to minimize the length of the longest route get what you want?