A note on “A unified solution framework for multi-attribute vehicle routing problems”

Overview & Synopsis

In this note, the authors propose correcting one erroneous formula from [Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2014). A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research, 234(3), 658-673] in charge of lunch breaks. In the original paper, the authors propose to compute several attribute values from the solution of a vehicle routing problem; like the earliest and latest starting time for sequences of customers to visit. The computed values allow us to quickly evaluate the feasibility and the marginal cost of some neighbor solutions. Several variants of the class of vehicle routing problems can be addressed using this approach. In the case of drivers' lunch break scheduling, the proposed formula combines optimistic values for the earliest and the latest completion times of the sequence of customers to visit. Using these values to evaluate neighbor solutions, may conclude that unfeasible solutions are feasible, or underestimate the completion time of a driver's route. In this note, we describe a counterexample to identify the error in the formula. We also adapt the formula to the correct result.