1 Introduction and Background

India, one of the emerging economies in the world, is undergoing rapid growth in urbanization and vehicle ownership leading to greater levels of pollution, traffic congestion, and associated delays. One of the ways to address this problem is to make public transportation a comfortable, flexible, economical, and reliable service. Such a system has the potential to encourage a mode shift from private transportation to public transportation, which can help in reducing congestion. One of the important steps in this direction is to have a service that satisfies the needs of both passengers and operators [1,2,3]. From a passenger’s perspective, one of the most important objectives will be to minimize delays, while from operator’s perspective, it will be to reduce the operational costs using optimal fleet size and manpower, thereby maximizing their profit. One of the important steps in this direction is to develop a schedule that satisfies the above two objectives.

Dynamic scheduling is a problem of assigning trips optimally to buses that are located at one or more bus depots to make the system efficient [4]. It allows users to efficiently transfer from one bus to another and to minimize their waiting time. It also allows efficient use of drivers by optimising their fleet size and allows transit agencies to follow the regulations on how long a driver is allowed to drive before taking rest or break [5]. Overall, scheduling can help in planning efficient fleet operations resulting in higher capacity utilization and reduction in the passenger waiting time [5,6,7,8,9]. On the other side, uncertainty in arrival time information due to dynamic vehicle dispatching is one problem. Extra delay due to lesser services during off-peak hours is also a challenge. Both these can be handled by disseminating the real-time information about the arrival times to passengers through mobile applications, web page announcements, and bus stop display boards.

In an ideal scenario, a schedule should be prepared in a way that can distribute the passenger load across the buses, avoid bus bunching, and minimize the passenger waiting times at bus stops [10]. However, variability in the passenger demands and traffic conditions push the system into undesirable states. An optimal schedule is characterized by minimal fleet size or minimal operational costs [11]. Bunte et al. [11] defined scheduling problem as “Given a set of timetabled trips with fixed travel times (departure and arrival) and start and end locations as well as travel times between all pairs of end stations, the objective is to find an assignment of trips to vehicles such that, (i) each trip is covered exactly once, (ii) each vehicle performs a feasible sequence of trips and (iii) the overall costs are minimized.” Lampkin and Saalmans [12] formulated a constrained optimization problem to determine the optimal frequency of transit buses. Their main objective was to minimize the total travel time for a given fleet size constraint. A random search procedure was adopted to solve the optimization problem. Newell [13] proposed a method to develop schedules to minimize passenger waiting time and formulated a mathematical model to compute the optimum number of trips required to meet specified passenger demand. Silman et al. [14] determined optimum frequencies for a set of bus routes with a given fleet size that can minimize the total travel time using gradient method procedure. Dashora [15] used an expert system-based model to allocate the buses for different routes between a maximum and minimum number, based on additional bus allocation criteria. Jian et al. [16] proposed a basic fixed job scheduling model to formulate the single depot transit vehicle assignment. The algorithm was solved based on the concepts of a greedy algorithm. Hao et al. [17] proposed a model on Multi-Depot Vehicle Scheduling Problem with Route Time Constraints (MDVSPRTC) to minimize the capital cost and the overall operational cost with a series of constraints and the problem was solved using Max–Min Ant System (MMAS). Fu and Yang [18] proposed a methodology in which the buses were dispatched in pairs, where the lead vehicle picks up passengers in all the bus stops and the following vehicle was allowed to skip certain bus stops. Ibeas et al. [19] presented an optimization model to decide dispatch headway of buses and fleet size by considering the costs from both the operator and user side. Wagale et al. [20] developed a Demand and Travel time Responsive (DTR) model to determine the optimal timetable for each bus stop and the optimal headways to be provided. Irrespective of the objective function or method being used for the scheduling process, a transit scheduler requires the basic details regarding transit services [21] such as route structures (origin and destination), span of service (the hours of operation for each route), service frequencies, time points, terminal points, and passenger demand over time across all bus stops.

From the above studies, it can be observed that the developed models minimized the costs efficiently but provided only fixed schedules based on specific passenger demand and traffic pattern, which were not able to adapt to traffic variations. Also, only a few studies considered the capacity constraint of the bus and many studies did not consider the increase in passenger waiting times in modelling. It was also observed that researchers considered passengers and bus companies as isolated agents and made decisions separately by ignoring the impact of one agent’s decisions on the other agent. With these gaps, the present study aims to develop a model that takes into account the interaction of prospective passengers and bus companies to achieve the maximum financial benefit as well as social satisfaction as the study will particularly focus on (1) Develop a methodology for a dynamic scheduling strategy that can adapt to the variations in passenger demand, traffic variations, waiting time of the passengers, and capacity constraints of the buses, and (2) conduct a performance evaluation of the developed strategy with a fixed schedule that is available for the route upon selecting suitable parameters such as passenger waiting time and percentage utilization of bus capacity.

2 Data Collection and Preparation

With the advancements in technology and availability of real-time Automatic Vehicle Location (AVL) data, buses can be monitored in real time to know about their positions. For the purpose of data collection, bus route 19B of The Metropolitan Transport Corporation (MTC), Chennai was selected as test route. It spans across 29.4 km connecting Kelambakkam and Saidapet bus depots, with 12 major intermediate bus stops [22] and the selected bus route is shown in Fig. 1. The selected route is a typical representative of Indian traffic conditions with traffic characteristics, geometric characteristics, volume levels, and land use characteristics.

Fig. 1
figure 1

19B route

Full size image

The buses that were used to collect the data in the present study were fitted with speed lock devices to travel at a maximum speed of 60 km/h. The service was scheduled to have an average dispatch headway of 10–15 min [23]. For the purpose of demonstrating the proposed scheme, data obtained from a total of 51 fixed schedule-based trips (starting time of the trip, arrival times of bus at all bus stops, real-time speeds of buses, capacity, etc.) were collected and analysed further. The collected AVL data included the device ID of the unit, time stamp, and latitude and longitude of the location at which the entry was made.

Figure 2 shows the variation in speed of buses in the selected route over a day. From Fig. 2, it can be observed that there are (i) two visible troughs, one in the morning and one in the evening representing the morning and evening peak periods and (ii) three peaks representing the morning off-peak, afternoon off-peak, and late night trips. Table 1 shows the descriptive statistics of travel times in the selected route.

Fig. 2
figure 2

Hourly variation of speed along the considered route, 19B

Full size image
Table 1 Descriptive statistics of the sample trips along the considered route, 19B
Full size table

The collected data were further processed and used as inputs to predict the arrival time of the bus to all bus stops. The passenger arrival rates and alighting were not available for the route under study and hence were simulated assuming suitable arrival and alighting rates at respective bus stops. Further, these data were used to calculate the occupancy of the bus with the help of arrival and departure time of buses for testing purposes.

3 Methodology

Among the literature that addresses the bus scheduling problem, many of them used control or holding strategies to minimize passenger waiting time. Bus control methods at depots can be classified into two types: schedule-based control and headway-based control [28]. Schedule-based control strategies aim to maintain schedule adherence and the objective is to move off-schedule buses back to schedule. On the other hand, headway-based control strategies aim for headway adherence and the objective is to space the buses on the route evenly to achieve a uniform headway between the buses. Out of these, schedule adherence would be important in low-frequency routes as passengers would reach the bus stops based on the schedule. However, when the planned headways are low, the passengers do not pay attention to the schedules and they head to the bus stops randomly [29, 30]. Hence, headway adherence becomes more important than schedule adherence. As the selected 19B bus route had a peak period frequency ranging between 10 and 15 min, which can be classified as a medium frequency service, a headway-based approach was adopted. First, an expression for capacity constraint of buses was developed followed by the formulation of an objective function for dynamic scheduling taking into account the constraints due to bus capacity and maximum anticipated headway of passengers. These are explained in the section below.

3.1 Capacity Constraint

One of the important factors in improving the efficiency of public transport is providing a comfortable service to passengers. However, during peak hours of passenger demand, buses may reach its seating capacity at one of the bus stops during its travel and may cause discomfort to passengers who are boarding at succeeding bus stops due to unavailability of the seat. To overcome this problem, the present study keeps track of bus occupancy, i.e. number of passengers travelling on the bus and its capacity. If bus attains its capacity during its travel, an additional bus would be dispatched from the depot to serve passengers. This strategy may lead to having more number of buses on the route with low headways during peak hours but can be effective in reducing the waiting times of the passengers without much loss to the operators. The bus occupancy at any point of time was calculated as a function of passenger arrival rates, alighting rates, headways, and estimated time of arrival of buses to each stop as

$$P_{k} = \mathop \sum \limits_{j = 1}^{k} \left( {\lambda_{j} h_{j} - \alpha_{j} P_{k - 1} } \right),$$
(1)

where \(P_{k}\) is the number of passengers travelling in the bus at kth bus stop, \(\lambda_{j}\) is the passenger arrival rate at the jth bus stop, \(h_{j}\) is the headway of buses at jth bus stop, \(P_{k - 1}\) is the number of on-board passengers in the bus, and \(\alpha_{j}\) is the passenger alighting rate at the jth bus stop. Also, in order to make efficient decisions, the present study estimates the passenger occupancy values at all bus stops iteratively using expected arrival time of current bus to all bus stops (from the current bus stop to the end stop), a unique feature of the proposed methodology. The expected arrival times of buses to future bus stops were calculated using a methodology developed by Vanajakshi et al. [31].

3.2 Dynamic Scheduling

Bus service reliability at a given stop can be defined as the probability of a bus arriving at the stop within the maximum passenger anticipated headway [32]. The headway regularity metric (p) used in the present study can best describe the level of service provided at a bus stop by the service [32] and can be expressed as

$$p = P\{ {\text{headway}}_{k} < H_{b} \} ,$$
(2)

where \(H_{b}\) is the maximum passenger anticipated headway. Alternatively, this would be the optimal headway that should be provided in the route considering both minimal cost and minimal waiting time. This optimal headway can be expressed as a function of dwell time, passenger arrival rate, and passenger boarding rate as

$$h_{k} = (1 + \rho_{k - 1} )(h_{k - 1} - d_{k - 1}^{p} ),$$
(3)

where \(\rho_{k - 1}\) is the passenger arrival rate divided by the passenger boarding rate at the previous stop, \(d_{k - 1}^{p}\) is the dwell time of the previous bus at the previous stop, and \(h_{k - 1}\) is the headway of the bus when it reached the previous stop. To take into the account of variations in traffic conditions, dwell time, and passenger arrival rate, time taken to travel in kth link between two consecutive bus trips, \(\Delta t_{k}\) was incorporated as an additional term in Eq. (3) as

$$h_{k} = \left( {1 + \rho_{k - 1} } \right)\left( {h_{k - 1} - d_{k - 1}^{p} } \right) + \Delta t_{k} ,$$
(4)
$$h_{k - 1} = \left( {1 + \rho_{k - 2} } \right)\left( {h_{k - 2} - d_{k - 2}^{p} } \right) + \Delta t_{k - 1} .$$
(5)

Upon substituting \(h_{k - 1}\) in terms of \(h_{k - 2}\) dispatch headway of the bus, \(h_{k}\) can be simplified as

$$h_{k} = \left( {1 + \rho_{k - 1} } \right)\left( {1 + \rho_{k - 2} } \right)\left( {h_{k - 2} - d_{k - 2}^{p} } \right) - \left( {1 + \rho_{k - 1} } \right)d_{k - 1}^{p} + \left( {1 + \rho_{k - 1} } \right)\Delta t_{k - 1} + \Delta t_{k} .$$
(6)

By further substituting up to \(h_{1}\), general formulation to decide departure headways at kth stop that considers variations in passenger arrival rates, dwell times, and changes in traffic conditions can be written as

$$h_{k} = \left[ {\prod\nolimits_{{j = 2}}^{k} {\left( {1 + \rho _{{j - 1}} } \right)h_{1} } } \right] - \left[ {\sum\limits_{{l = 2}}^{k} {\left\{ {\prod\nolimits_{{j = 1}}^{k} {\left( {1 + \rho _{{j - 1}} } \right)d_{{l - 1}}^{p} } - \prod\nolimits_{{j = 1}}^{k} {\left( {1 + \rho _{{j - 1}} } \right)\Delta t_{{l - 1}} } } \right\} + \Delta t_{k} } } \right].$$
(7)

With prior information about passenger arrival rates at various bus stops throughout the day and expected arrival time of buses to each bus stop along the route, the seat availability in the bus can be calculated using Eq. (1).

  • Case 1: In case, if the bus reaches its capacity at a particular stop, the next bus would be dispatched from depot such that it reaches that particular bus stop within an anticipated headway. The corresponding departure headway of the next bus would be calculated using Eq. (7) and can be expressed as

    $$h_{1} = \frac{{h_{k} + \left[ {\sum\limits_{{l = 2}}^{k} {\left\{ {\prod\nolimits_{{j = 1}}^{k} {\left( {1 + \rho _{{j - 1}} } \right)d_{{l - 1}}^{p} } - \prod\nolimits_{{j = 2}}^{k} {\left( {1 + \rho _{{j - 1}} } \right)\Delta t_{{l - 1}} } } \right\} + \Delta t_{k} } } \right]}}{{\prod\nolimits_{{j = 2}}^{k} {\left( {1 + \rho _{{j - 1}} } \right)} }}.$$
    (8)

  • Case 2: If the capacity of the bus never reached during a trip, the next departure time would be purely governed by the maximum anticipated headways. This would ensure the optimal departure time considering the traffic conditions, maximum anticipated headways from the perspective of passengers, and capacity constraint of bus subjected to the availability of buses in the depot to be dispatched.

3.3 Model Formulation

A demand and travel time responsive scheduling strategy that can benefit the operator was developed with an objective function to maximize the headways of buses subject to various constraints such as bus capacity and maximum anticipated headway as

Objective function:

$${\text{Max:}}\;h_{o}^{i} .$$
(9)

Subjected to constraints

$$\begin{array}{ll} {h_{k}^{i} \le H_{k}^{i} } & \quad {k = 1,2,3, \ldots ,12} \\ \end{array} ,$$
(10)
$$\begin{array}{*{20}c} {h_{k}^{i} \le H_\text{cap}^{i} } & \quad {k = 1,2,3, \ldots ,12} \\ \end{array} ,$$
(11)

where, i denotes the trip number, \(h_{o}^{i}\) is the departure headway where the operator would like to maximize to reduce the total number of trips, \(h_{k}^{i}\) is the headway at the kth bus stop which is governed by Eq. (8), \(H_{k}^{i}\) is the maximum headway that is planned to be provided at the kth bus stop at the corresponding time, l denotes the bus stop numbers which were skipped by the previous bus because of capacity being reached, \(H_{cap}^{i}\) is the maximum allowable headway between the current bus and the previous bus which skipped the bus stop. It has to be noted that the second constraint will be considered only when the previous bus reaches the capacity at some bus stop that is identified using Eq. (1). The input data required for implementing the above-mentioned demand and travel time responsive bus scheduling and how they are obtained are discussed below:

  • Passenger arrival rates at each bus stop: The passenger arrival rates were not available for the route under study and hence were assumed. These data can be accurately obtained in real time with the help of automatic passenger counting (APC) systems or automatic ticketing systems.

  • Alighting rate of passengers: It is denoted as a proportion of the number of passengers currently travelling on the bus. This was also varied across different bus stops and time of the day, i.e. peak and off-peak periods. In real time, these data can be obtained from the automatic ticketing systems.

  • Arrival time of the bus at all bus stops: The time taken to travel between any two bus stops was predicted using a methodology proposed by Vanajakshi et al. [31] that uses the information received from GPS units.

  • Maximum passenger anticipated headways: The maximum anticipated headways were assigned based on the peak and off-peak. These values were assumed to be ranging from 10 min in peak period to 40 min in the off-peak period.

  • Real-time speed of the buses: The bus speed at any particular time/instant was taken to be the closest available speed that was obtained from GPS data.

  • Capacity of the bus: The capacity of the buses was taken as 75 passengers.

  • Boarding rate: The boarding rate at any bus stop was assumed to be 2 s/passenger.

4 Implementation and Evaluation

For the purpose of evaluating the above implemented scheme, two parameters were selected as performance measures: (i) passenger waiting times at bus stops, which denotes the level of service experienced by the users, a metric the passenger would be interested in and (ii) utilization percentage of bus capacity, which denote the efficiency with which the service is being operated, a metric the operator would be interested in. The output obtained by implementing the above scheme, i.e. optimized schedule, is shown in Table 2.

Table 2 Optimized schedule obtained from the proposed methodology
Full size table

From Table 2, it can be observed that more buses were dispatched during peak hours and were mainly decided by the capacity of the buses being reached and limited by the maximum number of buses available for dispatch. During off-peak hours, the schedule is mainly decided by the maximum headway/waiting time constraint.

4.1 Passenger Waiting Time

The passenger waiting time is the amount of time that a passenger waits at a bus stop before boarding a bus. These values were calculated for all bus stops in the selected route for each trip and the corresponding results are presented in Fig. 3 for sample trips and bus stops.

Fig. 3
figure 3

Evaluation of the proposed methodology w.r.t. passenger waiting time

Full size image

Figure 3a shows the variation in the passenger waiting time for a sample trip across the bus stops in the selected route and Fig. 3b shows the average waiting times. From Fig. 3a, it can be observed that waiting times are varying from bus stop to bus stop and from Fig. 3b, it can be observed that the 6th, 7th, 10th, 11th, and 12th bus stops have relatively high waiting times compared to other bus stops, indicating the effect of land use such as the presence of residential area. As passenger waiting times may vary with respect to the time of the day, an in-depth analysis was carried out at two sample bus stops (6th bus stop, a residential area and 10th bus stop, an industrial area) to check the variation of the same and is presented in Fig. 3c, d.

From these figures, it can be observed that the waiting times are more (still within the limit of anticipated headway) during the afternoon period when the demand is very low. Also, it can be observed that waiting times are minimized in the morning and evening periods when there is high demand.

Finally, a comparison of passenger waiting times was made with the fixed schedule (with constant dispatch headway of 30 min) that the service provider is already following [15] and is shown in Fig. 4. From Fig. 4, it can be observed that the waiting times are minimized in the peak passenger demand periods, i.e. in the morning and evening. Also, it can be observed that the average passenger waiting times are reduced up to 10 min per passenger in the proposed strategy compared to the fixed schedule strategy. As expected, waiting times are relatively higher during off-peak periods, i.e. afternoon and early morning. These higher delays might have been due to lower demand in the off-peak period.

Fig. 4
figure 4

Comparison of passenger waiting time variation between the proposed strategy and fixed schedule strategy

Full size image

4.2 Percentage of Bus Capacity Utilization

The percentage of bus capacity utilization is the ratio between the total number of passengers travelling on the bus to the total capacity of the bus. The passenger count values were continually stored and these were used to compute the percentage of bus capacity utilized. Here, higher percentage values indicate a higher efficiency of the service and this information can be used to avoid lower efficiency trips in order to make the service economical for operators. Figure 5 shows the variation in the percentage of bus capacity utilization at different time periods of the day.

Fig. 5
figure 5

Evaluation of the proposed methodology w.r.t. percentage utilization of bus capacity

Full size image

From Fig. 5, it can be observed that a trip that started around 12 PM which is an off-peak period had a utilization of 65%, and a trip that started around 9 AM, which is a peak period, reached 100% capacity at the 7th bus stop, which is in accordance with the expectation.

In the next level, average utilization of bus capacity across all bus stops was studied over time within a day and compared with the fixed scheduling strategy as shown in Fig. 6. From Fig. 6, it can be observed that the fixed schedule has an average percentage utilization of only 10% for early morning and morning off-peak time trips, which makes the service less economical for the operators. On the other hand, the proposed strategy shows a percentage utilization of 40% in those periods, benefitting the operator. On an average, it can be observed that percentage utilization obtained using the proposed strategy is 8% better than the fixed schedule strategy. In addition, it can be observed that the proposed strategy also serves more passengers compared to the fixed schedule strategy.

Fig. 6
figure 6

Comparison of percentage utilization between the proposed strategy and fixed schedule strategy

Full size image

5 Summary and Conclusions

One of the most important factors for a bus service to be successful is its service efficiency. A real-time schedule which adapts to the current passenger demand and traffic conditions will help in ensuring an efficient service to the commuters and also maximizing the profit for operators. The current study developed such a solution and demonstrated it for route number 19B, which connects Saidapet and Kelambakkam in the city of Chennai, India. A demand and travel time responsive scheduling model was developed taking into account the constraints due to bus capacity and number of available buses, and ensuring that the service does not exceed the maximum anticipated headway. The main highlights of the study are

  • A sample scheduling methodology was developed and evaluated considering passenger waiting time and percentage utilization of capacity as performance measures.

  • The proposed dynamic scheduling methodology performed better in terms of passenger waiting times and percentage utilization of capacity.

  • The waiting times were reduced by 10 min per passenger and were bounded by the maximum anticipated headways at different stops over various time periods of the day.

  • The percentage of bus capacity utilized was observed to be higher in peak periods when compared to off-peak periods and the percentage utilization of bus capacity was increased by 8% on an average throughout the day.

  • Since the fixed schedule strategy did not involve any measures to handle the real-time demands, often passengers resort to other modes of transport to avoid the long waiting times. The proposed strategy dispatches buses to serve extra demands immediately and hence serves more passengers.

Though the scheduling model requires real field data about passenger alighting and boarding rates at each bus stop, data were assumed suitably for testing purposes. This aspect of passenger count can be addressed using the latest automatic passenger counters or ticketing machines. In case of a single route with fixed fleet (as considered in this study), the proposed method can be improved by estimating accurate travel demand and arrival times for all bus stops along the given route. At a system level, the proposed method can be improved by preparing a dynamic schedule for multiple routes considering the vehicles from multiple depots to achieve the maximum utilization of capacity, thereby maximizing the operator’s profits and passenger’s satisfaction.