Volume 22, No 6, 2015, P. 55–77

UDC 519.85
A. V. Khmelev
A three-phase heuristic for the vehicle fleet and route optimization

Abstract:
We consider the applied vehicle routing problem with time windows. Each driver works in a given shift. Each shift has the start, finish and set of pauses which need to be scheduled en route. We introduce the mathematical formulation for this problem in terms of the mixed integer linear programming. In order to tackle large instances, we developed a three-phase local search algorithm with an effective procedure for search in neighbourhoods. Computational experiments for instances from one delivery company have shown the efficiency of the developed algorithm and significant reduction in costs.
Tab. 2, ill. 4, bibliogr. 13.

Keywords: vehicle routing, time window, work shift, pause, local search, fleet optimization.

DOI: 10.17377/daio.2015.22.496

Aleksey V. Khmelev ¹
1. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: avhmel@gmail.com

Received 3 June 2015
Revised 11 August 2015

References

[1] Yu. A. Kochetov and A. V. Khmelev, Hybrid local search for the heterogenous fixed fleet vehicle routing problem, Diskretn. Anal. Issled. Oper., 22, No. 5, 5–29, 2015.

[2] N. Bent and P. van Hentenryck, A two-stage hybrid local search for the vehicle routing problem with time windows, Transp. Sci., 38, No. 4, 515–530, 2004.

[3] N. Bostel, P. Dejax, P. Guez, and F. Tricoire, Multiperiod planning and routing on a rolling horizon for field force optimization logistics, in B. Golden, S. Raghavan, and E. Wasil, eds., The Vehicle Routing Problem: Latest Advances and New Challenges, pp. 503–525, Springer, New York, 2008 (Oper.
Res./Comput. Sci. Interfaces, Vol. 43).

[4] O. Bräysy and M. Gendreau, Vehicle routing problem with time windows. Part I: Route construction and local search algorithms, Transp. Sci., 39, No. 1, 104–118, 2005.

[5] O. Bräysy and M. Gendreau, Vehicle routing problem with time windows. Part II: Metaheuristics, Transp. Sci., 39, No. 1, 119–139, 2005.

[6] J.-Ph. Gagliardi, J. Renaud, A. Ruiz, and L. C. Coelho, The vehicle routing problem with pauses, Tech. Rep. CIRRELT-2104-22, Interuniv. Res. Cent. Enterp. Netw., Logist. Transp., Montreal, Canada, 2014. Available at https://www.cirrelt.ca/DocumentsTravail/CIRRELT-FSA-2014-22.pdf. Accessed Oct. 15, 2015.

[7] H. Gehring and J. Homberger, Parallelization of a two-phase metaheuristic for routing problems with time windows, Asia-Pac. J. Oper. Res., 18, No. 1, 35–47, 2001.

[8] A. Goel, Vehicle scheduling and routing with drivers’ working hours, Transp. Sci., 43, No. 1, 17–26, 2009.

[9] A. Goel, C. Archetti, and M. Savelsbergh, Truck driver scheduling in Australia, Comput. Oper. Res., 39, No. 5, 1122–1132, 2012.

[10] A. Goel and T. Vidal, Hours of service regulations in road freight transport: An optimization-based international assessment, Transp. Sci., 48, No. 3, 391–412, 2014.

[11] T. Mladenovic and P. Hansen, Variable neighborhood search, Comput. Oper. Res., 24, No. 11, 1097–1100, 1997.

[12] Yu. Nagata and O. Bräysy, A powerful route minimization heuristic for the vehicle routing problem with time windows, Oper. Res. Lett., 37, No. 5, 333–338, 2009.

[13] S. Sahoo, S. Kim, B.-I. Kim, B. Kraas, and A. Popov, Jr., Routing optimization for waste management, Interfaces, 35, No. 1, 24–36, 2005.

[14] T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins, A unified solution framework for multi-attribute vehicle routing problems, Eur. J. Oper. Res., 234, No. 3, 658–673, 2014.