Cumulative VRP with Time Windows: A Trade-Off Analysis

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
208 Downloads (Pure)


In this work, the Cumulative Vehicle Routing Problem (CumVRP) is studied. It is a routing optimization problem, in which the objective is to construct a set of vehicle routes with the minimum cumulative cost in terms of distance and weight over a traveled arc. The CumVRP can be defined with hard and soft time windows constraints for incorporating customer service. To tackle this problem, a matheuristic approach based on combining mathematical programming and an iterative metaheuristic algorithm Greedy Randomized Adaptive Search Procedure (GRASP) is proposed. In each step of our approach, a feasible solution (set of routes) is built using GRASP, and, afterward, the solution is optimized using a MILP optimizer. The main objective of this research is to analyze the trade-off between the environmental cost produced by the delivery of goods complying with the limits of time windows and the customer’s dissatisfaction when these limits are violated at a certain time limit previously defined. The results show that the environmental cost is reduced if the violation of the upper limits of the customers’ time windows is allowed. These violations generate a cost associated with penalties that are well balanced with respect to the reduction of emissions.

Original languageEnglish
Title of host publicationComputational Logistics - 11th International Conference, ICCL 2020, Proceedings
EditorsEduardo Lalla-Ruiz, Martijn Mes, Stefan Voß
Number of pages15
ISBN (Electronic)978-3-030-59747-4
ISBN (Print)978-3-030-59746-7
Publication statusPublished - 22 Sept 2020
Event11th International Conference on Computational Logistics, ICCL 2020 - Online conference, Enschede, Netherlands
Duration: 28 Sept 202030 Sept 2020
Conference number: 11

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference11th International Conference on Computational Logistics, ICCL 2020
Abbreviated titleICCL
Internet address


  • Cumulative Vehicle Routing Problem
  • Green VRP
  • Matheuristic
  • MILP
  • Time windows


Dive into the research topics of 'Cumulative VRP with Time Windows: A Trade-Off Analysis'. Together they form a unique fingerprint.

Cite this