[GraphHopper] Routing with multi depots and depot priority

[me at pgwelch.info]

Hi Alain, 

For the second problem, it may also be worthwhile you looking at the
routing library part of Google's OR tools
http://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/tsp/routing_library.html
[3] 

Just to confirm my understanding - you want to plan the order of depots
and customers on courier routes, such that travel time or distance is
minimised, whilst goods are always picked up before being delivered. Is
this correct? 

Do you always know which route a specific item will go onto? If so your
problem is some variant of the travelling salesman problem. If not (you
want the algorithm to assign goods to routes as well as order on the
route), then you have a variant of the vehicle routing problem. 

Are all depots visited on the route before any goods are delivered? Or
is it possible to (for example) pickup goods A and B from a depot,
deliver B, pickup goods C from another depot? If all pickups happen
before any delivery your problem will probably be some variant of the
vehicle routing problem with backhauls, if not it will be a variant of
pickup and delivery vehicle routing problem. 

Also what, roughly speaking, is the size of your problem? (the total
number of depots and customers you want the algorithm to assign together
in one go) Smaller problems are *much easier* to solve. 

>> One algorythm problem is there are several depot whith priority for the depot versus the customers who need good from such depot. 

I didn't really understand this bit, can you elaborate? Do you always
know which depot the goods for a customer should be picked up from or do
you want the algorithm to decide this? 

best regards 

Phil 

On 24.08.2013 21:53, Peter K wrote: 

> Hi Alain,
> 
> there are two different problems within those vehicle routing problems. The first one is to find out all necessary distances between depots and customers. And the second is to optimize the overall route taking all requirements and restrictions/priorities into account.
> 
> The first problem is called "many to many shortest path calculation" can be solved from graphhopper (although there are optimizations possible).
> 
> For the second I suggest to look into tools like optaplanner which uses (meta)heuristics:
> http://java.dzone.com/articles/false-assumptions-vehicle [2]
> 
> I think on the mailing list are people with more knowledge in this logistic area which could probably be of a better help :)
> 
> Kind Regards,
> Peter.
> 
>> Hi,
>> 
>> I've been consulted for a project involving some couriers (one in a first time) to make delivery to customers but with also several pick up on the route because the goods are provided by several depots to the courier. We have a databse with the different depots and the app will choose the depot the closest to the customer concerned.
>> I'm a total newbie with such spatial and routing problems....
>> 
>> We would like to receive a list of customers address from a separate web app, feed an server app with this list of address and then process it to get the coordinate from OSM and then propose a route to the courier. 
>> One algorythm problem is there are several depot whith priority for the depot versus the customers who need good from such depot. The courier can't deliver goods that he did'nt yet get.
>> Is there somebody who can give me some clue to process with this precedence of passing to some depot to serve some customers. 
>> 
>> Hoping my rough request are understandable,
>> Best regards
>> Alain 
>> 
>> _______________________________________________
>> GraphHopper mailing list
>> GraphHopper at openstreetmap.org
>> http://lists.openstreetmap.org/listinfo/graphhopper [1]
> 
> _______________________________________________
> GraphHopper mailing list
> GraphHopper at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/graphhopper [1]

 

Links:
------
[1] http://lists.openstreetmap.org/listinfo/graphhopper
[2] http://java.dzone.com/articles/false-assumptions-vehicle
[3]
http://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/tsp/routing_library.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20130825/87e4501c/attachment.html>