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

Alejandro Fernández Gil*, Eduardo Lalla-Ruiz, Mariam Gómez Sánchez, Carlos Castro

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
55 Downloads (Pure)


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 CO2 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.

Original languageEnglish
JournalAnnals of operations research
Publication statusE-pub ahead of print/First online - 31 Jan 2023


  • Cumulative vehicle routing problem with time windows
  • Fuel consumption
  • Green VRP
  • Matheuristic
  • Soft time windows
  • 2023 OA procedure


Dive into the research topics of 'The cumulative vehicle routing problem with time windows: models and algorithm'. Together they form a unique fingerprint.

Cite this