AN ADAPTIVE LARGE NEIGHBORHOOD SEARCH APPROACH FOR SOLVING THE ELECTRIC VEHICLE ROUTING PROBLEM WITH TIME WINDOWS
ZAMAN PENCERELİ ELEKTRİKLİ ARAÇ ROTALAMASI PROBLEMİ İÇİN BİR UYARLANABİLİR GENİŞ KOMŞULUK ARAMA YÖNTEMİ
- Tez No: 392249
- Danışmanlar: DOÇ. DR. BÜLENT ÇATAY
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 70
Özet
Zaman Pencereli Elektrikli Araç Rotalama Problemi (E-ZARP), çokça bilinen Zaman Pencereli Araç Rotalama Problemi (ZARP)'nin genişletilmiş bir biçimidir. ZARP'den farklı olarak, E-ZARP'de filo, batarya şarj kapasitesinden dolayı sınırlı sürüş menziline sahip elektrikli araçlardan (EA) oluşmaktadır. Batarya şarj seviyesi, alınan yol ile orantılı bir şekilde azaldığından dolayı EA, rotasındaki müşterilere hizmet vermeyi sürdürebilmek için, bataryasını şarj etmek amacıyla rotasının herhangi bir yerinde, şarj istasyonuna uğramak durumunda kalabilir. Şarj işlemi herhangi şarj seviyesinde olabilmekte ve şarj işleminden sonra bataryanın tam şarj olduğu kabul edilmektedir. Şarj süresi, şarj edilen miktar ile doğru orantılıdır. İstasyon sayısı genellikle az olup istasyonlar uzak noktalarda konumlanmışlardır. Bu da problemin zorluk derecesini arttırmaktadır. Bu tezde, belirtilen problemi çözmek için bir Uyarlanabilir Geniş Komşuluk Arama Yöntemi (UGKA) önerilmiştir. UGKA yöntemi, boz-onar sistemine dayanmaktadır. Olurlu çözüm, bazı müşteri ve istasyonların rotalarından çıkarılmaları ile bozulmakta, çıkarılan müşterilerin, şarj işlemi de gerekli ise istasyonlar ile beraber çözüme tekrar eklenmeleri ile onarılmaktadır. Birçok çıkarma ve ekleme algoritması kullanılmış ve bu algoritmalar yöntem içinde, geçmiş performansları baz alınarak dinamik ve uyarlanabilir bir şekilde seçilmiştir. Elde edilen yeni çözüm Benzetilmiş Tavlama kriterine gore kabul edilmiştir. Bizim yaklaşımımız, literatürde var olan çıkarma ve ekleme algoritmaları ile E-ZARP için özel olarak tasarlanmış yeni mekanizmaları birleştirmektedir. Önerilen UGKA'nın performansını test etmek için, Schneider et al. (2014)'de sunulan örnekler ve sonuçlar kullanılmıştır. Sonuçlarımız, önerilen yöntemin, makul süreler içinde iyi sonuçlar bulmada etkili olduğunu göstermiştir.
Özet (Çeviri)
The Electric Vehicle Routing Problem with Time Windows (E-VRPTW) is an extension to the well-known Vehicle Routing Problem with Time Windows (VRPTW). Different from VRPTW, the fleet in E-VRPTW consists of electric vehicles (EVs) which have a limited driving range due to their battery charge capacities. Since the battery charge level decreases proportional to the distance traveled, an EV may need to visit recharging stations to have its battery recharged in order to be able to continue servicing the customers along its route. The recharging may take place at any battery level and after the recharging the battery is assumed to be full. Recharging time is proportional to the amount charged. The number of stations is usually small and the stations are dispersed in distant locations, which increases the difficulty of the problem. In this thesis, we propose an Adaptive Large Neighborhood Search (ALNS) method to solve this problem. ALNS is based on the destroy-and-repair framework where at any iteration the existing feasible solution is destroyed by removing some customers and recharging stations from their routes and then repaired by inserting the removed customers to the solution along with the stations when recharging is necessary. Several removal and insertion algorithms are applied by selecting them dynamically and adaptively based on their past performances. The new solution is accepted according to the Simulated Annealing criterion. Our approach combines the removal and insertion mechanisms from the literature with some new mechanisms designed specifically for E-VRPTW. To test the performance of the proposed ALNS we use the instances and benchmark results presented in by Schneider et al (2014). Our computational results show that the proposed method is effective in finding good solutions in reasonable amount of time.
Benzer Tezler
- Kapasite kısıtlı araç rotalama problemi ve çözüm yöntemleri
Capacitated vehicle routing problem and solution approaches
ZEYNEP BİRECİK
Doktora
Türkçe
2023
Endüstri ve Endüstri MühendisliğiYıldız Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. DOĞAN ÖZGEN
- An adaptive local search algorithm for vehicle routing problems with simultaneous and mixed pickups and deliveries
Eş zamanlı ve karışık dağıtım ve toplamalı araç rotalama problemleri için bir adaptif lokal arama algoritması
MUSTAFA AVCI
Yüksek Lisans
İngilizce
2014
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ŞEYDA AYŞE TOPALOĞLU
- Sürdürülebilir toplu konut yerleşmesi tasarımı için Pareto genetik algoritmaya dayalı bir model önerisi: SSPM
A model for sustainable site layout design with pareto genetic algorithm: SSPM
YAZGI AKSOY
- An adaptive large neighborhood search for the multi-compartment inventory routing problem
Çok bölmeli envanter rotalama problemi için uygulanabilir geniş komşuluk araması
CEREN GÜLTEKİN
Yüksek Lisans
İngilizce
2021
Endüstri ve Endüstri MühendisliğiÖzyeğin ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. OKAN ÖRSAN ÖZENER
DOÇ. ALİ EKİCİ
- Rich vehicle routing: A data-driven heuristic application for a logistics company
Zengin araç rotalama: Bir lojistik firması için veri odaklı sezgisel uygulama
MUSTAFA SALİH ÇAVUŞ
Yüksek Lisans
İngilizce
2019
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiYönetim Bilimleri Ana Bilim Dalı
PROF. DR. BURÇİN BOZKAYA