TY - JOUR
T1 - The cumulative vehicle routing problem with time windows
T2 - models and algorithm
AU - Fernández Gil, Alejandro
AU - Lalla-Ruiz, Eduardo
AU - Gómez Sánchez, Mariam
AU - Castro, Carlos
N1 - Funding Information:
This research was partially supported by ANID-PFCHA/Doctorado Nacional /2020-21200871 and CONICYT-PFCHA (Doctorado Nacional /2017-21171857), and Programa de Incentivo a la Iniciación Científica (PIIC, UTFSM).
Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2023/1/31
Y1 - 2023/1/31
N2 - 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.
AB - 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.
KW - 2023 OA procedure
KW - Fuel consumption
KW - Green VRP
KW - Matheuristic
KW - Soft time windows
KW - Cumulative vehicle routing problem with time windows
UR - http://www.scopus.com/inward/record.url?scp=85147115201&partnerID=8YFLogxK
U2 - 10.1007/s10479-022-05102-7
DO - 10.1007/s10479-022-05102-7
M3 - Article
AN - SCOPUS:85147115201
SN - 0254-5330
JO - Annals of operations research
JF - Annals of operations research
ER -