Density Based and Balanced Data Partition Strategy for Improving School Bus Routing

Abstract

Araç Rotalama Probleminin bir türü olarak kabul edilen Okul Otobüsü Rotalama Problemi, taşımacılık modellerinin farklılığı, verinin büyüklüğü, zaman, mesafe ve araç kapasitesi kısıtlaması gibi nedenlerden dolayı farklı çözüm metotları geliştirilerek çözülmeye çalışılan karmaşık problemlerden birisidir. Türkiye'de bu sektörün büyüklüğü ve insanların günlük yaşamına olan etkisi nedeni ile bu alanda çalışma yapılmasına karar verilmiştir. Problem çözümünde Bingöl ilinde hizmet veren bir taşımacılık firmasının verilerinden istifade edilmiş ve firmanın gerçek hayatta karşılaştığı problemler tespit edilerek çözüm geliştirilmeye çalışılmıştır. Problem üç aşamada çözülmeye çalışılmıştır. Problemin çözümünde ilk aşamada araçların yönlendirileceği bölgeleri belirlemek için yoğunluk bazlı kümeleme algoritmalarından birisi olan DBSCAN algoritmasına yeni özellikler katılarak küme parçalama ve/veya birleştirme işlemleri gerçekleştirilerek araç kapasitelerine ve coğrafik yakınlıklara uygun şekilde öğrenciler kümelendirilmiştir. İkinci aşamada ülkemizde pratikte kullanılan modelde her bir otobüsün harekete başladığı nokta farklı olduğundan, hangi aracın hangi kümeye yönlendirileceğine karar vermek için araç-küme atama işlemi yapılmış, bunun için Macar Atama Algoritması kullanılmıştır. Son aşamada ise her bir araç için en kısa mesafe ve zamanda öğrencilerin hangi sırayla taşınacağını belirlemek üzere Genetik Algoritma ile Otobüs Rotalama işlemi gerçekleştirilmiştir. Kıyaslama veri setlerinde, daha kısa sürede çözüme kavuşturulan problemin iyi bir performans göstergesi olduğu için geliştirilen yaklaşımın çözüm kalitesinin güçlü ve etkili olduğu sayısal sonuçlar ile kanıtlanmıştır.