Algorithms for the vehicle routing problem with time windows and the location-routing problem

Abstract

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.

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.