Vehicle and crew scheduling problem in public bus transportation

Abstract

Bu tezde, toplu taşıma operasyonlarının araç ve sürücü çizelgeleme aşamaları, bir toplu taşıma idaresinin gerçek hayat probleminden esinlenilerek çalışılmıştır. Problemde amaç önceden belirlenmiş seferleri ve araç atamalarından kaynaklanacak ölü kilometre seferlerini, sürücülerin toplam çalışma ve vardiya sürelerini dikkate alarak taşımacılığı minimum maliyetle karşılamak için gereken farklı tipteki araç ve sürücülerin sayısını optimal şekilde belirlemektir. Her iki alt problem için tamsayılı programlama modelleri geliştirilmiştir. Sürücü çizelgelemede, toplam çalışma süresini aşan görev sıralamalarını elemek üzere tekrarlamalı geçerli eşitsizlik yaratma yöntemi geliştirilmiştir. Her alt problem için geliştirilen çözüm yöntemlerinin performansları detaylı deneylerle araştırılmıştır ve sonuçlar önerilen optimal arama çözüm yöntemlerinin çözüm süreleri açısından oldukça etkili olduğunu göstermiştir. Bunun yanında, bütüncül problem için sıralı ve entegre olmak üzere iki yaklaşım önerilmiştir. Entegre yaklaşımda tamsayılı bir programlama modeli geliştirilmiş ve küçük boyutlu örnek problemler optimal olarak çözülmüştür. Ancak üstel artan çözüm süreleri nedeniyle büyük boyutlu problemler makul süreler içerisinde çözülememiştir. Bu nedenle araç ve sürücü çizelgeleme problemleri için geliştirilmiş olan tamsayılı programlama modellerinin sırayla çözüldüğü bir sıralı yaklaşım önerilmiştir. Bu yaklaşımın performansı kapsamlı sayısal deneyle araştırılmıştır ve sonuçlar sıralı yaklaşımın en fazla 120 sefere sahip örnekler için oldukça etkin ve verimli olduğunu göstermiştir. Ayrıca sıralı yaklaşım küçük boyutlu örnekler üzerinden entegre yaklaşım ile kıyaslanmıştır ve sonuçlar sıralı yaklaşımın çok makul sürede optimale yakın sonuçlar bulmada oldukça etkin olduğunu göstermiştir.

In this thesis, the vehicle and crew scheduling phases of the transportation planning process are studied, motivated by the real problem of a public bus transportation authority. The objective is to determine the optimal number of different types of vehicles and crew members (drivers) to cover a given set of trips and deadheads, regarding working and spread time limitations of drivers at minimum cost. Binary programming models are formulated for each subproblem. In crew scheduling, an iterative valid inequality generation scheme is developed for eliminating task sequences violating the working time constraints. Performances of the developed solution methodologies for the subproblems are investigated through detailed experimentations, and the results show that the proposed optimal-seeking solution procedures are quite effective in terms of solution times. Furthermore, sequential and integrated approaches are proposed for the whole problem. As an integrated approach, a binary programming model is formulated and optimally solved for small-sized problem instances. However, larger instances cannot be solved within reasonable time limits due to exponentially increasing solution times. Therefore, a sequential approach is proposed. The performance of the developed approach is investigated through detailed experimentation and the results show that our approach is quite efficient for instances with up to 120 trips. Additionally, the sequential approach is compared with the integrated one for small-sized instances and found to be quite effective in finding near optimal solutions within very reasonable computation times.