Geri Dön

Exact solution approaches for non-Hamiltonian vehicle routing problems

Hamilton olmayan araç rotalama problemleri için kesin çözüm yaklaşımları

  1. Tez No: 470039
  2. Yazar: AMİNE GİZEM ÖZBAYGIN
  3. Danışmanlar: PROF. DR. HANDE YAMAN PATERNOTTE, PROF. DR. OYA KARAŞAN
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Ulaşım, Industrial and Industrial Engineering, Transportation
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2017
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    Türkçe

    2016

    Fizik ve Fizik Mühendisliğiİstanbul Teknik Üniversitesi

    Fizik Mühendisliği Ana Bilim Dalı

    PROF. DR. AYŞE SİLİER

  2. 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

    İngilizce

    2015

    Fizik ve Fizik Mühendisliğiİstanbul Teknik Üniversitesi

    Fizik Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. AHMET LEVENT SUBAŞI

  3. 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

    İngilizce

    2021

    Matematikİstanbul Teknik Üniversitesi

    Matematik Mühendisliği Ana Bilim Dalı

    PROF. DR. GÜLÇİN MİHRİYE MUSLU

    DOÇ. DR. HANDAN BORLUK

  4. Group analysis of nonlinear dynamical systems

    Nonlineer dinamik sistemlerin grup analizi

    NAVID AMIRI BABAEI

    Doktora

    İngilizce

    İngilizce

    2024

    İnşaat Mühendisliğiİstanbul Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    PROF. DR. TEOMAN ÖZER

  5. 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

    İngilizce

    2013

    Fizik ve Fizik Mühendisliğiİzmir Yüksek Teknoloji Enstitüsü

    Fizik Ana Bilim Dalı

    PROF. DR. RAMAZAN TUĞRUL SENGER