A NOVEL APPROACH FOR SOLUTION OF DYNAMIC VEHICLE ROUTING PROBLEMS

Year 2017, Volume: 22 Issue: 3, 807 - 823, 30.07.2017

Yonca Erdem Demirtaş Erhan Özdemir

Abstract

Vehicle Routing Problem (VRP) is a well-known NP-Hard optimization problem that has been studied for many years. In the VRP, all information about the problem is known at the beginning of the solution procedure. It is basically a static problem, although many VRP problems change over time in the real world. These problems are called as Dynamic VRP (DVRP) in the literature. In most cases, the real world information can change or appear after the solution process begins. These characteristics make the DVRP harder than static VRP. In this study DVRP is examined and a Particle Swarm Optimization algorithm is proposed. The most known benchmarks are solved with the proposed algorithm and the results are compared with the previously employed methods in the literature. The propose algorithm is used to solve a real world DVRP and the obtained results are compared with the route that is used by the factory.

Keywords

Dynamic Vehicle Routing Problem, Meta Heuristics, Particle Swarm Optimization, Local Search Techniques

DİNAMİK ARAÇ ROTALAMA PROBLEMLERİ İÇİN YENİ BİR ÇÖZÜM ÖNERİSİ

Abstract

Araç Rotalama Problemi (ARP) üzerinde çok uzun zamandır çalışılan bir optimizasyon problemidir. Bir ARP’de tüm problem girdileri önceden bilinir ve problem boyunca değişmezler. Her ne kadar ARP, NP-Zor sınıfında iyi bilinen statik bir problem olsa da gerçek hayatta benzeri problemler dinamik bir şekilde değişmektedir. Bu tip problemler Dinamik ARP (DARP) olarak isimlendirilmektedir. Diğer taraftan DARP’de problem girdilerinin başlangıçta tamamı veya bir kısmı bilinmez ya da planlama esnasında ortaya çıkabilir veya değişebilirler. Bu iki önemli karakteristikten dolayı DARP, ARP’ye oranla daha zor bir problem olarak bilinmektedir. Bu çalışmada, DARP incelenmiş ve Parçacık Sürü Optimizasyonu (PSO) yöntemi ile bir çözüm önerilmiştir. Literatürde çalışılan test problemleri PSO ile çözülmüş ve sonuçlar literatürde yer alan diğer yöntemler ile karşılaştırılmıştır. Ele alınan bir gerçek hayat probleminin çözümü için önerilen PSO algoritması uygulanarak elde edilen sonuçlar hali hazırda kullanılan rotalar ile karşılaştırılmaktadır.

Keywords

Dinamik Araç Rotalama Problemi, Meta Sezgisel Algoritmalar, Parçacık Sürü Optimizasyonu, Yerel Arama Teknikleri

References

• BIANCHI, L. (2000). Notes On Dynamic Vehicle Routing-The State of The Art.
• CHRISTOFIDES, N. ve BEASLEY, J. E. (1984). “The Period Routing Problem”, Networks, 14(2): 237-256.
• CORMEN, T. H., LEISERSON, C. E., RIVEST, R. L. ve STEIN, C. (2009). Introduction to Algorithms (Cilt 3). Cambridge: MIT Yayım.
• CROES, G. A. (1958). “A Method For Solving Traveling-Salesman Problems”, Operations Research, 6(6): 791-812.
• DANTZIG, G. B. ve RAMSER, J. H. (1959). “The Truck Dispatching Problem”, Management Science, 6(1): 80-91. FISHER, M. (1995). “Vehicle Routing”, (İçinde) Handbooks In Operations Research and Management, 8: 1-33, Elsevier.
• HANSHAR, F. T. ve OMBUKI- BERMAN, M., B. (2007). “Dynamic Vehicle Routing Using Genetic Algorithms”, Applied Intelligence, 27(1): 89-99.
• KENNEDY, J. ve EBERHART, R. (1995). “Particle Swarm Optimization”, Proceeding of the IEEE international conference on neural networks, 1942-1948.
• KHOUADJIA, M. R., SARASOLA, B., ALBA, E., JOURDAN, L. ve TALBI, E. G. (2012). “A Comparative Study Between Dynamic Adapted PSO and VNS for the Vehicle Routing Problem with Dynamic Requests”, Applied Soft Computing, 12(4): 1426- 1439.
• KILBY, P., PROSSER, P. ve SHAW, P. (1998). “Dynamic VRPs: A Study of Scenarios”, University of Strathclyde Technical Report.
• LARSEN, A. (2000). The Dynamic Vehicle Routing Problem. Doktora Tezi, Institute of Mathematical Modelling, Technical University of Denmark.
• LUND, K., MADSEN, O. B. ve RYGAARD., J. M. (1996). Vehicle routing with varying degree of dynamism. The Department Informatics of Mathematical Modelling. Technical University of Denmark.
• MIRHASSANI, S. A. ve ABOLGHASEM, N. (2011). “A Particle Swarm Optimization Algorithm for Open Vehicle Routing Problem”, Expert Systems with Application, 38(9): 11547-11551.
• MONTEMANNI, R., GAMBERDELLA, L. M., RIZZOLI, A. E. ve DONATI, A. V. (2005). “Ant Colony System for a Dynamic Vehicle Routing Problem”, Journal of Combinatorial Optimization, 10(4): 327-343.
• PILLAC, V., GENDREAU, M., GUÉRET, C., ve MEDAGLIA, A. L. (2013). “A Review of Dynamic Vehicle Routing Problems”, European Journal of Operational Research, 225(1): 1-11.
• PSARAFTIS, H. N. (1988). “Dynamic vehicle routing problems”, (İçinde) Vehicle Routing: Methods and Studies: 223-248, North-Holland, Amsterdam.
• PSARAFTIS, H. N. (1995). “Dynamic Vehicle Routing: Status and Prospects”, Annals of Operations Research, 61(1): 143-164.
• SHI, Y. ve EBERHART, R. C. (1999). “Empirical Study of Particle Swarm Optimization”, Proceedings of the IEEE Congress on Evolutionary Computation: 1945-1950. TAILLARD, É. (1993). “Parallel Iterative Search Methods for Vehicle Routing Problems”, Networks, 23(8): 661-673.
• TOTH, P. ve VIGO, D. (2001). “The Vehicle Routing Problem”, Society for Industrial and Applied Mathematics.
• WANG, W., WU, B., ZHAO, Y. ve FENG, D. (2006). “Particle Swarm Optimization for Open Vehicle Routing Problem”, (İçinde) Computational Intelligence: 999-1007, Springer.
• WOODRUFF, D. L. (1998). Advances in Computational and Stochastic Optimization, Logic Programming and Heuristic Search, Springer.
• YU, X., GEN, M. (2010). Introduction to Evolutionary Algorithms. Springer Science - Business Media.