Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller

Hande KÜÇÜKAYDIN (MEF Üniversitesi, Endüstri Mühendisliği Bölümü, İstanbul, Türkiye)
Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi
1 0
Yıl: 2019 Cilt: 34 Sayı: 4 Sayfa Aralığı: 2061 - 2078 Metin Dili: Türkçe DOI: 10.17341/gazimmfd.421828 İndeks Tarihi: 06-01-2021

Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller

Öz:
Bu çalışmada, araçların kullanıldıkları süreye bağlı maliyetlerin oluştuğu ve araçların depodan başlamazamanının bir karar verici tarafından belirlendiği zaman pencereli bir araç rotalama problemi elealınmaktadır. Problemi çözmek için biri yinelemeli yerel arama meta-sezgiselinden, diğeri değişkenkomşuluk arama meta-sezgiselinden yararlanan iki sütun türetme temelli mat-sezgisel geliştirilmiştir.Geliştirilen mat-sezgiseller ilk önce literatürden alınarak türetilen küçük bir veri kümesi üzerinde problemineniyi sonucunu bulan kesin bir yöntem ile karşılaştırılarak kaliteli sonuçlar ürettiklerini kanıtlamışlardır.Yöntemlerin ürettikleri sonuçların doğruluk derecesinden emin olunduktan sonra, daha büyük 87 örneküzerinde her mat-sezgisel her örnekte 3 kere çalıştırılarak test edilmiştir. Bilgisayımsal sonuçlar değişkenkomşuluk arama meta-sezgiseli kullanan mat-sezgiselin, daha kaliteli ve verimli sonuçlar vererek dahabaşarılı bir algoritma olduğunu göstermiştir. Bu sayede kesin bir yöntemle makul bir ana işlemci zamanındaçözülemeyen büyük ölçülü problemler için çok kısa bir zaman içerisinde iyi bir olurlu çözüm elde etmekmümkün hale gelmiştir.
Anahtar Kelime:

Column generation based matheuristics for a vehicle routing problem with time windows and variable start time

Öz:
In this study, a vehicle routing problem with time windows is investigated, where the costs depend on the total duration of vehicle routes and the starting time from the depot for each vehicle is determined by a decision maker. In order to solve the problem, two column generation based mat-heuristics are developed, where the first one makes use of the iterated local search and the second one uses the variable neighbourhood search. In order to assess the accuracy of the mat-heuristics, they are first compared with an exact algorithm on small instances taken from the literature. Since their performance are quite satisfactory, they are further tested on 87 large instances by running each algorithm 3 times for each instance. The computational results prove that the mat-heuristic using the variable neighbourhood search outperforms the other one. Hence, this enables to obtain a good feasible solution in a very short time when it is not possible to solve large instances with an exact solution method in a reasonable CPU time.
Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
  • 1. Toth P. ve Vigo D., Vehicle Routing: Problems, Methods, and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 2014. 2. Dantzig, G.B. ve Ramser, J.H., The truck dispatching problem, Management Science, 6 (1), 80-91, 1959.
  • 3. De Bruecker P., Beliën J., De Boeck L., De Jaeger S., Demeulemeester E., A model enhancement approach for optimizing the integrated shift scheduling and vehicle routing problem in waste collection, European Journal of Operational Research, 266 (1), 278-290, 2018.
  • 4. Männel D. ve Bortfeldt A., Solving the pickup and delivery problem with three-dimensional loading constraints and reloading ban, European Journal of Operational Research, 264 (1), 2018.
  • 5. de Souza Lima F.M., Pereira D.S.D., da Conceição S.V., de Camargo R.S., A multi-objective capacitated rural school bus routing problem with heterogeneous fleet and mixed loads, 4OR A Quarterly Journal of Operations Research, 15 (4), 359-386, 2017.
  • 6. Hosseini M.B., Dehghanian F., Salari M., Selected capacitated location-routing problem with incentivedependent returns in designing used products collection network, European Journal of Operational Research, 272 (2), 2019.
  • 7. Ceselli A., Righini G., Salani M., A column generation algorithm for a rich vehicle routing problem, Transportation Science, 43 (1), 56-69, 2009.
  • 8. Desaulniers G., Madsen O.B., Ropke S., The Vehicle Routing Problem With Time Windows, Vehicle Routing: Problems, Methods, and Applications, Editörler: Toth P. ve Vigo D., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 119-159, 2014.
  • 9. François V., Neighborhood Search Algorithms for Multi-Trip Vehicle Routing, Doktora Tezi, Liège Üniversitesi, HEC Liège, Belçika, 2018.
  • 10. Hsu C.-I, Hung S.-F., Li H.-C., Vehicle routing problem with time-windows for perishable food delivery, Journal of Food Engineering, 80 (2), 465-475, 2007.
  • 11. Liberatore F., Righini G., Salani M.A., A column generation algorithm for the vehicle routing problem with soft time windows, 4OR A Quarterly Journal of Operations Research, 9 (1), 49-82, 2011.
  • 12. Bettinelli A., Ceselli A., Righini G., A branch-and-cutand-price algorithm for the multi-depot heterogenous vehicle routing problem with time Windows, Transportation Research Part C, 19 (5), 723-740, 2011.
  • 13. Dabia S., Ropke S., van Woensel T., De Kok T., Branch and price for the time-dependent vehicle routing problem with time windows, Transportation Science, 47 (3), 380-396, 2013.
  • 14. Savelsbergh M.W.P., The vehicle routing problem with time windows: Minimizing route duration, ORSA Journal On Computing, 4 (2), 146-154, 1992.
  • 15. Ioachim I, Gélinas S., Soumis F., Desrosiers J., A dynamic programming algorithm for the shortest path problem with time windows and linear node costs, Networks, 31 (3), 193-204, 1998.
  • 16. Desaulniers G., Villeneuve D., The shortest path problem with time windows and linear waiting costs, Transportation Science, 34 (3), 312-319, 2000.
  • 17. Archetti C., Speranza M.G., A survey on matheuristics for routing problems, EURO Journal on Computational Optimization, 2 (4), 223-246, 2014.
  • 18. Desaulniers G., Desrosiers J., Ioachim I., Solomon M. M., Soumis F., Villeneuve D., A unified framework for deterministic time constrained vehicle routing and crew scheduling problems, Fleet Management and Logistics, Editörler: Crainic T.G. ve Laporte G., Kluwer, Boston, 57-93, 1998.
  • 19. Desrosiers J. ve Lübbecke M.E., A primer in column generation, Column Generation, Editörler: Desaulniers G., Desrosiers J., Solomon M.M., Springer, New York, 1-32, 2005.
  • 20. Lübbecke M.E., Desrosiers J., Selected topics in column generation, Operations Research, 53 (6), 1007-1023, 2005.
  • 21. Gutiérrez-Jarpa G., Desaulniers G., Laporte G., Marianov V., A branch-and-price algorithm for vehicle routing problem with deliveries, selective pickups and time windows, European Journal of Operational Research, 206 (2), 341-349, 2010.
  • 22. Salani M. ve Vacca I., Branch and price for the vehicle routing problem with discrete split deliveries and time windows, European Journal of Operational Research, 213 (3), 470-477, 2011.
  • 23. Desaulniers G., Lessard F., Hadjar A., Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows, 42 (3), 387-404, 2008.
  • 24. Feillet D., A tutorial on column generation and branchand-price for vehicle routing problems, 4OR A Quarterly Journal of Operations Research, 8 (4), 407- 424, 2010.
  • 25. Azi N., Gendreau M., Potvin J.-Y., An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, European Journal of Operational Research,, 202 (3), 756-763, 2010.
  • 26. Boschetti M., Maniezzo V., Roffilli M., Röhler A.B., Matheuristics: Optimization, simulation and control, Hybrid Metaheuristics, Lecture Notes in Computer Science 6373, Editörler: Blesa M., Blum C., Raidl G., Roli A., Sampels M., Springer Berlin Heidelberg, 171- 177, 2010.
  • 27. Danna E. ve Pape C., Branch-and-price heuristics: a case study on the vehicle routing problem with time windows, Column Generation, Editörler: Desaulniers G., Desrosiers J., Solomon M.M., Springer, ABD, 99- 129, 2005.
  • 28. Archetti C., Bianchessi N., Speranza M.G., A column generation approach for the split delivery vehicle routing problem, Networks, 58 (4), 241-254, 2011.
  • 29. Archetti C., Speranza M.G., Vigo D., Vehicle Routing Problems with Profits, Vehicle Routing: Problems, Methods, and Applications, Editör: Toth P. ve Vigo D., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 273-298, 2014.
  • 30. Archetti C., Bianchessi N., Speranza M.G., Optimal solutions for routing problems with profits, Discrete Applied Mathematics, 161 (4-5), 547-557, 2013.
  • 31. Archetti C., Bianchessi N., Speranza M.G., The capacitated team orienteering problem with incomplete service, Optimization Letters, 7 (7), 1405-1417, 2013.
  • 32. Archetti C., Bianchessi N., Hertz A., Speranza M.G., Incomplete service and split deliveries in a routing problem with profits, Networks, 63 (2), 135-145, 2014.
  • 33. Archetti C., Bianchessi N., Hertz A., Speranza M.G., The split delivery capacitated team orienteering problem, Networks, 63 (1), 16-33, 2014.
  • 34. Aghezzaf E-H, Raa B., Landeghem H.V., Modeling inventory routing problems in supply chains of high consumption products, European Journal of Operational Research, 169 (3), 1048-1063, 2006.
  • 35. Raa B., Aghezzaf E.-H., Designing distribution patterns for long-term inventory routing with constant demand rates, International Journal of Production Economics, 112 (1), 255-263, 2008.
  • 36. Raa B., Aghezzaf E.-H., A practical solution approach for the cyclic inventory routing problem, European Journal of Operational Research, 192 (2), 429-441, 2009.
  • 37. Parragh S. N., Cordeau J.F., Doerner K. F., Hartl R. F., Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints, OR Spectrum, 34 (3), 593-633, 2012.
  • 38. Parragh S. N. ve Schmid V., Hybrid column generation and large neighborhood search for the dial-a-ride problem, Computers and Operations Research, 40 (1), 490-497, 2013.
  • 39. Cacchiani V., Hemmelmayr V. C., Tricoire F., A set covering based heuristic algorithm for the periodic vehicle routing problem, Discrete Applied Mathematics, 163 (1), 53-64, 2014.
  • 40. Dasgupta S., Papadimitriou C., Vazirani U., Algorithms, McGraw-Hill Education, New York, 2006.
  • 41. Russell S. ve Norvig P., Artificial Intelligence: A Modern Approach, Prentice Hall, Upper Saddle River, New Jersey, 2010.
  • 42. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to Algorithms, The MIT Press, Cambridge, Massahusetts, London, England, 2009.
  • 43. Dror M., Note on the complexity of the shortest path models for column generation in VRPTW, Operations Research, 42 (5), 977-978, 1994.
  • 44. Raidl G. R., Puchinger J., Combining (Integer) Linear Programming Techniques and Metaheuristics for Combinatorial Optimization, Hybrid Metaheuristics: An Emerging Approach to Optimization, Editörler: Blum C., Blesa M., Roli A., Sampels M., Springer Berlin Heidelberg, 31-62, 2008.
  • 45. Talbi E.-G., Metaheuristics: From Design to Implementation, New Jersey, Wiley, 2009.
  • 46. Glover F., Kochenberger G. A., Handbook of Metaheuristics, Dordrecht, Kluwer Academic Publishers, 2003.
  • 47. Cuervo D.P., Goos P., Sörensen K., Arráiz E., An iterated local search algorithm fort he vehicle routing problem with backhauls, 237 (2), 454-464, 2014.
  • 48. Hansen P., Mladenovic N., Perez J.A.M., Variable neighborhood search: methods and applications, Annals of Operations Research, 175 (1), 367-407, 2010.
  • 49. Parragh S.N., Schmid V., Hybrid column generation and large neighborhood search for the dial-a-ride problem, Computers and Operations Research, 40 (1), 490-497, 2013.
  • 50. Solomon M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35 (2), 254-265, 1987.
APA Kucukaydin H (2019). Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller. , 2061 - 2078. 10.17341/gazimmfd.421828
Chicago Kucukaydin Hande Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller. (2019): 2061 - 2078. 10.17341/gazimmfd.421828
MLA Kucukaydin Hande Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller. , 2019, ss.2061 - 2078. 10.17341/gazimmfd.421828
AMA Kucukaydin H Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller. . 2019; 2061 - 2078. 10.17341/gazimmfd.421828
Vancouver Kucukaydin H Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller. . 2019; 2061 - 2078. 10.17341/gazimmfd.421828
IEEE Kucukaydin H "Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller." , ss.2061 - 2078, 2019. 10.17341/gazimmfd.421828
ISNAD Kucukaydin, Hande. "Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller". (2019), 2061-2078. https://doi.org/10.17341/gazimmfd.421828
APA Kucukaydin H (2019). Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 34(4), 2061 - 2078. 10.17341/gazimmfd.421828
Chicago Kucukaydin Hande Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 34, no.4 (2019): 2061 - 2078. 10.17341/gazimmfd.421828
MLA Kucukaydin Hande Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol.34, no.4, 2019, ss.2061 - 2078. 10.17341/gazimmfd.421828
AMA Kucukaydin H Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2019; 34(4): 2061 - 2078. 10.17341/gazimmfd.421828
Vancouver Kucukaydin H Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2019; 34(4): 2061 - 2078. 10.17341/gazimmfd.421828
IEEE Kucukaydin H "Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller." Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 34, ss.2061 - 2078, 2019. 10.17341/gazimmfd.421828
ISNAD Kucukaydin, Hande. "Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller". Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 34/4 (2019), 2061-2078. https://doi.org/10.17341/gazimmfd.421828
Sayfa Oluşturulma Tarihi
23-04-2024 16:26

İLETİŞİM

TÜBİTAK ULAKBİM TR Dizin

Yüzüncüyıl, İşçi Blokları Mahallesi

Muhsin Yazıcıoğlu Caddesi No:51/C

06530 Çankaya / ANKARA +90 (312) 298 92 00

trdizin@tubitak.gov.tr

TÜBİTAK ULAKBİM Ulusal Akademik Ağ ve Bilgi Merkezi Cahit Arf Bilgi Merkezi © Tüm Hakları Saklıdır. Gizlilik Politikası Kullanım Şartları