Heuristic and exact approaches for multi-objective routing
Çok amaçlı rotalama için sezgisel ve kesin yaklaşımlar
- Tez No: 330616
- Danışmanlar: PROF. DR. MUSTAFA MURAT KÖKSALAN
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Bölümü
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 150
Özet
Bu tezde, iki amaçlı rotalama problemini ele alıyoruz. Bu problem iki amaçlı en kısa yolu bulma problemi (hedefler arası etkin yolların bulunması) ve iki amaçlı gezgin satıcı probleminin (etkin yollardan oluşan etkin turların bulunması) birleşimidir. Etkin turların bulunması için çözüm yolları geliştirdik. Rotalama problemini iki farklı hareket alanında inceledik; karesel parçalara bölünmüş ayrık hareket alanı ve sürekli hareket alanı. Ayrık hareket alanında, hareket bölgesini eş büyüklükteki karelerle tanımladık. Aracın komşu noktalar arasında hareketine izin verdik. Sürekli hareket alanı durumunda, aracın iki boyutlu uzayda her türlü hareketi yapabileceği kabul edildi. En çok tercih edilen çözümü bulmak için öncelikle minimize edilecek tercih fonksiyonu konveks benzeri olan bir karar verici için iki amaçlı tamsayı programlamada kullanılabilecek genel bir interaktif algoritma geliştirdik. Sonrasında bu algoritmayı iki amaçlı rotalama probleminde uyguladık. Algoritma her iterasyonunda, birkaç etkin tur bulmaktadır. Bu etkin turları bulmak için, öncelikle hedef çiftleri arasındaki tüm etkin yolları bulduk ve bu yolları algoritmaya girdi olarak verdik. Kullanılabilecek etkin yolların sayısını azaltmak için, amaç fonksiyonları üzerinde kısıtlar olduğu durumda bazı kurallar geliştirdik. Yaklaşımımızı, ayrık hareket alanındaki insansız hava aracı (İHA) rotalama probleminde denedik. Ayrıca, sürekli hareket alanında rotalama problemini İHA rotalama problem özelinde inceledik. Her hedef çifti arasındaki etkin yolları bulmak için yöntemler geliştirdik. Sonrasında, etkin yollardan oluşan etkin turları karışık tamsayılı doğrusal olmayan programlama ile bulduk. Buna ek olarak, interaktif algoritmanın sürekli hareket alanındaki rotalama problemine nasıl uygulanabileceğini ele aldık.
Özet (Çeviri)
In this thesis, we consider the bi-objective routing problem. This problem is a combination of the bi-objective shortest path problem (finding the efficient arcs between nodes) and the bi-objective traveling salesperson problem (finding the efficient tours composed of efficient arcs). We develop solution procedures to find efficient tours. We consider two different terrain structures; discretized terrain and continuous terrain. In the discretized terrain, the terrain is approximated with grids and we allow the vehicle to move between adjacent grid points. In the continuous terrain, we consider a two dimensional plane and there are no restrictions on the movement of the vehicle. To find the most preferred solution, we first develop a general interactive algorithm for a decision maker whose preferences are consistent with an underlying quasiconvex function to be minimized for any bi-criteria integer program. We then apply our algorithm to the bi-objective routing problem. In each iteration of the algorithm, we find a number of efficient tours made up of the efficient arcs. For this, we initially find all efficient arcs between all pairs of nodes and introduce these arcs to the interactive algorithm. We establish some rules that decrease the number of efficient arcs required for finding an efficient tour that satisfies some constraints. We demonstrate the approach on the routing problem of unmanned air vehicles (UAVs) which are assumed to travel on a discretized terrain. We also study the routing problem in continuous terrain, specifically for the UAV routing problem. We develop methods to find the approximate efficient frontier of the shortest path problem between each node pair. We then find the efficient tours that use a subset of the efficient arcs using a mixed integer nonlinear program. We also discuss the implementation of the interactive algorithm for the routing problem in the continuous terrain.
Benzer Tezler
- Heuristic approaches for the multi-objective routing problem for a fleet of unmanned aerial vehicles
İnsansız hava aracı filosunun çok-amaçlı rotalama problemi için sezgisel yaklaşımlar
BÜŞRA BİŞKİN
Yüksek Lisans
İngilizce
2019
Endüstri ve Endüstri MühendisliğiHacettepe ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ DİCLEHAN TEZCANER ÖZTÜRK
DR. ÖĞR. ÜYESİ CEREN TUNCER ŞAKAR
- Bütünleşik üretim ve dağıtım çizelgeleme problemleri için çözüm yaklaşımları
Solution approaches for integrated production and distribution scheduling problems
ECE ÇETİN YAĞMUR
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiKonya Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. SAADETTİN ERHAN KESEN
- Exploring metaheuristic algorithms and solving phases for addressing a rich vrp encountered by a Turkish distributor
Türk dağıtıcıların karşılaştığı zengin araç rotalama problemi için metasezgisel algoritmaların ve çözüm süreçlerinin araştırılması
AHMAD BASSALEH
Yüksek Lisans
İngilizce
2024
Endüstri ve Endüstri MühendisliğiÖzyeğin ÜniversitesiEndüstri Mühendisliği ve Operasyon Yönetimi
Prof. EKREM DUMAN
Dr. MEHMET BAYRAM YİLDİRİM
- Belirsizlik altında heterojen filo ve zaman pencereli rotalama problemi: Hızlı tüketim sektöründe bir uygulama
Heterogeneous vehicle routing with time windows under uncertainty: Implementation in fast moving goods industry
ELÇİN ÖZEN KURU
Yüksek Lisans
Türkçe
2018
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. FERHAN ÇEBİ
- Channel assignment and routing for multi-radio wireless mesh networks
Çoklu radyolu kablosuz çokgen bağlantılı ağlarda kanal atama ve rotalama problemi
SITKI GÜLTEN
Yüksek Lisans
İngilizce
2008
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Bölümü
DOÇ. DR. OYA EKİN KARAŞAN