High frequency bus operations in metropolitan areas should provide a reliable service to passengers by reducing their EWTs at bus stations. In several metropolis such as London and Singapore bus operators receive monetary incentives if they manage to reduce the EWTs of passengers or penalties if they fail to do so. However, optimizing the regularity of bus operations by preventing bus bunching is a computationally intractable problem and bus operators are not able to schedule the daily bus trips in an optimal way. Therefore, they rely on in-house expertise to manage their operations without fully exploiting the potential of applying operational control measures such as dispatching and bus holding at stations. For this reason, our work models the regularity-based bus operations and introduces REFLEX, an AI agent which enables the implementation of bus control actions. REFLEX uses a heuristic Sequential Exterior Point Greedy method for optimizing bus service operations and is tested in a trial with a major bus operator in Asia. REFLEX was able to optimize bus services with 200+ daily trips in just 1-2 minutes of computational time, while providing 17-35% theoretical service regularity improvement subject to a set of strict operational constraints such as adherence to layover times and departure frequencies ranges. Thanks to REFLEX rapid computation, bus operators can also simulate further service regularity improvements resulting from relaxing some operational constraints or adding more trips. Looking further, REFLEX can be combined with e-paper based timetable displays to provide a fully dynamic operational schedule and will be extended to support multi-modal interchange optimization.

1.Introduction

High frequency bus operations in metropolitan areas are regularity-based and strive to reduce passenger excess waiting times (EWT) at stations by avoiding bus bunching and maintain even headways between consecutive bus trips. However, bus routes are naturally unstable systems and headway variance tends to increase along a route, causing buses to bunch together1). When a bus arrives at a station with a long headway, a large number of passengers must board (and alight), causing further delay. To provide more reliable services, transportation authorities around the world have established Quality Incentive Contracts based on monthly penalty/bonus schemes. For example, metropolis such as London2) and Singapore3) have adopted a scheme that penalizes operators based on passengers EWT.

Several approaches have been proposed to alleviate bus bunching, such as skipping stops or embedding slack time in the schedule to hold buses in control points with the use of simulations4-6).

Moving a step further7), proposed a distributed control architecture based on multi-agent negotiation where stops and buses act as agents that communicate in real time to achieve dynamic coordination. The work of the reference8) was also one of the first addressing the regularity-based problem by considering all running buses as agents that negotiate the implementation of control measures that might affect some of them more than others.

Due to the inter-connectivity and high frequency of all daily trips of a bus service, the optimization of regularity-based bus services is a multivariate problem. As a result, this problem is computationally intractable and bus operators (i) generate ad-hoc daily bus schedules with the use of commercial manual planning software and in-house experience which do not mitigate properly the service reliability issues, (ii) cannot respond to bunching or other adverse operational situations by updating the daily schedules or introducing control measures that ensure the improvement of service reliability.

2.Regularity-based Bus Operations

A number of daily bus trips is assigned to every bus service in a city during the tactical planning phase. Improving the performance of regularity-based services without introducing on-demand trips can only be achieved by re-scheduling the departure times of existing bus trips or via bus holding at stations.

Bus services should satisfy a number of requirements imposed by the transport authority and the service operator. A first requirement comes from the bus frequency allocation phase which dictates that departure times between two successive bus trips should remain within a predefined time range for addressing the passenger demand levels.

Another typical constraint is the Maximum Loading Point constraint which dictates that over a time period at least a number of bus trips should serve selected bus stations to ensure that passenger demand is not greater than the bus service supply. Finally, the layover time constraint dictates that bus drivers should take a short break of 0-25 minutes before starting their next trip.

The control variables of the regularity-based optimization problem are the departure time changes of bus trips and the bus holding times at any other station.

Bus operators need mainly to minimize the EWT at a specific number of bus stations subject to all operational constraints which were described above. The EWT of passengers can be modeled by a nonlinear function which is not convex leading to a computational intractable problem with exponential computational complexity, that requires uo to 10175 years to find the optimal dispatching and bus holding control measures for a bus service with 180 daily trips assuming that one computer performs 1012 operations per second.

3.Optimizing Regularity-based Bus Services with REFLEX

REFLEX follows a rolling horizon approach for identifying the most suitable control measures. It gathers Automated Vehicle Location (AVL) information about the service operations and re-schedules the remaining daily trips by applying dispatching and bus holding changes as presented in Fig. 1. Therefore, REFLEX acts as an artificial intelligent agent which observes the bus operations through AVL sensors and acts using actuators (bus dispatching time changes and bus holding) for achieving the EWT reduction and operational constraints satisfaction goals.

REFLEX utilizes Stochastic Annealing (SA) to converge to a stochastic global minimum of the passenger EWT function. In case of operational constraints, the constrained optimization problem is approximated by an unconstrained one with the use of a Sequential Exterior Point Greedy method (SEPG) for converging to a stochastic global EWT minimum while satisfying the operational constraints described above.

REFLEX uses an iterative heuristic search method which is composed of the following features:

(i) approximating the regularity-based constrained optimization problem by an unconstrained one with the use of an exterior point penalty function
(ii) start the solution search by applying some random dispatching/bus holding measures and utilize a greedy hill-climbing search for finding new dispatching and bus holding control measures that reduce the value of the passengers EWT
(iii) terminate the search when the hill-climbing search cannot find any new control measures that improve further the EWT.

This global minimization method is stochastic (heuristic) and is presented in Fig. 2. As a consistency check, the algorithm can be run from a number of different random starting points to check if a better stochastic global optimum can be found since an exact optimization method cannot be applied due to the non-convexity of the objective function and the computational complexity.

REFLEX manages to converge rapidly to a stochastic global optimum and reduces the computational complexity from exponential to polynomial time that depends on the required sequences until convergence.

4.REFLEX Testing and Vaildation with Data from a Major Operator in Asia

The main scope of the case study is to test REFLEX capabilities on (i) improving regularity-based bus operations in terms of passenger EWT reduction; (ii) satisfying all operational constraints; (iii) converging fast to a solution for enabling implementation of dynamic control measures.

Bus operators, especially in metropolitan areas, utilize advanced software packages for planning the daily trips of bus services and rely also upon their in-house expertise during the operational phase. For this purpose, we tested how much the bus operator can be benefited by implementing the REFLEX for improving its existing planned operations. For this we test two bus services (one circular and one two-directional) which are carefully selected such that:

a) the first bus service operations violate several operational constraints but feasible re-planning solutions exist;
b) the second bus service operations violate many operational constraints which cannot be satisfied without introducing additional trips.
The circular service operates n=245 daily trips, covers 7.5km and serves S=22 bus stops with an average trip travel time of 37 minutes (the topology of both services is presented in Fig. 3).

The circular bus service is a feeder service covering residential blocks, schools, public amenities and connecting them to a Mass Rapid Transit (MRT) station.

It also had an EWT score of 0.2098 minutes and five (5) operational constraints were violated during the daily operations with the use Bus operations optimized. After applying REFLEX the daily EWT theoretical gain was 22% with dispatching time re-planning which increased further to 35% with bus holding control measures. In addition, all operational constraints were satisfied. The improvement of passengers’ excess waiting times at every critical station is presented also in Fig. 4 and the satisfaction of the five violated frequency range constraints in Fig. 5.

The computational performance tests were implemented on a 2556MHz processor machine with 1024MB RAM and REFLEX converged in 1 min. and 41 sec. showcasing that it can be applied for dynamic optimization of the entire day bus operations.

The second case study is one high-frequency two-directional bus service with n=224 bus trips per day (112 for direction 1 and 112 for direction 2). The average trip travel time for direction 1 is 1 hour and 33 minutes and for direction 2 is 1 hour and 29 minutes (direction 1 length: 23.5km; direction 2 length: 22.6km). Both directions serve the same number of bus stops (60 bus stops per direction) and the topology of the bus stops was presented in Fig.3.

The daily bus operations optimized by the service operator with the use of commercial software and in-house expertise led to a service-wide EWT score of 0.06932 minutes and thirty (30) violations of layover time constraints resulting to non-proper resting times for drivers in 14% of the cases.

In this case, REFLEX searched for optimal dispatching and bus holding control measures and converged in 1 min. 57 sec. after reducing the EWT score by 17%. The thirty (30) violated layover time constraints were also reduced to six (6) affecting the resting time of only 2.7% bus drivers instead of 14% as presented in Fig. 6. REFLEX identified also that for satisfying all layover time constraints the bus operator should introduce additional　 bus trips to that service.

The infeasibility issue of the two-directional service allows REFLEX to explore how its exterior point penalty can put more emphasis on satisfying some constraints while violating others according to the bus operator requirements. Results from this sensitivity analysis show that giving more importance to some constraints against others can satisfy the constraint priorities of bus operators while not deteriorating significantly the service-wide EWT score (variation of less than 2%).

Due to REFLEX rapid convergence, the bus operator can explore different scenarios. For instance, REFLEX not only optimizes the regularity-based operations subject to satisfying all operational constraints but it is also capable of exploring the improvement in terms of regularity if some of the constraints are violated. This is very valuable because the bus operator might decide to violate some secondary operational constraints if the regularity improvement is too strong. Results on this direction for the bi-directional service are presented in Fig. 7.

5.Conclusion

To improve regularity-based operations in dense metropolitan areas, we introduced a dynamic dispatching and bus holding framework (REFLEX). REFLEX was trialed for the regularity-based optimization of the daily bus operations of two inner city bus services (circular and bi-directional). REFLEX was able to satisfy all operational constraints if feasible solution(s) existed.

REFLEX is structured in such a way that allowed the prioritization of operational constraints and showcased a 17%-35% improvement of the service-wide EWT of passengers compared to the daily bus operations planned based on bus operator’s in-house expertise and commercial software. Part of this research was made possible thanks to the cooperation with NEC Laboratories Singapore.

Reference

1) Strathman, James G, Thomas J Kimpel, Kenneth J Dueker, Richard L Gerhart, and Steve Callas. 2002. “Evaluation of Transit Operations: Data Applications of Tri-Met’s Automated Bus Dispatching System.” Transportation 29 (3). Springer: 321–45.

2) “Transport for London: Bus Routes and Borough Reports.” 2015. https://www.tfl.gov.uk/forms/14144.aspx

3) “Land Transport Authority: Bus Service Reliability Framework.” 2015.

4) Delgado, Felipe, Juan Carlos Muñoz, Ricardo Giesen, and Aldo Cipriano. 2009. “Real-Time Control of Buses in a Transit Corridor Based on Vehicle Holding and Boarding Limits.” Transportation Research Record: Journal of the Transportation Research Board 2090 (1). Trans Res Board: 59–67.

5) Daganzo, Carlos F. 2009. “A Headway-Based Approach to Eliminate Bus Bunching: Systematic Analysis and Comparisons.” Transportation Research Part B: Methodological 43 (10). Elsevier: 913–21.

6) Bartholdi, John J, and Donald D Eisenstein. 2012. “A Self-Coördinating Bus Route to Resist Bus Bunching.” Transportation Research Part B: Methodological 46 (4). Elsevier: 481–91.

7) Zhao, Jiamin, Satish Bukkapatnam, and Maged M Dessouky. 2003. “Distributed Architecture for Real-Time Coordination of Bus Holding in Transit Networks.” Intelligent Transportation Systems, IEEE Transactions on 4 (1). IEEE: 43–51.

8) Gkiotsalitis, Konstantinos, and Nitin Maslekar. 2015. “Improving Bus Service Reliability with Stochastic Optimization.” In Intelligent Transportation Systems (ITSC), 2015 IEEE 18th International Conference on, 2794–9. IEEE.

Authors’ Profiles

Konstantinos Gkiotsalitis
NEC Laboratories Europe
NEC Europe Ltd.

Nitin Maslekar
NEC Laboratories Europe
NEC Europe Ltd.