Periyodik Araç Rotalama Probleminin Üç Farkli Türevi Üzerine
Loading...
Date
2016
Authors
Ahmet CAMCI
Nail Özgür ÖZPEYNİRCİ
Journal Title
Journal ISSN
Volume Title
Publisher
Open Access Color
OpenAIRE Downloads
OpenAIRE Views
Abstract
Araç rotalama problemi güncel bir problem olup ellili yıllardan beri çalışılmaktadır. Önceleri araç rotalama problemi karmaşık oluşu ve teknolojinin yeterli olmaması sebebiyle literatürde yaygın olarak ele alınamamıştır. Doksanlı yıllarda gelişen teknoloji ile araç rotalama problemleri çalışılabilir hale gelmiş ve araç rotalama problemi üzerine yapılan çalışmaların sayısı artmıştır Araç rotalama problemi bir veya daha fazla depodan çıkan araçların tüm müşterileri ziyaret ederek tekrar depoya dönmesi üzerine kurulu bir problemdir. Araç rotalama problemi kat edilen mesafeyi en küçükleyerek ulaşım giderlerini ve harcanan zamanı azalttığı gibi aynı zamanda araç sayısını en aza indirerek maliyetlerin düşmesine yardımcı olur. Buna ek olarak karbon salınımını da düşürerek çevreye verilen zararı azaltır. Son yıllarda tedarik zinciri ve dağıtım kanallarının rekabetçi piyasadaki önemi oldukça artmıştır. Dolayısıyla firmaların araç rotalama problemine olan ilgisi de artmıştır. Araç rotalama probleminin gerçek hayat ihtiyaçları üzerine birçok türevi oluşmuştur. Bunun sebebi farklı tipteki şirketlerin işleyişlerinin değişkenlik göstermesidir. Örneğin müşterilerin sadece belirli saat aralıklarında ziyaret edilebilmesi kargo şirketinin aynı anda hem dağıtım hem de toplama işlemi yapması bazı müşterilerin aynı araçla ve belirli bir sıra ile ziyaret edilme zorunluluğu olması gibi sebeplerden dolayı problemin birçok türevi literatürde tanımlanmış ve çalışılmıştır. Araç rotalama probleminin literatürde sıklıkla çalışılan türevlerinden birisi periyodik araç rotalama problemidir. Bu problem belirlenen bir periyot içerisinde müşterilerin bir veya daha fazla ziyaret edilmesi üzerine kuruludur. Her periyotta ziyaret edilecek müşterilere ve her periyot için araç rotalarına karar verilmektedir. Amaç genellikle toplam rota uzunluklarını en aza indirmektir. Ziyaret günlerinin uygun şekilde düzenlenmesi maliyetler ve araç sayısı açısından büyük avantaj sağlar. Bu projede periyodik araç rotalama problemi üzerine gerçek hayattan esinlenilen iki yeni problem tanımlanmıştır ve bu problemler için matematiksel modeller alt sınırlar ve sezgisel çözüm yöntemleri geliştirilmiştir. Geliştirilen yöntemlerin sonuç kalitesi ve süre performansları rassal olarak oluşturulan örnekler üzerinde test edilmiştir. İlk problem bir müşteriye yapılan her ziyareti takip eden günde farklı amaçlı bir ziyaret yapılmasını gerektirmektedir. İlk ziyaret talep toplama ikinci ziyaret ise ürünlerin teslimi olarak düşünülebilir. İlk tip ziyaret küçük hızlı ve zaman kapasiteli araçlarla ikinci tip ziyaret ise görece büyük yavaş ve fiziksel kapasiteye sahip araçlarla yapılmaktadır. Bu sebeple birbirini takip eden günlerde aynı rotaların kullanılması mümkün olmamaktadır. Gerçek hayatta müşterilerin daha sık ziyaret edilmesi satışları artırmakta ancak toplam rota uzunluğunun da artmasına sebep olmaktadır. Proje kapsamında çalışılan ikinci problemde periyodik araç rotalama problemi kararlarına ek olarak müşterilerin ziyaret sıklığının müşteri talebini değiştirmesi durumu incelenmiştir. Proje kapsamında ele alınan problemler detaylı olarak tanımlanmış matematik modeli geliştirilmiş ve çözüm karmaşıklığı incelenmiştir. Problemler için alt sınır algoritmaları ve sezgisel yöntem geliştirilmiştir. Geliştirilen alt sınır algoritmaları ve sezgisel yöntemin performansları rassal örnekler üzerinde test edilmiştir.
Description
Keywords
Bilgisayar Bilimleri- Yazılım Mühendisliği-Endüstri Mühendisliği
Fields of Science
Citation
Aksen D. Kaya O. Sibel Salman F. ve Tüncel O. (2014). An adaptive large neighbor-\r\nhood search algorithm for a selective and periodic inventory routing problem.\r\nJournal of Operational Research\r\nEuropean\r\n 239(2):413-426.Periyodik Araç Rotalama Probleminde Ziyaret Sıklığının Belirlenmesi (Bildiri - Ulusal Bildiri\r\n- Sözlü Sunum)Alegre J. Laguna M. ve Pacheco J. (2007). Optimizing the periodic pick-up of raw\r\nmaterials for a manufacturer of auto parts.\r\nEuropean Journal of Operational Research\r\n\r\n179(3):736-746.Periyodik Araç Rotalama Probleminin Bir Türevi Üzerine (Bildiri - Ulusal Bildiri - Sözlü\r\nSunum)Periodic Vehicle Routing Problem with Two Typesof Visits (Bildiri - Uluslararası Bildiri -\r\nSözlü Sunum)Angelelli E. ve Speranza M. G. (2002). The application of a vehicle routing model to a\r\nwaste-collection problem: two case studies.\r\nJournal of the Operational Research Society\r\n\r\n53:944-952.Periyodik Araç Rotalama Probleminin Bir Türevi Üzerine (Bildiri - Ulusal Bildiri - Sözlü\r\nSunum)Baldacci R. Bartolini E. Mingozzi A. ve Valletta A. (2011). An exact algorithm for the\r\nperiod routing problem.\r\n 59(1):228-241.Operations Research\r\nBaptista S. Oliveira R. C. ve Zúquete E. (2002). A period vehicle routing case study.\r\nEuropean Journal of Operational Research\r\n 139:220-229.Beltrami E. ve Bodin L. (1974). Networks and vehicle routing for municipal waste collec-\r\ntion.\r\nNetworks\r\n 4(1):65-94.Cacchiani V. Hemmelmayr V. C. ve Tricoire F. (2014). A set-covering based heuristic\r\nalgorithm for the periodic vehicle routing problem. Discrete Applied Mathematics 163:53-\r\n64.Campbell A. M. ve Wilson J. H. (2014). Forty years of periodic vehicle routing.\r\n\r\nNetworks\r\n63(1):2-15.\r\nChao I.-M. Golden B. L. ve Wasil E. (1995). An improved heuristic for the period vehicle\r\nrouting problem.\r\nNetworks\r\n 26(6):25-44.Christofides N. ve Beasley J. E. (1984). The period routing problem. Networks 14:237\u0015256.\r\nClarke G. ve Wright J. W. (1964). Scheduling of vehicles from a central depot to a number\r\nof delivery points.\r\nOperations Research\r\n 12(4):568-581.Coene S. Arnout A. ve Spieksma F. C. R. (2010). On a periodic vehicle routing problem.\r\n 61(12):1719-1728.Journal of the Operational Research Society\r\nCook T. M. ve Russell R. A. (1978). A Simulation and Statistical Analysis of Stochastic\r\nVehicle Routing With Timing Constraints.\r\n 9:673-687.Decision Sciences\r\nCordeau J.-F. Gendreau M. ve Laporte G. (1997). A tabu search heuristic for periodic\r\nand multi-depot vehicle routing problems.\r\nNetworks\r\n 30(2):105-119.Cordeau J.-F. Laporte G. ve Mercier A. (2001). A unifed tabu search heuristic for\r\nvehicle routing problems with time windows.\r\nSociety\r\nThe Journal of the Operational Research\r\n 52(8):928-936.Croes G. A. (1958). A method for solving traveling-salesman problems.\r\narch\r\nOperations Rese-\r\n 6(6):791-812.Dantzig G. Fulkerson R. ve Johnson S. (1954). Solution of a large-scale traveling-\r\nsalesman problem.\r\n 2:393-410.Operations Research\r\nDumas Y. Desrosiers J. ve Soumis F. (1991). The pickup and delivery problem with\r\ntime windows.\r\nEuropean Journal of Operational Research\r\n68\r\n 54(1):7-22.Eilon S. Watson-Gandy C. D. T. ve Christofides N. (1971).\r\nDistribution management:\r\nmathematical modelling and practical analysis by Samuel Eilon C. D. T. Watson-Gandy\r\nand Nicos Christofides\r\n. Grifin London.Eksioglu B. Vural A. V. ve Reisman A. (2009). The vehicle routing problem: A taxonomic\r\nreview.\r\nComputers and Industrial Engineering\r\n 57(4):1472-1483.Francis P. ve Smilowitz K. (2006). Modeling techniques for periodic vehicle routing prob-\r\nlems.\r\nTransportation Research Part B: Methodological\r\n 40(10):872-884.Francis P. Smilowitz K. ve Tzur M. (2006). The period vehicle routing problem with\r\nservice choice. Transportation Science\r\n 40(4):439-454.Gendreau M. Laporte G. Musaraganyi C. ve Taillard E. D. (1999). A tabu search\r\nheuristic for the heterogeneous fleet vehicle routing problem.\r\nComputers and Operations \r\n 26(12):1153-1173.Research\r\nGolden B. L. ve Wasil E. A. (1987). Computerized vehicle routing in the soft drink\r\nindustry.\r\nOperational Research\r\n 35(1):6-17.Hemmelmayr V. C. Doerner K. F. ve Hartl R. F. (2009). A variable neighborhood\r\nsearch heuristic for periodic routing problems.\r\n\r\nEuropean Journal of Operational Research\r\n195(3):791-802.Laporte G. (2009). Fifty years of vehicle routing.\r\n 43(4):408-416.Transportation Science\r\nLysgaard J. Letchford A. N. ve Eglese R. W. (2004). A new branch-and-cut algorithm\r\nfor the capacitated vehicle routing problem.\r\nMathematical Programming\r\nMladenovi¢ N. ve Hansen P. (1997). Variable neighborhood search.\r\n 100(2):423-445.Computers & Opera-\r\n 24(11):1097-1100.tions Research\r\nMourgaya M. ve Vanderbeck F. (2006). The periodic vehicle routing problem: classi\u001ccation\r\nand heuristic.\r\nRAIRO - Operations Research\r\n69\r\n 40:169-194.Russell R. ve Igo W. (1979). An assignment routing problem.\r\nNetworks\r\n 9(1):1-17.Russell R. A. ve Gribbin D. (1991). A multiphase approach to the period routing problem.\r\nNetworks\r\n 21:747-765.Solomon M. M. (1987). Algorithms for the vehicle routing and scheduling problems with\r\ntime window constraints.\r\n 35:254-265.Toth P. ve Vigo D. (1999). A heuristic algorithm for the symmetric and asymmetric vehicle\r\nrouting problems with backhauls.\r\n 113(3):528-543.Vidal T. Crainic T. G. Gendreau M. Lahrichi N. ve Rei W. (2012). A hybrid genetic\r\nalgorithm for multidepot and periodic vehicle routing problems.\r\n\r\nOperational Research\r\n60(3):611-624.Vidal T. Crainic T. G. Gendreau M. ve Prins C. (2013). Heuristics for multi-attribute\r\nvehicle routing problems: A survey and synthesis.\r\nEuropean Journal of Operational Research\r\n 231(1):1-21.Wen M. Cordeau J.-F. Laporte G. ve Larsen J. (2010). The dynamic multi-period\r\nvehicle routing problem. Computers and Operations Research\r\n 37(9):1615-1623.
WoS Q
Scopus Q
Source
Volume
Issue
Start Page
End Page
Collections
