Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:2, 340-352
Volume 27, No 2, 2020, P. 43-64
UDC 519.8+518.25
I. N. Kulachenko and P. A. Kononova
A hybrid local search algorithm for consistent periodic vehicle routing problem
Abstract:
Under consideration is some new real-world application of vehicle routing planning in a finite time horizon. Let a company have a set of capacitated vehicles in depots and serve a set of customers. There is a frequency for each customer which describes how often the customer should be visited. Time intervals between two consecutive visits are fixed, but the visiting schedule is flexible. To obtain competitive advantages, the company tries to increase the service quality. To this end, each customer should be visited by one driver only. The goal is to minimize the total length of the vehicle paths over the planning horizon under the frequency constraints and driver shift length constraints.
We present a mixed-integer linear programming model for this new consistent capacitated vehicle routing problem. To find near optimal solutions, we design the variable neighborhood search metaheuristic with several neighborhood structures. The driver shift length and capacitated constraints are penalized and included into the objective function. Some numerical results for the real-test cases are discussed.
Tab. 6, illustr. 1, bibliogr. 28.
Keywords: penalty method, metaheuristic, Kernighan–Lin neighborhood, vehicle of limited capacity.
DOI: 10.33048/daio.2020.27.673
Igor N. Kulachenko 1
Polina A. Kononova 2
1. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
2. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: soge.ink@gmail.com, pkononova@math.nsc.ru
Received October 31, 2019
Revised December 27, 2019
Accepted February 19, 2020
References
[1] G. B. Dantzig and J. H. Ramser, The truck dispatching problem, Manage. Sci. 6 (1), 80–91 (1959).[2] S. Salhi, A. Imran, and N. A. Wassan, The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation, Comput. Oper. Res. 52, 315 – 325 (2014).
[3] N. Christofides and J. E. Beasley, The period routing problem, Networks 14 (2), 237–256 (1984).
[4] A. A. Kovacs, S. N. Parragh, and R. F. Hartl, A template-based adaptive large neighborhood search for the consistent vehicle routing problem, Networks 63 (1), 60–81 (2014).
[5] M. Gaudioso and G. Paletta, A heuristic for the periodic vehicle routing problem, Transp. Sci. 26 (2), 86–92 (1992).
[6] C. Groër, B. Golden, and E. Wasil, The consistent vehicle routing problem, Manuf. Serv. Oper. Manage. 11 (4), 630–643 (2009).
[7] E.-G. Talbi, Metaheuristics: From design to implementation (Wiley, Hoboken, NJ, 2009).
[8] N. Mladenovic and P. Hansen, Variable neighborhood search, Comput. Oper. Res. 24, 1097–1100 (1997).
[9] P. Hansen and N. Mladenovic, Developments of variable neighborhood search, in Essays and Surveys in Metaheuristics (Springer, New York, 2002), pp. 415–439.
[10] B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J. 49 (2), 291–307 (1970).
[11] P. A. Kononova and Yu. A. Kochetov, The variable neighborhood search for the two machine flow shop problem with a passive prefetch, Diskretn. Anal. Issled. Oper. 19 (5), 63–82 (2012) [Russian] [J. Appl. Ind. Math. 7 (1), 54–67 (2013)].
[12] I. N. Kulachenko and P. A. Kononova, The VNS approach for a consistent capacitated vehicle routing problem under the shift length constraints, Commun. Comput. Inf. Sci. 1090, 51–67 (2019).
[13] I. N. Kulachenko, P. A. Kononova, Yu. A. Kochetov, and A. A. Kurochkin, The variable neighborhood search for a consistent vehicle routing problem under the shift length constraints, IFAC-PapersOnLine 52 (13), 2314–2319 (2019).
[14] E. H. L. Aarts and J. K. Lenstra, Local Search in Combinatorial Optimization (Wiley, Chichester, 1997).
[15] The Vehicle Routing Problem: Latest Advances and New Challenges (Springer, New York, 2008).
[16] L. K. Grover, Local search and the local structure of NP-complete problems, Oper. Res. Lett. 12 (4), 235–243 (1992).
[17] E. V. Alekseeva, Yu. A. Kochetov, and A. A. Plyasunov, Complexity of local search for the $p$-median problem, Eur. J. Oper. Res. 191 (3), 736–752 (2008).
[18] G. Z. Gutin and A. Yeo, Small diameter neighbourhood graphs for the traveling salesman problem: At most four moves from tour to tour, Comput. Oper. Res. 26 (4), 321–327 (1999).
[19] R. K. Ahuja, Ö. Ergun, J. B. Orlin, and A. P. Punnen, A survey of very large-scale neighborhood search techniques, Discrete Appl. Math. 123 (1–3), 75–102 (2002).
[20] Yu. A. Kochetov, Computational bounds for local search in combinatorial optimization, Zh. Vychisl. Mat. Mat. Fiz. 48 (5), 788–807 (2008) [Russian] [Comput. Math. Math. Phys. 48 (5), 747–763 (2008)].
[21] P. Toth and D. Vigo, Vehicle Routing: Problems, Methods, and Applications (SIAM, Philadelphia, PA, 2014).
[22] Yu. A. Kochetov, P. A. Kononova, and M. G. Paschenko, Formulation space search approach for the teacher/class timetabling problem, Yugosl. J. Oper. Res. 18 (1), 1–11 (2008).
[23] V. C. Hemmelmayr, K. F. Doerner, and R. F. Hartl, A variable neighborhood search heuristic for periodic routing problems, Eur. J. Oper. Res. 195 (3), 791–802 (2009).
[24] Yu. A. Kochetov and A. V. Khmelev, A hybrid algorithm of local search for the heterogeneous fixed fleet vehicle routing problem, Diskretn. Anal. Issled. Oper. 22 (5), 5–29 (2015) [Russian] [J. Appl. Ind. Math. 9 (4), 503–518 (2015)].
[25] A. V. Khmelev and Yu. A. Kochetov, A hybrid VND method for the split delivery vehicle routing problem, Electron. Notes Discrete Math. 47, 5–12 (2015).
[26] I. A. Davydov, Yu. A. Kochetov, and E. Carrizosa, A local search heuristic for the (r|p)-centroid problem in the plane, Comput. Oper. Res. 52, 334–340 (2014).
[27] Z. S. Diakova and Yu. A. Kochetov, A double VNS heuristic for the facility location and pricing problem, Electron. Notes Discrete Math. 39, 29–34 (2012).
[28] I. A. Davydov, Yu. A. Kochetov, and E. Carrizosa, VNS heuristic for the (r|p)-centroid problem on the plane, Electron. Notes Discrete Math. 39, 5–12 (2012).
