A hybrid local search algorithm for consistent periodic vehicle routing problem

I. N. Kulachenko ; P. A. Kononova

Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 43-64.

Résumé

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.

Détail

Keywords: penalty method, metaheuristic, Kernighan–Lin neighborhood, vehicle of limited capacity.

Bibliographie

[1] Dantzig G. B., Ramser J. H., “The truck dispatching problem”, Manage. Sci., 6:1 (1959), 80–91 | DOI | MR | Zbl

[2] Salhi S., Imran A., Wassan N. A., “The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation”, Comput. Oper. Res., 52 (2014), 315–325 | DOI | MR | Zbl

[3] Christofides N., Beasley J. E., “The period routing problem”, Networks, 14:2 (1984), 237–256 | DOI | MR | Zbl

[4] Kovacs A. A., Parragh S. N., Hartl R. F., “A template-based adaptive large neighborhood search for the consistent vehicle routing problem”, Networks, 63:1 (2014), 60–81 | DOI | MR | Zbl

[5] Gaudioso M., Paletta G., “A Heuristic for the Periodic Vehicle Routing problem”, Transport. Sci., 26:2 (1992), 86–92 | DOI | Zbl

[6] Groër C., Golden B., Wasil E., “The consistent vehicle routing problem”, Manufacturing Service Operations Manage, 11:4 (2009), 630–643 | DOI | MR

[7] Talbi E.-G., Metaheuristics: From design to implementation, Wiley, Hoboken, NJ, 2009 | Zbl

[8] Mladenović N., Hansen P., “Variable neighborhood search”, Comput. Oper. Res., 24 (1997), 1097–1100 | DOI | MR | Zbl

[9] Hansen P., Mladenović N., “Developments of variable neighborhood search”, Essays and surveys in metaheuristics, Springer, New York, 2002, 415–439 | DOI | MR

[10] Kernighan B. W., Lin S., “An efficient heuristic procedure for partitioning graphs”, Bell Syst. Tech. J., 49:2 (1970), 291–307 | DOI | Zbl

[11] P. A. Kononova, Yu. A. Kochetov, “The variable neighborhood search for the two machine flow shop problem with a passive prefetch”, J. Appl. Ind. Math., 7:1 (2013), 54–67 | DOI | MR | MR | Zbl

[12] Kulachenko I. N., Kononova P. A., “The VNS approach for a consistent capacitated vehicle routing problem under the shift length constraints”, Commun. Comput. Inform. Sci., 1090 (2019), 51–67 | DOI

[13] Kulachenko I. N., Kononova P. A., Kochetov Yu. A., Kurochkin A. A., “The variable neighborhood search for a consistent vehicle routing problem under the shift length constraints”, IFAC-PapersOnLine, 52:13 (2019), 2314–2319 | DOI

[14] Aarts E. H. L., Lenstra J. K., Local search in combinatorial optimization, Wiley, Chichester, 1997 | MR

[15] The vehicle routing problem: Latest advances and new challenges, Springer, New York, 2008 | Zbl

[16] Grover L. K., “Local search and the local structure of NP-complete problems”, Oper. Res. Lett., 12:4 (1992), 235–243 | DOI | MR | Zbl

[17] Alekseeva E. V., Kochetov Yu. A., Plyasunov A. A., “Complexity of local search for the $p$-median problem”, Eur. J. Oper. Res., 191:3 (2008), 736–752 | DOI | MR | Zbl

[18] Gutin G. Z., Yeo A., “Small diameter neighbourhood graphs for the traveling salesman problem: at most four moves from tour to tour”, Comput. Oper. Res., 26:4 (1994), 321–327 | DOI | MR

[19] Ahuja R. K., Ergun Ö., Orlin J. B., Punnen A. P., “A survey of very large-scale neighborhood search techniques”, Discrete Appl. Math., 123:1–3 (2002), 75–102 | DOI | MR | Zbl

[20] Yu. A. Kochetov, “Computational bounds for local search in combinatorial optimization”, Comput. Math. Math. Phys., 48:5 (2008), 747–763 | DOI | MR | Zbl

[21] Toth P., Vigo D., Vehicle routing: Problems, methods, and applications, SIAM, Philadelphia, PA, 2014 | MR | Zbl

[22] Kochetov Yu. A., Kononova P. A., Paschenko M. G., “Formulation space search approach for the teacher/class timetabling problem”, Yugoslav J. Oper. Res., 18:1 (2008), 1–11 | DOI | MR | Zbl

[23] Hemmelmayr V. C., Doerner K. F., Hartl R. F., “A variable neighborhood search heuristic for periodic routing problems”, Eur. J. Oper. Res., 195:3 (2009), 791–802 | DOI | Zbl

[24] Yu. A. Kochetov, A. V. Khmelev, “A hybrid algorithm of local search for the heterogeneous fixed fleet vehicle routing problem”, J. Appl. Ind. Math., 9:4 (2015), 503–518 | DOI | MR | MR | Zbl

[25] Khmelev A. V., Kochetov Yu. A., “A hybrid VND method for the split delivery vehicle routing problem”, Electron. Notes Discrete Math., 47 (2015), 5–12 | DOI | MR | Zbl

[26] Davydov I. A., Kochetov Yu. A., Carrizosa E., “A local search heuristic for the $(r|p)$-centroid problem in the plane”, Comput. Oper. Res., 52 (2014), 334–340 | DOI | MR | Zbl

[27] Diakova Z. S., Kochetov Yu. A., “A double VNS heuristic for the facility location and pricing problem”, Electron. Notes Discrete Math., 39 (2012), 29–34 | DOI | MR | Zbl

[28] Davydov I. A., Kochetov Yu. A., Carrizosa E., “VNS heuristic for the $(r|p)$-centroid problem on the plane”, Electron. Notes Discrete Math., 39 (2012), 5–12 | DOI | MR | Zbl