Londra Metrosu Rota Planlamasında Maliyet Duyarlı Arama

Proje Bağlamı

Rota planlama, sistemin neyi optimize etmek üzere tasarlandığına bağlı olarak farklı algoritmaların önemli ölçüde farklı davranışlar gösterebildiği bir arama problemidir.

Londra Metrosunun graf gösterimini kullanarak istasyonlar arasında rota bulmak için klasik arama algoritmalarını uyguladım ve karşılaştırdım. Ağ; istasyon bağlantıları, seyahat süresi maliyetleri, metro hatları ve ücret bölgesi bilgilerini içeriyordu.

Yalnızca bir algoritmanın hedefe ulaşıp ulaşamadığını değerlendirmek yerine yöntemleri iki farklı hedef açısından karşılaştırdım:

• ağın ne kadarının keşfedilmesi gerektiği
• elde edilen rotanın seyahat maliyeti

Proje böylece temel bir arama problemini ele aldı: hesaplama verimliliği ile rota maliyeti aynı strateji tarafından her zaman birlikte optimize edilemiyorsa hangi algoritma tercih edilmelidir?

Araştırma Hedefleri

1. Gerçek bir ulaşım ağı üzerinde BFS, DFS, Uniform Cost Search ve sezgisel yönlendirmeli aramayı uygulamak.
2. Algoritmaları hem ziyaret edilen düğüm sayısı hem de toplam rota maliyeti açısından karşılaştırmak.
3. Alternatif bir rota optimizasyon hedefini temsil etmek için UCS'yi açık bir hat değiştirme cezası ile genişletmek.
4. Gereksiz graf keşfini azaltmak için Londra ücret bölgesi bilgisini kullanan bir sezgisel yöntem geliştirmek.
5. Arama verimliliği, rota maliyeti ve algoritmanın içerdiği optimizasyon hedefi arasındaki ödünleşimi analiz etmek.

Veri Kümesi

Londra Metrosu verileri bağlantıları şu bilgilerle tanımlıyordu:

• Başlangıç istasyonu
• Varış istasyonu
• Metro hattı
• Ortalama seyahat süresi
• Birincil ve ikincil ücret bölgeleri

Bu kayıtları, her istasyonu komşu istasyonlarına, seyahat maliyetlerine ve metro hatlarına bağlayan graf yapılarına dönüştürdüm.

Sezgisel arama yönteminde kullanılmak üzere ayrıca bir bölge gösterimi oluşturdum.

NetworkX gibi harici bir graf kütüphanesi kullanılmadı; arama prosedürleri özel olarak oluşturulmuş Python graf yapıları üzerinde çalıştı.

Yöntem

Genişlik Öncelikli Arama

BFS, grafı seviye seviye keşfetti.

Algoritma, seyahat süresini doğrudan minimize etmek yerine daha az istasyon geçişine sahip yolları önceliklendirdi. Ziyaret edilen düğümlerin tutulduğu bir küme, tekrarlanan keşifleri ve döngüleri önledi.

Derinlik Öncelikli Arama

DFS, geri izleme yapmadan önce ağın bir dalını özyinelemeli olarak keşfetti.

Döngüsel metro ağında istasyonların tekrar tekrar ziyaret edilmesini ve sonsuz döngüleri önlemek için ziyaret edilen düğümlerin takip edilmesi gerekiyordu.

Uniform Cost Search

UCS, yolları kümülatif seyahat sürelerine göre önceliklendirdi.

Her aşamada mevcut en düşük maliyetli rota önce genişletildi; böylece arama derinliği yerine seyahat maliyeti temel optimizasyon kriteri hâline geldi.

Hat Değişikliklerini Dikkate Alan Maliyet Duyarlı UCS

UCS'yi, bir rota metro hattı değiştirdiğinde ek 10 dakikalık ceza uygulayacak şekilde genişlettim.

Değiştirilmiş hedef fonksiyonu böylece iki unsuru birlikte temsil etti:

• seyahat süresi
• hat değişikliklerine atanan ek maliyet

Bu yaklaşım, hedef fonksiyonuna yalnızca seyahat süresinin ötesindeki tercihler eklendiğinde optimal rota tanımının nasıl değişebileceğine ilişkin basit bir örnek sundu.

Bölge Bilgisiyle Yönlendirilen Sezgisel Arama

Varış noktasının bölge bilgisine daha yakın görünen istasyonları önceliklendirmek için ücret bölgesi bilgisini kullanan sezgisel bir arama yöntemi geliştirdim.

Mevcut istasyon ile varış istasyonu aynı bölgeyi paylaşıyorsa sezgisel fonksiyon sıfır döndürdü. Aksi durumda, keşfi yönlendirmek için istasyonların bölge kümeleri karşılaştırıldı.

UCS'nin aksine bu sezgisel yöntem kümülatif seyahat süresini doğrudan optimize etmiyordu. Amacı, mevcut bölge bilgisine göre daha umut verici görünen ağ bölümlerine aramayı yönlendirerek gereksiz keşfi azaltmaktı.

Sonuçlar

Algoritmalar dört Londra Metrosu rotası üzerinde karşılaştırıldı:

Bölge bilgisiyle yönlendirilen sezgisel yöntem, dört rotanın tamamında BFS'ye kıyasla grafın önemli ölçüde daha küçük bir bölümünü keşfetmeyi gerektirdi.

BFS ile karşılaştırıldığında ziyaret edilen düğüm sayısı yaklaşık olarak şu oranlarda azaldı:

• %71 — Canada Water → Stratford
• %77 — New Cross Gate → Stepney Green
• %70 — Ealing Broadway → South Kensington
• %85 — Baker Street → Wembley Park

En büyük fark Baker Street ile Wembley Park arasında görüldü: DFS 101 düğümü ziyaret ederken sezgisel arama yalnızca 4 düğümü ziyaret etti.

Rota Maliyeti

Buna karşılık gelen seyahat maliyetleri şöyleydi:

UCS, dört test rotasının tamamında gözlemlenen minimum seyahat maliyetini elde etti.

Sezgisel yöntem üç rotada aynı düşük maliyeti, önemli ölçüde daha az düğüm keşfederek elde etti; ancak Canada Water → Stratford rotasında biraz daha yüksek maliyet üretti.

DFS bu karşılaştırmada tutarlı biçimde en zayıf rotaları üretti. Örneğin Baker Street ile Wembley Park arasında BFS, UCS ve sezgisel aramanın maliyeti 13 iken DFS'nin maliyeti 68 oldu.

Sonuçlar böylece açık bir ödünleşimi ortaya koydu: en az sayıda durumu keşfeden yöntemin minimum maliyetli rotayı döndürmesi garanti değildi.

Uygulama Zorlukları

Çeşitli uygulama sorunları, ders kitaplarındaki arama algoritmaları ile gerçek bir ulaşım ağı üzerinde graf araması arasındaki pratik farkları ortaya koydu.

• Döngüler ve tekrarlanan durumlar: Ziyaret edilen düğümler açıkça takip edilmediğinde DFS aynı istasyonları tekrar tekrar ziyaret edebiliyordu.
• Kümülatif maliyet takibi: UCS'de yalnızca tek tek kenarları dikkate almak yerine maliyetlerin tüm yollar boyunca doğru şekilde aktarılması gerekiyordu.
• Bölge gösterimi: Ücret bölgesi bilgileri birden fazla gösterim biçimi içerdiğinden sezgisel karşılaştırmalar öncesinde standartlaştırılmaları gerekiyordu.
• Sezgisel yöntemin kalitesi: Bölge yakınlığı her zaman minimum seyahat süresine tam olarak karşılık gelmediğinden verimli keşif en düşük maliyetli rotayı garanti etmiyordu.
• Birden fazla hedef: Hat değiştirme cezalarının eklenmesi rota maliyetinin anlamını ve dolayısıyla hangi çözümün optimal sayıldığını değiştirdi.

Katkılar

• Python ile BFS, DFS, UCS, maliyet duyarlı UCS ve sezgisel yönlendirmeli graf aramasını uyguladım.
• Londra Metrosu bağlantı, seyahat süresi, hat ve bölge verilerinden graf gösterimleri oluşturdum.
• Alternatif bir rota optimizasyon hedefini temsil etmek için açık bir 10 dakikalık hat değiştirme cezası ekledim.
• Aramayı varış noktasına yönlendirmek için bölge tabanlı bir sezgisel yöntem geliştirdim.
• Algoritmaları dört rota üzerinde hem ziyaret edilen düğüm sayısı hem de seyahat maliyetleri açısından değerlendirdim.
• Sezgisel yönlendirme kullanarak graf keşfini BFS'ye kıyasla yaklaşık %70–85 azalttım.
• UCS'nin gözlemlenen minimum seyahat maliyetini tutarlı biçimde elde ettiğini, sezgisel aramanın ise çoğu durumda önemli ölçüde daha az keşifle benzer maliyetli rotalar üretebildiğini gösterdim.
• Döngüler, sezgisel yöntemin kalitesi, kümülatif maliyet aktarımı ve veri gösterimiyle ilgili uygulama ve modelleme sorunlarını analiz ettim.

Projenin Önemi

Proje, "en iyi" rota bulma algoritmasının tek bir tanımı olmadığını gösterdi.

Hedef gözlemlenen minimum seyahat maliyeti olduğunda UCS en güçlü yöntemdi; sezgisel yönlendirme ise arama maliyetini önemli ölçüde azalttı. Test edilen dört rotanın üçünde sezgisel yöntem çok daha az düğüm keşfederken aynı minimum gözlemlenen maliyeti elde etti; kalan rotada ise bu verimlilik biraz daha yüksek rota maliyetiyle birlikte geldi.

UCS'yi hat değiştirme cezasıyla genişletmek, hedef fonksiyonunun yalnızca seyahat süresinin ötesindeki unsurları temsil edecek şekilde nasıl değiştirilebileceğini de gösterdi.

Daha genel sonuç, algoritma seçiminin problemin neyi optimize etmek üzere tasarlandığına bağlı olduğuydu. Hesaplama maliyeti, seyahat maliyeti ve aktarma cezaları farklı hedefleri temsil eder; bunlardan birini iyileştirmek diğerlerini de zorunlu olarak optimize etmez.