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
- Tez No: 246745
- Danışmanlar: YRD. DOÇ. DR. OSMAN ALP
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2009
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Bölümü
- Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- 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
- 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
2019
Endüstri ve Endüstri MühendisliğiYıldız Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ TUFAN DEMİREL
- 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
2024
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MERVE CENGİZ TOKLU
- Sivil havacılıkta uçucu ekip çizelgelemesi
Crew scheduling in civil aviation
GÖKHAN KORKMAZ
Yüksek Lisans
Türkçe
2013
Sivil HavacılıkHava Harp Okulu KomutanlığıEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. TUFAN DEMİREL
- 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
2021
Denizcilikİstanbul Teknik ÜniversitesiDeniz Ulaştırma Mühendisliği Ana Bilim Dalı
DOÇ. DR. EMRE AKYÜZ