01.04.2019, 13:23
Ulaştırma ve Toplu Taşıma Sistemlerinde Sıklık - 7
Formülasyonlar plancıların akım atamalarına (v ve w değişkenleri) ilişkin yolcu kararlarının ikamesi gibi sıklık (y değişkeni) tayinleri ile ilgili el zamanlı kararlarını çözümlemektedir. Amaç fonksiyonu; kısıtlar, y değişkeni ve ihtimal dâhilindeki bağıntıları içermemesine karşın, model bu değerleri, bu gibi değişkenleri içeren kısıtlara göre v’nin minimize edilmesi için tercih edecektir. Yay akım değer v, amaç fonksiyonunda, akım korunumu ve yay uygunluğuna (örneğin sıklık) tabi olarak minimize edilmektedir. Bekleme süresi w aynı zaman amaç fonksiyonunda minimize edilirken, kısıt aldığı değer ile daha düşük bir bağıntı sergilemektedir.
Kısıtlarla ilgili olarak hatlara (y’nin sabitlenmiş değeri) sıklıkların verili bir dizini için gözlemler dâhilinde, sonuçlanan doğrusal (lineer) problem formüllerde belirtildiği üzere bağımsız bir atama problemini teşkil etmektedir. Kısıt yl(a()f(a) = 1 için ihtiyaç dışı olduğunda, sabitlenmiş bir sıklığı içermekte olup dahası v ve w değişkenlerinin dâhil olduğu diğer kısıtların yokluğunda, önerilen karma tam sayılı tekil düzeyli formülasyon 1995 yılında yapılan referans çalışmalarda önerilmiş olan doğrusal olmayan tek düzeyli formülasyona denktir (bir ayrışıklıkla sınırlı).
Bu tarz çalışmalar kapsamında önerilen dönüşümler, bir diğerinden farklı olarak problemin karmaşıklığının orijinal kaynağını değiştirmektedir. Orijinal formülasyon aynı düzeyli doğrusal olmayan (standart çözüm yöntemi bulunmayan) iken önerilen formülasyon ise karma tam sayılı doğrusaldır (kesin çözüm yöntemleri bulunan). Önerilen formülasyonun karmaşıklığının temel kaynağı, ikili değişkenlerin varlığı olup dahası sıklık aralıklarının ayrışıklığı, ihtimal dâhilindeki sıklıkların θ dizisindeki boyutuna eşit olan bir katsayıya biniş yayı (ve v değişkenlerinin sayısı yerine) serisini genişletmektedir.
Önerilen tam sayılı doğrusal programlama (MILP) formülasyonunun sıklık optimizasyon problemine optimal bir çözüm hesaplama imkanı vermesine karşın, büyük boyutlu numunelerin çözümünün zor olacağı öngörülmektedir. Sıklık aralıklarının ayrışıklığının uygulanması ile birlikte, problemin çözüm alanının üssel olacağı (lθllLl)terkibi bir duruma (en kötü durum) dönüşeceği de vurgulanmalıdır.
Bu karmaşıklığın üstesinden gelmek için tabu araştırmasına dayalı bir sezgisel ötesi yaklaşım önerilmiştir. Yöntem sıklık alanlarında kısmi bir araştırmaya dayalı iken (plancının kararı bu yönde olduğundan) kullanıcı kararlarını gösteren değişkenler atama alt modelinin devreye sokulması ile hesaplanmaktadır. Kısmi optimuma yönelmekten kaçınmak için kısmi arama mekanizmasının temeline tabu konsepti uygulanmaktadır. Araştırma stratejisi işletimciye dayalı olarak yapılandırılırken gerçek problemle bilgiyi birleştirmektedir. Ardından bir indirgeme yöntemi yapısal olarak bu işletimcilerin başarılı bir uygulamasınca tanımlanmaktadır. Atama alt modeline (hesaplamalı maliyetli olabilen) olan sıkı bağımlılığı engellemek için tabu araştırmasının özel bir mekanizması uygulanmaktadır. Nüfus bazlı bir sezgisel ötesi yaklaşımın (genetik algoritmalar gibi) her bir üretim prosesinin çok sayıda kişi üzerinden değerlendirmeye neden olmasından dolayı, benzer bir mekanizma gerektirmesi gerektiği de not edilmelidir. Bu bağlamda önerilen sezgisel ötesi yaklaşım dâhilindeki temel anlayışlar değerlendirilmektedir.
Kısmi prosedür verili herhangi bir çözümde yakınsaklığı belirlemek için devreye sokulan bir işletimi kullanan bir çalışmadır. Bu tarz çalışmalar kapsamındaki çözüm θ sıklığı dizisine endeks düzenleme yolu ile ortaya konmaktadır. Düzendeki her bir alan toplu ulaştırma sistemindeki bir hattı temsil etmekte ve sahip olduğu değer de söz konusu hattın sıklığını ifade etmektedir. İhtimal dâhilindeki sıklıklar dizisinin en düşük değerden (θ1) en yüksek değere (θm) sıralandığı kabulü yapılmaktadır. Bu yolla bir hat sıklığı artarken (ya da azalırken) θ’daki en yüksek (ya da en düşük) değerine ulaşmaktadır. Bu kapsamdaki bir çözümdeki bir hat sıklığının azalmasının gözlemlendiğinde, her zaman için cazibesini (kullanıcı açısından) ya da en üst limitini düşüreceği görülmektedir. Buna karşılık bir çözümdeki bir hat sıklığındaki bir artış ise onu daha cazip hale getirmekte ya da alt limitini yükseltmektedir. Yakınsaklık yapısını tanımlayan hareket işletimi, bir artış bir düşüş değişimi şeklinde, çözümün hat sıklığının bir çiftindeki yoğunlaşmış değişimdir. Bu temel işletim dâhilinde her bir çözüm, lLl X (lLl-1) komşu çözüme sahip iken her bir hattın sıklığı azalabilir ya da artabilir.
Tabu araştırması sezgisel ötesi bir yaklaşım olup kısmi optimallikten öte çözüm alanını tayin etmek için kısmi bir prosedüre kılavuzluk etmektedir. Bunu yapmak için de araştırma mevcut çözümü kötüleştiren rotaları kabule edebilir ve o zamana kadar icra edilmiş kimi rotaları da engelleyebilir. Tabu araştırmasının temel unsurlarından birisi de hafıza kullanımıdır. Bu tarz çalışmalar kapsamında kısa vadeli hafıza stratejilerine odaklanılmaktadır.
Bu tarz çalışmalar kapsamında kısa vadeli hafıza olarak adlandırılan en genel tür kullanılmaktadır. Tabu başlangıçlı olarak adlandırılan bir tabu listesi, en son iterasyonu kaydetmekte iken her bir hat kendi sıklığına göre değişmektedir. Her bir hatta Test-artışı ve Test-azalışı ikame edilerek sırası ile sıklıklarının artış ve azalışı temin edilmektedir. Eğer iterasyon < Tabu başlangıçlı (Test-azalışı) + sabit ya da iterasyon < Tabu başlangıçlı (Test-artışı) + sabit ise hareketin (Test-azalışı ya da Test-artışı) tabuda aktif olduğu söylenir. Bu çözümlemedeki iterasyondan kasıt, tabuyu aktive bir hareketin bulunduğu durumdaki iterasyonların sayısını gösteren sabiteye bağlı olarak mevcut iterasyon sayısını göstermektedir. Genel ifade ile araştırma mekanizması genellikle tabuyu aktif hale getiren hareketlerden kaçınmaktadır. Bununla beraber tabuyu aktif hale getirmeyen hareketlerin sayısı azdır, amaç kriterleri dâhilinde ilave mekanizmalar uyarlanmaktadır.
Amaç kriterleri, tabu aktivasyon kurallarının iptal edilebilirliği paralelinde, hesapta uygulanmaktadır. Bu tarz çalışmalar kapsamında, maliyeti dâhil edilen çözümlerin (yolcu atama alt modeline bir gereksinime neden olduğundan) amaç değerlerinin hesaplamalarının verilmesi ile birlikte, sadece hat sıklıklarının herhangi birisindeki tabuyu aktif hale getiren durumların dışındaki yakınsak çözümler değerlendirilmektedir. İhtimal dâhilindeki yakınsak çözümlerin sayısı Nmin (algoritmanın bir parametresi) minimum eşik değerinden öte olan tabuyu aktif hale getirmeyen hareketlerin (sıklıkları artırıp azaltabilen hatların sayısının ürünü şeklinde hesaplanarak) ortalamasınca özel olarak sağlanırken, uygulanan amaç kriteri, Nmin tarafından belirlenen yakınsak çözümlerin sayısı minimuma ulaşana kadar en düşük Tabu başlangıçlı (TestX) + sabit (X’in artış ya da azalışın yerine ikame edildiği) hat sıklıklarının tabuyu aktif hale getiren durumu gerçekleştirmektedir. Bu hükmen, amaç olarak kabul edilmektedir.
1-Eğer minimum<i+e<maksimum -> i + ilave yakınsaklıklar,
Aday yakınsak çözümler yukarıda açıklanan stratejiden elde edilen sonuçlarla rassallık kuralına göre değerlendirilmektedir.
Bu kapsamda kesin model açıklamalarının uygulanmasından ve yaklaşık çözüm yönteminin uygulanmasından elde edilen sayısal sonuçlar raporlanmıştır. Bu kapsamda üç temel test durumu kullanılmaktadır:
1-1980 yılında yapılan çalışma küçük bir şehir olan Mandl’daki durumu ifade etmektedir. Grafiği 15 düğüm noktası ve 21 doğrudan olmayan uçtan oluşmaktadır. Bu durumla ilgili herhangi bir güzergâh ağı olmadığından dolayı, belirli bir çalışmadaki amaca göre ağ türetilmiştir. OD matrisi 172 O-D çiftinden oluşmakta olup bu, düğüm noktası sayısına göre oldukça büyük bir değeri ifade etmektedir.
2-Uruguay’ın Rivera şehrindeki durumdur. Grafiği 84 düğüm noktası ve 143 doğrudan olmayan uçtan oluşmakta iken OD matrisi 378 O-D çiftinden oluşmakta olup 12 saatlik bir zaman aralığındaki talebi ifade etmektedir. Şehrin toplu ulaştırma sistemini temsilen bir hat dizi hesaba katılmış olup inşa edildiği 2003 yılı itibari ile işletime alınmış, gidiş-geliş istikametli 11 hat ve 2 dairesel hattan oluşmaktadır.
3-Uruguay’ın başkenti Montevideo’ya karşılık gelen durumdur. Belirtilen grafiği 4945 düğüm noktası ve 14.672 uçtan oluşmakta olup 133 otobüs güzergâhına sahip bir toplu ulaştırma sistemini ifade etmektedir. Kalkış-varış verisi (hem O-D yerleşimi ve hem de seyahat miktarı) rassal olarak üretilmekte, gerçekçi özellikler oluşturulmaya çalışılmakta olup söz konusu durum, şehre eşit olarak dağıtılmış 7425 O-D çiftini içermektedir.
İlk iki durumda grafiğin elemanları yüksek dereceli ayrışıklıkta verilmiş, ayrıca her bir düğüm noktasının bir otobüs durağı gibi rota kesimlerinin potansiyel bir bitiş noktasıdır. Bu durum Şekil 3’de görülebilmektedir. Mandl’daki durum için θ = (1/60, 1/50, 1/40, 1/30, 1/20, 1/10, 1/5, 1/2) gibi bir sıklık olası değerler dizisi yapılandırmakta ve Çift Eklenti Algoritmasını kullanan gidiş-geliş yönlü simetrik 7 hatlık bir dizi üretmektedir. Filo boyutu için üst limit referans çalışmalarından alınmış olup 80’lik bir dizidir. Rivera için ise mevcut sistemindeki hatlar tarafından kullanılan sıklıktan faydalanılmış olup 27 olarak belirtilen filo boyutu için sonuç değerine göre θ = (1/60, 1/40, 1/30, 1/20)’dir.
Kısıtlarla ilgili olarak hatlara (y’nin sabitlenmiş değeri) sıklıkların verili bir dizini için gözlemler dâhilinde, sonuçlanan doğrusal (lineer) problem formüllerde belirtildiği üzere bağımsız bir atama problemini teşkil etmektedir. Kısıt yl(a()f(a) = 1 için ihtiyaç dışı olduğunda, sabitlenmiş bir sıklığı içermekte olup dahası v ve w değişkenlerinin dâhil olduğu diğer kısıtların yokluğunda, önerilen karma tam sayılı tekil düzeyli formülasyon 1995 yılında yapılan referans çalışmalarda önerilmiş olan doğrusal olmayan tek düzeyli formülasyona denktir (bir ayrışıklıkla sınırlı).
Bu tarz çalışmalar kapsamında önerilen dönüşümler, bir diğerinden farklı olarak problemin karmaşıklığının orijinal kaynağını değiştirmektedir. Orijinal formülasyon aynı düzeyli doğrusal olmayan (standart çözüm yöntemi bulunmayan) iken önerilen formülasyon ise karma tam sayılı doğrusaldır (kesin çözüm yöntemleri bulunan). Önerilen formülasyonun karmaşıklığının temel kaynağı, ikili değişkenlerin varlığı olup dahası sıklık aralıklarının ayrışıklığı, ihtimal dâhilindeki sıklıkların θ dizisindeki boyutuna eşit olan bir katsayıya biniş yayı (ve v değişkenlerinin sayısı yerine) serisini genişletmektedir.
Önerilen tam sayılı doğrusal programlama (MILP) formülasyonunun sıklık optimizasyon problemine optimal bir çözüm hesaplama imkanı vermesine karşın, büyük boyutlu numunelerin çözümünün zor olacağı öngörülmektedir. Sıklık aralıklarının ayrışıklığının uygulanması ile birlikte, problemin çözüm alanının üssel olacağı (lθllLl)terkibi bir duruma (en kötü durum) dönüşeceği de vurgulanmalıdır.
Bu karmaşıklığın üstesinden gelmek için tabu araştırmasına dayalı bir sezgisel ötesi yaklaşım önerilmiştir. Yöntem sıklık alanlarında kısmi bir araştırmaya dayalı iken (plancının kararı bu yönde olduğundan) kullanıcı kararlarını gösteren değişkenler atama alt modelinin devreye sokulması ile hesaplanmaktadır. Kısmi optimuma yönelmekten kaçınmak için kısmi arama mekanizmasının temeline tabu konsepti uygulanmaktadır. Araştırma stratejisi işletimciye dayalı olarak yapılandırılırken gerçek problemle bilgiyi birleştirmektedir. Ardından bir indirgeme yöntemi yapısal olarak bu işletimcilerin başarılı bir uygulamasınca tanımlanmaktadır. Atama alt modeline (hesaplamalı maliyetli olabilen) olan sıkı bağımlılığı engellemek için tabu araştırmasının özel bir mekanizması uygulanmaktadır. Nüfus bazlı bir sezgisel ötesi yaklaşımın (genetik algoritmalar gibi) her bir üretim prosesinin çok sayıda kişi üzerinden değerlendirmeye neden olmasından dolayı, benzer bir mekanizma gerektirmesi gerektiği de not edilmelidir. Bu bağlamda önerilen sezgisel ötesi yaklaşım dâhilindeki temel anlayışlar değerlendirilmektedir.
Kısmi prosedür verili herhangi bir çözümde yakınsaklığı belirlemek için devreye sokulan bir işletimi kullanan bir çalışmadır. Bu tarz çalışmalar kapsamındaki çözüm θ sıklığı dizisine endeks düzenleme yolu ile ortaya konmaktadır. Düzendeki her bir alan toplu ulaştırma sistemindeki bir hattı temsil etmekte ve sahip olduğu değer de söz konusu hattın sıklığını ifade etmektedir. İhtimal dâhilindeki sıklıklar dizisinin en düşük değerden (θ1) en yüksek değere (θm) sıralandığı kabulü yapılmaktadır. Bu yolla bir hat sıklığı artarken (ya da azalırken) θ’daki en yüksek (ya da en düşük) değerine ulaşmaktadır. Bu kapsamdaki bir çözümdeki bir hat sıklığının azalmasının gözlemlendiğinde, her zaman için cazibesini (kullanıcı açısından) ya da en üst limitini düşüreceği görülmektedir. Buna karşılık bir çözümdeki bir hat sıklığındaki bir artış ise onu daha cazip hale getirmekte ya da alt limitini yükseltmektedir. Yakınsaklık yapısını tanımlayan hareket işletimi, bir artış bir düşüş değişimi şeklinde, çözümün hat sıklığının bir çiftindeki yoğunlaşmış değişimdir. Bu temel işletim dâhilinde her bir çözüm, lLl X (lLl-1) komşu çözüme sahip iken her bir hattın sıklığı azalabilir ya da artabilir.
Tabu araştırması sezgisel ötesi bir yaklaşım olup kısmi optimallikten öte çözüm alanını tayin etmek için kısmi bir prosedüre kılavuzluk etmektedir. Bunu yapmak için de araştırma mevcut çözümü kötüleştiren rotaları kabule edebilir ve o zamana kadar icra edilmiş kimi rotaları da engelleyebilir. Tabu araştırmasının temel unsurlarından birisi de hafıza kullanımıdır. Bu tarz çalışmalar kapsamında kısa vadeli hafıza stratejilerine odaklanılmaktadır.
Bu tarz çalışmalar kapsamında kısa vadeli hafıza olarak adlandırılan en genel tür kullanılmaktadır. Tabu başlangıçlı olarak adlandırılan bir tabu listesi, en son iterasyonu kaydetmekte iken her bir hat kendi sıklığına göre değişmektedir. Her bir hatta Test-artışı ve Test-azalışı ikame edilerek sırası ile sıklıklarının artış ve azalışı temin edilmektedir. Eğer iterasyon < Tabu başlangıçlı (Test-azalışı) + sabit ya da iterasyon < Tabu başlangıçlı (Test-artışı) + sabit ise hareketin (Test-azalışı ya da Test-artışı) tabuda aktif olduğu söylenir. Bu çözümlemedeki iterasyondan kasıt, tabuyu aktive bir hareketin bulunduğu durumdaki iterasyonların sayısını gösteren sabiteye bağlı olarak mevcut iterasyon sayısını göstermektedir. Genel ifade ile araştırma mekanizması genellikle tabuyu aktif hale getiren hareketlerden kaçınmaktadır. Bununla beraber tabuyu aktif hale getirmeyen hareketlerin sayısı azdır, amaç kriterleri dâhilinde ilave mekanizmalar uyarlanmaktadır.
Amaç kriterleri, tabu aktivasyon kurallarının iptal edilebilirliği paralelinde, hesapta uygulanmaktadır. Bu tarz çalışmalar kapsamında, maliyeti dâhil edilen çözümlerin (yolcu atama alt modeline bir gereksinime neden olduğundan) amaç değerlerinin hesaplamalarının verilmesi ile birlikte, sadece hat sıklıklarının herhangi birisindeki tabuyu aktif hale getiren durumların dışındaki yakınsak çözümler değerlendirilmektedir. İhtimal dâhilindeki yakınsak çözümlerin sayısı Nmin (algoritmanın bir parametresi) minimum eşik değerinden öte olan tabuyu aktif hale getirmeyen hareketlerin (sıklıkları artırıp azaltabilen hatların sayısının ürünü şeklinde hesaplanarak) ortalamasınca özel olarak sağlanırken, uygulanan amaç kriteri, Nmin tarafından belirlenen yakınsak çözümlerin sayısı minimuma ulaşana kadar en düşük Tabu başlangıçlı (TestX) + sabit (X’in artış ya da azalışın yerine ikame edildiği) hat sıklıklarının tabuyu aktif hale getiren durumu gerçekleştirmektedir. Bu hükmen, amaç olarak kabul edilmektedir.
Yakınsak çözümlerin gerçekleştirilmesi için sistematik bir yol olarak, amaç üstü strateji uygulanmaktadır. Bu strateji hedeflenen değer bir amaç değeri olarak gerçekleştiren çözümü bulduktan sonra, ilave çözümlerin sayısını tayin etmektedir. Başvurulacak yakınsak çözümlerin sayısının bağıntısını korumak için, tayin edilecek minimum ve maksimum çözümlerin sayısını gösteren iki değer (sırası ile minimum ve maksimum parametreler) kullanmaktadır. Daha özel olarak eğer amaç değeri i. yakınsak çözümün tayinine kadar beklenen seviyeye ulaşır ya da geçer ise araştırma aşağıdaki tayinleri gerçekleştirmektedir:
1-Eğer minimum<i+e<maksimum -> i + ilave yakınsaklıklar,
2-Eğer i+e<minimum -> minimum yakınsaklıklar,
3-Eğer maksimum<i+e -> maksimum yakınsaklıklar
Aday yakınsak çözümler yukarıda açıklanan stratejiden elde edilen sonuçlarla rassallık kuralına göre değerlendirilmektedir.
Her bir yakınsak çözümün değerlendirilmesinde, ilgili denklemler ile formüle edilmiş olan atama modellerini çözen referans çalışmalarca önerilmiş olan etiket ayarlı algoritmalar uygulanmaktadır. Genel ifadeler ile algoritma, en kısa yol etiketlemeli algoritmasına oldukça benzer olup açısal maliyetlerinin dikkate alınıyor olmasının yanı sıra temel farklılık, akımın dağılımını gerçekleştiren ve ayrıca çözümde hiper yol yapısını üreten genel hatların sıklıklarının dikkate alınıyor olmasıdır.
Optimizasyon modelindeki kısıtlar ile ilgili olarak, filo boyutu üst limitini ihlal eden çözümlerin devre dışı bırakılmasının yerine, fizibıl olmayan çözümlere ve ekstra otobüs katılımlarının cezalandırılmasının çalışılmasına izin verilmektedir. Kullanıcıların toplam süresine göre otobüs etkilerinin hesaplanması (amaç değerinin çözümü veren otobüs sayısına bölünmesi ile hesaplanmaktadır) uygun filo boyutunu aşan otobüs miktarının cezalandırılması ile gerçekleştirilmektedir.
Bu kapsamda kesin model açıklamalarının uygulanmasından ve yaklaşık çözüm yönteminin uygulanmasından elde edilen sayısal sonuçlar raporlanmıştır. Bu kapsamda üç temel test durumu kullanılmaktadır:
1-1980 yılında yapılan çalışma küçük bir şehir olan Mandl’daki durumu ifade etmektedir. Grafiği 15 düğüm noktası ve 21 doğrudan olmayan uçtan oluşmaktadır. Bu durumla ilgili herhangi bir güzergâh ağı olmadığından dolayı, belirli bir çalışmadaki amaca göre ağ türetilmiştir. OD matrisi 172 O-D çiftinden oluşmakta olup bu, düğüm noktası sayısına göre oldukça büyük bir değeri ifade etmektedir.
2-Uruguay’ın Rivera şehrindeki durumdur. Grafiği 84 düğüm noktası ve 143 doğrudan olmayan uçtan oluşmakta iken OD matrisi 378 O-D çiftinden oluşmakta olup 12 saatlik bir zaman aralığındaki talebi ifade etmektedir. Şehrin toplu ulaştırma sistemini temsilen bir hat dizi hesaba katılmış olup inşa edildiği 2003 yılı itibari ile işletime alınmış, gidiş-geliş istikametli 11 hat ve 2 dairesel hattan oluşmaktadır.
3-Uruguay’ın başkenti Montevideo’ya karşılık gelen durumdur. Belirtilen grafiği 4945 düğüm noktası ve 14.672 uçtan oluşmakta olup 133 otobüs güzergâhına sahip bir toplu ulaştırma sistemini ifade etmektedir. Kalkış-varış verisi (hem O-D yerleşimi ve hem de seyahat miktarı) rassal olarak üretilmekte, gerçekçi özellikler oluşturulmaya çalışılmakta olup söz konusu durum, şehre eşit olarak dağıtılmış 7425 O-D çiftini içermektedir.
İlk iki durumda grafiğin elemanları yüksek dereceli ayrışıklıkta verilmiş, ayrıca her bir düğüm noktasının bir otobüs durağı gibi rota kesimlerinin potansiyel bir bitiş noktasıdır. Bu durum Şekil 3’de görülebilmektedir. Mandl’daki durum için θ = (1/60, 1/50, 1/40, 1/30, 1/20, 1/10, 1/5, 1/2) gibi bir sıklık olası değerler dizisi yapılandırmakta ve Çift Eklenti Algoritmasını kullanan gidiş-geliş yönlü simetrik 7 hatlık bir dizi üretmektedir. Filo boyutu için üst limit referans çalışmalarından alınmış olup 80’lik bir dizidir. Rivera için ise mevcut sistemindeki hatlar tarafından kullanılan sıklıktan faydalanılmış olup 27 olarak belirtilen filo boyutu için sonuç değerine göre θ = (1/60, 1/40, 1/30, 1/20)’dir.
15
açık
