Synchronized arc routing for snow plowing operations. (English) Zbl 1251.90070
Summary: We introduce a synchronized arc routing problem for snow plowing operations. In this problem, routes must be designed in such a way that street segments with two or more lanes in the same direction are plowed simultaneously by different synchronized vehicles. A mixed integer formulation and an adaptive large neighborhood search heuristic are proposed. The performance of the proposed algorithm is evaluated over a large instance set, including artificial and real data. Computational results confirm the efficiency of the algorithm.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
arc routing; snow plowing; road maintenance; synchronized routes; adaptive large neighborhood searchReferences:
| [1] | Dali Z. Optimization of vehicle routing for plowing and snow disposal. In: Wang Y, Yi P, An S, Wang H., editors, Proceedings of the ninth international conference of chinese transportation professionals. ICCTP 2009: critical issues in transportation system planning, development, and management, Harbin, China; 2009. p. 2738-44.; Dali Z. Optimization of vehicle routing for plowing and snow disposal. In: Wang Y, Yi P, An S, Wang H., editors, Proceedings of the ninth international conference of chinese transportation professionals. ICCTP 2009: critical issues in transportation system planning, development, and management, Harbin, China; 2009. p. 2738-44. |
| [2] | Dueck, G., The great deluge algorithm and the record-to-record travel, Journal of Computational Physics, 104, 86-92 (1993) · Zbl 0773.65042 |
| [3] | Fu, L.; Trudel, M.; Kim, V., Optimization winter road maintenance operations under real time information, European Journal of Operational Research, 196, 332-341 (2009) · Zbl 1156.90340 |
| [4] | Golbaharan N. An application of optimization to the snow removal problem – a column generation approach. PhD thesis, Linköping University, Linköping, Sweden; 2001.; Golbaharan N. An application of optimization to the snow removal problem – a column generation approach. PhD thesis, Linköping University, Linköping, Sweden; 2001. |
| [5] | Gupta D, Tokar-Erdemir E, Kuchera D, Mannava AK, Xiong W, Optimal workforce planning and shift scheduling for snow and ice removal. Technical report, Industrial and Systems Engineering Program, Department of Mechanical Engineering, University of Minnesota; 2010.; Gupta D, Tokar-Erdemir E, Kuchera D, Mannava AK, Xiong W, Optimal workforce planning and shift scheduling for snow and ice removal. Technical report, Industrial and Systems Engineering Program, Department of Mechanical Engineering, University of Minnesota; 2010. |
| [6] | Jang, W.; Noble, J. S.; Hutsel, T., An integrated model to solve the winter asset and road maintenance problem, IIE Transactions, 42, 675-689 (2010) |
| [7] | Laporte, G.; Musmanno, R.; Vocaturo, F., An adaptive large neighbourhood search heuristic for the capacitated arc-routing problem with stochastic demands, Transportation Science, 44, 125-135 (2010) |
| [8] | Martello, S.; Toth, P., Knapsack problems: algorithms and computer implementations (1990), Wiley: Wiley New York · Zbl 0708.68002 |
| [9] | Norrman, J.; Eriksson, M.; Lindqvist, S., Relationship between road slipperiness traffic, accident risk and winter road maintenance activity, Climate Research, 15, 185-193 (2005) |
| [10] | Perrier N, Campbell JF, Gendreau M, Langevin A. Vehicle routing models and algorithms for winter road spreading operations, in hybrid algorithms for service, computing and manufacturing systems: routing, scheduling and availability solutions. IGI Books, Hershey, PA, 2011.; Perrier N, Campbell JF, Gendreau M, Langevin A. Vehicle routing models and algorithms for winter road spreading operations, in hybrid algorithms for service, computing and manufacturing systems: routing, scheduling and availability solutions. IGI Books, Hershey, PA, 2011. |
| [11] | Perrier, N.; Langevin, A.; Amaya, C. A., Vehicle routing for urban snow plow operations, Transportation Science, 42, 44-56 (2008) |
| [12] | Perrier, N.; Langevin, A.; Campbell, J. F., A survey of models and algorithms for winter road maintenance. Part I: system design for spreading and plowing, Computers & Operations Research, 33, 209-238 (2006) · Zbl 1077.90520 |
| [13] | Perrier, N.; Langevin, A.; Campbell, J. F., A survey of models and algorithms for winter road maintenance. Part II: system design for snow disposal, Computers & Operations Research, 33, 239-262 (2006) · Zbl 1077.90521 |
| [14] | Perrier, N.; Langevin, A.; Campbell, J. F., A survey of models and algorithms for winter road maintenance. Part III: vehicle routing and depot location for spreading, Computers & Operations Research, 34, 211-257 (2007) · Zbl 1109.90306 |
| [15] | Perrier, N.; Langevin, A.; Campbell, J. F., A survey of models and algorithms for winter road maintenance. Part IV: vehicle routing and fleet sizing for plowing and snow disposal, Computers & Operations Research, 34, 258-297 (2007) · Zbl 1110.90026 |
| [16] | Razmara G. Snow removal routing problems - Theory and applications. PhD thesis, Linköping University, Linköping Studies in Science and Technology, Linköping, Sweden; 2004.; Razmara G. Snow removal routing problems - Theory and applications. PhD thesis, Linköping University, Linköping Studies in Science and Technology, Linköping, Sweden; 2004. |
| [17] | Ropke, S.; Pisinger, D., An adaptive large neighbourhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40, 455-472 (2006) |
| [18] | Salazar-Aguilar, M. A.; Langevin, A.; Laporte, G., An adaptive large neighborhood search heuristic for a snow plowing problem with synchronized routes, (Pahl, J.; Reiners, T.; Voss, S., Network optimization - International network optimization conference (INOC 2011). Lecture notes in computer science (2011), Springer: Springer Hamburg, Germany), 406-411 |
| [19] | Shaw, P., Using constraint programming and local search methods to solve vehicle routing problems, Lecture notes in computer science, vol. 1520 (1998), Springer: Springer Berlin, p. 417-31 |
| [20] | Sochor J, Yu C. A heuristic method for routing snowplows after snowfall. MSc thesis, Division of Optimization, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden; 2004.; Sochor J, Yu C. A heuristic method for routing snowplows after snowfall. MSc thesis, Division of Optimization, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden; 2004. |
| [21] | Usman, T.; Fu, L.; Miranda-Moreno, L. F., Quantifying safety benefit of winter road maintenance: accident frequency modeling, Accident Analysis and Prevention, 42, 1878-1887 (2010) |
| [22] | Venäläinen, A.; Kangas, M., Estimation of winter road maintenance costs using climate data, Meteorological Applications, 10, 69-73 (2003) |
| [23] | Ville de Montréal. Snow removal 101, \( \langle\) http://ville.montreal.qc.ca \(\rangle \); Ville de Montréal. Snow removal 101, \( \langle\) http://ville.montreal.qc.ca \(\rangle \) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
