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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Archetti C and Savelsbergh M (2009). The trip scheduling problem. Transportation Science 43 (4): 417–431.
Archetti C, Hertz A and Speranza MG (2007). Metaheuristics for the team orienteering problem. Journal of Heuristics 13 (1): 49–76.
Avella P, Boccia M and Sforza A (2004). Solving a fuel delivery problem by heuristic and exact approaches. European Journal of Operational Research 152 (1): 170–179.
Baltz A, El Ouali M, Jäger G, Sauerland V and Srivastav A (2014). Exact and heuristic algorithms for the travelling salesman problem with multiple time windows and hotel selection. Journal of the Operational Research Society 66: 615–626.
Benjamin AM and Beasley JE (2010). Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities. Computers & Operations Research 37 (12): 2270–2280.
Boctor FF, Renaud J and Cornillier F (2011). Trip packing in petrol stations replenishment. Omega 39 (1): 86–98.
Buhrkal K, Larsen A and Ropke S (2012). The waste collection vehicle routing problem with time windows in a city logistics context. Procedia—Social and Behavioral Sciences 39: 241–254, 2012. Seventh International Conference on City Logistics which was held on 7–9 June 2011, Mallorca, Spain.
Chao I-M, Golden BL and Wasil EA (1996). The team orienteering problem. European Journal of Operational Research 88 (3): 464–474.
Day JM, Wright PD, Schoenherr T, Venkataramanan M and Gaudette K (2009). Improving routing and scheduling decisions at a distributor of industrial gases. Omega 37 (1): 227–237.
Furman KC, Song J-H, Kocis GR, McDonald MK and Warrick PH (2011). Feedstock routing in the ExxonMobil downstream sector. Interfaces 41 (2): 149–163.
Goel A (2009). Vehicle scheduling and routing with drivers’ working hours. Transportation Science 43 (1): 17–26.
Goel A (2010). Truck driver scheduling in the European Union. Transportation Science 44 (4): 429–441.
Goel A, Archetti C and Savelsbergh M (2012). Truck driver scheduling in Australia. Computers & Operations Research 39 (5): 1122–1132.
Goel A and Kok L (2010). Truck driver scheduling in the United States. Transportation Science 46 (3): 317–326.
Goel A and Vidal T (2014). Hours of service regulations in road freight transport: An optimization-based international assessment. Transportation Science 48 (3): 391–412.
Golden BL, Assad AA and Wasil EA (2002). Routing vehicles in the real world: Applications in the solid waste, beverage, food, dairy, and newspaper industries. In: Toth P and Vigo D (eds). The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications. SIAM: Philadelphia, pp 245–286.
Kim B-I, Kim S and Sahoo S (2006). Waste collection vehicle routing problem with time windows. Computers & Operations Research 33 (12): 3624–3642.
Laporte G (2009). Fifty years of vehicle routing. Transportation Science 43 (4): 408–416.
Lin S (1965). Computer solutions of the traveling salesman problem. Bell System Technical Journal 44 (10): 2245–2269.
Osman IH (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research 41 (4): 421–451.
Privé J, Renaud J, Boctor FF and Laporte G (2006). Solving a vehicle-routing problem arising in soft-drink distribution. Journal of the Operational Research Society 57 (9): 1045–1052.
Renaud J, Boctor FF and Laporte G (1996). An improved petal heuristic for the vehicle routeing problem. Journal of the Operational Research Society 47 (2): 329–336.
Repoussis PP, Paraskevopoulos DC, Zobolas G, Tarantilis CD and Ioannou G (2009). A web-based decision support system for waste lube oils collection and recycling. European Journal of Operational Research 195 (3): 676–700.
Rochat Y and Semet F (1994). A tabu search approach for delivering pet food and our in Switzerland. Journal of the Operational Research Society 45 (11): 1233–1246.
Sahoo S, Kim S, Kim B-I, Kraas B and Popov Jr A (2005). Routing optimization for waste management. Interfaces 35 (1): 24–36.
Savelsbergh MWP (1992). The vehicle routing problem with time windows: Minimizing route duration. ORSA Journal on Computing 4 (2): 146–154.
Tarantilis CD and Kiranoudis CT (2001). A meta-heuristic algorithm for the efficient distribution of perishable foods. Journal of Food Engineering 50 (1): 1–9.
Tarantilis CD and Kiranoudis CT (2002). Distribution of fresh meat. Journal of Food Engineering 51 (1): 85–91.
Uzar MF and Çatay B (2012). Distribution planning of bulk lubricants at BP Turkey. Omega 40 (6): 870–881.
van Anholt RG, Coelho LC, Laporte G and Vis IFA (2013). An inventory-routing problem with pickups and deliveries arising in the replenishment of automated teller machines. Technical Report CIRRELT-2013-71, Montreal, Canada.
Vansteenwegen P, Souffriau W and Sörensen K (2012). The travelling salesperson problem with hotel selection. Journal of the Operational Research Society 63 (2): 207–217.
Vidal T, Crainic TG, Gesndreau M and Prins C (2014). A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research 234 (3): 658–673.
Acknowledgements
This research was partially supported by Grants OPG 0293307, OPG 0172633 and 2014-05764 from the Canadian Natural Sciences and Engineering Research Council (NSERC) and by Engage Grant CGO 98069 from NSERC. This support is gratefully acknowledged. The authors also thank Louis Leclerc, Operations Manager, and Steve Thiboutot, Information Systems Manager, from Ameublement Tanguay, for their constant availability and comments, and for providing us with relevant data. We thank an associate editor and four anonymous referees for their valuable comments on a previous version of this paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Coelho, L., Gagliardi, JP., Renaud, J. et al. Solving the vehicle routing problem with lunch break arising in the furniture delivery industry. J Oper Res Soc 67, 743–751 (2016). https://doi.org/10.1057/jors.2015.90
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2015.90