Skip-stop schedules for public transportation

© 2017 Dr. Joanne Suk Chun ChewPublic transit skip-stop operations were first introduced to cope with the traffic congestion. Skip-stop operations take place when each vehicle services a subset of stations along a route, which together covers all stations. Most skip-stop scheduling problems in the literature were case based real-life problems. As a complementary contribution to the literature, we considered the generic fundamental skip-stop scheduling problems, and designed heuristics to solve them. We investigated variants of this problem. Five types of problems were considered: (i) minimizing passenger in-vehicle traveling time; (ii) minimizing passenger waiting time with equal passenger size problem; (iii) minimizing passenger waiting time with unequal passenger size and overtaking scheduling problem; (iv) minimizing passenger waiting time with unequal passenger size and non-overtaking scheduling problem; (v) minimizing passenger waiting time, in-vehicle traveling time and passenger capacity surplus time. A case study on Melbourne train network was also considered based on the problem (v). Optimal heuristic algorithms were developed for problem (i). For problems (iii), (iv) and (v), various methods were designed for each problem. In particular, the heuristic algorithm of TBHA for the problem (iii) obtained competitive solutions with negligible running times for all the instances tested and had the worst case ratio of the total passenger waiting time found to the minimum total passenger waiting time found of 1.30. In problem (iv), push and ρ-push heuristic algorithms produced high-quality solutions and also take a negligible time to run the programs of all sizes. In problem (v), column generation with NOVHA as the subproblem outperformed the other methods used in terms of the computational times and solutions. When solving the case study, CG with NOVHA as the subproblem produced a solution that improved passenger waiting and in-vehicle traveling time from the current train system by 12.7%