A Two-Stage Partitioning Approach for the Min-Max K Windy Rural Postman Problem

Oliver Lum

Carmine Cerrone

Bruce Golden

Edward Wasil

1

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)

​

​

​

​

2

OAR Lib Content

• Well-Known Algorithms
• Single-Source Shortest Paths
• All-Pairs Shortest Paths
• Min-Cost Matching
• Min-Cost Flow
• Hierholzer’s Algorithm
• Minimum Spanning Tree
• Minimum Spanning Arborescence
• Connectivity Tests

​

​

​

​

3

Applications

• Well-established
• Package Delivery
• Snow Plowing
• Military Patrols
• Variants
• Time-Windows
• Close-Enough
• Turn Penalties
• Asymmetric Costs

​

4

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

​

5

Min-Max K WRPP

6

= Required

= Included in route

= Not traversed

Min-Max K WRPP

• Literature review
• 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 63:1 (2014): 34-45.

​

7

Benavent’s 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).

8

8

1

2

3

4

5

6

7

8

Benavent’s Algorithm

• Set up a directed, acyclic graph (DAG) 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

9

0

2

1

8

Benavent’s 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)

10

0

2

1

8

3

4

5

6

7

Compactness Metrics

• In practice, usable routes must often exhibit intuitive properties like connectedness and compactness. Two metrics proposed in Constantino et al. “The mixed capacitated arc routing poblem with non-overlapping routes.” European Journal of Operational Research (2015, under review)
• Route Overlap Index (ROI)

​

​

• Average Traversal Distance (ATD)

​

11

Route Overlap Index

12

Average Traversal Distance

13

6

4

2

1

3

7

5

6

4

2

1

3

7

5

Compact Routes

Non-compact Routes

Benavent’s Approach

14

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

15

1

2

3

4

1

2

3

4

1

2

4

3

5

6

5

6

5

7

7

Partitioning Scheme

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

16

1

2

3

4

1

2

3

4

5

6

5

7

if link i must be deadheaded

oth.

Partitioning Scheme

• Linear weights, chosen empirically

17

Partitioning Scheme

• Linear weights, chosen empirically, evenly spaced in �[.01, .03]

18

Partitioning Scheme

• Partition the transformed graph into k approximately equal parts.

19

1

2

3

4

1

2

3

4

5

6

5

7

Partitioning Scheme

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

20

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

Partitioning Approach

21

Benavent’s Approach

22

Results

• Tested on a 64-bit PC running an Intel i5 4690K 3.5 GHz CPU, with 8 GB RAM
• Two sets of benchmark instances
• Real street networks taken from cities using the crowd-sourced Open Street Networks database
• Trimmed to largest connected component
• ~50% of links randomly assigned to be required
• Artificial rectangular networks
• ~50% of links randomly assigned to be required

23

Results: Street Networks

24

Results: Rectangular Networks

25

Conclusions and Future Work

• Advantages of partitioning heuristic
• Can solve 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 )
• Speed – each perturbation takes considerable time
• Future Work
• Exploring relationship between number of vehicles, and tuning parameters

​

26

Large Instance

27

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 Postman Problem." 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." Computational Optimization and Applications 4:1 (1995): 67-77.
• Derigs, Ulrich. Optimization and operations research. Eolss Publishers Company Limited, 2009.
• Dussault, Benjamin, et al. "Plowing with precedence: A variant of the windy postman problem."Computers & Operations Research (2012).
• Edmonds, Jack, and Ellis L. Johnson. "Matching, Euler tours and the Chinese postman." Mathematical Programming 5:1 (1973): 88-124.

​

28

References

• Eiselt, Horst A., Michel Gendreau, and Gilbert Laporte. "Arc routing problems, part II: The rural postman problem." Operations Research 43:3 (1995): 399-414.
• Frederickson, Greg N. "Approximation algorithms for some postman problems." Journal of the ACM(JACM) 26:3 (1979): 538-554.
• Grotschel, Martin, and Zaw Win. "A cutting plane algorithm for the windy postman problem." Mathematical Programming 55:1-3 (1992): 339-358.
• Hierholzer, Carl, and Chr Wiener. "Uber die Moglichkeit, einen Linienzug ohne Wiederholung und ohneUnterbrechung zu umfahren." Mathematische Annalen 6:1 (1873): 30-32.
• http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow2

29

References

• 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
• Karypis, George, and Vipin Kumar. "A fast and high quality multilevel scheme for partitioning irregulargraphs." SIAM Journal on Scientific Computing 20:1 (1998): 359-392.
• Kolmogorov, Vladimir. "Blossom V: a new implementation of a minimum cost perfect matching algorithm." Mathematical Programming Computation 1:1 (2009): 43-67.
• Lau, Hang T. A Java library of graph algorithms and optimization. CRC Press, 2010.

30

References

• Letchford, Adam N., Gerhard Reinelt, and Dirk Oliver Theis. "A faster exact separation algorithm for blossom inequalities." Integer Programming and Combinatorial Optimization. Springer Berlin Heidelberg, 2004. 196-205.
• Padberg, Manfred W., and M. Ram Rao. "Odd minimum cut-sets and b-matchings." Mathematics of Operations 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 the mixed Chinese postman problem." Optimization and Engineering 3:2 (2002): 157-187

31

Backup

32

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
• Open Street Maps Integration
• Gephi toolkit (open source graph visualization) Integration

​

33

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

​

Problem:

Solution:

Interchange

• Two-Interchange and Or-Interchange move a (string of) required link(s) to a different position in the route

34

Two-Interchange

Swap

• Change 1-to-1, 1-to-0, and 2-to-0 swap or move edges off of a route

35

Change 1-to-0

Compact Representation

• A route may be represented simply as an ordered list of the required links it traverses, with implied shortest paths taken between them

36

A New Objective Function

• Attempt to incorporate compactness into the measure of solution quality

37