Designing Demand-Responsive Bus Services for Imbalanced Demand

Traditional public transport systems typically operate using a fixed-route and fixed-timetable scheme. To introduce a level of flexibility to the operations and, ultimately, make public transportation more attractive, research on public transport planning and optimization shifts towards more tailored options, which we call: `demand-responsive systems'.

In this thesis, we explore demand-responsive bus operations to improve the efficiency of public bus systems when there is demand imbalance. When a single bus line operating between a city center and a terminal station is considered, there exists a clear imbalance in the demand for transportation between the two directions during peak hours. We try to exploit this imbalance. We introduce the Demand-Responsive System with Express Services (DRS-ES) to increase the frequency of service in the peak direction by allowing vehicles to take an express service in the off-peak direction. Mixed Integer Quadratic Programs are developed to optimize the decisions of this system based on expected demand. Different variants of the DRS-ES are analyzed. Experiments show that the demand-responsive operation can indeed improve the average travel time of passengers. However, only small and medium-size instances can be solved to optimality due to problem complexity.

Variable Neighborhood Search (VNS) algorithms are developed to optimize the operational decisions of the DRS-ES within a couple of minutes. This means that just before the peak hours, VNS algorithms can decide which buses should make an express service in the off-peak direction and when to depart from the city center and the terminal. Experiments show that the total passenger travel time improves about 10\% on average for a real-size benchmark instance as a result of the increased frequency of service in the peak direction. In fact, the improvement reaches up to 40\% especially if only waiting times are considered or in case of limited vehicle capacity. The performance of the system is also analyzed under different fleet sizes and capacities, durations of peak hours, and demand scenarios.

We then propose a much more flexible and complex variant of the DRS-ES, the On-Demand System with ShortCuts (ODS-SC). Similar to the DRS-ES, the ODS-SC aims to increase the efficiency of service during peak hours by allowing vehicles to take shortcuts between the city center and the terminal. Unlike the DRS-ES, the decisions are optimized based on passenger requests for the peak hours. Passengers indicate their origin, destination, and desired pick-up time through an app or an online platform before the peak hours. Since the passenger requests are explicitly taken into account, each passenger is assigned to a service that serves their origin and destination. This assignment is communicated to the passengers when the peak hours start. In the ODS-SC, it is decided separately for each bus and each shortcut whether to take the shortcut or follow the regular route. In contrast, in the DRS-ES, a single express route, taking all shortcuts, was used by all express services. Additionally, express services were allowed only in the off-peak direction in the DRS-ES, whereas shortcuts are allowed in both directions in the ODS-SC.

Given the practical importance of efficiently solving the ODS-SC in short-time, a VNS algorithm is developed to optimize the operational decisions of the ODS-SC. Based on the received requests, the VNS algorithm decides which shortcuts to take by each bus in each direction, when to depart from the city center and the terminal, and the corresponding passenger assignments in a matter of minutes. Experiments show that with the on-demand operation, the total passenger travel time improves up to 45\% on a real-size line compared to its traditional fixed-route operation. The performance of the system is also analyzed considering different fleet and demand scenarios. In addition, passengers without requests but just showing up at their origin stops are also served in the ODS-SC. The impact of these passengers on the system performance is also analyzed.

Overall, the results show that traditional fixed-route operation loses its efficiency in the presence of demand imbalance. In contrast, the demand-responsive and the on-demand operations can significantly improve passenger travel times. On the one hand, the DRS-ES offers a solution that responds to the demand imbalance without requiring a reservation system between passengers and the operator. On the other hand, the ODS-SC, while providing greater flexibility, requires a reservation and communication system between passengers and the operator in return for even more substantial improvements in passenger travel times.

We also study the transit network design problem (TNDP) in the traditional public transport network optimization. After deciding on the infrastructure network, i.e. the set of stops or stations and the roads or tracks between these, in the TNDP, the set of lines of a bus, train or tram system is decided. When addressing the TNDP with passenger travel time in mind, the passenger assignment problem (PAP) needs to be addressed explicitly. The PAP is a complex problem on its own and even the simplest version requires determination of the shortest path for all demand pairs in the network. In the TNDP, typically bi-level optimization models and/or metaheuristics are used where the PAP is solved when evaluating a line plan. In doing so, the PAP is often addressed by representing the transit network with a so-called `Change-and-Go' (CNG) network with dummy transfer nodes in order to model transfer penalties as part of the passenger travel time. Then, in order to solve the PAP, the all-pairs shortest path problem needs to be solved for this CNG network representation, which is often claimed to be the most time consuming part of the algorithms. To overcome this, we present a much more efficient network representation, the `Direct Link Network' (DLN), where additional edges are added instead of additional nodes. We compare the theoretical complexity of both representations and the computation time required to solve the PAP by using CNG and DLN on the most commonly used benchmark networks and also several real-life networks. The results show that with the DLN representation, the PAP can be solved on average 350 times faster than with CNG. Consequently, DLN can significantly speed up all TNDP algorithms that solve the PAP over and over when designing a public transport network.