Research Article
BibTex RIS Cite

A NOVEL APPROACH FOR SOLUTION OF DYNAMIC VEHICLE ROUTING PROBLEMS

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

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.

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.

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

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

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.

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.
There are 21 citations in total.

Details

Primary Language Turkish
Journal Section Articles
Authors

Yonca Erdem Demirtaş

Erhan Özdemir

Publication Date July 30, 2017
Published in Issue Year 2017 Volume: 22 Issue: 3

Cite

APA Erdem Demirtaş, Y., & Özdemir, E. (2017). DİNAMİK ARAÇ ROTALAMA PROBLEMLERİ İÇİN YENİ BİR ÇÖZÜM ÖNERİSİ. Süleyman Demirel Üniversitesi İktisadi Ve İdari Bilimler Fakültesi Dergisi, 22(3), 807-823.