Solving City Bus Scheduling Problems in Bangkok by Eligen-Algorithm

The modeling of city bus scheduling problems is considered to optimize the number of buses and their scheduling in the city. The vehicle scheduling problem (VSP) can be solved by some heuristic algorithms. The disadvantage of these algorithms is that the solution quality decreases as the number of depots increases. Therefore, in this paper, we develop the Eligen-algorithm, which uses the techniques of column elimination and column generation, for solving the multiple-depot vehicle scheduling problems (MDVSPs). The advantage of this algorithm is that the solution quality improves as the number of depots grows. Moreover, this algorithm is faster and gives better solutions than the nearest bus-stop heuristic algorithm (NB) and the joined nearest bus-stop heuristic algorithm (JNB) which we developed before. For example problem instance, we use the modeling of city bus scheduling problem in Bangkok, Thailand.