Şehir içi toplu taşım araçlarının günlük seferlerinin duraklardaki bekleyen yolcu sayılarının yoğunluğuna göre Genetik Algoritma ile planlanması

Büyükşehirlerde nüfus yoğunluğunun artması ile birlikte toplu taşımanın önemi de hızla artmaktadır. Toplu taşımanın önemiyle doğru orantılı olarak da belediyeler ilgili taşıma maliyetleri konusunda araştırma ve maliyetleri düşürme konusunda yoğun çalışmalar yapmaktadırlar. Bu maliyetlerde toplu taşıma süreleri, araçların sefer sayıları, yol uzunlukları, yolcuların şikayetleri gibi birçok kısıt göz önüne alınarak planlama yapmak zorunda kalmışlardır. Bu planlamalar bir ekip tarafından yapılması ve gerçeklemesi oldukça zor bir hale gelmiştir. 

Planlamaların yapılması konusunda geçmişte birçok araştırma yapılmıştır. Bu araştırmaların başında yol planlanması ve en kısa yol hesaplamaları gibi araştırmalar yapılmıştır. Bu hesaplamalara bağlı olarak sezgisel algoritmalar başarılı sonuçlar vermiştir. Bu tür araştırmalarda genetik algoritma her bir düğüme (durak) a göre çalıştırılır. Bu çalışmada toplu taşımada kullanılan otobüslerin sefer süreleri, ve frekansları genetik algoritma ile optimize edilmeye çalışılmıştır. Geliştirilen algoritmada otobüslerin sefer sayıları, yolcu memnuniyeti ve bekleme süreleri de göz önüne alınarak optimize işlemi yapılmıştır.

Giriş

Gelişmiş ve gelişmekte olan ülkelerde, büyükşehirlerdeki ve halk otobüsleri en yaygın toplu taşıma taşıyıcılarıdır. Toplu taşıma araçlarına yönelik kullanıcı memnuniyetini etkileyen faktörler arasında yer alan artan seyahat süresi, kötü konfor, ekonomik olmayan işlemler ve duraklardaki bekleme süreleridir. Bu sorunlar, uygun koordinasyon ile çözülebilir önemli toplu taşıma problemleri arasında yer alır. Başarılı bir koordinasyon ifade edecek olursak; 

• Seyahat kapasitesini genişletmek ve rahat aktarım yapmak, 

• Her bir durak arası farklı hizmet alanları oluşturarak servisleri minimize etmek, 

• İyi planlama ve ortak bir tarife yapısı . 

Kötü koordine edilmiş transferler için uzun, düzensiz bekleme süresi hizmetlerin bağlanmasını gerektirebilir. Seyahat ve talep arasındaki ilişki toplu taşımanın detaylarında bulunmaktadır. Bu detaylar arasında ekonomi, yolcu memnuniyeti, transfer süreleri bulunmaktadır. Bu gibi kısıtlar göz önüne alınarak taşıma süresi ve toplu taşıma araçlarının sayıları optimize edilmiştir.

Literatür Araştırmaları

Birçok araştırma çalışmaları otobüs güzergahı ağ tasarımı sorunları yapılmıştır yolları ve programları kapsayan gelişme. Lampkin ve Saalmans (1967), Sil adam ve ark. (1974), Dubois ve ark. (1979), Mandl (1980) ve Baaj ve Mahmassani, (1995) sezgisel bir yaklaşım kullanarak otobüs güzergahları geliştirdi . Shrivastava ve Dhingra(2001) başarıyla besleyici tasarımı için sezgisel bir yaklaşım uygulamaya b anliyö tren istasyonları besleyici halk otobüsleri için yönlendirir. Sezgisel algoritmalar teorik sıkı değil, gerçek ağlar için başarıyla kullanılmaktadır ve optimal değerleri sağlama yeteneğine sahiptir. Genetik algoritmalar (GA) güçlü optimizasyon teknikleri, başarılı bir yönlendirme için kullanılan ve olmuştur çizelgeleme problemleri. Pattnaik et al. (1998), Gundaliya ve ark. (2000), Tom ve Mohan (2003), otobüs güzergahı ağlarının tasarımı için gaz kullandı. Shrivastava ve Halk otobüsleri Dhingra (2002) başarıyla oluşturulan koordineli programları banliyö trenleri, mevcut programları kullanarak geliştirilen besleyici rota ağı GA. Chien et al. (2003) ve hizmet headway optimize etmek için bir model sundu bir banliyö (çok-bir) seyahat desen bir alanda hizmet veren bir otobüs güzergahı. otobüs güzergahı, sistemin toplam maliyetini en aza indirmeyi, operatör de dahil olmak üzere ve optimize kullanıcı maliyetleri, çalışma ağı çapraz bağlantılar da dikkate alınıyor. Zhao ve Ubaka(2004) transit yolu ağı için matematiksel bir yöntem sundu Optimize edilmiş revaskülarizasyon. 

Genetik Algoritma

1. [Başlat] n kromozom rastgele nüfus oluşturma (problem için uygun çözümler)
2. [Fitness] nüfusun her kromozom x fitness f (x) değerlendirilmesi
3. [Yeni nüfus] yeni nüfus tamamlanana kadar aşağıdaki adımları tekrarlayarak yeni bir nüfus oluşturulur
   • [Seçim], fitness fonksiyonuna göre bir nüfus iki ebeveynin kromozomları seçin
   • [Crossover] yeni bir çocuk oluşturmak için ebeveynlerin üzerine bir crossover olasılık çaprazla. Çapraz yapıldı, yavrular ebeveynler tam bir kopyasıdır.
   • [Mutasyon] Popülasyonda her bir mutasyon olasılığına göre yeni yavrular.
   • [Doğru] Yeni bir nüfus yerleştirin yeni yavrular 
4. [Değiştirin] algoritma daha fazla çalıştırmak için yeni oluşturulan nüfus kullanın
5. [Test] bitiş koşulu sağlandığı takdirde, durdurma ve şimdiki nüfus içinde en iyi çözüm geri döndür.
6. [Döngü] 2. adıma git

Kromozom Oluşturma

Kromozom bir şekilde temsil çözüm hakkında bilgi içermelidir. En çok kullanılan kodlama yolu ikili bir dizedir. Kromozom, aşağıdaki gibi görünmektedir. 

Kromozomlar oluşturulurken Hat Id ve o hatta ait olan saatlik otobüs sayıları (frekans) ikilik tabana dönüştürülerek birleştirilir. Crossover ve mutation işlemi ise bu kromozom üzerinde yapılır.

Crossover

Kullanacağımız kromozoma karar verdikten sonra crossover uygulamak için frekans bölmesi (6bit) alınır. Problemin uygulanması gereğince çaprazlama iki kromozom arasında en son 3 bitin yer değiştirmesi ile yapılır. Bu işlemden sonra yeni bir kromozom oluşmuş olur ve bunu biz kullanmak üzere kayıt altında tutarız. Crossover işlemi aşağıdaki şekilde gösterilmiştir.

Crossover sonrası sonuçları incelersek;

Hat Id si 5 olan yolun frekansı crossover öncesi 5, crossover işlemi sonrasında frekans 3 oluyor

Hat Id si 14 olan yolun frenkansı crossover öncesi 11, crossover işlemi sonrasında frekans 13 oluyor.

Mutasyon

Mutasyon işlemi seçilmiş olan bir kromozomun en son bitinin değiştirilerek yeni bir gen oluşması ile elde edilir. Son bitin değiştirilmesinin sebebi her bir hatta ait otobüs sayılarında büyük değişiklikler yapmamaktır. Örnek bir mutasyon işlemi aşağıdaki örnekte bildirilmiştir.

Yukarıdaki şekilde de görüldüğü gibi 14 Numaralı Hat frekansı mutasyon öncesi 12 iken mutasyon işlemi sonucunda 13 e yükselmiştir.

Algoritmanın Probleme Uygulanması

Adım 1

Veriler yüklenerek popülasyon oluşturulur.

Adım 2

Alınan veriler öncelikle amaç fonksiyonuna göre maliyetleri hesaplanır. Bu maliyetler her bir yola ait olacak şekilde aşağıdaki formül ile hesaplanır.

Adım 3

Amaç fonksiyonuna göre hesaplanan değerler kaydedilerek diğer işlemlere devam edilir. Bu aşamada yeni maliyeD oluşan listeden rastgele bir miktarda Hat seçilerek geneDk aşamaları uygulanır. Bu aşamalar;

• Elitizim;
  • Bu işlemde rastgele olarak alınan listelerden fitness functionlar uygulanır ve her bireyin ceza puanları bu değerlere göre azaltılır. Projede başlangıçta bütün hatlara ait puanlar 100 olarak belirlenmiştir. Ceza puanına göre sıralanan bireylerden en iyileri seçilerek elit olarak belirlenir.

• Crossover
  • BuişlemdesistemtaraCndanelitüyelerdışındakalan4kromozomseçilerekaralarındaçaprazlamaişlemleriyapılır.
• Mutasyon
  • Bu işlemde ise seçilen 2 gen’in son bitleri değiştirilir. Son bit 0 ise 1 , 1 ise 0 olacak şekilde düzenlenir.

Amaç Fonksiyonunda ve Fitness FuncDonda kullanılan terimlerin açıklamaları;

Adım 4

Bu aşamada toplam maliyet tekrar hesaplanır. İsteğe bağlı şekilde düşüş yaşanıp yaşanmadığı kontrol edilerek döngü devamı sağlanacağı gibi belirli bir iterasyon sayısı kadar da tekrarlanabilir. Sonuç olarak algoritma sonlandırılır.

Program Arayüzleri

Algoritma çalışmadan önce;

Burada sadece itarasyon sayısını değişken olarak alınmıştır. Geriye kalan bilgilerin tamamı İlgili makaleden alınmıştır[1].

Ekranda görünmekte olan sol üst tarataki listeye algoritmada her bir adımda yapılan değişiklikler eklenmiştir. Sağ alt tarata gözüken listede ise algoritma sonucunda değişen frekanslar gösterilmiştir. Aşağıdaki şekilde program çalıştırıldıktan sonraki ekran görüntüsü gösterilmiştir.

Sonuç

Toplu taşıma araçlarının duraklarda bekleyen yolcu sayılarına göre gelme sıklığı konusunda genetik algoritma ile çalışılmıştır. Algoritma sonucunda gerçek veriler ile yapılan bir diğer uygulama olmadığından karşılaştırma işlemi yapılamamıştır. 

Algoritma çalıştırıldığında geçmiş veriler göz önüne alındığında optimize edilmiş hali ile karşılaştırmalar yapılmıştır.

Kaynaklar

[1] Shrivastava P. and O’Mahony M. (2007), Design of Feeder Route Network Using Combined Genetic Algorithm and Specialized Repair Heuristic,  Journal of Public Transport, 10, 2, 99-123 

[2] Pattnaik, S. B., Mohan, S., and Tom, V. M. ~1998!. ‘‘Urban bus transit route network design using genetic algorithm.’’ J. Transp. Eng.,124(4), 368-375

[3] Tom, V. M., Mohan, S., 2003. Transit route network design using frequency coded genetic algorithm. Journal of Transportation Engineering 129 (2), 186-195.

[4] Kidwai, F.A., Marwah B.R., Deb, K. & Karim M. R. (2005). A Genetic Algorithm Based Bus Scheduling Model for Transit Network, Proceedings of the Eastern Asia Society for Transportation Studies, Vol. 5,477 – 489

Emre Çevik

Ocak 2012