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

Mohammed Bazirha ()
Additional contact information
Mohammed Bazirha: INSEA

Annals of Operations Research, 2025, vol. 351, issue 1, No 10, 253-278

Abstract: Abstract 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.

Keywords: Lunch break; Time windows; Mathematical modeling; Vehicle routing problem; Simulated annealing (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-023-05742-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:351:y:2025:i:1:d:10.1007_s10479-023-05742-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-023-05742-3

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().