A multi-shift vehicle routing problem with windows and cycle times. (English) Zbl 1273.90032

Summary: In many applications of the vehicle routing problem with time windows (VRPTW), goods must be picked up within desired time frames. In addition, they have some limitations on their arrival time to the central depot. In this paper, we present a new version of VRPTW that minimizes the total cycle time of the goods. In order to meet the time windows and also to minimize the cycle time, the courier’s schedule is allowed to vary. An algorithm named VeRSA is proposed to solve this problem. VeRSA employs concepts of scheduling theorems and algorithms to determine feasible routes and schedules of the available couriers. We prove a theoretical lower bound that provides a useful bound on the optimality gap. We also conduct a set of numerical experiments. VeRSA obtains a feasible solution faster than solving the MIP. The optimality gap using our proposed lower bound is smaller than the gap found with the standard LP relaxation.


90B06 Transportation, logistics and supply chain management
90B35 Deterministic scheduling theory in operations research


Full Text: DOI


[1] Angelelli E., Grazia Speranza M., Savelsbergh M.W.P.: Competitive analysis for dynamic multiperiod uncapacitated routing problems. Networks 49, 308–317 (2007) · Zbl 1141.90334
[2] Kallehauge, B., Larsen, J., Madsen, O.B.G., Solomon, M.M.: Vehicle routing problem with time windows. Column Gener., 67–98 (2005) · Zbl 1130.90316
[3] Lee Y.H., Pinedo M.: Scheduling jobs on parallel machines with sequence-dependent setup times. Eur. J. Oper. Res. 100, 464–474 (1997) · Zbl 0917.90193
[4] Pinedo M.: Scheduling: theory, algorithms, and systems. Springer, Berlin (2008) · Zbl 1155.90008
[5] Ren Y., Dessouky M., Ordóñez F.: The multi-shift vehicle routing problem with overtime. Comput. Oper. Res. 37, 1987–1998 (2010) · Zbl 1188.90038
[6] Toth P., Vigo D.: The vehicle routing problem. Society for Industrial Mathematics, Canada (2002) · Zbl 0979.00026
[7] Wolsey L.A: Integer programming. Wiley, NY (1998) · Zbl 0930.90072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.