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ı: Belirtilmemiş.
Ö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
- 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
- A genetic algorithm for the location-routing problem with time windows
Zaman kısıtlı yerleşim-rotalama problemi için bir genetik algoritma
HANDE ÖZGÖNENÇ
Yüksek Lisans
İngilizce
2006
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. SEDEF MERAL
- Capacitated vehicle routing problem with time windows
Zaman kısıtlı araç rotalama problemi
EKİM ÖZAYDIN
Yüksek Lisans
İngilizce
2003
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiMühendislik ve Doğa Bilimleri Ana Bilim Dalı
YRD. DOÇ. DR. TONGUÇ ÜNLÜYURT
- An ant colony algorithm for the time-independent and time-dependent vehicle routing problem with time windows
Zaman-bağımsız ve zaman-bağımlı zaman kısıtlı araç rotalama problemine bir karınca kolonisi yaklaşımı
UMMAN MAHİR YILDIRIM
Yüksek Lisans
İngilizce
2008
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Bölümü
DOÇ. DR. BÜLENT ÇATAY
- An algorithm for the capacitated vehicle routing problem with time windows
Teslim zaman aralığı ve araç kapasitesi kısıtlı araç rotalama problemi için bir algoritma
OSMAN PEHLİVANOĞLU
Yüksek Lisans
İngilizce
2005
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SEDEF MERAL