Techniques for large scale deployment of demand-aware bus transit systems

• Main Author: Perera, Talagalage Thilina Dharshana
• Other Authors: Thambipillai Srikanthan
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Engineering::Computer science and engineering::Computer applications::Computer-aided engineering; Engineering::Computer science and engineering::Computer applications::Computers in other systems
• Online Access: https://hdl.handle.net/10356/144682
• Institution: Nanyang Technological University

Public transit systems have been constantly plagued by the inherent connectivity gap due to fixed routes and schedules of feeder bus services. Demand-aware bus transit systems that rely on real-time scheduling of flexible routes have gained popularity as an alternative to bridge the connectivity gap, thereby enhancing user experience and operator profitability. In this research, scalable techniques have been proposed to realize citywide deployment of a demand-aware bus transit system to replace the conventional fixed-route based feeder bus services. In Chapter 3, a graph-based representation has been proposed to model demand-aware flexible route generation. The mixed integer programming model for generating the optimal flexible routes incorporates real-life scenarios including actual distances of the road network and asymmetric distance/time matrices that represent the different `to and fro' distance/travelling times between two given points. The proposed model can successfully generate optimal flexible routes to enhance the travel times of passengers (user experience) or vehicle miles travelled by the fleet (operator profitability). In particular, the normalized weighted technique has been introduced to facilitate trade-off analysis based on user requirements to ensure that the flexible routes are sensitive to both the user experience and operator profitability. The proposed model has been successfully employed to prune the design space to speed up route computations without compromising optimality. Experimental results demonstrate the capability of the model in performing diverse what-if analyses by varying different input parameters. A heuristic routing technique has been proposed in Chapter 4 to accelerate the flexible route generation process by combining both the Ꜫ-constraint method and a genetic algorithm. The technique incorporates nearest neighbour heuristic to generate superior initial solutions, selection of genetic operators for fast convergence, and a hybrid parent selection algorithm for balancing solution quality and diversity. Experimental results confirm that routes generated by the proposed technique deviate only 3% from the optimal values. The rapid convergence of the proposed technique results in a 26% reduction in runtime when compared to a widely-used baseline algorithm. A directionality-centric technique has been proposed for the systematic segmentation of bus transit network in Chapter 5. The network segmentation technique generates sub-zones based on the feasible shortest path routes from its bus stops to the destination. Heuristic technique proposed in Chapter 4 has been employed to generate the flexible routes of the size limited sub-zones. This has led to notable speed-up of flexible route computations that can also benefit from parallel computations, thereby paving the way for a highly scalable technique without compromising the responsiveness demanded by demand-aware bus transit systems. The outlier bus stops of sub-zones are incorporated into the neighbouring sub-zones on-the-fly to minimize vehicle detours. Moreover, dynamic methods for demand-aware allocation of EVs and workload balancing among sub-zones improves the overall responsiveness of a large-scale deployment. Experimental results confirm that the routes generated using the proposed technique achieves over 7x speed-up when compared to a global, heuristic routing technique without compromising on solution quality. A similar performance improvement was also evident for the case of sporadic demands, highlighting the applicability of the proposed network segmentation technique to real-life scenarios. In Chapter 6, applicability of the proposed methods to a large scale deployment of demand-aware bus transit system has been demonstrated. This necessitated the systematic segmentation of feeder bus services into sub-zones and outlier bus stops as well as point-to-point trunk services. Identification of independent transit hub regions of a large scale transit system as well as segmenting each transit hub into workload balanced zones has notably improved the responsiveness of route computations. Experimental results confirm that, compared to a widely-used unsupervised learning algorithm, the zone-wise runtime has improved by 83% while also improving the quality of routes. A demand-aware scheduling technique to improve the user experience and operator profitability of trunk bus services has also been proposed in this chapter. In Chapter 7, the various techniques proposed in this thesis have been integrated into a framework to realize the citywide deployment of demand-aware flexible routing. The model for demand prediction was trained using multi-modal sensing inputs from mobile apps and vision-based crowd counting. This has paved the way for estimating near-future demand at each bus stop to schedule flexible routes in real-time. Runtime performance of citywide route generation process has also been improved by the offline processing of a significant component of the workload and by limiting the generation of sub-zones, based on near-future demand estimation, to online. Experiments confirm that the flexible routes can be computed in 20 and 24 seconds for workloads of 50 and 65 passengers respectively, when implemented on a 4-core Xeon E5-1630 V4 CPU running at 3.70 GHz. The proposed sensing methods also lend well for the periodic generation of offline schedules for trunk bus services. Finally, real-life deployment of the proposed techniques for the city-wide replacement of fixed-route based bus transit systems has been successfully demonstrated to minimise the connectivity gap inherent in current implementations.