Planning of train movements in single track railways
Tek hatlı demiryollarında tren hareketlerinin planlanması
- Tez No: 406540
- Danışmanlar: DOÇ. DR. İSMAİL ŞAHİN
- Tez Türü: Doktora
- Konular: Ulaşım, İnşaat Mühendisliği, Transportation, Civil Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: Yıldız Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: İnşaat Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Ulaştırma Bilim Dalı
- Sayfa Sayısı: 113
Özet
Demiryolu, kara ulaşım türleri arasında, taşınan yolcu-km veya ton-km başına enerji verimiliği en yüksek, arazi kullanımı en düşük tür olarak bilinmektedir. Ayrıca, yük taşımacılığındaki ekonomik verimliliği de karayoluna göre daha yüksektir. Yolcu taşımacılığında, belirli bir mesafeye kadar olan taşımalarda, havayoluna karşı da, enerji verimililiği bakımından üstünlük göstermektedir. Bu nedenlerle, çevresel ve ekonomik sürdürülebilirlik adına, taşımacılıkta demiryolunun pazar payının yükseltilmesi büyük önem taşımaktadır. Daha iyi bir dakiklik marifetiyle müşteri memnuniyetinin arttırılması, bu konuda geliştirilebilecek stratejilerden biridir. Gerçekte, çoğu demiryolu sisteminde, trenler, önceden belirlenmiş bir zaman çizelgesine göre hareket etmektedir. Bu çizelgede, trenlerin, rotaları üzerinde bulunan tüm referans noktalarına (istasyonlar, saydingler) varış, bu noktalardan kalkış ya da bu noktalardan durmadan geçiş zamanları kayıtlıdır. Günlük işletimde, trenlerden bazıları, çeşitli sebeplerden dolayı gecikebilir. Bu gecikmeler, bir yayılma etkisi yaratarak, diğer trenlere de sirayet etmektedir. Sonuç olarak, hazırlanan zaman çizelgesi geçerliliğini yitirmekte, yeniden çizelgeleme gereksinimi ortaya çıkmaktadır. Yeniden çizelgelemeyi verimli bir şekilde yapmak, sistemin dakiklik performansının artmasını sağlayacaktır. Uygulamada, yeniden çizelgeleme, dispeçer adı verilen operatörler tarafından, elle yapılmaktadır. İnsan beyninin hesap yeteneği sınırlıdır. Bu durum, insanlar tarafından elle yapılan yeniden çizelgemenin kalitesi üzerine sınırlar koymaktadır. Günümüzün modern bilgisayarlarının hesap yeteneklerinden yararlanarak, bu verimliliği arttırmak mümkündür. Bu tez çalışmasında, öncelikle, tek hatlı bir demiryolunda yeniden çizelgeleme probleminin optimum çözümünü verecek bir matematiksel model geliştirilmiştir. Bu model, demiryolu işletimi ile ilgili pek çok kısıtı (örn. istasyon ve saydinglerin kapasiteleri) dikkate almakta ve trenlerin ağırlıklandırılmış gecikmelerinin xvii toplamını en küçüklemeyi amaçlamaktadır. Tren çizelgelemesi problemi, güçlü bir NP-Tam problemdir. Problemin bu doğası, geliştirilen model, 4 adet doğu yönlü ve 3 adet batı yönlü tren gibi küçük boyutlu problemler üzerinde denendiğinde bile kendini açık olarak göstermiştir. Bu, yeniden çizelgeleme için büyük bir handikaptır. Yeniden çizelgeleme problemi, dinamik bir ortamda çözülmek durumundadır. Trenler hareket halindedir ve algoritmanın çözüm üretmesi çok uzun sürecek olursa, çözüm süresi içinde trenlerde ilave gecikmeler meydana gelebilecektir. Bu durum gerçekleşirse, modelin ürettiği çözüm değersiz hale gelecektir. Net olmak gerekirse, bir yeniden çizelgeme algoritmasının, işini en fazla 5 ancak tercihen 3 dakika içinde bitirmesi gerekmektedir. Düz bir karışık tamsayılı programlama modeli, bu iş için yetersiz kalmaktadır. Böyle bir model, mutlaka bazı ilave prosedürler ile desteklenmelidir. Bu tezde, bu prosedürlere“hızlandırma rutini”adı verilmiştir. Çalışmada, üç farklı hızlandırma rutini kullanılmıştır. Bunlardan ilki, AIMMS'in“lazy constraint”özelliğini aktifleştirmektir. AIMMS, kullanıcıya, optimum çözümde bağlayıcı olma olasılığ çok düşük olan kısıtları“lazy”olarak işaretleme olanağı sunmaktadır.“Lazy”olarak işaretlenen kısıtlar, ilk başta problemin doğrusal programlama gevşetmesine dahil edilmemektedir. Bu kısıtlar dahil edilmeden çözülen doğrusal programlama gevşetmesinin çözümünün bu kısıtları ihlal edip etmediği kontrol edilmektedir. İhlal ettiği kısıt varsa, bu kısıt, kısıt havuzuna yeniden dahil edilmekte ve DP gevşetmesi yeniden çözülmektedir. Bu çalışmada, istasyon / sayding kapasitesi kısıtlarının büyük çoğunluğu“lazy”olarak işaretlenmiştir. İkinci hjızlandırmarutini, sezgisel bir çözüm uzayı kısıtlama algoritmasıdır. Bu algoritma, ilk önce, açgözlü bir algoritma kullanarak, problem için bir çözüm üretmektedir. Bu açgözlü algoritma, istasyon ve sayding kapasitelerini, hattın kilitlenmesi durumunu dikkate almamaktadır. Bu çözüm üretildikten sonra, ana modelin çözümü, açgözlü algoritmanın ürettiği çözümden fazla uzaklaşamayacak şekilde kısıtlanmaktadır. Bu algoritma, modelden yüzlerce ikili değişkeni ve binlerce kısıtı attığı için, çözüm hızında radikal bir iyileşme sağlamaktadır. Ancak, bulunan çözümün optimum olduğu artık garanti edilememektedir, lakin, üretilen çözümlerin oldukça iyi olduğu görülmüştür. Üçüncü hızlandırma rutini olarak, bir çok amaçlı optimizasyon uygulaması yapılmıştır. Bu uygulamada, ana problem ile tamamen aynı karar değişkenleri ve uygun çözümler bölgesine sahip, ancak amaç fonksiyonu farklı bir problem çözülmektedir. Bu problemin amaç fonksiyonu, tüm trenlerin ağırlıklandırılmış gecikmelerinin maksimumunu minimize etmektir. Bu problemin optimum çözümü, ana problem için başlangıç uygun çözümü olarak kullanılmaktadır. Ayrıca, ana problemdeki trenlerin ağırlıklandırılmış gecikmeleri, ilk problemde bulunan maksimum değeri geçmeyecek şekilde kısıtlanmıştır. Nihai model, 18 istasyonu bulunan, hayali bir tek hatlı demiryolunda test edilmiştir. En kötü durumda, tüm bu hızlandırma rutinleri ile birlikte, model, 6 doğu yönlü ve 5 batı yönlü tren içeren problemleri 3 dakikanın altında bir süre içinde çözebilmiştir.
Özet (Çeviri)
Railway is known to be the best mode of land transport in terms of energy consumption and land use per passenger-km or ton-km transported; and also in terms of economic efficiency for freight transportation. It is also known to be superior to air transport in terms energy consumption per passenger-km up to some specific distance of travel. Thus, it is of crucial importance to increase the market share of rail transport for economic and environmental sustainability. Customer satisfaction through better punctuality is one of the possible strategies towards this purpose. In reality, most of the railways operate according to a timetable, within which, all trains have predetermined departure times from, arrival times at and / or passing times without stopping through all the reference points (stations, sidings) in their routes. In daily operation, some of the trains may get delayed for various reasons. This creates a knock-on effect, spreading the delay to other trains. Thus, the timetable becomes invalid, and rescheduling of the traffic becomes necessary. Efficient rescheduling helps the railway system be more punctual. In practice, rescheduling is done by human operators (called dispatchers) by manual methods. Human brain has a limited computational ability. This puts an upper limit on the effectiveness of rescheduling solutions produced manually by humans. Fortunately, the computational power of today's modern computers can provide significant improvement. In this thesis, first, a mixed integer programming model for solving the rescheduling problem on a single track railway line to optimality is developed. The model considers most of the real constraints in a real railway operation like deadlock prevention and capacities of stations/sidings and aims to minimize the total weighted delay of the trains. Train scheduling is a strongly NP-Complete problem. This nature of the problem was clearly observed even in the small sized problems, like 4 eastbound trains and 3 westbound trains. This is a big drawback in a rescheduling problem, because rescheduling has to be done in a dynamic environment. Trains are xv moving and they can get some additional delays during the computation process, if it takes too long. This would make the solution produced worthless. To be specific, any algorithm for train rescheduling has to finish its job in at most 5 minutes, but, preferably, in 3 minutes. Therefore, a plan mixed-integer programming proved to be inadequate for rescheduling. It has to be supported with some additional procedures. We call these procedures as“speed-up routines”. In this thesis, three different speed-up routines were used. The first was using the“lazy constraint”attribute of AIMMS. This attribute enables the user to mark the constraints that are unlikely to be binding. Then, the solver excludes them when computing the linear programming relaxation of the model and checks to solution of the linear programming relaxation against the constraints marked as“lazy”. If it finds that one of the lazy constraints is violated, it adds the violated constraint into the constraint pool and re-solves the linear programming relaxation. In the model, most of the station / siding capacity constraints were marked as lazy. The second speed-up routine was a heuristic solution space restriction algorithm. The algorithm first produces a solution by implementing a greedy algorithm. This algorithm neglects the station / siding capacity constraints and deadlock prevention. Then, it restricts the solution to be not much different from the outcome of the greedy heuristic. This eliminates hundreds of binary variables and thousands of constraints from the model and provides a radical increase in the model's computational speed. However, the optimality of the solution is no longer guaranteed, although the model produces good solutions. The third speed-up routine was adopting a multiobjective approach. The objective of the main model is to minimize the total weighted delay of all trains. In the multiobjective approach, first, a problem with the same variables, parameters and feasible region, but a different objective function is defined. The objective function is minimizing the maximum weighted delay of all trains. Then, the optimal solution from this model is used as an initial feasible solution for the main problem. Also, in the main problem, weighted delay of each train is constrained not to exceed the maximum weighted delay computed in the first problem. This routine also provided a speed-up. The final model was tested on a hypothetical single track railway line with 18 stations. In the worst cases, the final model with all the speed up routines managed to solve the problems with 6 eastbound trains and 5 westbound trains in less than three minutes.
Benzer Tezler
- Tek hatlı demiryollarında çatışma çözümlerinin gecikme odaklı istatistiksel analizi
Statistical analysis of delay-based conflict resolutions in single-track railways
İREM OLGAY ŞENKARDEŞ
Yüksek Lisans
Türkçe
2023
UlaşımYıldız Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. İSMAİL ŞAHİN
- Tramvay istasyonlarında tasarım ve güvenlik esaslarının araştırılması: İstanbul T1 Tramvay Hattı incelemesi
Tram stop design and safety parameters research Istanbul T1 Tram Line sample survey
ESİN KASIMOĞLU
Yüksek Lisans
Türkçe
2015
Ulaşımİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. ZÜBEYDE ÖZTÜRK
- Haberleşme temelli tren kontrol sisteminde emniyetli fren modeli
Safe braking model in communication based train control system
CAN BERK GENÇER
Yüksek Lisans
Türkçe
2020
Ulaşımİstanbul Teknik ÜniversitesiRaylı Sistemler Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET TURAN SÖYLEMEZ
- An algorithm to generate alternative train schedules on single trace railroads
Tek hatlı demiryollarında alternatif tren tarifeleri üreten bir algoritma
HİKMET BAYIRTEPE
Doktora
İngilizce
1995
İnşaat MühendisliğiOrta Doğu Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF.DR. ÖZDEMİR AKYILMAZ
- Zaman – mekân boyutuyla kentsel erişilebilirliğe yönelik analiz araçlarının belirlenmesi: Engelliler örneği
Determining of analysis tools for urban accessibility with the time-space approach: The example of the people with disabilities
OZAN ARİF KESİK
Doktora
Türkçe
2023
Bilim ve Teknolojiİstanbul Teknik ÜniversitesiBilişim Uygulamaları Ana Bilim Dalı
PROF. DR. ARİF ÇAĞDAŞ AYDINOĞLU