Local Optima Network Analysis of Multi-Attribute Vehicle Routing Problems

Sebastián Muñoz-Herrera () and Karol Suchan
Additional contact information
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
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

Mathematics, 2022, vol. 10, issue 24, 1-21

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.

Keywords: local optima network; vehicle routing problem; multiple traveling salesman problem; network analysis; fitness landscape analysis (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/24/4644/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/24/4644/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:24:p:4644-:d:997026

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().