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

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...

Full description

Saved in:
Bibliographic Details
Main Author: Perera, Talagalage Thilina Dharshana
Other Authors: Thambipillai Srikanthan
Format: Thesis-Doctor of Philosophy
Language:English
Published: Nanyang Technological University 2020
Subjects:
Online Access:https://hdl.handle.net/10356/144682
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-144682
record_format dspace
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Engineering::Computer science and engineering::Computer applications::Computer-aided engineering
Engineering::Computer science and engineering::Computer applications::Computers in other systems
spellingShingle Engineering::Computer science and engineering::Computer applications::Computer-aided engineering
Engineering::Computer science and engineering::Computer applications::Computers in other systems
Perera, Talagalage Thilina Dharshana
Techniques for large scale deployment of demand-aware bus transit systems
description 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.
author2 Thambipillai Srikanthan
author_facet Thambipillai Srikanthan
Perera, Talagalage Thilina Dharshana
format Thesis-Doctor of Philosophy
author Perera, Talagalage Thilina Dharshana
author_sort Perera, Talagalage Thilina Dharshana
title Techniques for large scale deployment of demand-aware bus transit systems
title_short Techniques for large scale deployment of demand-aware bus transit systems
title_full Techniques for large scale deployment of demand-aware bus transit systems
title_fullStr Techniques for large scale deployment of demand-aware bus transit systems
title_full_unstemmed Techniques for large scale deployment of demand-aware bus transit systems
title_sort techniques for large scale deployment of demand-aware bus transit systems
publisher Nanyang Technological University
publishDate 2020
url https://hdl.handle.net/10356/144682
_version_ 1688665429590933504
spelling sg-ntu-dr.10356-1446822021-01-07T00:56:29Z Techniques for large scale deployment of demand-aware bus transit systems Perera, Talagalage Thilina Dharshana Thambipillai Srikanthan School of Computer Science and Engineering ASTSRIKAN@ntu.edu.sg Engineering::Computer science and engineering::Computer applications::Computer-aided engineering Engineering::Computer science and engineering::Computer applications::Computers in other systems 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. Doctor of Philosophy 2020-11-19T00:46:16Z 2020-11-19T00:46:16Z 2020 Thesis-Doctor of Philosophy Perera, T. T. D. (2020). Techniques for large scale deployment of demand-aware bus transit systems. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/144682 10.32657/10356/144682 en This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0). application/pdf Nanyang Technological University