Çok periyotlu araç rotalama problemi için mantık temelli bir Benders ayrıştırma yöntemi

Abstract

Çok periyotlu araç rotalama problemi, müşteri taleplerinin birden fazla döneme yayılan bir planlama ufku içinde karşılanmasını gerektiren, klasik araç rotalama probleminin daha genel ve karmaşık bir türüdür. Bu problemde hem rotalama hem de müşteri ziyaret sıklıklarının belirlenmesi gerekir, bu da onu pratikte karşılaşılan lojistik uygulamaları için oldukça önemli hale getirmektedir. Bu çalışmada problem için yönsüz kesi temelli bir tam sayılı programlama formülasyonu önerilmiş ve mantık temelli Benders ayrıştırmasına dayalı özgün bir kesin çözüm yöntemi geliştirilmiştir. Ana problem genelleştirilmiş atama problemi şeklinde tanımlanırken, alt problemler her dönem için bağımsız araç rotalama problemleri olarak ele alınmıştır. Çalışmada iki farklı algoritma versiyonu sunulmuş, biri kesen düzlem tabanlı yinelemeli bir çözüm süreci takip ederken, diğeri ise ticari çözücünün geri çağırma fonksiyonundan faydalanmaktadır. Yapılan hesaplama deneyleri, her iki algoritmanın da küçük ölçekli örneklerde etkin olduğunu, özellikle ikinci versiyonun büyük ölçekli örneklerde çok daha üstün performans gösterdiğini ortaya koymuştur. Elde edilen bulgular, mantık temelli Benders ayrıştırmasının çok periyotlu araç rotalama probleminin çözümünde umut vadeden bir yöntem olduğunu göstermektedir.

Keywords

• Araç rotalama
• Çok periyotlu rotalama
• Mantık temelli Benders ayrıştırma
• Kesin çözüm algoritmaları

A Logic-Based Benders decomposition framework for the multi-period vehicle routing problem

Abstract

The period vehicle routing problem is a generalized and a more complex version of the classical vehicle routing problem where customer demands must be fulfilled over a planning horizon spanning multiple periods. In this problem, both routing and customer visit frequency decisions must be addressed simultaneously, which makes it highly relevant for real-life logistics and distribution settings. This study proposes an undirected cut-based mathematical model for the problem and develops a logic-based Benders decomposition framework as a novel exact solution method. The master problem is formulated as a generalized assignment problem, while the subproblems are defined as independent vehicle routing problems for each period. Two algorithmic variants are presented: one follows a cutting plane-based, iterative cut solution process while the other exploits callback functionalities of a commercial solver. Computational experiments demonstrate that both approaches are effective on small instances, while the second variant achieves superior performance on larger instances. The results highlight the potential of logic-based Benders decomposition as a promising approach for solving the period vehicle routing problem.

Keywords

• Vehicle routing
• Multi-period routing
• Logic-based Benders decomposition
• Exact algorithms

References

1. [1] Beltrami EJ, Bodin LD. “Networks and vehicle routing for municipal waste collection”. Networks, 4(1), 65-94, 1974.
2. [2] Elbek M, Wøhlk S. “A variable neighborhood search for the multi-period collection of recyclable materials”. European Journal of Operational Research, 249(2), 540-550, 2016.
3. [3] Çopur O, Yıldız M, Göven S, Güneri AÖ, Yavuz AB, Gökçe MA, Yurtseven C. “Periodic route optimization for FMCG distributors”. International Conference on Production Research (ICPR), Chicago, IL, USA, 9-15 August 2019.
4. [4] Alves F, Alvelos FP, Rocha AMA, Pereira AI, Leitao P. “Periodic vehicle routing problem in a health unit”. International Conference on Operations Research and Enterprise Systems (ICORES), Prague, Czech Republic, 19-21 February 2019.
5. [5] Foster BA, Ryan DM. “An integer programming approach to the vehicle scheduling problem”. Journal of the Operational Research Society, 27(2), 367-384, 1976.
6. [6] Christofides N, Beasley JE. “The period routing problem”. Networks, 14(2), 237-256, 1984.
7. [7] Russell R, Igo W. “An assignment routing problem”. Networks, 9(1), 1-17, 1979.
8. [8] Campbell AM, Wilson JH. “Forty years of periodic vehicle routing”. Networks, 63(1), 2-15, 2014.

9. [9] Cordeau JF, Gendreau M, Laporte G. “A tabu search heuristic for periodic and multi-depot vehicle routing problems”. Networks, 30(2), 105-119, 1997.
10. [10] Huerta-Muñoz DL. The flexible periodic vehicle routing problem: modeling alternatives and solution techniques. Doktora tezi, Universitat Politècnica de Catalunya, Barcelona, Spain, 2018.
11. [11] Tan CCR, Beasley JE. “A heuristic algorithm for the period vehicle routing problem”. Omega, 12(5), 497-504, 1984.
12. [12] Fisher ML, Jaikumar R. “A generalized assignment heuristic for vehicle routing”. Networks, 11(2), 109-124, 1981.
13. [13] Archetti C, Fernández E, Huerta-Muñoz DL. “The flexible periodic vehicle routing problem”. Computers & Operations Research, 85, 58-70, 2017.
14. [14] Baldacci R, Bartolini E, Mingozzi A, Valletta A. “An exact algorithm for the period routing problem”. Operations Research, 59(1), 228-241, 2011.
15. [15] Cacchiani V, Hemmelmayr VC, Tricoire F. “A set-covering based heuristic algorithm for the periodic vehicle routing problem”. Discrete Applied Mathematics, 163, 53-64, 2014.
16. [16] Rothenbächer AK. “Branch-and-price-and-cut for the periodic vehicle routing problem with flexible schedule structures”. Transportation Science, 53(3), 850-866, 2019.
17. [17] Bettinelli A, Ceselli A, Righini G. “A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows”. Transportation Research Part C: Emerging Technologies, 19(5), 723-740, 2011.
18. [18] Contardo C, Martinelli R. “A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints”. Discrete Optimization, 12, 129-146, 2014.
19. [19] Toru E, Yılmaz G. “Günlük planlanmış bakım ve onarım servis planlaması için zaman pencereli birçok depolu araç rotalama problemi”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 29(8), 913-919, 2023.
20. [20] Francis P, Smilowitz K, Tzur M. “The period vehicle routing problem with service choice”. Transportation Science, 40(4), 439-454, 2006.
21. [21] Archetti C, Jabali O, Speranza MG. “Multi-period vehicle routing problem with due dates”. Computers & Operations Research, 61, 122-134, 2015.
22. [22] Larrain H, Coelho LC, Archetti C, Speranza MG. “Exact solution methods for the multi-period vehicle routing problem with due dates”. Computers & Operations Research, 110, 148-158, 2019.
23. [23] Rodríguez-Martín I, Salazar-González JJ, Yaman H. “The periodic vehicle routing problem with driver consistency”. European Journal of Operational Research, 273(2), 575-584, 2019.
24. [24] Cordeau JF, Laporte G, Mercier A. “A unified tabu search heuristic for vehicle routing problems with time windows”. Journal of the Operational Research Society, 52(8), 928-936, 2001.
25. [25] Basir SA, Şahin G, Özbaygın G. “A comparative study of alternative formulations for the periodic vehicle routing problem”. Computers & Operations Research, 165, 106583, 2024.
26. [26] Benders JF. “Partitioning procedures for solving mixed-variables programming problems”. Numerische Mathematik, 4(1), 238-252, 1962.
27. [27] Hooker J. Logic-Based Methods for Optimization: Combining Optimization And Constraint Satisfaction. John Wiley & Sons, 2000.
28. [28] Hooker JN, Ottosson G. “Logic-based Benders decomposition”. Mathematical Programming, 96(1), 33-60, 2003.
29. [29] Riazi S, Seatzu C, Wigström O, Lennartson B. “Benders/gossip methods for heterogeneous multi- vehicle routing problems”. 2013 IEEE 18th Conference on Emerging Technologies & Factory Automation (ETFA), Cagliari, Italy, 10-13 September 2013.