Solving the vehicle routing problem with lunch break arising in the furniture delivery industry

Leandro C Coelho, Jean-Philippe Gagliardi, Jacques Renaud and Angel Ruiz
Additional contact information
Leandro C Coelho: CIRRELT and Université Laval, Québec, Canada
Jean-Philippe Gagliardi: CIRRELT and Université Laval, Québec, Canada
Jacques Renaud: CIRRELT and Université Laval, Québec, Canada
Angel Ruiz: CIRRELT and Université Laval, Québec, Canada

Journal of the Operational Research Society, 2016, vol. 67, issue 5, 743-751

Abstract: In this paper, we solve the Vehicle Routing Problem with Lunch Break (VRPLB), which arises when drivers must take pauses during their shift, for example, for lunch breaks. Driver breaks have already been considered in long haul transportation when drivers must rest during their travel, but the underlying optimization problem remains difficult and few contributions can be found for less than truckload and last mile distribution contexts. This problem, which appears in the furniture delivery industry, includes rich features such as time windows and heterogeneous vehicles. In this paper, we evaluate the performance of a new mathematical formulation for the VRPLB and of a fast and high performing heuristic. The mixed integer linear programming formulation has the disadvantage of roughly doubling the number of nodes, and thus significantly increasing the size of the distance matrix and the number of variables. Consequently, standard branch-and-bound algorithms are only capable of solving small-sized instances. In order to tackle large instances provided by an industrial partner, we propose a fast multi-start randomized local search heuristic tailored for the VRPLB, which is shown to be very efficient. Through a series of computational experiments, we show that solving the VRPLB without explicitly considering the pauses during the optimization process can lead to a number of infeasibilities. These results demonstrate the importance of integrating drivers pauses in the resolution process.

Date: 2016
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.palgrave-journals.com/jors/journal/v67/n5/pdf/jors201590a.pdf Link to full text PDF (application/pdf)
http://www.palgrave-journals.com/jors/journal/v67/n5/full/jors201590a.html Link to full text HTML (text/html)
Access to full text is restricted to subscribers.

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:pal:jorsoc:v:67:y:2016:i:5:p:743-751

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().