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

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.