Geri Dön

Shortest path problem wıth dısjunctıve conflıct constraınts

Ayırıcı çatışma kısıtlı en kısa yol problemi

PDF İndir

  1. Tez No: 929844
  2. Yazar: BAHADIR PAMUK
  3. Danışmanlar: PROF. DR. İSMAİL KUBAN ALTINEL, PROF. DR. TEMEL ÖNCAN
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2025
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 120

Özet

Bu çalışmada oklar arasındaki ayrık çatışma ilişkilerini de dikkate alan birden çoka en kısa yol probleminin bir uzantısı ele alınmaktadır. Ayırıcı çatışma kısıtlı en kısa yol problemi olarak adlandırılan bu problemde, en kısa yol ağacının herhangi bir çatışan ok çifti içermesine izin verilmez. Polinom olarak çözülebilen birçok birleşimsel eniyileme probleminde olduğu gibi, çatışma ilişkilerinin eklenmesi problemi NP-zor yapar. Bu tez kapsamında üç yeni algoritma önerilmektedir. Önerilen ilk algoritma, birden çoka en kısa yol probleminin çözümünden, etkili bir güncelleme yordamından ve dallanmayı budamak için hızlı bir olursuzluk saptama yönteminden yararlanan bir dal ve sınır algoritmasıdır. İkinci olarak, en kısa yol problemine özgü olurluluk gerekli koşullarından yararlanan, derinlik öncelikli bir dalış algoritması geliştirilmiştir. Üçüncü olarak, çatışma çizgesinin bağımsız kümelerini kullanan, verimli bir tur önleyici dizgeden ve yine hızlı bir olursuzluk saptayıcısından yararlanan bir dal ve sınır algoritması geliştirilmiştir. Son olarak, hem rastgele oluşturulmuş hem de gerçekçi test örnekleri üzerinde kapsamlı bir şekilde test edilen yeni algoritmalar, piyasada bulunan en son teknolojiye sahip bir karma tamsayılı doğrusal program çözücü ile karşılaştırılmıştır. Kapsamlı bilgisayısal deneylere göre, yeni algoritmalardan en etkin olanı çözücüden çok daha başarılıdır. Diğerlerinin başarımları ise karşılaştırılabilir düzeydedir.

Özet (Çeviri)

An extension of the ordinary one-to-many shortest path problem that also considers additional disjunctive conflict relations between the arcs is considered in this study. In this problem called SPC, optimal shortest path tree is not allowed to include any conflicting arc pair. As is the case with many polynomially solvable combinatorial optimization problems, the addition of conflict relations makes the problem NP-hard. We propose three novel algorithms for SPC. One such algorithm is a novel branch-and-bound algorithm, which benefits from the solution of the one-to-many shortest path relaxation, an efficient primal-dual re-optimization scheme and a fast infeasibility detection procedure for pruning the branch-and-bound tree. The second solution method is a greedy depth first search algorithm, which benefits from the sufficient conditions of infeasibility special to shortest path problem. The third one is also a branch-and-bound algorithm; but it searches through the solution space using the stable sets of the conflict graph, benefiting from an efficient circuit prevention and a fast infeasibility detection procedure for pruning the branch-and-bound tree. Several MILP formulations are tested in order to find the best one. At last, new algorithms are extensively tested on both randomly generated and realistic test instances, comparing them with the best MILP formulation implemented with a state-of-the-art commercially available MILP solver. According to the obtained results, it is possible to say that the best of the novel algorithms outperforms the solver, while the other two's performances are comparable.

Benzer Tezler

  1. Tez No

    676636

    Automated curriculum design for reinforcement learning with graph theory and evaluation heuristics

    Çizge kuramı ve değerlendirme bazlı sezgisel yöntemler ile pekiştirmeli öğrenme için otomatik müfredat tasarımı

    ANIL ÖZTÜRK

    Yüksek Lisans

    İngilizce

    İngilizce

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. NAZIM KEMAL ÜRE

  2. Tez No

    222807

    Shortest path problem with re-routing en-route

    Yol üzerinde yeniden rotalamayı dikkate alan en kısa yol problemi

    BANU KARAKAYA

    Yüksek Lisans

    İngilizce

    İngilizce

    2008

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Bölümü

    YRD. DOÇ. DR. OSMAN ALP

  3. Tez No

    112588

    The Robust shortest path problem with interval data uncertainties

    Aralık sayılar belirsizliğinde en kısa yol problemi

    ABDULLAH SIDDIK KARAMAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2001

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

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

    DOÇ. DR. MUSTAFA Ç. PINAR

  4. Tez No

    433931

    Parallel algorithms for shortest path problem on time dependent graphs

    Zamana bağımlı çizgelerde en kısa yol problemi için paralel algoritmalar

    MEHMET AKİF ERSOY

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CAN ÖZTURAN

  5. Tez No

    394374

    Path planning for ships in the presence of obstacles

    Engelli ortamlarda gemiler için yol planlaması

    DİNDAR ÖZ

    Doktora

    İngilizce

    İngilizce

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. ALİ FUAT ALKAYA

    DOÇ. DR. VURAL AKSAKALLI

Geri Dön