Geri Dön

A heuristic algorithm for an integrated routing and scheduling problem with stops en-route

Yol üzerinde durmayı dikkate alan bütünleşik rotalama ve çizelgeleme problemleri için sezgisel bir yöntem

  1. Tez No: 246745
  2. Yazar: EMRE UZUN
  3. Danışmanlar: YRD. DOÇ. DR. OSMAN ALP
  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: 2009
  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 Bölümü
  12. Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  13. Sayfa Sayısı: 80

Özet

Bu calışmada karayollarında tehlikeli madde taşıyan araçlarda sıkça karşılaşılan bütünleşik rotalama ve çizelgeleme problemi incelenmiştir. Problemin amacı, bir ağ üzerindeki iki nokta arasında en düşük riski veren bir rota ve bu rota üzerinde seyreden tehlikeli madde taşıyan bir aracın nerede ve ne kadar durması gerektiğini belirten bir çizelge bulmaktır. Problemin hedefi, rota üzerinde herhangi bir kaza durumunda etkilenecek ve gün içerisinde değişen ortalama insan sayısnı en aza indirgeyecek, önceden belirlenmiş bir süre içerisinde kat edilmesi gereken rotayı ve çizelgeyi belirlemektir. Literatürde bu problemi optimal olarak çözen algoritmalar mevcuttur. Ancak bu algoritmalar büyük boyutlu ağlarda yetersiz kalmaktadır. Bu tezdeki amaç, büyük boyutlu ağlarda çalışabilecek bir sezgisel yöntem geliştirmektir. Problemin rotalama ve çizelgeleme süreçleri, birbirleri ile iletişim halinde olan iki ayri süreç olarak belirlenip, bunlar için farklı çözüm yöntemleri geliştirilmiştir. Rotalama için her iterasyonda bir önceki iterasyonun en iyi rotasını kullanarak yeni rotalar üreten bir sezgisel yöntem üzerinde durulmuştur. Çizelgeleme için ise karışık tamsayılı programlama, dinamik programlama ve sezgisel yöntemler olmak üzere üç ayrı yaklaşım tartışılmıştır. Geliştirilen algoritma çeşitli test ağlarında uygulanmış ve performansı optimal sonuçlar ile karşılaştırılmıştır. Ayrıca, Türkiye Karayolları Ağı kullanılarak algoritmanın büyük ağlardaki performansı test edilmiştir.

Özet (Çeviri)

In this study, we examine an integrated routing and scheduling problem thatarises in the context of transportation of hazardous materials. The purpose ofthe problem is to nd a minimum risk route between an origin and a destinationpoint on a given network and to build a schedule on this route that determineswhere and how long to stop for a truck carrying hazardous materials. The objectiveis to minimize the risk imposed to the society while completing the pathwithin a given time limit. The risk is dened as the expected population exposurein the presence of an accident which varies dierent times in a day. Thereare exact algorithms available in the literature that solve the problem. However,these algorithms are not capable of solving large sized networks due to memoryconstraints. Our aim is to develop a heuristic procedure that can handle largernetworks. We separate the problem into two independent components, routingand scheduling, and propose solution algorithms which would communicate eachother when running the algorithm. For the routing component we dene a neighborhoodstructure that can be used to generate several paths around a givenpath on a network. The search procedure takes an initial path and improvesit by generating dierent paths in the dened neighborhood. For the schedulingcomponent, we discuss mixed integer programming, dynamic programmingand heuristic approaches. We run the proposed heuristic algorithm on severaltest networks and compare its performance with the optimal solutions. We alsopresent the application of the heuristic procedure on a large sized Turkey RoadNetwork.

Benzer Tezler

  1. Esnek üretim sistemlerinde çizelgeleme

    Flexible manufacturing systems scheduling

    SERAP AKKUŞ TUNCER

    Yüksek Lisans

    Türkçe

    Türkçe

    1993

    İşletmeİstanbul Teknik Üniversitesi

    PROF. DR. AYHAN TORAMAN

  2. Havayolu operasyonlarında uçuş eşleme için sezgisel bir yaklaşımın geliştirilmesi

    Development of a heuristic algorithm approach for airline crew pairing problem in airline operations

    MELEK SEBİLE KURTER

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    Endüstri ve Endüstri MühendisliğiYıldız Teknik Üniversitesi

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

    DR. ÖĞR. ÜYESİ TUFAN DEMİREL

  3. Karınca kolonisi ve parçacık sürü optimizasyonu algoritmaları ile 360 derece performans değerlendirme modeli: Bir yazılım firmasında uygulaması

    A 360-degree performance evaluation model using ant colony and particle swarm optimization algorithms: An application in a software company

    ZEYNEP YAĞIZ

    Yüksek Lisans

    Türkçe

    Türkçe

    2024

    Endüstri ve Endüstri MühendisliğiSakarya Üniversitesi

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

    DOÇ. DR. MERVE CENGİZ TOKLU

  4. Sivil havacılıkta uçucu ekip çizelgelemesi

    Crew scheduling in civil aviation

    GÖKHAN KORKMAZ

    Yüksek Lisans

    Türkçe

    Türkçe

    2013

    Sivil HavacılıkHava Harp Okulu Komutanlığı

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

    YRD. DOÇ. TUFAN DEMİREL

  5. Karınca kolonisi optimizasyonu ve genetik algoritma tabanlı tramp gemi rotalama ve çizelgeleme

    Ant colony optimization and genetic algorithm based tramp ship routing and scheduling

    SEHER SUENDAM ARICI

    Yüksek Lisans

    Türkçe

    Türkçe

    2021

    Denizcilikİstanbul Teknik Üniversitesi

    Deniz Ulaştırma Mühendisliği Ana Bilim Dalı

    DOÇ. DR. EMRE AKYÜZ