OAR Lib: An Open Source Arc Routing Library By Oliver Lum Advised By Professor Bruce Golden 1 Introduct ion Approach Validation Schedule Conclusio n Visit edges, minimize cost Ubiquitous: What is Arc Routing? Package Delivery Snow Plowing Military Patrols Various interesting wrinkles: Time-Windows Turn Penalties Asymmetric Costs

2 Introducti on Approach Validation Schedule Conclusion Provide research community with standard, efficient implementation for ease of comparison. Motivation Reduce start-up overhead for budding operations researchers. Begin personal research. Provide a set of Java based tools that can lay the groundwork for easy extensibility. 3 Introducti on Approach Validation

Schedule Conclusion Graphs Definitions Undirected: (V,E) Directed: (V,A) Mixed: (V,E,A) Windy: (V,E) Vertex Edge: (i, j) Degree Euler Tour Strongly Connected 4 Introducti on Approach Validation Schedule

Conclusion P vs. NP: Objective The major dividing line in computational tractability. Asymptotic complexity makes solving all interesting arc routing problems to optimality impossible, (working assumption that P ~= NP). Heuristics attempt to get close, in polynomial time. 5 Introductio n Approach Problems / Algorithms Validation Schedule

Conclusion Problem Classical Modern Undirected Chinese Postman Problem Edmonds N/A Directed Chinese Postman Problem Thimbleby N/A Mixed Chinese Postman Problem Frederickson Yaoyuenyeung Windy Chinese Postman Problem Win

Benavent Directed Rural Postman Problem Christofides Benavent 6 Introductio n Approach The Undirected Chinese Postman Validation Schedule Conclusion Requirement: Visit every edge in the graph, and return to the starting node (closed). Graph: (Connected) Only Edges

7 Introductio n Approach The Undirected Chinese Postman: Algorithms Validation Schedule Conclusion Euler Tour Theorem: A connected, undirected graph has a tour visiting each edge exactly once iff every node has even degree. Idea Step I: Identify nodes with odd-degree. Step II: Optimally connect them so that they now have even degree, yielding an augmented graph.

Step III : Construct the Euler tour on this augmented graph. 8 Introductio n Approach The Undirected Chinese Postman Validation Schedule Conclusion Cost function: C Edge set: E Vertex set: V te : represents number of additional times we traverse edge e. : set of edges incident on v.

9 Introductio n Approach The Undirected Chinese Postman: Algorithms Validation Schedule Conclusion Euler Tour Theorem: A connected, undirected graph has a tour visiting each edge exactly once iff every node has even degree. Idea Step I: Identify nodes with odd-degree. Step II: Optimally connect them so that they now have even degree, yielding an augmented graph. Step III : Construct the

Euler tour on this augmented graph. 10 Introductio n Approach The Undirected Chinese Postman: Algorithms Validation Schedule Conclusion Euler Tour Theorem: A connected, undirected graph has a tour visiting each edge exactly once iff every node has even degree. Idea Step I: Identify nodes with odd-degree. Step II: Optimally connect them so that they now have even

degree, yielding an augmented graph. Step III : Construct the Euler tour on this augmented graph. 11 Introductio n Approach The Undirected Chinese Postman: Algorithms Validation Schedule Conclusion Euler Tour Theorem: A connected, undirected graph has a tour visiting each edge exactly once iff every node has even degree. Idea Step I: Identify nodes with odd-degree.

Step II: Optimally connect them so that they now have even degree, yielding an augmented graph. Step III : Construct the Euler tour on this augmented graph. 12 Introductio n Approach Validation Schedule Conclusion Step II: The Undirected Chinese Postman: Algorithms In order to connect the odd nodes in a least-cost way, we may use any

matching algorithm. Step III: Once we have an Eulerian graph, we may construct an Euler tour by using Fleurys algorithm. 13 Introductio n Approach The Directed Chinese Postman Validation Schedule Conclusion Requirement: Visit every edge in the graph, returning to the starting node (closed). Graph: (Strongly Connected) Only Arcs

14 Introductio n Approach The Directed Chinese Postman: Algorithms Validation Schedule Conclusion Euler Tour Theorem: A strongly connected, directed graph has a tour visiting each edge exactly once iff every node has in-degree = out-degree. Idea Step I: Identify nodes with a degree imbalance. Step II: Optimally add paths between them until theyre all balanced.

Step III : Construct the Euler tour on this augmented graph. 15 Introductio n Approach Validation Schedule Conclusion The Directed Chinese Postman Cost function: C fij : represents number of additional times we traverse the shortest path from i to j. outdegree indegree of vertex v. : set of vertices with excess outgoing arcs. : set of vertices with excess incoming arcs. 16 Introductio n Approach

The Directed Chinese Postman: Algorithms Validation Schedule Conclusion Euler Tour Theorem: A strongly connected, directed graph has a tour visiting each edge exactly once iff every node has in-degree = out-degree. Idea Step I: Identify nodes with a degree imbalance. Step II: Optimally add paths between them until theyre all balanced. Step III : Construct the Euler tour on this augmented graph. 17 Introductio

n Approach The Directed Chinese Postman: Algorithms Validation Schedule Conclusion Euler Tour Theorem: A strongly connected, directed graph has a tour visiting each edge exactly once iff every node has in-degree = out-degree. Idea Step I: Identify nodes with a degree imbalance. Step II: Optimally add paths between them until theyre all balanced. Step III: Construct the Euler tour on this augmented graph.

18 Introductio n Approach The Directed Chinese Postman: Algorithms Validation Schedule Conclusion Euler Tour Theorem: A strongly connected, directed graph has a tour visiting each edge exactly once iff every node has in-degree = out-degree. Idea Step I: Identify nodes with a degree imbalance. Step II: Optimally add paths between them until theyre all

balanced. Step III : Construct the Euler tour on this augmented graph. 19 Introductio n Approach The Mixed Chinese Postman Validation Schedule Conclusion Requirement: Visit every edge in the graph, and return to the starting node. Graph: Mix of Edges and Arcs 20 Introductio n

Approach The Mixed Chinese Postman: Algorithms Validation Schedule Conclusion Euler Tour Theorem: A strongly connected, mixed graph has a tour visiting each edge exactly once if every node has in-degree = out-degree, and is of even degree. Phase I: Even Degree Phase II: In-Out-Degree Phase III: Even Parity 21 Introductio n Approach Validation

Schedule Conclusion The Mixed Chinese Postman Cost function: C xs : represents number of times we traverse link s. arcs / directed edges going out of v. 1 if we orient edge e from i to j, 0 oth. : the number of additional times we traverse link s. 22 Introductio n Approach Validation Schedule Conclusion Phase I: Even Degree The Mixed Chinese Postman: Algorithms Solve the UCPP on the mixed graph, ignoring

arc direction. Then, add arcs and edges corresponding to the paths from the matching. Phase II: In-Out-Degree Phase III: Even Parity 23 Introductio n Approach Validation Schedule Conclusion Phase I: Even Degree Phase II: In-Out-Degree The Mixed Chinese Postman: Algorithms Solve the DCPP on the graph, where each edge is replaced by two arcs (one per

direction), keeping track of the flow solution to determine which direction the (original) edges get oriented, and if any other augmentations are needed. Phase III: Even Parity 24 Introductio n Approach Validation Schedule Conclusion Phase I: Even Degree Phase II: In-Out-Degree Phase III: Even Parity The Mixed Chinese Postman: Algorithms We search for cycles

that consist of alternating paths between odd-nodes. Alternating here means switching between paths that are composed of edges left undirected after Phase II, and paths that are composed of added arcs, (irrespective of direction). 25 Introductio n Approach Validation Schedule Conclusion Phase I: Even Degree The Mixed Chinese Postman: Algorithms

Phase II: In-Out-Degree Phase III: Even Parity Do the reverse procedure, (symmetry first, then evenness), and pick the better answer. 26 Introductio n Approach Validation Schedule Conclusion Use Results from Frederickson, along with two observations: The Mixed Chinese Postman: Algorithms II We should replace added arcs or directed edges with shortest

paths if theyre less costly. If we have an edge connecting nodes i and j, and we can construct two paths from i to j that incur savings, then we can simply reverse the orientation of this edge and add the paths. 27 Introductio n Approach Validation Schedule Conclusion Use Results from Frederickson, along with two observations: The Mixed Chinese Postman: Algorithms

II We should replace added arcs or directed edges with shortest paths if theyre less costly. If we have an edge connecting nodes i and j, and we can construct two paths from i to j that incur savings, then we can simply reverse the orientation of this edge and add the paths. 28 Introductio n Approach Validation Schedule Conclusion Use Results from Frederickson, along with two observations:

The Mixed Chinese Postman: Algorithms II We should replace added arcs or directed edges with shortest paths if theyre less costly. If we have an edge connecting nodes i and j, and we can construct two paths from i to j that incur savings, then we can simply reverse the orientation of this edge and add the paths. 29 Introductio n Approach The Windy Chinese Postman

Validation Schedule Conclusion Requirement: Visit every edge in the graph, and return to the starting node. Graph: (Connected), Edges only, but can possibly have asymmetric costs (and therefore simulate arcs). 30 Introductio n Approac h The Windy Chinese Postman: Algorithms Validatio n Schedule

Conclusio n Idea: if G is Eulerian, then there is a polynomial algorithm to determine a min-cost windy tour, so, lets make it Eulerian! 31 Introductio n Approac h The Windy Chinese Postman: Algorithms Validatio n Schedule Conclusio n Idea: if G is Eulerian, then there is a

polynomial algorithm to determine a min-cost windy tour, so, lets make it Eulerian! Solve the UCPP using average edge costs. 32 Introductio n Approach Validation Schedule Conclusion The Windy Chinese Postman Cost function: C : represents number of times we traverse edge e from i to j. arcs / directed edges going into v. 33 Introductio n Approac

h The Windy Chinese Postman: Algorithms Validatio n Schedule Conclusio n Idea: if G is Eulerian, then there is a polynomial algorithm to determine a min-cost windy tour, so, lets make it Eulerian! Solve the UCPP using average edge costs. Construct the optimal tour over the resulting graph (involves solving a min-cost flow over a digraph where each there is are three arcs per edge, one of them being of average cost). 34

Introductio n Approac h The Windy Chinese Postman: Algorithms II Validatio n Average costs arent everything, lets try giving precedence to edges where the cost asymmetry is highest, (more than 20% of the total average cost). Direct edges like this in the direction of lowest cost. Solve a min-cost flow problem where demands are determined only by these high stakes edges. Edges in the solution are given zero cost when solving the

UCPP. Schedule Conclusio n Use some of the local improvement procedures weve already seen: Replace non-required paths with shortest paths. Get rid of redundant cycles. 35 Introductio n Approach The Directed Rural Postman Validation Schedule Conclusion

Requirement: Visit a subset of edges in the graph that are labeled as required. Graph: Only Arcs 36 Introductio n Approach The Directed Rural Postman: Algorithms Validation Schedule Conclusion Idea: Connect the components of the graph induced by the required arcs, and then solve a min-cost flow problem. Step I: Simplify the graph.

Step II: Find an MST on the collapsed graph. Step III: Solve a mincost flow problem on the resulting graph. 37 Introductio n Approach Validation Schedule Conclusion The Directed Rural Postman Cost function: C Set of required arcs: Set of vertices: xa : represents number of times we traverse arc a. 38

Introductio n Approach The Directed Rural Postman: Algorithms Validation Schedule Conclusion Idea: Connect the components of the graph induced by the required arcs, and then solve a min-cost flow problem. Step I: Simplify the graph. Step II: Find an MST on the collapsed graph. Step III: Solve a mincost flow problem on the resulting graph. 39 Introductio n

Approach The Directed Rural Postman: Algorithms Validation Schedule Conclusion Idea: Connect the components of the graph induced by the required arcs, and then solve a min-cost flow problem. Step I: Simplify the graph. Step II: Find an MST on the collapsed graph. Step III: Solve a mincost flow problem on the resulting graph. 40 Introductio n Approach

The Directed Rural Postman: Algorithms Validation Schedule Conclusion Idea: Connect the components of the graph induced by the required arcs, and then solve a min-cost flow problem. Step I: Simplify the graph. Step II: Find an MST on the collapsed graph. Step III: Solve a mincost flow problem on the resulting graph. Repeat Steps II and III, rooting the MST at each of the components, and picking the best solution. 41 Introductio

n Approach The Directed Rural Postman: Algorithms II Validation Schedule Conclusion Here, we model the problem as an WRPP, and apply the heuristic of Benavent, except that we first compute an MST over the connected components of the original graph, and add the corresponding edges to the required graph. 42 Introductio n

Approach Validation / Verification Validatio n For UCPP, DCPP, and DRPP well generate our own test instances for which the optimal solution will be known, or solved for using and IP formulation and an industrial grade solver. For MCPP, and WPP, test on benchmark instances made public at http://www.uv.es/corber an/instancias.htm for which the optimal solution is known. Schedule Conclusion We shall use Wilcoxons Rank Sum test in order to validate the fact that our code is actually implementing the

desired heuristic, taking results from the papers in which these are presented, and testing them against our solutions. 43 Introductio n Approach Validatio n For some problems, we shall use instances made public by Angel Corberan: Databases Instances satisfy the connectivity assumptions of the problem. Instances have integer costs along the edges. Instances have no negative cost cycles. We shall, in general

check for these in the code so that our library exhibits predictable failure states. Schedule Conclusion For the rest of the problems, we shall randomly generate test instances which will also be posted with the other instances, and with the code. These will be solved to optimality using the IP formulations presented here, and an industrial grade solver like CPLEX or Gurobi. These will meet the same set of assumptions as Corberans instances. 44 Introductio n

Approach Validation DCPP / UCPP Exact Solvers Septemb er / October Schedule Investigate Plowing with Precedenc e May Performan ce Optimizati on / Tuning February WPP Heuristics Decembe r Conclusion

Schedule MCPP Heuristics Novembe r DRPP January Extensibilit y (CPLEX / Gurobi, Gephi / Graphviz) March April 45 Introductio n Approach Implementati on Validation Schedule Conclusion The implementation language will be primarily in Java,

with the option to write certain pieces in C++ if necessary, (using JNI). The code will be tested on two different setups, on all major operating systems (Windows, OSX, Linux). (Desktop) Intel i7 920 Processor, 2.67 GHz, 8GB RAM. (Laptop) Macbook Air (2012). Version control using Git. 46 Introductio n Approach Validation Schedule Conclusio n To be hosted at my personal github at https://github.com/olibear . Deliverable s Test instances All code

Solvers Graph architecture Extensible interfaces and abstract classes integrated utilities. Documentation (including tutorials and a readme) Mid-year and Final Report 47 Introductio n Approach Validation Schedule Conclusio n 1. Thimbleby, Harold. "The directed chinese postman problem." Software: Practice and Experience 33.11 (2003): 1081-1096. 2. http://www.ise.ncsu.edu/fangroup/or766.dir/or766_ch9.pdf 3. Eiselt, Horst A., Michel Gendreau, and Gilbert Laporte. "Arc routing problems, part I: The Chinese postman problem." Operations Research 43.2 (1995): 231-242. 4. Yaoyuenyong, Kriangchai, Peerayuth Charnsethikul, and Vira Chankong. "A heuristic algorithm for the mixed Chinese postman problem." Optimization and Engineering 3.2 (2002): 157-187. References

5. Benavent, Enrique, et al. "New heuristic algorithms for the windy rural postman problem." Computers & operations research 32.12 (2005): 3111-3128. 6. Eiselt, Horst A., Michel Gendreau, and Gilbert Laporte. "Arc routing problems, part II: The rural postman problem." Operations Research 43.3 (1995): 399-414. 7. Campos, V., and J. V. Savall. "A computational study of several heuristics for the DRPP." Computational Optimization and Applications 4.1 (1995): 67-77. (Replace this with Carmines paper when I get it). 8. Dussault, Benjamin, et al. "Plowing with precedence: A variant of the windy postman problem." Computers & Operations Research (2012). 9. Win, Zaw. "On the windy postman problem on Eulerian graphs." Mathematical Programming 44.1-3 (1989): 97-112. 10. Christofides, Nicos, et al. "An algorithm for the rural postman problem on a directed graph." Netflow at Pisa. Springer Berlin Heidelberg, 1986. 155-166. 48