IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v53y2019i3p867-881.html
   My bibliography  Save this article

The (Over)zealous Snow Remover Problem

Author

Listed:
  • Kaj Holmberg

    (Department of Mathematics, Linköping Institute of Technology, 581 83 Linköping, Sweden)

Abstract

Planning snow removal is a difficult, infrequently occurring optimization problem, concerning complicated routing of vehicles. Clearing a street includes several different activities, and the tours must be allowed to contain subtours. The streets are classified into different types, each type requiring different activities. We address the problem facing a single vehicle, including details such as precedence requirements and turning penalties. We describe a solution approach based on a reformulation to an asymmetric traveling salesman problem in an extended graph, plus a heuristic for finding feasible solutions and a reordering procedure. The method has been implemented and tested on real life examples, and the solution times are short enough to allow online usage. We compare the solutions to lower bounds obtained by solving a mixed integer programming model. We study two different principles for the number of sweeps on a normal street, encountered in discussions with snow removal contractors. A principle using a first sweep in the middle of the street around the block, in order to quickly allow usage of the streets, is found to yield interesting theoretical and practical difficulties. The online appendix is available at https://doi.org/10.1287/trsc.2018.0851 .

Suggested Citation

  • Kaj Holmberg, 2019. "The (Over)zealous Snow Remover Problem," Transportation Science, INFORMS, vol. 53(3), pages 867-881, May.
    • Handle: RePEc:inm:ortrsc:v:53:y:2019:i:3:p:867-881
    DOI: 10.1287/trsc.2018.0851
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2018.0851
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2018.0851?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Nathalie Perrier & André Langevin & Ciro-Alberto Amaya, 2008. "Vehicle Routing for Urban Snow Plowing Operations," Transportation Science, INFORMS, vol. 42(1), pages 44-56, February.
    2. Moon, Chiung & Kim, Jongsoo & Choi, Gyunghyun & Seo, Yoonho, 2002. "An efficient genetic algorithm for the traveling salesman problem with precedence constraints," European Journal of Operational Research, Elsevier, vol. 140(3), pages 606-617, August.
    3. J Clossey & G Laporte & P Soriano, 2001. "Solving arc routing problems with turn penalties," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(4), pages 433-439, April.
    4. D Soler & E Martínez & J C Micó, 2008. "A transformation for the mixed general routing problem with turn penalties," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(4), pages 540-547, April.
    5. Enrique Benavent & David Soler, 1999. "The Directed Rural Postman Problem with Turn Penalties," Transportation Science, INFORMS, vol. 33(4), pages 408-418, November.
    6. Helsgaun, Keld, 2000. "An effective implementation of the Lin-Kernighan traveling salesman heuristic," European Journal of Operational Research, Elsevier, vol. 126(1), pages 106-130, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    2. D Soler & E Martínez & J C Micó, 2008. "A transformation for the mixed general routing problem with turn penalties," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(4), pages 540-547, April.
    3. Cerrone, Carmine & Dussault, Benjamin & Wang, Xingyin & Golden, Bruce & Wasil, Edward, 2019. "A two-stage solution approach for the Directed Rural Postman Problem with Turn Penalties," European Journal of Operational Research, Elsevier, vol. 272(2), pages 754-765.
    4. Debdatta Sinha Roy & Adriano Masone & Bruce Golden & Edward Wasil, 2021. "Modeling and Solving the Intersection Inspection Rural Postman Problem," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1245-1257, July.
    5. Irnich, Stefan, 2008. "Solution of real-world postman problems," European Journal of Operational Research, Elsevier, vol. 190(1), pages 52-67, October.
    6. Nikolakopoulos, Athanassios & Sarimveis, Haralambos, 2007. "A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1911-1929, March.
    7. Eliécer Gutiérrez & Andrés Medaglia, 2008. "Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks," Annals of Operations Research, Springer, vol. 157(1), pages 169-182, January.
    8. Xiaoguang Bao & Xinhao Ni, 2024. "Approximation algorithms for two clustered arc routing problems," Journal of Combinatorial Optimization, Springer, vol. 47(5), pages 1-12, July.
    9. A. Scholz & G. Wäscher, 2017. "Order Batching and Picker Routing in manual order picking systems: the benefits of integrated routing," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(2), pages 491-520, June.
    10. van Gils, Teun & Ramaekers, Katrien & Braekers, Kris & Depaire, Benoît & Caris, An, 2018. "Increasing order picking efficiency by integrating storage, batching, zone picking, and routing policy decisions," International Journal of Production Economics, Elsevier, vol. 197(C), pages 243-261.
    11. Ghosh, Diptesh, 2016. "Exploring Lin Kernighan neighborhoods for the indexing problem," IIMA Working Papers WP2016-02-13, Indian Institute of Management Ahmedabad, Research and Publication Department.
    12. Elena Fernández & Gilbert Laporte & Jessica Rodríguez-Pereira, 2019. "Exact Solution of Several Families of Location-Arc Routing Problems," Transportation Science, INFORMS, vol. 53(5), pages 1313-1333, September.
    13. B. I. Goldengorin & D. S. Malyshev & P. M. Pardalos & V. A. Zamaraev, 2015. "A tolerance-based heuristic approach for the weighted independent set problem," Journal of Combinatorial Optimization, Springer, vol. 29(2), pages 433-450, February.
    14. Krešimir Mihić & Kevin Ryan & Alan Wood, 2018. "Randomized Decomposition Solver with the Quadratic Assignment Problem as a Case Study," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 295-308, May.
    15. Jiang, Zhongzhou & Liu, Jing & Wang, Shuai, 2016. "Traveling salesman problems with PageRank Distance on complex networks reveal community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 463(C), pages 293-302.
    16. Jean-Charles Créput & Amir Hajjam & Abderrafiaa Koukam & Olivier Kuhn, 2012. "Self-organizing maps in population based metaheuristic to the dynamic vehicle routing problem," Journal of Combinatorial Optimization, Springer, vol. 24(4), pages 437-458, November.
    17. Lin, Shih-Wei & Ying, Kuo-Ching, 2016. "Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics," Omega, Elsevier, vol. 64(C), pages 115-125.
    18. Henke, Tino & Speranza, M. Grazia & Wäscher, Gerhard, 2015. "The multi-compartment vehicle routing problem with flexible compartment sizes," European Journal of Operational Research, Elsevier, vol. 246(3), pages 730-743.
    19. Lamb, John D., 2012. "Variable neighbourhood structures for cycle location problems," European Journal of Operational Research, Elsevier, vol. 223(1), pages 15-26.
    20. Marcel Turkensteen & Dmitry Malyshev & Boris Goldengorin & Panos M. Pardalos, 2017. "The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems," Journal of Global Optimization, Springer, vol. 68(3), pages 601-622, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:53:y:2019:i:3:p:867-881. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.