OAR Lib: An Open Source Arc Routing Library

By Oliver Lum

Carmine Cerrone

Bruce Golden

Edward Wasil

1

OAR Lib (Motivation)

• An open-source java library aimed at new operations researchers in the field of arc-routing
• An architecture for future software development in routing and scheduling
• Design Philosophy: Usability First, Performance Second
• OSM Integration
• Gephi toolkit (open source graph visualization) Integration

​

2

• A (perceived) barrier to entry that coding experience in a non-modeling language is required
• No centralized, standardized implementations of many routing algorithms
• Existing APIs are frequently developed with graph theoretic research in mind
• Realistic test data procurement
• Figure generation for papers

​

Problem:

Solution:

OAR Lib (Content)

• Single-Vehicle Solvers
• Un/Directed Chinese Postman (UCPP/DCPP)
• Mixed Chinese Postman (MCPP)
• Windy Chinese Postman (WPP)
• Directed Rural Postman Problem (DRPP)
• Windy Rural Postman Problem (WRPP)
• Multi-Vehicle Solvers
• Min-Max K Windy Rural Postman Problem (MM-k WRPP)

​

​

​

​

3

OAR Lib (Content)

• Common Algorithms:
• Single-Source Shortest Paths
• All-Pairs Shortest Paths
• Min-Cost Matching (JNI)
• Min-Cost Flow
• Hierholzer’s Algorithm
• (Stochastic) Minimum Spanning Tree
• Minimum Spanning Arborescence (JNI)
• Connectivity Tests

​

​

​

​

4

Applications

• Ubiquitous:
• Package Delivery
• Snow Plowing
• Military Patrols
• Various interesting wrinkles:
• Time-Windows
• Close-Enough
• Turn Penalties
• Asymmetric Costs

​

5

The Min-Max K WRPP

• A natural extension of the WRPP
• Objective: Minimize the max route cost
• Homogenous fleet, K vehicles
• Asymmetric Traversal Costs
• Required and unrequired edges
• Generalization of the directed, undirected, and mixed variants
• Takes into account route balance, and customer satisfaction

​

6

The Min-Max K WRPP

7

= Required

= Included in route

= Untraversed

The Min-Max K WRPP

• Existing Literature:
• Benavent, Enrique, et al. “Min-Max K-vehicles windy rural postman problem.” Networks 54.4 (2009): 216-226.
• Benavent, Enrique, Angel Corberan, Jose M. Sanchis. “A metaheuristic for the min-max windy rural postman problem with K vehicles.” Computational Management Science 7.3 (2010): 269-287.
• Benavent, Enrique, et al. “A branch-price-and-cut method for the min-max k-windy rural postman problem.” Networks (2014, to appear).

​

8

Existing Algorithm

• Solve the single-vehicle variant. This produces a solution that can be represented as an ordered list of required edges (where any gaps are traversed via shortest paths).

9

9

Existing Algorithm

• Set up a directed, acyclic graph with m+1 vertices, (0,1,…m) where the cost of the arc (i-1,j) is the cost of the tour starting at the depot, going to the tail of edge i, continuing along the single-vehicle solution through edge j, and then returning to the depot.

10

0

2

1

8

Existing Algorithm

• Calculate a k-edge narrowest path from v₀ to v_m in the DAG, corresponding to a solution (a simple modification to Dijkstra’s single-source shortest path algorithm suffices).

11

0

2

1

8

3

4

5

6

7

A Partitioning Scheme

• Transform the graph into a vertex-weighted graph in the following way:
• Create a vertex for each edge in the original graph
• Connect two vertices i and j if, in the original graph, edge I and edge j shared an endpoint

12

1

2

3

4

1

2

3

4

1

2

4

3

5

6

5

6

5

7

7

A Partitioning Scheme

• Change the vertex weights to account for known dead-heading and distance to the depot.

13

1

2

3

4

1

2

3

4

5

6

5

7

A Partitioning Scheme

• Partition the transformed graph into k approximately equal parts.

14

1

2

3

4

1

2

3

4

5

6

5

7

A Partitioning Scheme

• Route the subgraphs induced by each partition using a single-vehicle solver.

15

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

16

Test Instance:

Cross-Section of Helsinki, Finland

​

|V|=1230

|E|=1468

= Required Edge

= Unrequired Edge

​

= Depot

Existing Approach Route 1

17

Existing Approach Route 2

18

Partitioning Approach

19

Results

20

Conclusions / Future Work

• Advantages:
• Capable of solving large instances
• Service contiguity – adjacent links are more likely to be serviced by the same vehicle
• Memory usage – the widest path calculation in the existing algorithm is extremely memory intensive ( order )
• Future Work:
• Incorporate / apply existing improvement procedures to both procedures and compare.
• Exploring relationship between number of vehicles, and tuning parameters

​

21

A Large Instance

22

Test Instance:

Cross-Section of Greenland

​

|V|=3047

|E|=3285

​

Runtime: 328.3 s

​

References

• Ahr, Dino, and Gerhard Reinelt. "New heuristics and lower bounds for the Min-Max k-Chinese PostmanProblem." Algorithms|ESA 2002. Springer Berlin Heidelberg, 2002. 64-74.
• Benavent, Enrique, et al. "New heuristic algorithms for the windy rural postman problem." Computers& operations research 32.12 (2005): 3111-3128.
• Campos, V., and J. V. Savall. "A computational study of several heuristics for the DRPP." ComputationalOptimization and Applications 4.1 (1995): 67-77.
• http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow2
• Edmonds, Jack, and Ellis L. Johnson. "Matching, Euler tours and the Chinese postman." Mathematicalprogramming 5.1 (1973): 88-124.

23

References

• Eiselt, Horst A., Michel Gendreau, and Gilbert Laporte. "Arc routing problems, part II: The ruralpostman problem." Operations Research 43.3 (1995): 399-414.
• Derigs, Ulrich. Optimization and operations research. Eolss Publishers Company Limited, 2009.
• http://en.wikipedia.org/wiki/Dijkstra's_algorithm
• http://en.wikipedia.org/wiki/Floyd\OT1\textendashWarshall_algorithm
• http://en.wikipedia.org/wiki/Prim%27s_algorithm
• Dussault, Benjamin, et al. "Plowing with precedence: A variant of the windy postman problem."Computers & Operations Research (2012).
• Frederickson, Greg N. "Approximation algorithms for some postman problems." Journal of the ACM(JACM) 26.3 (1979): 538-554.

24

References

• Grotschel, Martin, and Zaw Win. "A cutting plane algorithm for the windy postman problem." Math-ematical Programming 55.1-3 (1992): 339-358.
• Hierholzer, Carl, and Chr Wiener. "Uber die M�oglichkeit, einen Linienzug ohne Wiederholung und ohneUnterbrechung zu umfahren." Mathematische Annalen 6.1 (1873): 30-32.
• Karypis, George, and Vipin Kumar. "A fast and high quality multilevel scheme for partitioning irregulargraphs." SIAM Journal on scientic Computing 20.1 (1998): 359-392.
• Kolmogorov, Vladimir. "Blossom V: a new implementation of a minimum cost perfect matching algo-rithm." Mathematical Programming Computation 1.1 (2009): 43-67.
• Lau, Hang T. A Java library of graph algorithms and optimization. CRC Press, 2010.
• Letchford, Adam N., Gerhard Reinelt, and Dirk Oliver Theis. "A faster exact separation algorithm forblossom inequalities." Integer programming and combinatorial optimization. Springer Berlin Heidelberg,2004. 196-205.

25

References

• Padberg, Manfred W., and M. Ram Rao. "Odd minimum cut-sets and b-matchings." Mathematics ofOperations Research 7.1 (1982): 67-80
• Thimbleby, Harold. "The directed chinese postman problem." Software: Practice and Experience 33.11(2003): 1081-1096.
• Win, Zaw. "On the windy postman problem on Eulerian graphs." Mathematical Programming 44.1-3(1989): 97-112.
• Yaoyuenyong, Kriangchai, Peerayuth Charnsethikul, and Vira Chankong. "A heuristic algorithm for themixed Chinese postman problem." Optimization and Engineering 3.2 (2002): 157-187

26