Column generation-based methods for the electric vehicle routing problems with time windows
Zaman pencereli elektirikli araç rotalama problemi için sütun türetme algoritmasına dayalı çözüm yöntemleri
- Tez No: 752429
- Danışmanlar: PROF. DR. BÜLENT ÇATAY, DR. ÖĞR. ÜYESİ DUYGU TAŞ KÜTEN
- Tez Türü: Doktora
- Konular: Enerji, Ulaşım, Energy, Transportation
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 129
Özet
Zaman Pencereli Elektrikli Araç Rotalama Problemi (ZEARP), geleneksel araçlar yerine bir elektrikli araç (EA) filosunun kullanıldığı ve iyi bilinen Zaman Pencereli Araç Rotalama Problemi'nin (ZARP) bir uzantısıdır. EA'ların sınırlı bir sürüş menzili vardır ve bu nedenle bataryalarını şarj etmek için rotadaki bir istasyonu ziyaret etmeleri gerekebilir. Şarj için harcanan süre, aktarılan enerji miktarı ile doğrusal orantılıdır. Bu tezde ZEARP ve Esnek Teslimatlı Elektrikli Araç Rotalama Problemleri (ET-EARP) incelenmiştir. İlk problem klasik ZARP'ye dayanmaktadır ve problemde her müşteri için sadece bir teslimat yeri ve bununla ilgili zaman penceresinin sağlandığı varsayılır. İkinci problemde, bu varsayım, müşterilere birden fazla teslimat yeri ve her teslimat noktası için farklı bir zaman penceresi belirtme esnekliğinin sağlandığı şekilde genelleştirilmiştir. Bu problemlere çözüm elde etmek için kesin ve sezgisel algoritmalar geliştiririz. Bu algoritmalar Sütun Türetme yöntemine dayalı Dal-ve-Ücret (DÜ) ve Dal-ve-Ücret-ve-Kesit (DÜK) prosedürlerinden oluşmaktadır. Bu yöntemlerin ücretlendirme alt problemleri Pulse algoritmasına veya ng-rota algoritmasına dayanan farklı etiketleme algoritmaları kullanılarak çözülmektedir. Sütun türetme algoritmalarını iyileştirmek için kullanılan hızlandırma teknikleri şu şekildedir: (i) hem ileri hem de geriye doğru etiketlerin oluşturulduğu iki yönlü bir arama mekanizması, (ii) her yinelemede ücretlendirme alt probleminin çözülmesini önleyen bir yöntem, (iii) rota oluşturma sırasında müşterileri ağdan uzak istasyonlara bağlayan bağlantıları dinamik olarak ortadan kaldırmak için bir prosedür, (iv) alt optimal yolların erken ortadan kaldırılmasını sağlayan bir sınırlama prosedürü ve (v) üst sınırlar oluşturan bir tamsayılı programlama modeli. DÜK iyi bilinen bir dizi geçerli eşitsizlik uygulanarak güçlendirilir. ZEARP için önerilen yöntemler 100'e kadar müşteri ve 21 istasyona sahip örnekleri içeren bir veri seti kullanılarak değerlendirmiş ve mevcut bazı çözümler iyileştirilirken birçok yeni çözüm de sunulmuştur. Ayrıca, Pulse algoritması ile DÜ yöntemi kullanılarak 100 müşterili bir veri seti daha çözdülmüş ve elde edilen birkaç çözüm iyileştirilmiştir. ET-EARP için ise 120'ye kadar müşteriye sahip örnekleri içeren yeni bir veri seti oluşturulmuştur ve bu örnekler üzerinde çift yönlü Pulse prosedürü ile uygulanan DÜ algoritmasının performansını değerlendiren kapsamlı bir hesaplama çalışması sunulmaktadır.
Özet (Çeviri)
The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is an extension of the well-known Vehicle Routing Problem with Time Windows (VRPTW), where a fleet of electric vehicles (EVs) is used instead of conventional vehicles. EVs have a limited driving range, and thus, they may need to visit a station on the route to recharge their batteries. The duration spent to recharge the battery is linearly proportional to the amount of energy transferred. In this thesis, the EVRPTW and the EVRP with Flexible Delivery (EVRP-FD) are studied. The first problem is based on the classical VRPTW and assumes that for each customer only one delivery location and its related time window are provided. In the second problem, this assumption is generalized such that customers are offered the flexibility to specify multiple delivery locations for service to take place within different predetermined time windows. We develop exact and heuristic algorithms based on the Column Generation (CG) method that is embedded in Branch-and-Price (BP) and Branch-and-Price-and-Cut (BPC) procedures to obtain solutions for these problems. Pricing subproblems of those methods are solved by using different labeling algorithms all based on the Pulse algorithm or the ng-route algorithm and improved with the state-of-the-art acceleration techniques including (i) a bidirectional search mechanism in which both forward and backward labels are created, (ii) a method to prevent solving the pricing sub-problem at each iteration, (iii) a procedure for dynamically eliminating arcs that connect customers to remote stations from the network during the path generation, (iv) a bounding procedure providing early elimination of sub-optimal routes, and (v) an integer programming model that generates upper bounds. The BPC is strengthened by employing a well-known set of valid inequalities. The methods proposed for solving the EVRPTW are evaluated by using a benchmark data set that includes instances with up to 100 customers and 21 stations and several new solutions are introduced while some existing solutions are improved. The BP procedure with the Pulse algorithm also provides a number of new solutions for the instances with 100 customers to the literature. For the EVRP-FD, we present a new data set including instances with up to 120 customers and an extensive computational study is performed to evaluate the performance of the BP algorithm applied with the bidirectional Pulse procedure.
Benzer Tezler
- Enerji iletiminde gerilim kararlı en uygun reaktif güç desteklemelerinin incelenmesi
Başlık çevirisi yok
MUSTAFA BAĞRIYANIK
Doktora
Türkçe
1997
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. NUSRET YÜKSELER
- Elektrik pano yangınlarına karşı nesnelerin interneti destekli algılama sisteminin geliştirilmesi
Development of an internet of things supported detection system against electric panel fires
MUHAMMED FATİH PEKŞEN
Doktora
Türkçe
2024
Mühendislik BilimleriSakarya ÜniversitesiYangın ve Yangın Güvenliği Anabilim Dalı
PROF. DR. YILMAZ UYAROĞLU
- Olasılığa bağlı kısadevre analizi
Probabilistic short circuit analysis
Z.ELİF AYGEN
Yüksek Lisans
Türkçe
1995
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. NESRİN TARKAN
- Optimal resource allocation for delay and energy constrained wireless networks
Gecikme ve enerji kısıtlı kablosuz ağlarda optimal kaynak özgüleme
YALÇIN ŞADİ
Doktora
İngilizce
2015
Elektrik ve Elektronik MühendisliğiKoç ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SİNEM ÇÖLERİ ERGEN
- Büyük ölçekli havayolu ekip eşleme problemlerinin çözümü için bir kolon türetme stratejisi
A column generation strategy for large scale airline crew pairing problems
BAHADIR ZEREN
Doktora
Türkçe
2017
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. İBRAHİM OZKOL