Planning of Train Movements in Single Track Railways
Tezin Türü: Doktora
Tezin Yürütüldüğü Kurum: Yıldız Teknik Üniversitesi, Fen Bilimleri Enstitüsü, Türkiye
Tezin Onay Tarihi: 2015
Tezin Dili: İngilizce
Öğrenci: Gökçe Aydın
Danışman: İsmail Şahin
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Ö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.