Geri Dön

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

PDF İndir

  1. Tez No: 182073
  2. Yazar: SUAT BOĞ
  3. Danışmanlar: YRD. DOÇ. DR. SELÇUK SAVAŞ, YRD. DOÇ. DR. METİN TÜRKAY
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2006
  8. Dil: İngilizce
  9. Üniversite: Koç Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. Tez No

    392249

    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İ

    MERVE KESKİN

    Yüksek Lisans

    İngilizce

    İngilizce

    2014

    Endüstri ve Endüstri MühendisliğiSabancı Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. BÜLENT ÇATAY

  2. Tez No

    663973

    The capacitated vehicle routing problem with simultaneous pickup-delivery and time windows in the sustainable food supply chains

    Sürdürülebilir gıda tedarik zincirlerinde zaman pencereli ve eşzamanlı toplama-teslimatlı kapasite kısıtlı bir araç rotalama problemi

    MAHDI FARSHCHI

    Doktora

    İngilizce

    İngilizce

    2021

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. FATMA SEDEF MERAL

    PROF. DR. FERDA CAN ÇETİNKAYA

  3. Tez No

    752429

    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

    ECE NAZ DUMAN

    Doktora

    İngilizce

    İngilizce

    2022

    UlaşımSabancı Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. BÜLENT ÇATAY

    DR. ÖĞR. ÜYESİ DUYGU TAŞ KÜTEN

  4. Tez No

    604555

    The vehicle routing problem in urban logistics: Route balancing with time windows

    Başlık çevirisi yok

    BANU ULUSOY

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Endüstri ve Endüstri MühendisliğiKoç Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. METİN TÜRKAY

  5. Tez No

    329489

    Av arama algoritması ile sıkı zaman pencereli araç rotalama problemlerinin çözümü

    The solution vehicle routing problem with hard time windows with hunting search algorithm

    NİHAN GÜLSOY

    Yüksek Lisans

    Türkçe

    Türkçe

    2013

    Endüstri ve Endüstri MühendisliğiErciyes Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. SİNEM KULLUK

Geri Dön