An adaptation of Eppsteins algorithm building, for a given directed graph, the K shortest circuitless paths having at most P arcs between a source node and a target node. Herv BRICARD Optimization Group - IT department 2007, January 26th, Bordeaux LABRI. Agenda The downstream logistics business problem The business problem modelled in Graph Theory An hybrid resolution method based on Bellmans Algorithm and a business heuristics State of the art and choice of an exact resolution method The chosen exact resolution method: an adaptation of Eppsteins Algorithm Results Conclusion and perspectives Questions & Answers P/2 The downstream logistics business (1)
Les routes: problem illustration Moskva Teesport Bremerhaven Kleszczow Port Grimsby Luton Neuss Zeebrugge Leipzig Krakow geo. zone Machelen
Mnchen Wien Bratislava Nebikon Budapest Assembly plant Distribution center Trieste Novo Mesto Vercelli Santander Pitesti Livorno Bologna Palencia
Barcelona Valladolid Madrid Setubal Sevilla Puerto de Tarragona Barcelona Porto Torres Salerno Bursa Gandia Malaga Cadiz Koper
Palermo P/3 The downstream logistics business problem (2) PROBLEM DESCRIPTION Each vehicle must be routed from its assembly plant to a final distribution center which depends on the geographical localization of the customer that ordered this vehicle. Our aim as far as possible! is to compute several itineraries from the assembly plant to the final distribution center. These possible itineraries will be the k shortest paths from the plant to the final center, computed with the delay metric and the cost metric. Thus, we will have at most 2k itineraries between a given couple (assembly plant, final distribution center). P/4 The downstream logistics business problem (3) SOME VOCABULARY An itinerary between an assembly plant and a final distribution
center will be called a route . A route is composed of sections. A section is a triplet (Departure center, Arrival center, Transportation mode) There are four possible transportation modes for a section in our worldwide distribution network: boat, barge, train, and truck. A cost and and a delay are attached to each transportation section. Similarly, each center of our network has a transit cost and a transit delay. P/5 The downstream logistics business problem (4) PROBLEM SIZE AND CONSTRAINTS Our transportation network consists of: - a few assembly plants - hundreds of transit and final centers - thousands of transportation sections (Currently 1500, 3000 in 2009) We wish to compute, for each possible couple (Assembly plant, Final distribution center), under the constraints described below, the 5 quickest and the 5 cheapest routes. Thus, after the computation there will be at most 10 routes for each couple (Assembly plant, Final distribution center). C1: The computed routes must be circuitless.
C2: The computed routes must not have more than 6 transportation sections. P/6 Agenda The downstream logistics business problem The business problem modelled in Graph Theory An hybrid resolution method based on Bellmans Algorithm and a business heuristics State of the art and choice of an exact resolution method The chosen exact resolution method: an adaptation of Eppsteins Algorithm Results Conclusion and perspectives Questions & Answers P/7 The business problem modelled in Graph Theory (1) TRANSPORTATION NETWORK STRUCTURE Our transportation network might be seen as a directed graph. Its nodes stand for the centers , whereas its arcs stand for the transportation sections. The routes evoked earlier will also be referred to as paths , since this terminology is more common in Graph Theory. Each arc of this graph is valuated by two metrics: the delay and the cost. The nodes are not valuated.
In the business problem, however, the transportation sections AND the centers have a cost and a delay. We simply add, for a given metric, the valuation of a center to the valuations of its outgoing transportation sections; and thus, the aim is achieved: only the arcs of the graph will be valuated. Moreover, this graph does have circuits, and is a multi-graph, i.e. there can be several arcs connecting a node A to a node B. P/8 The business problem modelled in Graph Theory (2) THE MULTI-GRAPH FEATURE Krakow geographical zone Bremerhaven Kleszczow by train and Bremerhaven Kleszczow by truck are equivalent arcs. P/9 The business problem modelled in Graph Theory (3) THE MATHEMATICAL PROBLEM For each possible couple (departure node, arrival node), we have to find the 5 circuitless quickest paths having at most 6 arcs. Similarly, we must
find also the 5 circuitless cheapest paths having at most 6 arcs. Thus, after performing these two steps, whe will have at most 10 paths for a couple. This problem belongs to the constrained K shortest paths family, the two constraints for a path being in the present case: - the limitation of its number of arcs - the circuitless requirement P / 10 Agenda The downstream logistics business problem The business problem modelled in Graph Theory An hybrid resolution method based on Bellmans Algorithm and a business heuristics State of the art and choice of an exact resolution method The chosen exact resolution method: an adaptation of Eppsteins Algorithm Results Conclusion and perspectives Questions & Answers P / 11 An hybrid resolution method based on Bellmans
algorithm and a business heuristics (1) THE CHOSEN APPROACHED METHOD For a possible couple (departure node, arrival node), we first compute the 2 circuitless quickest paths having at most p arcs, using Bellmans algorithm several times. Then additional paths are built taking these two quickest paths as a basis, replacing each arc of these two paths by an equivalent (*) arc, whenever it is possible. (Two arcs are equivalent if they connect the same nodes) This is the core of the business heuristics. The final step is to sort by increasing delay the obtained paths, retaining only the 5 first ones. By the way, it is perfectly possible that we will have less than 5 paths at the end. The three steps above have to be performed for the cost metric as well. P / 12 An hybrid resolution method based on Bellmans algorithm and a business heuristics (2) SOME WORDS ON BELLMANS ALGORITHM This algorithm computes the shortest paths between all the nodes of the directed graph and a given target node. It is based on Dynamic Programming. Its main advantage for the present problem is its ability to compute
the shortest path having at most P arcs even more quickly than the unconstrained shortest path. Its complexity, for a directed graph with n nodes and m arcs, is: O(n m). P / 13 Agenda The downstream logistics business problem The business problem modelled in Graph Theory An hybrid resolution method based on Bellmans Algorithm and a business heuristics State of the art and choice of an exact resolution method The chosen exact resolution method: an adaptation of Eppsteins Algorithm Results Conclusion and perspectives Questions & Answers P / 14 State of the art and choice of an exact resolution method (1) THE ELEMENTARY PROBLEM The business problem we have to solve was described earlier.
Until recently it has been solved using an hybrid approached method. In order to solve it exactly, we have to find an exact resolution method for the following elementary problem: Given a directed valuated multi-graph containing circuits that is not necessarily strongly connex, compute the K shortest circuitless paths having at most P arcs from a source node to a target node. P / 15 State of the art and choice of an exact resolution method (2) WHY DO WE NEED AN EXACT METHOD ? Question: Why do we not simply stick to the approached method that has been operational until now ? Answer: Not only out of desire to see Science make progress An exact method would improve our results in two ways: in fact, we suspect that the approached method, Bellman combined with an equivalent arcs -based business heuristics to build supplementary paths has two drawbacks: - some good paths are not found and we miss them. - since the supplementary paths are not necessarily optimal, some of them can be really bad .
This suspicion will prove to be right ! P / 16 State of the art and choice of an exact resolution method (3) SOME EXACT ALGORITHMS DEALING WITH K-SHORTEST PATHS PROBLEMS Reminder: we consider a directed graph with n nodes and m arcs. The following list is not exhaustive Three efficient deviation algorithms retained our attention: Eppsteins Algorithm (EA and LVEA): the K shortest paths Asymptotical complexity for the computation of the K shortest paths between a source node and a target node : O(m + n log(n) + K) Recursive Enumeration Algorithm (REA): the K shortest paths Asymptotical complexity for the computation of the K shortest paths between a source node and a target node : O(m + K n log(m / n)) Yens Algorithm: the K shortest circuitless paths Asymptotical complexity for the computation of the K shortest circuitless paths between a source node and a target node : O(K n (m + n log(n))
P / 17 State of the art and choice of an exact resolution method (4) CHOICE OF AN EXACT RESOLUTION METHOD FOR OUR PROBLEM The choice is to adapt Eppsteins Algorithm in its Lazy Version (LVEA). Thus we will have an efficient algorithm computing the K shortest paths having at most P arcs between a source node and a target node. A post-filtering of these shortest paths will yield the circuitless paths among them. Note: the adaptation is designed in such a way it builds very few paths with circuits; but there are some, hence we have to filter the results of the adaptation of Eppsteins Algorithm to retain the circuitless paths. P / 18 State of the art and choice of an exact resolution method (5) SIMPLE VARIATION OF THE CHOSEN EXACT RESOLUTION METHOD THAT DOES NOT WORK Question: we could perform a double-filtering of the results of Eppsteins Algorithm (LVEA), to retain only the shortest paths having at most P arcs that are circuitless.
Why not ? Answer: we did try. Eppsteins Algorithm (LVEA), in this case, performs far too many useless iterations (= iterations yielding paths whose number of arcs are strictly greater then P and/or paths containing circuits): the computation time is simply unbearable. Taking a look at the graph below, one can get convinced that this behavior is normal. As an example, we will show that in the graph represented below, the first shortest paths will definitely contain a circuit. 12 days Source node 1 13 days 6 2 days 1 day 1 day
2 5 10 days 15 days 3 1 day 4 18 days Target node P / 19 State of the art and choice of an exact resolution method (6) ILLUSTRATION OF K-SHORTEST PATHS WITH CIRCUITS
12 days Source node 1 13 days 6 2 days 2 1 day 5 10 days 1 day 12 days Source
node 1 2 days 1 day 1 day 1 day 3 4 18 days Target node The shortest path 13 days
6 15 days 2 5 10 days 15 days 3 1 day 4 18 days Target node 2nd to 4th shortest paths
The 2nd shortest path has one circuit involving the 1 and 2 nodes, the 3th two circuits, and the 4th three circuits ! P / 20 Agenda The downstream logistics business problem The business problem modelled in Graph Theory An hybrid resolution method based on Bellmans Algorithm and a business heuristics State of the art and choice of an exact resolution method The chosen exact resolution method: an adaptation of Eppsteins Algorithm Results Conclusion and perspectives Questions & Answers P / 21 The exact resolution method: an adaptation of Eppsteins Algorithm (1) EPPSTEINS ALGORITHM IN A NUTSHELL: ILLUSTRATION OF THE DEVIATION ARC (also called SIDETRACK) FUNDAMENTAL CONCEPT a
Given a destination node t, we define the delta function for each arc a of the graph in the following way: delta(a) = l(a) + d(head(a), t) d(tail(a), t) l() yields the arc length, d() the minimal distance between two nodes, head() the head node of the (directed) arc and tail() its tail node. Intuitively, delta(a) is a measure of the additional cost we have to pay if, instead of taking the shortest path from tail(a) to t, we are first sidetracked along the a arc and then follow the shortest path from head(a) to t. If delta(a) > 0, a is a deviation arc. On the figure above, P / 22 delta(a) = 6. The exact resolution method: an adaptation of Eppsteins Algorithm (2) EPPSTEINS ALGORITHM IN A NUTSHELL: PRESENTATION This algorithm computes the k shortest paths between a source node s and a target node t. It needs to know the shortest path connecting the nodes of each couple (source node, target node). These shortest paths can be computed and saved once and for all by the Floyd-Warshall Algorithm, whose complexity is O(n3). Its main component is a priority queue. Each element of this priority queue is a succession of deviation arcs. We also will call such
an element a succession of sidetracks. P / 23 The exact resolution method: an adaptation of Eppsteins Algorithm (3) EPPSTEINS ALGORITHM IN A NUTSHELL: INITIALIZATION Second shortest path Shortest path A a Upon initialization, the priority queue contains only one succession of deviation arcs. And this succession contains only one deviation arc A which tails on the shortest path from s to t (shown in blue). This deviation arc is the smallest sidetrack - .i.e. the deviation arc for which delta() is minimal - among the sidetracks which tail on the shortest path from s to t. By the way, from this very sidetrack we can build the second shortest path (shown in red) from s to t: it goes from s to tail(A), then we have the arc A, and finally the shortest path from head(A) to t. P / 24
The exact resolution method: an adaptation of Eppsteins Algorithm (4) EPPSTEINS ALGORITHM IN A NUTSHELL: K-TH ITERATION The k-th iteration of Eppsteins Algorithm, which yields the k-th shortest path, consists of three steps: - 1) the extraction from Eppsteins Priority Queue of the succession of sidetracks that has the lowest priority. Lets name S this succession. Let prefix(S) be S amputed from its last arc. - 2) the building of the k-th shortest path, by linking up the Source Node to the Target Node using the sidetracks of this very succession S. - 3) the building of several new successions of sidetracks, one built by adding an arc to S, the others built by adding an arc to prefix(S). And finally, these successions of sidetracks are inserted in Eppsteins Priority Queue. An illustrative schema of this process follows ! P / 25 The exact resolution method: an adaptation of Eppsteins Algorithm (5) EPPSTEINS ALGORITHM : ILLUSTRATION
6 10 days Source Node 1 3 days 1 day 1 day 2 7 1 day 5 1 day 5 days 3 35 days
1 day 3 days 4 Target Node 1st shortest path Eppsteins shortest path number 1: (3 arcs) ==> ARC Arc__N1_N2__1 (1) ARC Arc__N2_N7__1 (1) ARC Arc__N7_N4__3 (3) Succession of sidetracks number 2: ARC Arc__N7_N5__3 (3) Eppsteins shortest path number 2: (5 arcs) ==> ARC Arc__N1_N2__1 (1) ARC Arc__N2_N7__1 (1) ARC Arc__N7_N5__3 (3) ARC Arc__N7_N3__1 (1) ARC Arc__N3_N4__1 (1)
Succession of sidetracks number 3: ARC Arc__N7_N5__3 (3) ARC Arc__N5_N4__5 (5) Eppsteins shortest path number 3: (4 arcs) ==> ARC Arc__N1_N2__1 (1) ARC Arc__N2_N7__1 (1) ARC Arc__N7_N5__3 (3) ARC Arc__N5_N4__5 (5) 5th succession of sidetracks 5th shortest path Succession of sidetracks number 4: ARC Arc__N1_N6__10 (10) Eppsteins shortest path number 4: (4 arcs) ==> ARC Arc__N1_N6__10 (10) ARC Arc__N6_N2__2 (2) ARC Arc__N2_N7__1 (1) ARC Arc__N7_N4__3 (3) Succession of sidetracks number 5: ARC Arc__N1_N6__10 (10) ARC Arc__N7_N5__3 (3) Eppsteins shortest path number5: (6 arcs) ==> ARC Arc__N1_N6__10 (10)
ARC Arc__N6_N2__2 (2) ARC Arc__N2_N7__1 (1) ARC Arc__N7_N5__3 (3) ARC Arc__N7_N3__1 (1) ARC Arc__N3_N4__1 (1) P / 26 The exact resolution method: an adaptation of Eppsteins Algorithm (6) OUR ADAPTATION: LIMITING EPPSTEINS ALGORITHM TO PATHS HAVING AT MOST P ARCS (General idea) The adaptation for computing paths having at most P arcs consists in modifying the third step of Eppsteins k-th iteration. The idea is to prevent Eppsteins Algorithm to insert in its Priority Queue a succession of sidetracks with the following properties: a) It will yield a too long and/or not circuitless path when building the shortest paths from them by the linking process illustrated earlier. b) All the children sidetracks built from it will have the same problem. Thus, the Priority Queue, when running Eppsteins Adapted Algorithm, will continuously have considerably less elements than it would have should we run the genuine algorithm.
P / 27 The exact resolution method: an adaptation of Eppsteins Algorithm (7) OUR ADAPTATION: LIMITING EPPSTEINS ALGORITHM TO PATHS HAVING AT MOST P ARCS (part 1: the aim is to avoid too long shortest paths) Note: lets still call S the succession of sidetracks that has the lowest priority, extracted in the first step of the k-th iteration of Eppsteins Algorithm. The first part of the adaptation is to insert a new built succession of sidetracks named S in the Priority Queue only if a necessary condition is satisfied. There are two cases: If S was obtained by adding an arc to S, the condition that must be satisfied is: it is possible to build using all the arcs of S a path having at most P-1 arcs starting from the Source Node to the head of the last arc of S ! If S was obtained by adding an arc to prefix(S), the condition that must be satisfied is: it is possible to build using all the arcs of prefix(S) a path having at most P-1 arcs starting from the Source Node s to the head of the last arc of prefix(S) ! P / 28
The exact resolution method: an adaptation of Eppsteins Algorithm (8) OUR ADAPTATION: LIMITING EPPSTEINS ALGORITHM TO CIRCUITLESS PATHS HAVING AT MOST P ARCS (part 2: the aim is still to avoid too long shortest paths) Note: lets still call S the succession of sidetracks that has the lowest priority, extracted in the first step of the k-th iteration of Eppsteins Algorithm. The second part of the adaptation is to insert a new built succession of sidetracks named S in the Priority Queue if an additional necessary condition is satisfied, regardless of how was obtained S. The necessary condition that must be satisfied to accept the insertion of S in Eppsteins Priority Queue is the following: If S has at least 2 arcs, let nbArcsMin1 be the minimum number of arcs between the source node s and the first arc of S. Likewise, let nbArcsMin2 be the minimum number of arcs between the last but one arc of S and the target node t. Then we must have: nbArcsMin1 + nbArcsMin2 + NbSidetracks(S) <= P ! P / 29
The exact resolution method: an adaptation of Eppsteins Algorithm (9) OUR ADAPTATION: LIMITING EPPSTEINS ALGORITHM TO CIRCUITLESS PATHS HAVING AT MOST P ARCS (part 3: the aim is to avoid some circuits) Note: lets still call S the succession of sidetracks that has the lowest priority, extracted in the first step of the k-th iteration of Eppsteins Algorithm. The second part of the adaptation is to insert a new built succession of sidetracks named S in the Priority Queue if an additional necessary condition is satisfied, regardless of how was obtained S. The condition that must be satisfied to avoid S AND its children succession of sidetracks yielding surely a path with circuit, is: If S has at least 3 arcs, S amputed of its last arc must not provoke surely a circuit when bulding a path because of its sidetracks. A trivial case: S amputed ot ils last arc does contain a circuit! But there are more subtle cases that are possible to test. P / 30 The exact resolution method: an adaptation of Eppsteins Algorithm (10)
OUR ADAPTATION: LIMITING EPPSTEINS ALGORITHM TO CIRCUITLESS PATHS HAVING AT MOST P ARCS (part 4: common sense) It is always useful, if possible, to have the smallest possible graph when performing an Adapted Eppstein constrained shortest paths computation between a source node and a target node. We can note that it is possible before such a computation to temporarily delete from the graph: - ingoing arcs to the source node - outgoing arcs from the target node We will obtain the same results, but using a reduced graph: this common sense observation was very useful to speed up significantly ourAdapted Eppstein Algorithm. There are some other common sense observations we did use, which we will not explain here, and did help us. P / 31 The exact resolution method: an adaptation of Eppsteins Algorithm (11) OUR ADAPTATION: LIMITING EPPSTEINS ALGORITHM TO PATHS HAVING AT MOST P ARCS (Which tool do we need ?) Question: in our adaptation, we always badly need, in order to decide whether the just mentioned conditions related to it can be
satisfied, to know the minimal number of arcs necessary to connect a node A to another node B. It is not imaginable to compute this sort of information each time it is needed whilst Eppsteins Adapted Algorithm is running. What can be done to make constantly available to the algorithm such an information ? Answer: it is necessary to compute the minimal number of arcs connecting the node A to the node B, for all possibles (A,B) couples, once and for all. This can be achieved using the Floyd algorithm, taking the number or arcs as the metric. This computation costs O(n3), n being as usual the number of nodes of the graph. P / 32 The exact resolution method: an adaptation of Eppsteins Algorithm (12) OUR ADAPTATION OF EPPSTEINS ALGORITHM: ILLUSTRATION 6 10 days Source Node 1
3 days 1 day 1 day 2 7 1 day The first constrained shortest path Eppsteins shortest path number 1: (3 arcs) ==> ARC Arc__N1_N2__1 (1) ARC Arc__N2_N7__1 (1) ARC Arc__N7_N4__3 (3) 5 1 day 5 days 3
3 (Here P= , and K=5) 35 days 1 day 3 days 4 Target Node The second constrained shortest path Succession of sidetracks number 2: ARC Arc__N1_N6__10 (10) ARC Arc__N6_N4__35 (35) Eppsteins shortest path number 2: (2 arcs) ==> ARC Arc__N1_N6__10 (10) ARC Arc__N6_N4__35 (35)
Succession of sidetracks number 2: ARC Arc__N7_N5__3 (3) Succession of sidetracks number 2: ARC Arc__N1_N6__10 (10) Succession of sidetracks number 2: ARC Arc__N1_N6__10 (10) ARC Arc__N7_N5__3 (3) It is remarkable that the succession of sidetracks : Succession of sidetracks number 3: ARC Arc__N7_N5__3 (3) ARC Arc__N5_N4__5 (5) does not appear any more. P / 33 Agenda The downstream logistics business problem The business problem modelled in Graph Theory An hybrid resolution method based on Bellmans algorithm and a business heuristics
State of the art and choice of an exact resolution method The chosen exact resolution method: an adaptation of Eppsteins algorithm Results Conclusion and perspectives Questions & Answers P / 34 Results (1) PROBLEM DATA: The transportation graph has hundreds of nodes, thousands of arcs, and currently 5666 couples (Departure node, Arrival node). 5 circuitless routes having at most 6 arcs were computed for each couple for the delay metric. The same computations were performed for the cost metric. Computer and compiler: AMD64 3400+. VC++ 8 in optimized mode; with sufficient RAM. MAIN RESULTS: Bellmans Algorithm & Business heuristics (computation of 2 paths and building upon these 2 paths up to 3 supplementary paths using equivalent arcs): 25706 distinct routes were found (15133 for the delay metric, 13964 for the cost metric) Computation time: 52 seconds. Eppsteins Adapted Algorithm : 48826 distinct routes were found (26928 routes found for each metric)
Computation time: 145 seconds. Note: an exact method must yield the same number of routes for each metric ! LESSONS LEARNT FROM THE MAIN RESULTS: The exact method yields 28646 good additional routes: HUGE BUSINESS IMPACT! 5526 routes found by the heuristic method are of POOR QUALITY, since they are not even found by the exact method. P / 35 Results (2) SECONDARY RESULTS: There is a couple (Departure node, Arrival node) for which the inner number of iterations of Eppsteins adapted algorithm reaches 128874. This 128874 is the value of K in Eppsteins Algorithm asymptotical complexity: O(m + n log(n) + K). INTERESTING REMARK: If we compute for the cost and the delay metrics the 5 shortest paths for all our 5666 couples (Departure node, Arrival node) with the genuine i.e. circuits are allowed, and there is no at most 6 arcs constraint - Eppsteins Algorithm in its lazy version (LVEA), the computation time is only a few seconds. ADDITIONAL REMARKS: The genuine Eppsteins Algorithm (LVEA) is extremely fast, in practice.
When K is high for a couple (Departure node, Arrival Node), it is usually that the real (= not limited with at most P arcs) shortest path has more than P arcs P / 36 Agenda The downstream logistics business problem The business problem modelled in Graph Theory An hybrid resolution method based on Bellmans algorithm and a business heuristics State of the art and choice of an exact resolution method The chosen exact resolution method: an adaptation of Eppsteins algorithm Results Conclusion and perspectives Questions & Answers P / 37 Conclusion and perspectives (1) CONCLUSION The results of the Eppsteins adapted Algorithm were shown to Renaults Logistics Department recently. The decision was that it will go live by May 2007.
PERSPECTIVES As an alternative to the Eppstein-based resolution method, we could also test in the future Yens algorithm with a post-filtering of its routes to keep only the ones having at most P arcs; and see whether it outperforms the present resolution method or not. It is less interesting now in January 2007 (It was not the case in February 2006) , since we improved we hope to its maximum the Adaptation of Eppsteins Algorithm to a point that is satisfactory. So, further research on this topic would be Pour la Science only P / 38 Conclusion and perspectives (2) BIBLIOGRAPHY [1] "Eppstein D.: Finding the k Shortest Paths. " IEEE Symposium on Foundations of Computer Science 1997. [2] "M. Jimnez, Andrs Marzal: A lazy version of Eppsteins K shortest paths algorithm. " Second international workshop, WEA 2003, Ascona, Switzerland, May 26-28, 2003. Proceedings. [3] "P.Lacomme, C.Prins, M.Sevaux: Algorithmes de graphes. " Eyrolles 2003.
P / 39 Agenda The downstream logistics business problem The business problem modelled in Graph Theory An hybrid resolution method based on Bellmans algorithm and a business heuristics State of the art and choice of an exact resolution method The chosen exact resolution method: an adaptation of Eppsteins algorithm Results Conclusion and perspectives Questions & Answers P / 40 Questions & Answers Thank you for your attention. Any question ? Email: [email protected] P / 41