A novel MILP formulation and an efficient heuristic for the vehicle routing problem with lunch break

The vehicle routing problem with time windows and lunch break (VRPTW-LB) is an NP-hard combinatorial optimization problem that belongs to the vehicle routing problem family. In the VRPTW-LB, each vehicle must serve assigned customers within their availability periods and take a mandatory break within its time slot for a given duration. This paper proposes a new mixed integer linear programming (MILP) formulation for the VRPTW-LB. The new MILP formulation is based on the idea of the intersection of two intervals, which must be non-empty. It provides a flexible schedule for lunch breaks by defining the earliest and latest start times at which each break can be taken, instead of defining its exact start time. A comparative study of MILP formulations from the literature and the proposed one is performed, which are tested on benchmark instances from the literature. These MILP formulations are powerless to solve large-scale instances. To overcome this limitation, an efficient lunch break scheduling algorithm is proposed and embedded into a simulated annealing (SA) based heuristic. Computational results highlight the competitiveness of the new MILP formulation with respect to other MILP formulations and the efficiency of the proposed heuristic in obtaining high-quality solutions in short CPU running times.