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

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