[GraphHopper] Routing with multi depots and depot priority

[Alain BUFERNE]

Yes you understand well
The goods can be available in any depot but we should in a first time, when
the customer send his order the web app in charge of thi decide which depot
will be used by taking the closest from the customer (it is not surely the
best if we consider the final route but it is the way the customer want to
go to ) and add the depot to the customer order. So at the routing time we
know for sure the adresses of the customers and the addresses of the depot
which will be used. Besides a depot can be used to pick up sevral goods fro
several customers.
At the end We want to minimize the distance (the problem is for cities so
shortest should be the fastest).


2013/8/25 <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
>
> 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
>
> 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 listGraphHopper at openstreetmap.orghttp://lists.openstreetmap.org/listinfo/graphhopper
>
>
>
> _______________________________________________
> GraphHopper mailing listGraphHopper at openstreetmap.orghttp://lists.openstreetmap.org/listinfo/graphhopper
>
>
>
>
> _______________________________________________
> GraphHopper mailing list
> GraphHopper at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/graphhopper
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20130825/00ec7bd8/attachment.html>