The multi‐shift vehicle routing problem with overtime

The multi‐shift vehicle routing problem with overtime

0.00 Avg rating0 Votes
Article ID: iaor20123269
Volume: 37
Issue: 11
Start Page Number: 1987
End Page Number: 1998
Publication Date: Nov 2010
Journal: Computers and Operations Research
Authors: , ,
Keywords: combinatorial optimization
Abstract:

In this paper, we study a new variant of the vehicle routing problem (VRP) with time windows, multi‐shift, and overtime. In this problem, a limited fleet of vehicles is used repeatedly to serve demand over a planning horizon of several days. The vehicles usually take long trips and there are significant demands near shift changes. The problem is inspired by a routing problem in healthcare, where the vehicles continuously operate in shifts, and overtime is allowed. We study whether the tradeoff between overtime and other operational costs such as travel cost, regular driver usage, and cost of unmet demands can lead to a more efficient solution. We develop a shift dependent (SD) heuristic that takes overtime into account when constructing routes. We show that the SD algorithm has significant savings in total cost as well as the number of vehicles over constructing the routes independently in each shift, in particular when demands are clustered or non‐uniform. Lower bounds are obtained by solving the LP relaxation of the MIP model with specialized cuts. The solution of the SD algorithm on the test problems is within 1.09–1.82 times the optimal solution depending on the time window width, with the smaller time windows providing the tighter bounds.

Reviews

Required fields are marked *. Your email address will not be published.