Exact solution approaches for non-Hamiltonian vehicle routing problems
Hamilton olmayan araç rotalama problemleri için kesin çözüm yaklaşımları
- Tez No: 470039
- Danışmanlar: PROF. DR. HANDE YAMAN PATERNOTTE, PROF. DR. OYA KARAŞAN
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Ulaşım, Industrial and Industrial Engineering, Transportation
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 195
Özet
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.
Özet (Çeviri)
In this thesis, we study different non-Hamiltonian vehicle routing problem variants and concentrate on developing efficient optimization algorithms to solve them. First, we consider the split delivery vehicle routing problem (SDVRP). We provide a vehicle-indexed flow formulation for the problem, and then, a relaxation obtained by aggregating the vehicle-indexed variables over all vehicles. This relaxation may have optimal solutions where several vehicles exchange loads at some customers. We cut-off such solutions either by extending the formulation locally with vehicle-indexed variables or by node splitting. We compare these approaches using instances from the literature and new randomly generated instances. Additionally, we introduce two new extensions of the SDVRP by restricting the number of splits and by relaxing the depot return requirement, and modify our algorithms to handle these extensions. Second, we focus on a problem unifying the notion of coverage and routing. In some real-life applications, it may not be viable to visit every single customer separately due to resource limitations or efficiency concerns. In such cases, utilizing the notion of coverage; i.e., satisfying the demand of multiple customers by visiting a single customer location, may be advantageous. With this motivation, we study the time constrained maximal covering salesman problem (TCMCSP) in which the aim is to find a tour visiting a subset of customers so that the amount of demand covered within a limited time is maximized. We provide flow and cut formulations and derive valid inequalities. Since the connectivity constraints and the proposed valid inequalities are exponential in the size of the problem, we devise different branch-and-cut schemes. Computational experiments performed on a set of problem instances demonstrate the effectiveness of the proposed valid inequalities in terms of strengthening the linear relaxation bounds as well as speeding up the solution procedure. Moreover, the results indicate the superiority of using a branch-and-cut methodology over a flow-based formulation. Finally, we discuss the relation between the problem parameters and the structure of optimal solutions based on the results of our experiments. Third, we study the vehicle routing problem with roaming delivery locations (VRPRDL) in which a customer order has to be delivered to the trunk of the customer's car during the time that the car is parked at one of the locations in the (known) customer's travel itinerary. We formulate the problem as a set covering problem and develop a branch-and-price algorithm for its solution. The algorithm can also be used for solving a more general variant in which a hybrid delivery strategy is considered that allows a delivery to either a customer's home or to the trunk of the customer's car. We evaluate the effectiveness of the many algorithmic features incorporated in the algorithm in an extensive computational study and analyze the benefits of these innovative delivery strategies. The computational results show that employing the hybrid delivery strategy results in average cost savings of nearly 20% for the instances in our test set. Finally, we consider the dynamic version of the VRPRDL in which customer itineraries may change during the execution of the planned delivery schedule, which can become infeasible or suboptimal as a result. We refer to this problem as the dynamic VRPRDL (D-VRPRDL) and propose an iterative solution framework in which the previously planned vehicle routes are re-optimized whenever an itinerary update is revealed. We use the branch-and-price algorithm developed for the static VRPRDL both for solving the planning problem (to obtain an initial delivery schedule) and for solving the re-optimization problems. Since many re-optimization problems may have to be solved during the execution stage, it is critical to produce solutions to these problems quickly. To this end, we devise heuristic procedures through which the columns generated during the previous branch-and-price executions can be utilized when solving a re-optimization problem. In this way, we may be able to save time that would otherwise be spent in generating columns which have already been (partially) generated when solving the previous problems, and find optimal solutions or at least solutions of good quality reasonably quickly. We perform preliminary computational experiments and report the results.
Benzer Tezler
- Spektral renormalizasyon grubu ile ölçek envaryant çizgeler üzerinde kritik üstellerin hesaplanması
Critical exponents on scale invariant networks by using spectral renormalization group
ASLI TUNCER ÖZDEMİR
Doktora
Türkçe
2016
Fizik ve Fizik Mühendisliğiİstanbul Teknik ÜniversitesiFizik Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞE SİLİER
- Richardson solution for the spin-orbit coupled fermi gas
Spin-momentum bağlı fermi gazlarında Richardson çözümü
BUĞRA TÜZEMEN
Yüksek Lisans
İngilizce
2015
Fizik ve Fizik Mühendisliğiİstanbul Teknik ÜniversitesiFizik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. AHMET LEVENT SUBAŞI
- The generalized fractional Benjamin Bona Mahony equation: Analytical and numerical results
Genelleştirilmiş kesirli Benjamin Bona Mahony denklemi: Analitik ve sayısal sonuçlar
GÖKSU ORUÇ
Doktora
İngilizce
2021
Matematikİstanbul Teknik ÜniversitesiMatematik Mühendisliği Ana Bilim Dalı
PROF. DR. GÜLÇİN MİHRİYE MUSLU
DOÇ. DR. HANDAN BORLUK
- Group analysis of nonlinear dynamical systems
Nonlineer dinamik sistemlerin grup analizi
NAVID AMIRI BABAEI
Doktora
İngilizce
2024
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. TEOMAN ÖZER
- Fröhlich polaron calculations in non-integer dimensional space as a model of confinement
Bir sınırlama modeli olarak tamsayı olmayan boyutlu uzayda Fröhlich polaron hesaplamaları
GÖZDE ÖZBAL
Yüksek Lisans
İngilizce
2013
Fizik ve Fizik Mühendisliğiİzmir Yüksek Teknoloji EnstitüsüFizik Ana Bilim Dalı
PROF. DR. RAMAZAN TUĞRUL SENGER