EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Two-Stage Matheuristic for the Capacitated Arc Routing Problem with Vehicle Dependence

Hugo Alexer Pérez-Vicente, Jonás Velasco, Luis E. Urbán-Rivero

Computation · 18.08.2026 · 14 (8) · 190

DOI: 10.3390/computation14080190 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Computation, online erschienen am 18.08.2026. Verfasst von Hugo Alexer Pérez-Vicente und 2 weiteren Autor:innen. Die Arbeit nennt 46 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In the capacitated arc routing problem (CARP), a fleet of capacitated vehicles based at a depot must cover the streets of a network where the demand is located at the lowest possible total cost. Waste collection, street sweeping, winter gritting, and mail delivery are among its best-known applications. This work introduces the CARP with vehicle dependence (CARP-VD), an extension in which the cost of servicing an edge, and that of traversing it without service, are specific to each vehicle type and formulates it as a mixed-integer linear program. A two-stage matheuristic is proposed: the first stage distributes the required edges among the vehicles without exceeding their capacities, and the second builds the route of each vehicle. A bound is derived that limits the optimality loss of this decomposition by its own deadheading cost. Both approaches are evaluated on 47 benchmark instances adapted from the literature under a common one-hour budget, and their robustness is assessed over six scenarios that vary the parameters of the adaptation. The matheuristic returns good-quality solutions in a fraction of the time on the smaller instances, and on those in which almost every edge requires service it improves the best solutions found by a commercial solver applied to the complete model by up to 44%.

Zitieren

APA

Pérez-Vicente, H. A., Velasco, J., & Urbán-Rivero, L. E. (2026). A Two-Stage Matheuristic for the Capacitated Arc Routing Problem with Vehicle Dependence. Computation, 14(8), 190. https://doi.org/10.3390/computation14080190

Vancouver

Pérez-Vicente HA, Velasco J, Urbán-Rivero LE. A Two-Stage Matheuristic for the Capacitated Arc Routing Problem with Vehicle Dependence. Computation. 2026;14(8):190. doi:10.3390/computation14080190

BibTeX
@article{PrezVicente2026,
  author = {Pérez-Vicente, Hugo Alexer and Velasco, Jonás and Urbán-Rivero, Luis E.},
  title = {A Two-Stage Matheuristic for the Capacitated Arc Routing Problem with Vehicle Dependence},
  journal = {Computation},
  year = {2026},
  volume = {14},
  number = {8},
  pages = {190},
  doi = {10.3390/computation14080190}
}
Kostenlos starten →