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

An Adaptive Large Neighborhood Search for the Location-routing Problem with Intra-route Facilities

Author

Listed:
  • Maximilian Schiffer

    (Chair of Operations Management, School of Business and Economics, RWTH Aachen University, 52072 Aachen, Germany)

  • Grit Walther

    (Chair of Operations Management, School of Business and Economics, RWTH Aachen University, 52072 Aachen, Germany)

Abstract

Recent research on location-routing problems has been focusing on locating facilities as the starting and end point of routes. In this paper, we investigate a new type of location-routing problem. In the location-routing problem with intra-route facilities, the location of depots is known, whereas the location of facilities for intermediate stops has to be determined to keep vehicles operational. We present an adaptive large neighborhood search which is enhanced by local search and dynamic programming components, and derive new penalty functions for time-efficient neighborhood evaluation. We show that this algorithm is suitable for solving various problems with intra-route facilities by deriving new best known solutions for the recently published electric location-routing problem with time windows and partial recharging, as well as for the battery swap station electric vehicle location-routing problem. Additionally, we create new real-world benchmark instances and show results as well. Furthermore, we assess the competitiveness of our algorithm on the electric vehicle routing problem with time windows for full and partial recharging, and derive new best known solutions for both problem variants.

Suggested Citation

  • Maximilian Schiffer & Grit Walther, 2018. "An Adaptive Large Neighborhood Search for the Location-routing Problem with Intra-route Facilities," Transportation Science, INFORMS, vol. 52(2), pages 331-352, March.
    • Handle: RePEc:inm:ortrsc:v:52:y:2018:i:2:p:331-352
    DOI: 10.1287/trsc.2017.0746
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2017.0746
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2017.0746?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. T. Ibaraki & S. Imahori & M. Kubo & T. Masuda & T. Uno & M. Yagiura, 2005. "Effective Local Search Algorithms for Routing and Scheduling Problems with General Time-Window Constraints," Transportation Science, INFORMS, vol. 39(2), pages 206-232, May.
    2. Christos D. Tarantilis & Emmanouil E. Zachariadis & Chris T. Kiranoudis, 2008. "A Hybrid Guided Local Search for the Vehicle-Routing Problem with Intermediate Replenishment Facilities," INFORMS Journal on Computing, INFORMS, vol. 20(1), pages 154-168, February.
    3. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2014. "A unified solution framework for multi-attribute vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 234(3), pages 658-673.
    4. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    5. Crevier, Benoit & Cordeau, Jean-Francois & Laporte, Gilbert, 2007. "The multi-depot vehicle routing problem with inter-depot routes," European Journal of Operational Research, Elsevier, vol. 176(2), pages 756-773, January.
    6. Psaraftis, Harilaos N., 1983. "k-Interchange procedures for local search in a precedence-constrained routing problem," European Journal of Operational Research, Elsevier, vol. 13(4), pages 391-402, August.
    7. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    8. Felipe, Ángel & Ortuño, M. Teresa & Righini, Giovanni & Tirado, Gregorio, 2014. "A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 71(C), pages 111-128.
    9. Schneider, M. & Stenger, A. & Goeke, D., 2014. "The Electric Vehicle Routing Problem with Time Windows and Recharging Stations," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62382, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    10. David Pisinger & Stefan Ropke, 2010. "Large Neighborhood Search," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 399-419, Springer.
    11. Divsalar, A. & Vansteenwegen, P. & Sörensen, K. & Cattrysse, D., 2014. "A memetic algorithm for the orienteering problem with hotel selection," European Journal of Operational Research, Elsevier, vol. 237(1), pages 29-49.
    12. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    13. Salhi, Said & Rand, Graham K., 1989. "The effect of ignoring routes when locating depots," European Journal of Operational Research, Elsevier, vol. 39(2), pages 150-156, March.
    14. Teodor Gabriel Crainic & Nicoletta Ricciardi & Giovanni Storchi, 2009. "Models for Evaluating and Planning City Logistics Systems," Transportation Science, INFORMS, vol. 43(4), pages 432-454, November.
    15. Angelelli, Enrico & Grazia Speranza, Maria, 2002. "The periodic vehicle routing problem with intermediate facilities," European Journal of Operational Research, Elsevier, vol. 137(2), pages 233-247, March.
    16. Schneider, M. & Stenger, A. & Hof, J., 2015. "An Adaptive VNS Algorithm for Vehicle Routing Problems with Intermediate Stops," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 63500, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    17. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    18. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2012. "An adaptive large neighborhood search heuristic for the Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 223(2), pages 346-359.
    19. Samuel Pelletier & Ola Jabali & Gilbert Laporte, 2016. "50th Anniversary Invited Article—Goods Distribution with Electric Vehicles: Review and Research Perspectives," Transportation Science, INFORMS, vol. 50(1), pages 3-22, February.
    20. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    21. Hiermann, Gerhard & Puchinger, Jakob & Ropke, Stefan & Hartl, Richard F., 2016. "The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations," European Journal of Operational Research, Elsevier, vol. 252(3), pages 995-1018.
    22. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    23. Martin W. P. Savelsbergh, 1992. "The Vehicle Routing Problem with Time Windows: Minimizing Route Duration," INFORMS Journal on Computing, INFORMS, vol. 4(2), pages 146-154, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dönmez, Sercan & Koç, Çağrı & Altıparmak, Fulya, 2022. "The mixed fleet vehicle routing problem with partial recharging by multiple chargers: Mathematical model and adaptive large neighborhood search," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 167(C).
    2. Wang, Weiquan & Zhao, Jingyi, 2023. "Partial linear recharging strategy for the electric fleet size and mix vehicle routing problem with time windows and recharging stations," European Journal of Operational Research, Elsevier, vol. 308(2), pages 929-948.
    3. Mariusz Jedliński & Mariusz Nürnberg, 2022. "Application of the Experimental Method in the Assessment of the Electromobility Paradigm for Courier Shipments in an Urban Agglomeration," Energies, MDPI, vol. 15(24), pages 1-17, December.
    4. Singh, Nitish & Dang, Quang-Vinh & Akcay, Alp & Adan, Ivo & Martagan, Tugce, 2022. "A matheuristic for AGV scheduling with battery constraints," European Journal of Operational Research, Elsevier, vol. 298(3), pages 855-873.
    5. Wolfinger, David & Gansterer, Margaretha & Doerner, Karl F. & Popper, Nikolas, 2023. "A Large Neighbourhood Search Metaheuristic for the Contagious Disease Testing Problem," European Journal of Operational Research, Elsevier, vol. 304(1), pages 169-182.
    6. Yu, Vincent F. & Jodiawan, Panca & Redi, A.A.N. Perwira, 2022. "Crowd-shipping problem with time windows, transshipment nodes, and delivery options," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).
    7. Bektaş, Tolga & Ehmke, Jan Fabian & Psaraftis, Harilaos N. & Puchinger, Jakob, 2019. "The role of operational research in green freight transportation," European Journal of Operational Research, Elsevier, vol. 274(3), pages 807-823.
    8. Erfan Ghorbani & Mahdi Alinaghian & Gevork. B. Gharehpetian & Sajad Mohammadi & Guido Perboli, 2020. "A Survey on Environmentally Friendly Vehicle Routing Problem and a Proposal of Its Classification," Sustainability, MDPI, vol. 12(21), pages 1-71, October.
    9. Jaller, Miguel & Pahwa, Anmol, 2023. "Coping with the Rise of E-commerce Generated Home Deliveries through Innovative Last-mile Technologies and Strategies," Institute of Transportation Studies, Working Paper Series qt5t76x0kh, Institute of Transportation Studies, UC Davis.
    10. Malladi, Satya S. & Christensen, Jonas M. & Ramírez, David & Larsen, Allan & Pacino, Dario, 2022. "Stochastic fleet mix optimization: Evaluating electromobility in urban logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    11. LIAN, Ying & LUCAS, Flavien & SÖRENSEN, Kenneth, 2022. "The electric on-demand bus routing problem with partial charging and nonlinear functions," Working Papers 2022005, University of Antwerp, Faculty of Business and Economics.
    12. Frey, Christian M.M. & Jungwirth, Alexander & Frey, Markus & Kolisch, Rainer, 2023. "The vehicle routing problem with time windows and flexible delivery locations," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1142-1159.
    13. Ammann, Pia & Kolisch, Rainer & Schiffer, Maximilian, 2023. "Driver routing and scheduling with synchronization constraints," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    14. Gläser, Sina, 2022. "A waste collection problem with service type option," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1216-1230.
    15. Davatgari, Amir & Cokyasar, Taner & Subramanyam, Anirudh & Larson, Jeffrey & Mohammadian, Abolfazl (Kouros), 2024. "Electric vehicle supply equipment location and capacity allocation for fixed-route networks," European Journal of Operational Research, Elsevier, vol. 317(3), pages 953-966.
    16. Moritz Baum & Julian Dibbelt & Andreas Gemsa & Dorothea Wagner & Tobias Zündorf, 2019. "Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles," Transportation Science, INFORMS, vol. 53(6), pages 1627-1655, November.
    17. Liu, Chuanju & Zhang, Junlong & Lin, Shaochong & Shen, Zuo-Jun Max, 2023. "Service network design with consistent multiple trips," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 171(C).
    18. Sergio Maria Patella & Gianluca Grazieschi & Valerio Gatta & Edoardo Marcucci & Stefano Carrese, 2020. "The Adoption of Green Vehicles in Last Mile Logistics: A Systematic Review," Sustainability, MDPI, vol. 13(1), pages 1-29, December.
    19. Göpfert, Paul & Bock, Stefan, 2019. "A Branch&Cut approach to recharging and refueling infrastructure planning," European Journal of Operational Research, Elsevier, vol. 279(3), pages 808-823.
    20. Luiz Eduardo Cotta Monteiro & Hugo Miguel Varela Repolho & Rodrigo Flora Calili & Daniel Ramos Louzada & Rafael Saadi Dantas Teixeira & Rodrigo Santos Vieira, 2021. "Optimization of a Mobile Energy Storage Network," Energies, MDPI, vol. 15(1), pages 1-23, December.
    21. Hendri Sutrisno & Chao-Lung Yang, 2023. "A two-echelon location routing problem with mobile satellites for last-mile delivery: mathematical formulation and clustering-based heuristic method," Annals of Operations Research, Springer, vol. 323(1), pages 203-228, April.
    22. Macrina, Giusy & Laporte, Gilbert & Guerriero, Francesca & Di Puglia Pugliese, Luigi, 2019. "An energy-efficient green-vehicle routing problem with mixed vehicle fleet, partial battery recharging and time windows," European Journal of Operational Research, Elsevier, vol. 276(3), pages 971-982.

    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. Schiffer, Maximilian & Schneider, Michael & Laporte, Gilbert, 2018. "Designing sustainable mid-haul logistics networks with intra-route multi-resource facilities," European Journal of Operational Research, Elsevier, vol. 265(2), pages 517-532.
    2. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    3. Erfan Ghorbani & Mahdi Alinaghian & Gevork. B. Gharehpetian & Sajad Mohammadi & Guido Perboli, 2020. "A Survey on Environmentally Friendly Vehicle Routing Problem and a Proposal of Its Classification," Sustainability, MDPI, vol. 12(21), pages 1-71, October.
    4. Masmoudi, Mohamed Amine & Hosny, Manar & Demir, Emrah & Genikomsakis, Konstantinos N. & Cheikhrouhou, Naoufel, 2018. "The dial-a-ride problem with electric vehicles and battery swapping stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 392-420.
    5. Schiffer, Maximilian & Walther, Grit, 2018. "Strategic planning of electric logistics fleet networks: A robust location-routing approach," Omega, Elsevier, vol. 80(C), pages 31-42.
    6. Hiermann, Gerhard & Puchinger, Jakob & Ropke, Stefan & Hartl, Richard F., 2016. "The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations," European Journal of Operational Research, Elsevier, vol. 252(3), pages 995-1018.
    7. Goeke, Dominik & Schneider, Michael, 2015. "Routing a mixed fleet of electric and conventional vehicles," European Journal of Operational Research, Elsevier, vol. 245(1), pages 81-99.
    8. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    9. Juho Andelmin & Enrico Bartolini, 2017. "An Exact Algorithm for the Green Vehicle Routing Problem," Transportation Science, INFORMS, vol. 51(4), pages 1288-1303, November.
    10. Goeke, D. & Schneider, M., 2015. "Routing a Mixed Fleet of Electric and Conventional Vehicles," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65939, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    11. Goeke, Dominik, 2019. "Granular tabu search for the pickup and delivery problem with time windows and electric vehicles," European Journal of Operational Research, Elsevier, vol. 278(3), pages 821-836.
    12. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    13. Hiermann, Gerhard & Hartl, Richard F. & Puchinger, Jakob & Vidal, Thibaut, 2019. "Routing a mix of conventional, plug-in hybrid, and electric vehicles," European Journal of Operational Research, Elsevier, vol. 272(1), pages 235-248.
    14. Pelletier, Samuel & Jabali, Ola & Laporte, Gilbert, 2019. "The electric vehicle routing problem with energy consumption uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 225-255.
    15. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.
    16. Cortés-Murcia, David L. & Prodhon, Caroline & Murat Afsar, H., 2019. "The electric vehicle routing problem with time windows, partial recharges and satellite customers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 184-206.
    17. Markov, Iliya & Varone, Sacha & Bierlaire, Michel, 2016. "Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 256-273.
    18. Sadati, Mir Ehsan Hesam & Çatay, Bülent, 2021. "A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    19. Jie, Wanchen & Yang, Jun & Zhang, Min & Huang, Yongxi, 2019. "The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology," European Journal of Operational Research, Elsevier, vol. 272(3), pages 879-904.
    20. Zhang, Shuai & Gajpal, Yuvraj & Appadoo, S.S. & Abdulkader, M.M.S., 2018. "Electric vehicle routing problem with recharging stations for minimizing energy consumption," International Journal of Production Economics, Elsevier, vol. 203(C), pages 404-413.

    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:52:y:2018:i:2:p:331-352. 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.