Exact solution approaches for non-Hamiltonian vehicle routing problems

Bu tezde, Hamilton olmayan araç rotalama problemlerinin farklı varyasyonları üzerine çalışılmış ve bu problemleri etkin bir biçimde çözebilmek için eniyileme algoritmaları geliştirilmiştir. İlk olarak, bölünmüş teslimli araç rotalama problemi (BTARP) ele alınmıştır. Bu problem için araç endeksli akış değişkenleri içeren bir matematiksel model önerilmiş ve karar değişkenleri tüm araç endeksleri üzerinden toplanarak gevşetilmiş bir model elde edilmiştir. Gevşetilmiş modelin eniyilenmesi sonucunda bulunan çözümlerde, bazı talep noktalarında, birden fazla araç arasında yük değişimi gerçekleşebildiği gözlemlenmiştir. Bu yapıya sahip çözümleri olurlu çözüm kümesinden elemek için gevşetilmiş modelin yerel olarak genişletilmesine dayalı yöntemler geliştirilmiştir. Önerilen yöntemler literatürde bulunan problem örnekleri ve yeni rastgele yaratılmış örnekler üzerinde test edilmiş ve karşılaştırılmıştır. Ayrıca, talep noktalarına yapılabilecek teslimat sayısı kısıtlanarak ve araçların depoya geri dönme zorunluluğu ortadan kaldırılarak BTARP'nin iki yeni varyasyonu tanımlanmış ve BTARP için geliştirilen algoritmalar kullanılarak bu varyasonların da çözülebileceği gösterilmiştir. Tezin ikinci bölümünde, kapsama ve rotalama kavramlarını bir araya getiren bir probleme odaklanılmıştır. Bazı durumlarda, kısıtlı kaynakların verimli bir biçimde kullanılabilmesi için, her talep noktasını ayrı ayrı ziyaret etmek yerine, bunlar arasından seçilen daha az sayıda talep noktasını içeren bir rota bulmak daha avantajlıdır. Çünkü bu şekilde, rota üzerinde olmayan, ancak ziyaret edilen noktalara makul bir mesafe katederek ulaşabilecek olan noktaların da taleplerini kısmen karşılamak mümkün olabilir. Buradan yola çıkarak tanımlanan zaman kısıtlı maksimal kapsayan satıcı probleminde amaç, belirli bir zaman kısıtı altında, talep noktalarının bir altkümesini ziyaret ederek, toplamda kapsanan talep miktarını ençoklayan rotayı bulmaktır. Bu problem için akış ve kesi tabanlı formülasyonlar ve geçerli eşitsizlikler önerilmiştir. Alt tur eleme kısıtları ve önerilen eşitsizliklerden bazıları üstel sayıda olduğundan, problemi çözmek için dal ve kesi algoritmaları geliştirilmiştir. Yapılan sayısal analizler, dal ve kesi algoritmalarının problemi akış modeline kıyasla çok daha etkin bir biçimde çözebildiğini, önerilen geçerli eşitsizliklerin, kesi formülasyonunun doğrusal gevşetme sınırlarını oldukça güçlendirdiğini ve çözüm sürelerini ciddi oranda azalttığını göstermiştir. Ayrıca, sayısal analizlerden elde edilen sonuçlar kullanılarak, problem parametrelerindeki değişikliklerin eniyi çözümün yapısına olan etkileri de incelenmiştir. Tezin üçüncü bölümünde, gezici teslimat noktalı araç rotalama problemi (GTNARP) çalışılmıştır. Bu problemde, müşterilerin gün içinde ziyaret edip belirli bir zaman geçireceği konumların bilindiği varsayılmaktadır. Amaç, her müşterinin siparişinin, müşterinin aracının bagajına (araç verilen konumlardan herhangi birinde park halindeyken) teslim edilmesini sağlayacak, en düşük maliyetli rotaları belirlemektir. GTNARP, küme kapsama problemi olarak modellenmiş ve çözümü için etkin bir dal ve fiyat algoritması geliştirilmiştir. Bu algoritma, problemin daha genel ve hibrit bir teslimat stratejisi benimseyen (teslimatın bagaja veya eve yapılmasına izin veren) bir varyasyonunu da çözebilmektedir. Algoritmanın performansını geliştirmek için kullanılan yöntemleri test etmek ve yenilikçi teslimat stratejilerinin faydalarını araştırmak amacıyla sayısal analizler yapılmıştır. Elde edilen sonuçlar, önerilen dal ve fiyat algoritmasının büyük ölçekli problem örneklerini bile oldukça etkin bir biçimde çözebildiğini ve hibrit teslimat stratejisi kullanıldığında toplam maliyetin ortalama %20 oranında azaltılabileceğini göstermiştir. Tezin son bölümünde, müşterilerin planlarının teslimatlar başladıktan sonra değişebileceği göz önünde bulundurularak, GTNARP'nin dinamik bir varyasyonu ele alınmıştır. Bu değişiklikler sonucu, gün başında planlanan teslimat rotalarına bağlı kalmak mümkün olmayabilir veya daha düşük maliyete sahip alternatif rotalar ortaya çıkabilir. Dinamik GTNARP için, tezin bir önceki bölümünde bahsi geçen dal ve fiyat algoritmasını yinelemeli biçimde kullanan bir çözüm yaklaşımı önerilmiştir. Temel olarak, müşteri planlarındaki her değişiklikten sonra dal ve fiyat algoritması çalıştırılır ve teslimat rotalarının henüz yapılmamış teslimatları içeren kısımları yeniden planlanır. Rotaların sıklıkla güncellenmesi gerekebileceğinden, teslimatların aksamaması için yeniden planlamanın hızlı bir şekilde yapılması oldukça kritiktir. Bu sebeple, yeniden planlama problemleri çözülürken, dal ve fiyat algoritmasının önceki yinelemelerde türettiği sütunları kullanılabilir duruma getiren sezgisel yöntemler geliştirilmiştir. Böylece, dal ve fiyat algoritmasının, sütun türetmeye daha az zaman ayırarak, eniyi çözüme daha hızlı ulaşması veya kısa bir süre içinde eniyiye yakın çözümler bulması sağlanabilmektedir. Önerilen yöntemleri test etmek için bir ön hesaplama çözümlemesi gerçekleştirilmiş ve elde edilen sonuçlar rapor edilmiştir.