Algorithms for the vehicle routing problem with time windows and the location-routing problem
Zaman çerçeveli araç rotalama problemi ve yer bulma-rotalama problemi için algoritmalar
- Tez No: 182073
- Danışmanlar: YRD. DOÇ. DR. SELÇUK SAVAŞ, YRD. DOÇ. DR. METİN TÜRKAY
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2006
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 81
Özet
Bu tezde literatürde yer alan iki rotalama problemi üzerinde çalışılmıştır. Bunlardanilkinde, zaman çerçeveli araç rotalama problemini (ZÇARP) çözüyoruz. ZÇARP, araçlarınkapasitelerini ve müşterilerin belirlediği zaman çerçevesi kısıtlarını ihlal etmeden, müşterilerehizmetin sağlanacağı rotaların belirlenmesini içermektedir. ZÇARP'nin çözümü için yeni birdal-kes algoritmasını sunuyoruz. Dal-kes ağacının düğümlerinde oluşan tüm döngülerinpolinom zamanda belirlenmesi ve ihlal edilen geçerli eşitsizliklerin kontrolü ile yok edilmeleriiçin bir ayırma yöntemi uygulamaktayız. Ayrıca karışık tam sayılı doğrusal programın düğümgevşetmelerinde bulunan döngüler üzerinde dallandırmayı sağlayan yeni bir dallandırmastratejisini de uygulamaktayız. Deneysel çalışmalar literatürde sık kullanılan Solomon'un testproblemleri üzerinde yapılmıştır. Şu ana kadar ZÇARP'nin çözümü için en başarılı olanalgoritmalar problemi basit problemlere ayrıştırıp, alt problem için en kısa yol probleminiçözen algoritmalardır. Sunulan algoritma literatürdeki diğer algoritmalarla kıyaslandığında,ayrıştırmaya dayanan kesin çözümlü algoritmaların (örneğin, kolon üretimi, Lagrangeangevşetmesi) bütün Solomon test problemleri üzerinde en iyi performansı göstermedikleritespit edilmiştir. Dal-kes algoritması geniş planlama horizonlu problemler üzerinde daha iyibir performans göstermiştir.Çalışılan problemlerin ikincisi yer belirleme-rotalama problemidir (YBRP). YBRPverilen aday tesis yerleri arasından en iyi yerlerin seçilmesini ve seçilen tesis yerlerinden tümmüşterilere hizmetin sağlanacağı araç rotalarının belirlenmesini kapsar. Çoklu ve kısıtlıkapasiteli tesis ve araçların bulunduğu yer belirleme-rotalama probleminin çözümü için birkolon üretimi algoritmasını öneriyoruz. Kolon üretimi algoritmamızdaki ana problem bir çokrotalama probleminde (örneğin, zaman çerçeveli araç rotalama problemleri) başarılı olduğugörülmüş küme bölme esasına dayalı bir formülasyondur. Fiyatlandırma alt problemi içinkaynak kısıtlı basit en kısa yol problemini çözüyoruz (KKBEKYP). Sunulan algoritmaliteratürde verilen çeşitli YBRP kıyaslama problemleri üzerinde test edilmiştir. Önerilen kolonüretimi algoritması çoğu kıyaslama problemi için sıkı aralıklar bulmayı başarmıştır.
Özet (Çeviri)
In this thesis we study two well-known routing problems. In the first, we solve thevehicle routing problem with time windows (VRPTW). The VRPTW involves designinga set of routes to serve all the customers without violating the capacity of vehicles andtime windows constraints of the customers. We present a new branch-and-cut algorithmfor solving the VRPTW. We apply a separation routine that detects all cycles in the nodesof the branch-and-cut tree in polynomial time and then tries to eliminate these cycles bychecking the violated valid inequalities. A new branching strategy that branches on thecycles found in the node relaxations of the MILP model is also introduced.Computational experiments are performed on the Solomon test problems. So far the mostsuccessful exact algorithms for the VRPTW applied shortest path decomposition to theproblem. When the proposed algorithm is compared with the other algorithms in theliterature, it has been shown that decomposition based exact algorithms (i.e., columngeneration, Lagrangean relaxation) do not perform the best for the entire Solomon testproblems, the performance of the proposed algorithm is better than decomposition basedexact approaches on the long horizon test problems.The second problem studied is the location-routing problem (LRP). The LRPconsists of selecting a subset of locations among given candidate facility locations anddetermining the vehicle routes to visit all the customers from the selected facilitylocations. We propose a column generation algorithm for the solution of the capacitatedlocation-routing problem in which we have multiple capacitated facilities and vehicles.The master problem in our column generation algorithm is a set-partition basedformulation which proved to be useful for a variety of routing problems such as thevehicle routing problem with time windows. For the pricing subproblem we solve theelementary shortest path problem with resource constraints (ESPPRC). The resultingalgorithm is tested on various LRP benchmark problems. The proposed columngeneration algorithm gives tight gaps for most of the benchmarks.
Benzer Tezler
- A solution approach for the vehicle routing problem with time windows and pick-ups and deliveries
Zaman pencereli ve toplamali ve daitimli araç rotalama problemi icin bir kurt optimizasyon algoritması
MILAD FARAMARZZADEH
Yüksek Lisans
İngilizce
2022
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ŞENER AKPINAR
- Araç planlama problemi ve problem için web tabanlı coğrafi bilgi sistemi tasarımı
Vehicle scheduling problem and geographic information system design for the problem
ARSLAN TAŞKIN
Yüksek Lisans
Türkçe
2012
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MURAT BASKAK
- Integrated vehicle routing and warehouse location problem
Entegre araç rotalama ve depo yerleşimi problemi
ARDA GEZDUR
Yüksek Lisans
İngilizce
2003
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SELÇUK SAVAŞ
YRD. DOÇ. DR. METİN TÜRKAY
- Vehicle routing problem with vendor selection, intermediate pick-ups and deliveries
Tedarikçi seçimli, ara dağıtım ve toplamalı araç rotalama problemi
UGUR EMEC
Yüksek Lisans
İngilizce
2013
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. BÜLENT ÇATAY
DOÇ. DR. BURÇİN BOZKAYA
- 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