IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i24p4644-d997026.html
   My bibliography  Save this article

Local Optima Network Analysis of Multi-Attribute Vehicle Routing Problems

Author

Listed:
  • Sebastián Muñoz-Herrera

    (Departamento de Ingeniería Industrial, Universidad Católica de la Santísima Concepción, Alonso de Ribera 2850, Concepcion 4090541, Chile
    Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Av. Diagonal las Torres 2640, Santiago 7941169, Chile
    These authors contributed equally to this work.)

  • Karol Suchan

    (Escuela de Informática y Telecomunicaciones, Facultad de Ingeniería y Ciencias, Universidad Diego Portales, Av. Ejército Libertador 441, Santiago 8370191, Chile
    Faculty of Applied Mathematics, AGH University of Science and Technology, al. A. Mickiewicza 30, 30-059 Krakow, Poland
    These authors contributed equally to this work.
    Current address: Facultad de Ingeniería y Ciencias, Universidad Diego Portales, Av. Ejército Libertador 441, Santiago 8370191, Chile.)

Abstract

Multi-Attribute Vehicle Routing Problems (MAVRP) are variants of Vehicle Routing Problems (VRP) in which, besides the original constraint on vehicle capacity present in Capacitated Vehicle Routing Problem (CVRP), other attributes that model diverse real-life system characteristics are present. Among the most common attributes studied in the literature are vehicle capacity and route duration constraints. The influence of these restrictions on the overall structure of the problem and the performance of local search algorithms used to solve it has yet to be well known. This paper aims to explain the impact of constraints present in different variants of VRP through the alterations of the structure of the underlying search space that they cause. We focus on Local Optima Network Analysis (LONA) for multiple Traveling Salesman Problem (m-TSP) and VRP with vehicle capacity (CVRP), route duration (DVRP), and both (DCVRP) constraints. We present results that indicate that measures obtained for a sample of local optima provide valuable information on the behavior of the landscape under modifications in the problem’s constraints. Additionally, we use the LONA measures to explain the difficulty of VRP instances for solving by local search algorithms.

Suggested Citation

  • Sebastián Muñoz-Herrera & Karol Suchan, 2022. "Local Optima Network Analysis of Multi-Attribute Vehicle Routing Problems," Mathematics, MDPI, vol. 10(24), pages 1-21, December.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:24:p:4644-:d:997026
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/24/4644/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/24/4644/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    2. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    3. Bektas, Tolga, 2006. "The multiple traveling salesman problem: an overview of formulations and solution procedures," Omega, Elsevier, vol. 34(3), pages 209-219, June.
    4. Gabriela Ochoa & Nadarajen Veerapen, 2018. "Mapping the global structure of TSP fitness landscapes," Journal of Heuristics, Springer, vol. 24(3), pages 265-294, June.
    5. Van Breedam, Alex, 1995. "Improvement heuristics for the Vehicle Routing Problem based on simulated annealing," European Journal of Operational Research, Elsevier, vol. 86(3), pages 480-490, November.
    6. Liming Zheng & Shiqi Luo, 2022. "Adaptive Differential Evolution Algorithm Based on Fitness Landscape Characteristic," Mathematics, MDPI, vol. 10(9), pages 1-33, 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. Kai Huang & Michael Xu, 2023. "Optimization Models for the Vehicle Routing Problem under Disruptions," Mathematics, MDPI, vol. 11(16), pages 1-21, August.

    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. Mohamed Cissé & Semih Yalçindag & Yannick Kergosien & Evren Sahin & Christophe Lenté & Andrea Matta, 2017. "OR problems related to Home Health Care: A review of relevant routing and scheduling problems," Post-Print hal-01736714, HAL.
    2. John E. Fontecha & Oscar O. Guaje & Daniel Duque & Raha Akhavan-Tabatabaei & Juan P. Rodríguez & Andrés L. Medaglia, 2020. "Combined maintenance and routing optimization for large-scale sewage cleaning," Annals of Operations Research, Springer, vol. 286(1), pages 441-474, March.
    3. Du, Mingyang & Cheng, Lin & Li, Xuefeng & Tang, Fang, 2020. "Static rebalancing optimization with considering the collection of malfunctioning bikes in free-floating bike sharing system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    4. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    5. Bruck, Bruno P. & Cordeau, Jean-François & Iori, Manuel, 2018. "A practical time slot management and routing problem for attended home services," Omega, Elsevier, vol. 81(C), pages 208-219.
    6. Chen, Qingfeng & Li, Kunpeng & Liu, Zhixue, 2014. "Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 218-235.
    7. Fröhlich von Elmbach, Alexander & Scholl, Armin & Walter, Rico, 2019. "Minimizing the maximal ergonomic burden in intra-hospital patient transportation," European Journal of Operational Research, Elsevier, vol. 276(3), pages 840-854.
    8. 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.
    9. Ehmke, Jan Fabian & Campbell, Ann Melissa & Urban, Timothy L., 2015. "Ensuring service levels in routing problems with time windows and stochastic travel times," European Journal of Operational Research, Elsevier, vol. 240(2), pages 539-550.
    10. Jose Carlos Molina & Ignacio Eguia & Jesus Racero, 2018. "An optimization approach for designing routes in metrological control services: a case study," Flexible Services and Manufacturing Journal, Springer, vol. 30(4), pages 924-952, December.
    11. Liu, Ran & Xie, Xiaolan & Garaix, Thierry, 2014. "Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics," Omega, Elsevier, vol. 47(C), pages 17-32.
    12. Alcaraz, Juan J. & Caballero-Arnaldos, Luis & Vales-Alonso, Javier, 2019. "Rich vehicle routing problem with last-mile outsourcing decisions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 129(C), pages 263-286.
    13. Ana Maria Anaya-Arenas & Thomas Chabot & Jacques Renaud & Angel Ruiz, 2016. "Biomedical sample transportation in the province of Quebec: a case study," International Journal of Production Research, Taylor & Francis Journals, vol. 54(2), pages 602-615, January.
    14. Lai, David S.W. & Caliskan Demirag, Ozgun & Leung, Janny M.Y., 2016. "A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 86(C), pages 32-52.
    15. Gong, Manlin & Hu, Yucong & Chen, Zhiwei & Li, Xiaopeng, 2021. "Transfer-based customized modular bus system design with passenger-route assignment optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 153(C).
    16. Asbach, Lasse & Dorndorf, Ulrich & Pesch, Erwin, 2009. "Analysis, modeling and solution of the concrete delivery problem," European Journal of Operational Research, Elsevier, vol. 193(3), pages 820-835, March.
    17. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    18. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    19. Gerhard Hiermann & Matthias Prandtstetter & Andrea Rendl & Jakob Puchinger & Günther Raidl, 2015. "Metaheuristics for solving a multimodal home-healthcare scheduling problem," 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. 23(1), pages 89-113, March.
    20. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).

    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:gam:jmathe:v:10:y:2022:i:24:p:4644-:d:997026. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.