OASIcs.SCOR.2014.76.pdf
- Filesize: 1.17 MB
- 13 pages
Document
A Model-Based Heuristic to the Min Max K-Arc Routing for Connectivity Problem
Authors
-
Part of:
Volume:
4th Student Conference on Operational Research (SCOR 2014)
Series: Open Access Series in Informatics (OASIcs) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2014-08-06
Cite AsGet BibTex
Vahid Akbari and Sibel Salman. A Model-Based Heuristic to the Min Max K-Arc Routing for Connectivity Problem. In 4th Student Conference on Operational Research. Open Access Series in Informatics (OASIcs), Volume 37, pp. 76-88, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/OASIcs.SCOR.2014.76
https://doi.org/10.4230/OASIcs.SCOR.2014.76
Abstract
We consider the post-disaster road clearing problem with the goal of restoring network connectivity in shortest time. Given a set of blocked edges in the road network, teams positioned at depot nodes are dispatched to open a subset of them that reconnects the network. After a team finishes working on an edge, others can traverse it. The problem is to find coordinated routes for the teams. We generate a feasible solution using a constructive heuristic algorithm after solving a relaxed mixed integer program. In almost 70 percent of the instances generated both randomly and from Istanbul data, the relaxation solution turned out to be feasible, i.e. optimal for the original problem.
Keywords
- Arc Routing Problem
- Mixed Integer Programming
- Heuristic
- Network Connectivity
- Road Clearance
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
D. T. Aksu and L. Ozdamar. A mathematical model for post-disaster road restoration: Enabling accessibility and evacuation. Transportation Research Part E: Logistics and Transportation Review, 61(0):56-67, 2014.
-
A. N. Asaly. Logistics planning for restoration of network connectivity after a disaster. Master’s thesis, Koc University, 2013.
-
A. N. Asaly and F. S. Salman. Global Logistics, New Directions in Logistics Management, chapter Arc Selection and Routing for Restoration of Network Connectivity after a Disaster. Taylor and Francis, 2014.
-
A. Assad, W. Pearn, and B. Golden. The capacitated Chinese postman problem: Lower bounds and solvable cases. American Journal of Mathematical and Management Science, 7:63-88, 1987.
-
E. Benavent, A. Corberán, I. Plana, and J. M. Sanchis. Min-max k-vehicles windy rural postman problem. Networks, 54(4):216-226, 2009.
-
A. Corberán, I. Plana, and J. M. Sanchis. A branch and cut algorithm for the windy general routing problem and special cases. Networks, 49(4):245-257, 2007.
-
J. Edmonds and E. L. Johnson. Matching, Euler tours and the Chinese postman problems. Mathematical Programming, 5:88-124, 1973.
-
H. A. Eiselt, M. Gendreau, and G. Laporte. Arc routing problems, Part II: The rural postman problem. Operations Research, 43(3):399-414, 1995.
-
C. S. Orloff. A fundamental problem in vehicle routing. Networks, 4(1):35-64, 1974.
-
W. L. Pearn. Solvable cases of the k-person Chinese postman problem. Operations Research Letters, 16:241-244, 1994.
-
Z. Win. Contributions to Routing Problems. PhD thesis, University of Augsburg, 1987.
-
S. Yan and Y.-L. Shih. Optimal scheduling of emergency roadway repair and subsequent relief distribution. Computers and Operations Research, 36:2049-2065, 2009.