The cumulative vehicle routing problem with time windows: models and algorithm

Alejandro Fernández Gil (), Eduardo Lalla-Ruiz (), Mariam Gómez Sánchez () and Carlos Castro ()
Additional contact information
Alejandro Fernández Gil: Universidad Técnica Federico Santa María
Eduardo Lalla-Ruiz: University of Twente
Mariam Gómez Sánchez: Universidad Técnica Federico Santa María
Carlos Castro: Universidad Técnica Federico Santa María

Annals of Operations Research, 2025, vol. 350, issue 1, No 12, 325-353

Abstract: Abstract The cumulative vehicle routing problem with time windows (CumVRP-TW) is a vehicle routing variant that aims at minimizing a cumulative cost function while respecting customers’ time windows constraints. Mathematical formulations are proposed for soft and hard time windows constraints, where for the soft case, violations are permitted subject to penalization. By means of the cumulative objective and the time windows consideration, routing decisions incorporate the environmental impact related to CO $$_2$$ 2 emissions and permit obtaining a trade-off between emissions and time windows fulfillment. To solve this problem, we propose a matheuristic approach that combines the features of the Greedy Randomized Adaptive Search Procedure (GRASP) with the exact solution of the optimization model. The solution approaches are tested on instances proposed in the literature as well as on a new benchmark suite proposed for assessing the soft time windows variant. The computational results show that the mathematical formulations provide optimal solutions for scenarios of 10, 20, and several of 50 customers within suitable computational times. Nevertheless, the same performance is not observed for several medium as well as for all large scenarios. In those cases, the proposed matheuristic algorithm is able to report feasible and improved routes for those instances where the exact solver does not report good results. Finally, we verify that the fuel consumption and carbon emissions are reduced when the violation of the time windows is allowed in the case of soft time windows.

Keywords: Cumulative vehicle routing problem with time windows; Green VRP; Matheuristic; Soft time windows; Fuel consumption (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-022-05102-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:350:y:2025:i:1:d:10.1007_s10479-022-05102-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-022-05102-7

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().