SBRP Algoritması: Okul Servisi Rota Planlama Problemi
Günde iki kez, milyonlarca öğrenci Türkiye genelinde okul servisine biner. Bu görünürde basit operasyon, matematiksel açıdan son derece karmaşık bir problemi barındırır: School Bus Routing Problem (SBRP) — Okul Servisi Rota Planlama Problemi. vitaRoute bu problemi pekiştirmeli öğrenme ile çözüyor.
SBRP Nedir?
SBRP (School Bus Routing Problem — Okul Servisi Rota Planlama Problemi), okul servisi araçlarının rotalarını optimize etmek için çözülmesi gereken kombinatorik optimizasyon problemidir. Problem şu soruyu yanıtlar: Belirlenen kısıtlar altında (araç kapasitesi, maksimum yürüme mesafesi, ilçe sınırları, okul saatleri) öğrencileri okula en verimli şekilde nasıl taşırsınız?
SBRP, birbirine bağlı üç alt problemden oluşur: (1) Durak belirleme — hangi noktalarda durak oluşturulacak? (2) Öğrenci atama — hangi öğrenci hangi durağa yürüyecek? (3) Rota oluşturma — araçlar durakları hangi sırayla ziyaret edecek?
Neden NP-Zor Bir Problem?
SBRP, NP-zor (NP-hard) problem sınıfına girer. Bu, problem boyutu arttıkça (daha fazla öğrenci, daha fazla araç) mümkün çözüm sayısının üstel olarak büyüdüğü anlamına gelir. 'Kesin' algoritmaların pratik sürelerde hesaplamayı tamamlaması mümkün olmaz.
100 öğrencili, 5 araçlı basit bir SBRP örneğinde olası çözüm uzayı 10⁴⁰'ı aşar. Saniyede 1 milyar çözüm değerlendirebilen en hızlı bilgisayar bile evrenin yaşından daha uzun süre gerekirdi.
- Durak sayısı arttıkça çözüm uzayı üstel büyür
- Araç kapasitesi, zaman ve mesafe kısıtları boyutu katlar
- Gerçek dünya değişkenleri (trafik, yol kapatmaları) statik modele uymaz
- Günlük değişen öğrenci sayıları dinamik yeniden optimizasyon gerektirir
Klasik SBRP Çözüm Yöntemleri
SBRP'yi çözmek için yıllar içinde çeşitli yaklaşımlar geliştirilmiştir. Her birinin avantajları ve sınırlamaları vardır:
- Açgözlü (Greedy) algoritmalar — Hızlı ama optimal olmayan çözümler üretir
- Genetik algoritmalar — İyi kalite ama yavaş hesaplama
- Simüle tavlama (Simulated Annealing) — Yerel minimumlardan kaçabilir ama parametre ayarı zordur
- Tabu arama (Tabu Search) — Güçlü ama domain bilgisi gerektirir
- Tamsayılı programlama (ILP) — Optimal ama yalnızca küçük örnekler için uygulanabilir
RL-SBRP: Pekiştirmeli Öğrenme ile SBRP
vitaRoute'un geliştirdiği RL-SBRP çerçevesi, pekiştirmeli öğrenme (Reinforcement Learning) tekniğini klasik SBRP formülasyonuyla bütünleştirmektedir. TÜBİTAK destekli Ar-Ge sürecimizde geliştirilen bu yaklaşım, hem çözüm kalitesi hem de hesaplama hızı bakımından klasik yöntemlere kıyasla anlamlı bir iyileştirme sağlamaktadır.
RL ajanı binlerce sanal Türkiye senaryosunda eğitilmiştir; İstanbul, Ankara ve Türkiye genelindeki gerçek yol ağı ve ilçe kısıtlarını dikkate alır.
- Klasik yöntemlere göre %40-60 daha hızlı hesaplama
- 1.000 öğrenci için maksimum 10 saniye
- Türkiye'ye özgü yol ağı ve ilçe kısıtları desteği
- Günlük değişen öğrenci listesine uyum (dinamik yeniden optimizasyon)
Türkiye'de Okul Servisi: Özel Kısıtlar
Türkiye'deki okul servisi operasyonları, SBRP'nin standart formülasyonunun ötesinde kısıtlar içerir. vitaRoute bunların tümünü model içinde ele alır:
- MEB yönetmeliğine göre maksimum yürüme mesafesi (ilköğretim için 500 m)
- İlçe sınırı kısıtlamaları (öğrenci bulunduğu ilçenin dışına rota çıkamaz)
- Okul oturma saatine göre son durak zamanı kısıtı
- Birden fazla okul için split rota desteği
- Sabah-akşam iki yönlü rota oluşturma
SBRP, görünürde operasyonel bir problem olsa da özünde çözümü onlarca yıldır araştırma gündeminde olan derin bir matematiksel zorluktur. vitaRoute'un RL-SBRP yaklaşımı, bu zorluğu pratik ve ölçeklenebilir bir çözüme dönüştürmektedir.
RL-SBRP Motorunu Deneyin
Ücretsiz planla başlayın ve kendi okul servisi güzergahlarınızı saniyeler içinde optimize edin.