A state space reduction heuristic for multiple depot vehicle scheduling problem

Abstract

Çok Garajlı Araç Çizelgeleme Problemi (ÇGAÇP), sefer tarifelerinde yer alan tarifelerin birden fazla garajda parklayan sınırlı sayıdaki araca atanması problemidir. Seferler arasındaki uyumluluk ilişkilerini göz önüne alarak minimum sayıda araç ve toplam ölü kilometre ile karşılanabilecek araç çizelgelerinin hazırlanmasını amaçlayan problem, toplu ulaşım işletmelerinin hazırlamak durumunda oldukları şehir içi otobüs taşımacılığı planlarından biridir.Bu tez çalışmasında, güncel literatür takip edilerek ÇGAÇP çözümünde kullanılmak üzere iki adet sezgisel metot geliştirilmiştir. Yinelemeli Çizelgeleme (Iterative Rescheduling) literatürde var olan Çizelgele - Kümele - Tekrar Çizelgele (Schedule - Cluster - Reschedule) sezgiselinin gelişmiş versiyonu iken, Sefer Birleştirici (Trips Merger) sezgiselinin çalışma prensibi Yinelemeli Çizelgeme sezgiselinin sonuçlarını kullanarak çözüm uzayını küçültmeye dayanmaktadır. İstanbul Elektrik, Tramvay ve Tünel (İETT) İşletmeleri Genel Müdürlüğü'nün sorumluluğunda olan Metrobüs Sistemi'ne ait araç çizelgeleme problemi ÇGAÇP olarak modellenmiş ve Yinelemeli Çizelgeleme ve Sefer Birleştirici sezgiselleri yardımıyla çözülmüştür. Araç çizelgelerinin hazırlanmasında manuel metotlar yerine matematiksel optimizasyon tekniklerinin kullanılmasının ve halihazırdaki çizelgeleme sistemi için geçerli olan hat değişikliğine izin vermeme kuralının göz ardı edilmesinin sayesinde daha düşük maliyetli araç çizelgelerinin elde edildiği gösterilmiştir.

Multiple Depot Vehicle Scheduling Problem (MDVSP) is the problem of assigning timetabled trips of different lines to a limited number of available vehicles emanating from multiple depots. It is a component of bus transit planning process of public transportation companies and aims to prepare vehicle schedules covered by minimum number of vehicles with minimum total deadhead kilometers while satisfying trip compatibility relations. In this thesis, two heuristic solution methodologies are devised to solve MDVSP by following the current literature. Iterative Rescheduling (IR) improves the existing heuristic method Schedule - Cluster - Reschedule (SCR) where Trips Merger (TM) is based on reducing the state space by using the outputs of IR solution.Vehicle scheduling problem of Metrobus System of Istanbul Electricity, Tramway, and Tunnel (IETT) General Directorate is modelled as MDVSP and solved by IR and TM heuristics. It is shown that preparing vehicle schedules of the system via mathematical optimization instead of manual methods and relaxing the rule of disallowance of line change which is applied in current scheduling methodology leads to less costly vehicle schedules.