A Two-Stage Matheuristic for the Capacitated Arc Routing Problem with Vehicle Dependence
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).
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}
}
EUVIMED