International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Menu

ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Adaptive Bus Routing Heuristics for Improving Vehicle Utilization and Reducing Commuter Waiting Times

S.R. Subramanya
School of Engineering and Computing, National University, San Diego, USA
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Abstract

Millions of people in cities around the world, especially in the developing and underdeveloped countries, depend on the (intra–city) public bus system to get to work and back home. In most cases, the system is strained – there are demands for more buses and routes than available. This has led to increased waiting times of the commuters. Also, since the routes are ‘static’, this might lead to underutilization of the buses. In this paper, we propose a system which makes use of sensors, and computing and wireless/mobile technologies in the buses and bus stops, and a central scheduler which gathers streaming data from the buses and bus stops and uses heuristics to determine in realtime ‘adaptive’ routes for the buses. These are expected to reduce the waiting times of commuters and increase the utilization of the buses.

Keywords
Public bus system; Adaptive bus routes; Commuter waiting times; Bus/vehicle utilization; Heuristics

INTRODUCTION
Millions of people in big cities around the world use the intra-city public bus system for their daily commutes. For example, the ridership in Singapore, Hong Kong, and London are 0.64, 0.53, and 0.78, with bus fleets (per Million populations) of 765, 816, and 918, respectively [1]. Public buses in Brazil are used quite heavily – 60 Million people take bus trips per day out of an urban population of 110 Million. The number of buses per Million inhabitants is 1,273. In Rio de Jeneiro, the share of the buses in motorized trips is about 80% compared to 15% for cars[2]. APSRTC, the Road Transport Corporation of Andhra Pradesh, a state in India holds the Guinness world record as the single corporation having the largest fleet in the world with over 22,600 buses. Over 15 Million passengers ride the APSRTC buses every day, a large percentage among them being intra–city passengers [3]. Close to 4.6 (4.598) Billion passenger journeys were made on local buses in England on a fleet of 36,000 buses in 2012/13, with half of these (2.315 Billion) in London, with a fleet of fleet of 9,000 buses. [4]
The traffic in big cities around the world, especially in the under–developed and developing countries, has been facing severe problems of congestion, leading to increased pollution. These problems have been increasing over the years, leading to environmental degradation and overall reduction of quality of life. The root causes of this are: (a) populations in big cities has been increasing with more people using public bus system; (b) the overall traffic has been increasing; (c) the road network cannot be expanded in proportion to demand; (d) the public bus system has largely remained unchanged.
In the current public intra–city bus transportation systems, the routes and the time-tables of the bus system are fixed (static). Although the frequencies of buses are higher during peak hours, it does not take into account the demand patterns along the routes. This, most often, results in overcrowding of buses and increased waiting times of commuters during peak hours. Also, during non–peak hours, buses would be going through several stops in their routes even though there may not be commuters either getting off or boarding the buses.
One of the ways of reducing the above problems is the provision of a good public intra–city bus transport system. This paper proposes an adaptive routing system for the intra–city buses, in order to improve the utilization of the buses, and also to minimize the waiting times of the commuters. The system uses heuristics which primarily make use of real– time data about the buses and passengers in them, and the passengers at the bus stops, and determine the adaptive routes for the buses.
The proposed system is somewhat of a hybrid between the traditional static (route and timetable) system and the DRTS (demand responsive transport system) which has considerable flexibility.The proposed system can be implemented using combinations of RFID (radio frequency ID), other sensors, wireless and mobile technologies, the Internet, and cloud computing. However, in this paper, we will not deal with those enabling technologies in the system. Our focus is on the heuristics of adaptive routing. There are two categories of conditions which warrant a deviation from a fixed route: recurrent conditions (ex. peak hour traffic) and non–recurrent conditions (ex. accidents, road construction/repair, extreme weather condition, etc.). The details of congestion conditions are detected by the use of appropriate technology solutions and are made available to the central scheduler. The scheduler would then determine the alternate/adaptive routes and send the route information to the affected buses.
In the next section we present some background and related work done with regard to dynamic transportation. Section 3 presents the proposed heuristics. Section 4 describes the simulation parameters of the heuristics. Section 5 gives future directions of this work, followed by conclusions.

BACKGROUND AND RELATED WORK
Almost all intra–city public bus services run according to pre–determined timetables having specific times of departure and arrival at stops along the route. These are often difficult to maintain in big cities due to traffic congestion, road blockages, bad weather, etc. Predictable effects such as morning and evening rush hour traffic are often handledby increasing the frequencies of buses on required routes. Predictable short–term increases in passenger numbers may be dealt with by havingextra buses, where two or more buses operate the same slot in the timetable. Unpredictable problems resulting in long delays may be dealt with by ‘turning around’ a bus before it reaches it terminus, in order to cater to the demands in the opposite direction, by having any remaining passengers on the bus disembark and continue on a following bus in their directions. Also, depending on the demands, extra buses may be dispatched from the closest depot to run partial routes.
Conventional bus services with fixed routes, fixed stops along the routes, and fixed times may not be effective and efficientin sparsely populated areaswith no heavy demands on bus service.This is necessarily due to circuitous routes, low frequencies, longer waiting times, and poorly used services. To alleviate the above problems, and still have a fairly efficient service, the demand responsive public transport systems (DRTS) providing a flexible point–to–point service have been proposed based on their feasibility due to developments in information and communicationtechnologies [5], as well as advances in optimization methods [6, 7]. DRTS exist in many cities, however, these often involve fixed origins or destinations, or fixed routes, or some form of pre-booking. Ad-hoc response to demand is a computational challenge; the underlying problem is NP-hard. A large number of computational heuristics were developed, e.g., [8, 9, 10]. Numerous optimization methods for DRTS have been proposed, a couple of samples are in [10, 11].
A general modeling framework for planning and managing DRTS and a Decision Support System (DSS) based on this framework is presented in [7]. It supports the study how different ways of operating the service affect its performance and efficiency, in a given scenario. It can generate good solutions in real-time.
Criteria affecting performance, key performance data and a limited set of performance measures for DRTS,and identification of the various factors that influence DRTS performance are provided in [12].It also describes the actions that rural DRTS have implemented to improve their performance, and a documentation of quantitative and qualitative effects on performance from those actions.Itserves as a resource to assist DRT systems to measure, assess, and improve their performance.
An adaptive and real–time routing component added as part of a conventional fixed-route bus system is described in [13]. It used a Markov chain process with reward model to estimate the optimal path for a bus, while still maintaining the scheduled bus stops. An objective function was used to minimize the bus travel time, by considering the value of time and fleet operating costs. Rerouting of buses was done to minimize the transit time, while also reducing the operating costs.In [14] a mathematical model to estimate regional bus travel time using artificial neural networks (ANN) is presented and is shown to perform better than forecasting methods, such as historical average and linear regression.
An adaptive transit system which is intended for low-density, spread-out populace in suburbia are presented in [15]. It presents a few different models with case studies of systems implemented in different cities. It also describes flexible routing, wherein the buses do not strictly follow fixed routes, but rather take deviations based on commuter requests. Three types of flexible routing mentioned are: (a) entire route, where buses may leave a route at any point; (b) point deviation, where buses may deviate only at pre-determined locations; (c) checkpoint, where buses may deviate with a (small) area and return to the fixed point on the scheduled route.
Traditional route planning problems are solved by computing shortest paths in a weighted graph representing a transportation network. Dijkstra’s Algorithm [16] is the fundamental shortest–path algorithm. It computes the shortest paths from a single source node to all other reachable nodes in the graph. For large graphs representing road networks, the classical Dijkstra algorithm is too slow. Also, for road/traffic networks, time–dependent edge weights, road restrictions, and multiple source and target nodes need to be considered. To handle these, numerous faster algorithms been developed in recent years. [17] presents a survey of numerous routing algorithms in road networks. These are not necessarily intra–city bus routes. It proposes new routing solutions to three extensions of transportation networks: (a) public transit networks, which are time–dependent and less hierarchical than road networks; (b) flexible queries–to optimize travel based on several query parameters; (c) batched shortest paths–consisting of multiple source–target pairs.
An efficient algorithm to find the shortest route between two nodes of a large–scale, time–dependent graph, which also allows the time-dependent arc cost functions to be updated at regular intervals is presented in [18].Finding all shortest distances between given source and target locations in large road networks, belongs to the many-to-many shortest path problem. Repeated applications of the Dijkstra’s algorithm is too time consuming, and efficient algorithms for the above problem are presented in [19], which considers both cases–the graph being static allowing preprocessing step, and the graph being dynamic with changing edge weights which precludes preprocessing.Using RFIDs (radio frequency identification) to track commuters and scheduling the buses based on passenger demand has been proposed in [20].
Methods to obtain optimal / near-optimal solutions to the routing and scheduling problems require extensive computations and enormous times, and faster methods, albeit suboptimal are desired. These use techniques such as Tabu Search, Simulated Annealing, Ant Systems, and Genetic Algorithms. A method of distributing the fleet of buses and their scheduling in an urban transit system using genetic algorithms is described in [21]. A model for the dynamic scheduling of bus operations in order for the optimization of vehicle utilization and commuter times is presented in [22]. It also presents the results of sensitivity analysis – the effects of varying numerous parameters such as passenger demand, travel time variation, skipping stops, etc., upon the performance of the system.

PROPOSED SYSTEM
In this section, we (a) present the architecture of the proposed system, (b) describe the major components of the system and their interactions, (c) describe the heuristics used in the (central scheduler of the) system.
A. System Architecture:
The overall architecture of the adaptively routed bus system is shown in Fig. 1. The three major components are (1) the buses; (2) the bus stops; (3) the bus routes; (4) the central scheduler. Note that the computing and communications in this system is not a distributed model, but a centralized one. The buses and bus stops are equipped with sensors, and with basic computing and mobile communications capabilities.
The central scheduler is a powerful computer capable of fast computations in order to respond in real–time to data streams arriving from the fleet of buses and bus stops. The scheduler also has mobile/wireless communications capabilities to receive/send the real–time to data streams. Optionally the commuters may have a mobile App on smartphones which can be used to get the expected arrival times of buses at the bus stops, the commute times between specified bus stops, the number of empty spots in the bus, etc.
A commuter arriving at a bus stop uses a touch screen terminal to select the destination. This will trigger an event resulting in sending a signal to the central scheduler. The central scheduler thus keeps track of the commuters arriving at the bus stops.
When a commuter boards and buys a ticket (or otherwise makes the destination known), the bus sends the destination information to the central scheduler. When commuters get off the buses, the information is suitably updated. Thus, at any time, the information about the commuters in any bus such as their destinations, the amount of time any commuter had to wait before boarding the bus, the expected time of arrival at the destination are known at the central scheduler.Based on the data sent by various sensors about road conditions, and the periodic GPS data samples from the buses, the central scheduler determines the congestion levels of the road segments.
B. Attributes and Functions of the Major Components of the System:
In this section we describe the attributes of (1) the buses, (2) the bus stops, (3) the bus routes, and the functions of (4) the central scheduler, which are shown in Fig. 2. The bus routes are the static routes as published in the bus route maps.
The data streams from the buses and bus stops contain timestamps so the scheduler can maintain the proper sequence of events. We assume that the mechanisms for error–free and secure transmissions of data streams are in place.
The attributes of the buses are: (a) the route with which the bus is associated; (b) bus capacity; (c) the number of commuters on the bus; (d) the destinations of the commuters on the bus; (e) the current position of the bus; (f) the total amount of time the commuters on the bus had waited, before getting onto the bus. The positions of the buses are sent by the GPS (global positioning system) devices in the buses. For the purposes of the heuristic, the position of the bus is assigned to be k soon after the bus leaves stop k, and will remain until it leaves the next stop.
The attributes of the bus stops are: (a) the number of commuters waiting at the stop; (b) the arrival times of the commuters at the stop; (c) the destinations of the commuters; (d) the bus stop name/number; (e) the route with which the bust stop is associated.
The attributes of the routes are: (a) the bus stops data along the route; (b) lengths of the road segments between successive bus stops; (c) the weight/cost of road segments. The cost of a road segment essentially determines the time taken to traverse the segment, and consists of fixed costs such as the length of the segment, the condition of the road, the number of traffic signal lights, etc., and variable costs such as the congestion on the road. The contributing factors to congestion are either the peak hour traffic (recurrent), or accidents, construction, extreme weather conditions, etc.
The major functions of the central scheduler are: (a) gathering and maintaining data from buses and bus stops; (b) determination of arrival times of buses at the stops; (c) determination of available capacity in the buses and their notifications to the bus stops (next in the route); (d) determination of adaptive (non-standard) routes; (e) prediction of commuter demands.
C. Adaptive Routing Heuristic:
In this section we present heuristics used by the central scheduler to determine adaptive routes for the buses. The determination is based primarily on the data/information received from the buses and the bus stops. It also (on rare occasions) makes the determination based on the non–recurrent conditions/events.
A non-standard route segment is part of a route which is not along the scheduled route, which reduces the transit time and/or overall passenger wait times. Adaptive routing essentially involves replacing short segment(s) of the standard route by non-standard routes.
The different ‘kinds’ of adaptive routes a bus may take are the following:
(1) A bus may take a non-standard route between any two scheduled stops (including two successive stops) in the route.
(2) A bus may skip a bus stop (or stops) in the standard route.
(3) A bus may go via bus stops in a different order than in the standard route.
In this paper, we formulate the conditions for the heuristics to determine adaptive routes. The exact detour involved in the adaptive route taken by a bus is not addressed here.
a) Notations
In this section we will give the terminology and definitions used in the formulation of conditions used in the determination of adaptive routes by the heuristics.
N :Number of routes
Mi :Number of buses in route i
Ri: Route i
Bj: Bus j
Sk: Bus Stop k
Cj: Capacity of bus j
Pjk: Number of commuters on bus j after the bus has just left stop k
Ajk: Available capacity of bus j after the bus has just left stop k = Cj – Pjk
Qk: Number of commuters waiting at bus stop k
U1 … UPj: Times commuters on bus j had spent waiting
V1 … VPj: (Expected) Times to destinations of commuters on bus j
W1 … WQk: Waiting Times of commuters at bus stop k until they board a bus
Si1 … SiQk: Destinations of commuters at bus stop k
Rjk: Number of commuters on bus j whose destination is bus stop k
Tk,k+1: (Expected) Transit from bus stop kto bus stop k+1
We assume that buses and bus stops have unique numbers (IDs) across all the routes.
b) Formulations of conditions of adaptive routing
In this section we present the formulations of the conditions which lead to determination of adaptive routes by the heuristics.
The bus takes adaptive routes (deviations from the fixed routes),possibly skipping some stop(s), under the following conditions:
(1) When the bus Bjis full and there are no passengers getting off the bus at the next stop k+1, then it skips stop k+1.
eqation
(2) When there are no passengers waiting for the bus at the next stop k+1, the bus which is just about to leave stop k can skip stop k+1 and reach the subsequent stop with some waiting commuters (via adaptive route).
eqation
(3) When a segment of the route is inaccessible (due to construction, accident, flooding, etc.).τiis a suitably determined threshold.
eqation
(4) When a segment of the route is severely congested.τcis a suitably determined threshold.
eqation
(5) When the sum of the waiting times of commuters on a bus leaving stop k exceeds the waiting times of commuters at stop k+1 by a certain factor α, then the bus skips stop k+1.
eqation
(6) When the sum of the waiting times of commuters at bus stop k exceeds a certain threshold τw, then a suitable bus in the vicinity with available capacity, which can afford a detour without causing delays to commuters onboard is alerted to go to the stop.
eqation
In cases (3), (4), and (5), “feeder” buses may need to be sent to the bus stops which are skipped by the normally scheduled bus(es), so as not to allow inordinate delays for commuters at those skipped stops.
D. Implementation:
The routes are modeled as weighted graphs. The bus stops are the vertices and the road segments between stops are the edges in the graph. Traffic conditions, road conditions, the rate of arrivals of commuters at the stops, and the destinations of the commuters, dynamically determine the edge weights (costs). Suitable speeded-up versions of the well–known algorithms for finding the least cost path between two vertices (ex. Dijkstra, Bellman–Ford), together with the heuristics for adaptive routing, is applied to determine the adaptive route between any two bus stops.

RESULTS AND DISCUSSION
The system for simulating the fleet of buses, the routes, bus stops, arrival of passengers and the proposed heuristics for the adaptive routing of buses is being implemented in Python. This section presents the description of the simulator including the simulation parameters and the events in the simulation. The actual results of simulation will be the topic of a forthcoming paper.
The parameters of simulation are:
• Commuter arrival rates at the bus stops
• Inter–arrival times of commuters at the bus stops
• The destinations of the commuters
• Commuters leaving bus stops without boarding a bus
• The number routes
• The number of bus stops in (each of) the routes
• The lengths (weights) of the road segments between stops
• The number of buses in (each of) the routes
• The capacity of the buses
• The starting times of buses at the bus terminuses in (each of) the routes
• The transit times of the buses between successive bus stops
This is event driven simulation. The following is a list of events, and suitable data is sent to the scheduler from a bus or bus stop. Data might also be sent (although rarely), due to non–recurrent events) from sensors along routes, or manually set by operators based on information received.
• Bus arriving at a bus stop
• Bus leaving a bus stop
• Commuter arriving at a bus stop
• Commuter leaving a bus stop, without getting on a bus
• Commuter(s) boarding a bus
• Commuter(s) getting off from a bus
• Severe congestion (above a threshold) in a route
• A non–recurrent condition (accident, construction, etc.) in a route
The data streams related to the above events are received by the central scheduler and used by the heuristics in its computations. This would then result in a set of events and corresponding data streams sent from the central scheduler to the buses and bus stops. These are:
• Adaptive route information sent to bus
• Expected arrival times of buses at bus stops (to be displayed both inside the buses as well as at the bus stops)
• Number of empty spots in buses (to be displayed at the bus stops, before the bus arrives)

CONCLUSIONS AND FUTURE WORK
Millions of people in big cities around the world depend on the (intra–city) public bus system to get to work and back home. Increasing city populations coupled with severe limitations to expansion of roads and routes in cities has restricted the improvements in the public bus system. This paper proposed heuristics for the ‘adaptive’ routing of buses based on the use of computing and communications technologies in the buses and bus stops, and a central scheduler which uses heuristics to determine improved schedules and routes for the buses. The adaptive routes enable the buses to take appropriate detours balancing the passenger demands and traffic conditions, which are expected to reduce the waiting times of commuters and increase the utilization of the buses.
The following list of items is planned for future work.
(1) Determination of the exact kind of adaptive routing that is selected for each of the conditions of adaptive routing.
(2) Development of metrics for vehicle utilization, and formulation of transit efficiency in order to formulate the optimization criteria for minimizing overall commuter waiting times and maximizing vehicle utilization.
(3) Graphical user interface for commuters arriving at bus stops, getting on/off buses, and the movement of buses along their routes, on a simulation timeline.
(4) Selection of actual maps from a given set of maps and the highlighting of actual routes of buses, and display of adaptive routes generated by the central scheduler on the maps.
(5) Operator interface through which several parameters of the system can be set, such as arrival rate / pattern of commuters at bus stops, the destinations of commuters, different levels of congestions at different segments of the various routes, etc.

ACKNOWLEDGEMENT
The author wishes to thank Mr. Timothy Wade,Sr. Security Integration Engineer at Leidos, for discussions of the heuristics, and his contributions toward the implementation of the simulation.

Figures at a glance
Figure 1 Figure 2
Figure 1 Figure 2
 

References