Eşzamanlı topla-dağıt araç rotalama problemi için sezgisel yaklaşımlar: Genetik algoritma ve kuş sürüsü eniyileme
Heuristic approaches for vehicle routing problem with simultaneous pickup and delivery: Genetic algorithm and particle swarm optimization
Yazar: FATMA PINAR GÖKSAL
Danışman: PROF. DR. FULYA ALTIPARMAK
Gazi Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2010
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Araç yönlendirme problemi = Vehicle routing problem ; Endüstri mühendisliği = Industrial engineering ; Genetik algoritmalar = Genetic algorithms ; Lojistik = Logistics ; Sezgisel yaklaşım = Intuitive approach

Özet:
Günümüz rekabet ortamında işletmelerin, tedarik zincirindeki süreçlerinieniyilemek ve etkin bir şekilde yönetmek amacıyla çeşitli stratejik veoperasyonel kararlar alması gerekmektedir. En önemli operasyonelkararlardan birisi araç rotalarının belirlenmesi ile ilgilidir. Klasik araçrotalama problemi, bir depodan müşterilerin dağıtım ya da toplama taleplerinikarşılayacak en uygun rotaların belirlenmesi olarak tanımlanabilir. Pratiktekarşılaşılan kısıtlamalara dayalı olarak literatürde farklı araç rotalamaproblemleri önerilmiştir. Bu problemlerden birisi Eşzamanlı Topla-Dağıt AraçRotalama Problemidir (ETD_ARP). ETD_ARP depodan müşterilere üründağıtımının yanı sıra müşterilerden de depoya geri dönecek ürünlerintoplanması operasyonlarının eşzamanlı gerçekleştirildiği bir araç rotalamaproblemidir. ETD_ARP bir NP-zor problemdir. Bu nedenle problemin çözümüiçin literatürde çeşitli sezgisel algoritmalar geliştirilmiştir. Bu tez kapsamındaETD_ARP'nin çözümü için Genetik Algoritma (GA), Kuş Sürüsü Eniyileme(KSE) ve Değişken Komşu İniş (DKİ) algoritmasına dayalı iki melez algoritma(GA_DKİ ve KSE_DKİ) geliştirilmiştir. Melez algoritmalarda GA ve KSEçözüm uzayında araştırma yapmak, DKİ ise arama sırasında bulunan bir ya dabirkaç çözüm etrafında derinlemesine aramayı gerçekleştirmek amacıylakullanılmıştır. GA_DKİ ve KSE_DKİ'nin performansını araştırmak amacıyladeneysel çalışma yapılmıştır. 76 test problemi ile yapılan deneysel çalışmada,GA_DKİ ve KSE_DKİ'nin çözüm kalitesi açısından literatürdeki diğeralgoritmalar ile rekabet edebildiği ve bazı problemler için bilinen eniyi çözümüiyileştirdiği görülmüştür.Bilim Kodu : 906.1.141Anahtar Kelimeler : Eşzamanlı topla-dağıt araç rotalama problemi, genetik: algoritma, kuş sürüsü eniyileme, değişken komşu iniş

Abstract:
In today?s competitive environment, it is obvious that companies should makestrategic and operational decisions in order to optimize and manage theprocesses in their supply chain more efficiently. One of the most importantoperational decisions concerns to determine of vehicle routes. Classical vehiclerouting problem can be defined as the problem of designing optimal delivery orpickup routes from one depot to a number of customers. Different variants ofvehicle routing problem depending on some restrictions, which are faced in thepractice, have been proposed in the literature. One of these variants is theVehicle Routing Problem with Simultaneous Pickup and Delivery (VRP_SPD).In the VRP_SPD, pickup and delivery demands of customers in each route aremet simultaneously. Since the VRP_SPD is an NP-hard problem, differentheuristic solution algorithms have been proposed to solve the problem in theliterature. In this thesis, two hybrid algorithms based on Genetic Algorithm(GA), Particle Swarm Optimization (PSO) and Variable Neighborhood Descent(VND) algorithm called GA_VND and PSO_VND are developed. While GA andPSO are used to explore solution space of the problem, VND is implemented tointensify around one or several good solutions found during search process ofthe hybrid algorithms. An experimental study is carried out to investigate theperformances of GA_VND and PSO_VND. The computational results over 76test instances indicate that the proposed hybrid algorithms compete with theheuristic approaches, which are proposed in the literature for the VRP_SPD, interms of solution quality and also GA_VND improves known best solution forsome instances.