Dynamic Urban Transit Optimization with Cross Entropy Method and Surrogate Functions


Student thesis: Doctoral Thesis

View graph of relations


Awarding Institution
Award date13 Sep 2022


This thesis investigates dynamic urban transit optimization problems subject to passenger demand variations. Reliable and effective transit network operations are vital to the sustainable development of urban areas. With recent technological advancements, incorporating real-time operational and demand data is becoming increasingly feasible for improving transit networks' performance. This calls for advanced techniques to tackle optimization problems that arise in transit planning. This thesis develops cross entropy method (CEM)-based and surrogate-assisted approaches for solving transit planning problems and seeks to achieve the following specific research objectives.

We first propose a multi-objective optimization framework which seeks jointly the settings of service lines and frequencies that could minimize the passengers' journey times, transfer rates, and operator's cost. A dynamic transit network model is formulated to capture the stochastic network demand, passengers' transfers and rolling stock recirculation. The optimization problem is solved by CEM, which samples potential solutions from statistically tractable distribution models with iterative updates via maximum likelihood. The explicit incorporation of operational constraints into the solution process enhances the sampled solutions' feasibility and hence the computational effectiveness compared with other metaheuristics in the literature. A CEM-based ranking algorithm is further developed for deriving the Pareto-frontiers for multi-objective transit network routing and frequency setting. The proposed framework is applied and tested on the Hong Kong Light Rail Transit (LRT) network using real-world scenario data.

Next, we present a multi-objective optimization framework aiming to derive optimal train unit assignment and service dispatching schedules that could minimize both operator and passenger costs. The dynamic transit network model established in the first study is extended to incorporate the deployment of flexible train composition. The CEM-based multi-objective solution algorithm will further be assisted by surrogate models that approximate the expensive-to-calculate objective function values in the optimization process. The proposed framework is applied and tested on the Hong Kong LRT network using real-world scenario data. The results reveal that dynamic transit operational plans can be derived with significantly reduced computational time via the proposed surrogate-assisted CEM.

Finally, we develop an adaptive optimization framework for coordinated rail transit network operations with flexible schedules and train unit composition with respect to prevailing passenger demand variations. The control problem is formulated as a Markov decision process and solved by a rollout surrogate-approximated dynamic programming approach. The underlying transit network model is used to derive short-term performance estimates up to a finite horizon. With concerns over computational effectiveness needed for real-time applications, a state-dependent surrogate function is incorporated to approximate the long-term performances associated with operational decisions over future stages. The surrogate approximation parameters are updated iteratively via a temporal difference learning process with the feeding of observations made from the transit operations. The proposed framework is implemented and tested in a real-world scenario of the Hong Kong LRT network. The results reveal reductions in passengers' waiting times through implementing the proposed framework in real-time. It also shows a significant computational time reduction via the surrogate approximation.

By fulfilling the above research objectives, this thesis contributes to advanced optimization techniques for solving transit optimization problems from different transit planning levels. Depending on use cases, the proposed frameworks may be employed as a unified framework or used separately to tackle the optimization problem of interest. Practical insights and findings from the thesis about efficient transit service plans suggest the potential of applying the proposed optimization frameworks to large-scale transit networks.