Geri Dön

A comparative analysis on undirected cut-based formulations of periodic vehicle routing problem

Periyodik araç rotalama probleminin kesi temelli formülasyonları üzerine karşılaştırmalı bir inceleme

  1. Tez No: 762078
  2. Yazar: OĞULCAN DOĞAN
  3. Danışmanlar: DR. ÖĞR. ÜYESİ AMİNE GİZEM TİNİÇ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2022
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 53

Özet

Klasik Araç Rotalama Problemi (ARP), tek bir planlama periyodu içerisinde bir müşteri grubunun taleplerini karşılamak amacıyla türdeş araçlardan oluşan bir araç filosu için en düşük maliyetli rotaları belirlemeye çalışan bir kombinatoryal eniyileme problemidir. Periyodik Araç Rotalama Problemi (PARP), planlama döneminin birden çok periyottan oluştuğu ve her müşterinin bir dizi olası ziyaret çizelgesine sahip olduğu klasik ARP'nin bir genellemesidir. Literatürde bu problemi çözmek amacıyla önerilmiş kesin çözüm yöntemleri, sezgisel algoritmalar ve metasezgisel çözüm yaklaşımları bulunmaktadır. Bununla birlikte PARP literatüründe, kesi temelli formülasyonlara odaklanan kapsamlı çalışma eksikliği bulunmaktadır. Bu tezde, yönsüz bir çizge üzerinde tanımlanan bir PARP için, bir temel modeli ve beş alternatif kesi temelli formülasyon öneriyor ve bunları inceliyoruz. Alternatif formülasyonlar geliştirmek için bağlantı kısıtlarının ve çizelgeleme seçimi kısıtlarının farklı türevleri kullanılmaktadır. Ayrıca, PARP için araç indislerinin kullanımını ortadan kaldıran bir yönsüz ve kesi temelli formülasyon da ortaya çıkarılmıştır. Tüm formülasyonlar sayıca üstel olarak büyüyen bağlantı kısıtları içerdiğinden, önerilen formülasyonların kesin çözümüne ulaşabilmek amacıyla dal-ve-kesi algoritması tasarlanmış ve kullanılmıştır. Formülasyon ve çözüm yöntemlerinin belirlenmesinin ardından, tüm formülasyonlar için hesaplamalı deneyler hazırlanmış ve uygulanmıştır. Deneylerin sonuçları, bazı alternatif formülasyonların çözüm performansını iyileştirme potansiyeline sahip olduğunu göstermektedir. Araç indisleri olmayan model, en iyi sonuca ulaşma ve çözüm süreleri açısından iyileştirme sağlarken, alternatif çizelge seçim kısıtlarına sahip modeller, çözüm kalitesi ve ortalama çözüm süreleri açısından umut verici sonuçlar vermektedir.

Özet (Çeviri)

The classical Vehicle Routing Problem (VRP) is a well-studied combinatorial optimization problem whose aim is to identify optimal routes for a fleet of homogeneous vehicles to satisfy the demands of a geographically dispersed set of customers, considering a single planning period. The Periodic Vehicle Routing Problem (PRVP) is a generalization of the classical VRP in which the planning horizon consists of multiple periods and each customer has a set of associated possible visit schedules. In the literature, there are many solution approaches proposed such as exact solution methods, heuristic algorithms, and metaheuristics. However, exact solution methods are much fewer in number compared to heuristic methods, and a comprehensive study focused on cut-based formulations of the problem is not available in the literature. In this thesis, we propose and study several cut-based formulations of the PVRP defined on an undirected network. Different versions of connectivity constraints and schedule selection constraints are used to develop alternative formulations. Moreover, new cut-based formulations which eliminates the use of vehicle indices are also introduced. Since the proposed formulations contain exponentially many connectivity constraints, we devise and implement branch-and-cut procedures to solve them exactly. The computational experiments are prepared and conducted for all of the formulations. The results of the experiments indicate that some of the alternative formulations have the potential to improve computational performance. The model without vehicle indices provides improvement in terms of reaching optimality and computation times, while the models with alternative schedule selection constraints provide promising results in terms of solution quality and average computation times.

Benzer Tezler

  1. Turkish-British economic relations 2002-2012: An intensely political relationship

    Türk-İngiliz ekonomik ilişkileri 2002-2012: Yoğun derecede siyasi bir ilişki

    JOHN ANGLISS

    Yüksek Lisans

    İngilizce

    İngilizce

    2012

    Uluslararası İlişkilerOrta Doğu Teknik Üniversitesi

    Uluslararası İlişkiler Ana Bilim Dalı

    DOÇ. DR. EBRU BOYAR

  2. Çin Tömür Batur Destanı üzerine mukayeseli bir inceleme

    A Comparative analysis on the epic of Çin Tömür Batur

    ABDULHAKİM MEHMET

    Yüksek Lisans

    Türkçe

    Türkçe

    1999

    Halk Bilimi (Folklor)Ege Üniversitesi

    Halk Bilimi Ana Bilim Dalı

    YRD. DOÇ. DR. ALİMCAN İNAYET

  3. A comparative analysis on the perception of consumers about marketing and marketers: The case of Türkiye and Guinea

    Tüketicilerin pazarlama ve pazarlamacı kavramı algılarına ilışkin karşılaştırmalı bir analiz: Türkiye ve Gine örneği

    JEAN CLAUDE LAMAH

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    İşletmeTokat Gaziosmanpaşa Üniversitesi

    İşletme (İngilizce) Ana Bilim Dalı

    DOÇ. DR. ELİF BOYRAZ

  4. X, Y ve Z kuşaklarının gelinliğe bakış açılarının karşılaştırılmalı olarak incelenmesi

    A comparative analysis on the perspectives of the generations X, Y and Z on wedding dress

    MEDİNE KAYNAK

    Doktora

    Türkçe

    Türkçe

    2022

    Giyim EndüstrisiGazi Üniversitesi

    Giyim Endüstrisi ve Moda Tasarımı Ana Bilim Dalı

    PROF. FATMA ÖZTÜRK

  5. A comparative analysis on modification of social networks over links with mechanism combinations

    Mekanizma kombinasyonları ile linkler üzerinden sosyal ağların modifikasyonu üzerine karşılaştırmalı bir analiz

    MERVE ÜNAL

    Yüksek Lisans

    İngilizce

    İngilizce

    2021

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. GÖNENÇ YÜCEL