A demand-responsive bus system for peak hours with capacitatedvehiclesD. Aktasa,∗ , P. Vansteenwegena , and K. Sörensenb
a<KU Leuven, Institute for Mobility – CIB>, <Leuven>, <Belgium>
dilay.aktas@kuleuven.be, pieter.vansteenwegen@kuleuven.beb<University of Antwerp, ANT/OR - Operations Research Group>, <Antwerp>, <Belgium>
kenneth.sorensen@uantwerpen.be∗
Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on Transportation Analysis
conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

March 31, 2022
Keywords: demand responsive bus services, flexible bus services, mixed integer programming

1

INTRODUCTION

When demand for transportation is much higher in one direction than in the opposite direction, buses areoften overcrowded in one direction and almost empty in the other. This happens mostly because of thelack of flexibility during operations of most traditional bus systems. To provide a better service, many
demand-responsive systems have recently been studied. Vansteenwegen et al. (2022) provide a literature
review on such systems.
To improve the efficiency of service in a corridor with uneven demand, Furth and Day (1985) suggest
applying stop-skipping. The authors provide valuable input on the advantages and disadvantages ofseveral strategies, however, the optimization of the systems are still lacking.
In this study, we focus on a single line where the demand for transportation in one direction during peak
hours is much larger than the demand in the opposite direction and the demand outside peak hours.
This imbalance in the demand is exploited to provide a better service for the larger flows. The system
we propose aims to increase the frequency of a service towards a city center during morning peak hours
compared to a conventional system, by allowing some of the vehicles to perform express services awayfrom the city center. For simplicity, we only consider morning peak hours, but the same system could
also be applied to evening peak hours. As a result, total passenger travel time is decreased and morepassengers are served especially if some vehicle capacities are considered.

2

METHODOLOGY

In a conventional system, a number of vehicles drives back and forth between a terminal and a city
center using regular routes based on a fixed timetable, even when the demand towards the city center ismuch larger than in the other direction. In the system we propose, it is decided beforehand whether abus heading away from the city center, should take the regular route or the express route. Taking theexpress route allows to increase the frequency towards the city center. Since the system no longer has
a fixed headway or a periodic timetable, the departure time of each bus, from the terminal and the city
center, should also be optimized. Figure 1 gives an example of a line, its regular route according to theconventional system and its express route. The express route is determined beforehand based on thelocation of the stops and the road network.

City Center

Terminal

Regular RouteExpress route
Figure 1 – General Representation

TRISTAN XI Symposium

Original abstract submittal

Aktas D., Vansteenwegen P., Sörensen K.

2

The demand-responsive system takes over from the conventional system at the beginning of peak
hours and immediately after peak hours, it returns back to the conventional system. The following two
scenarios are considered for the transition after peak hours:
1. Other vehicles are available in a depot to take over,
2. No other vehicles are available, thus the same vehicles should be available at the locations requiredby the regular timetable at the end of peak hours.
When optimizing this system, a fixed fleet of identical and capacitated vehicles are used, each of which
performing a number of services during peak hours. When peak hours start, the buses that are on theroad according to the conventional system continue their regular service at least until they reach the city
center or the terminal for the first time. Then, a bus is allowed to wait before departing but an express
service can only be performed by following the express route heading away from the city center. All
passenger demand must be served. Based on the expected demand (distributed uniformly) from and toeach stop within and outside peak hours, the objective is to minimize the total (expected) travel time ofpassengers traveling during peak hours measured by the sum of their in-vehicle time and waiting time.
We modeled this problem as a mixed integer quadratic program considering both scenarios for the transition after peak hours, separately. Due to the page limit, we cannot present the complete mathematicalmodels. Instead, we focus on the objective function and the most difficult challenges and different typeof constraints.
In case of constant and equal headways with no variance and uniform arrivals, the expected waiting timeof passengers corresponds to half of the headway (Osuna and Newell, 1972). In our case, as a result of
the service type and dwell time decisions, the headway between any two consecutive services is no longer
constant. Since the headway is no longer constant, the number of passengers arriving at a stop between
two consecutive services is also no longer constant and each has the expected waiting time of half ofthat headway, in case they can all board. This makes the total waiting time a quadratic function of thevariable headway as given in Equation 1 where wj,s,p equals to the headway between the pth and p − 1thbus departing from stop j and serving also stop s, and λj, s equals to the mean demand per min fromstop j to stop s during peak hours.
2
X wj,s,p
λj, s
(1)
2
j,s,p
When there is no more room in the bus, some passengers need to be left behind for the next service.
Suppose rpi,j,s,k,p denotes the number of passengers that cannot get on the pth service departing fromstop j to go to stop s by bus i in its k th service. It is assumed that passengers get on the buses in a
first-come, first-served basis. Therefore, for each of these passengers, the expected waiting time increases
by the additional time they need to wait for the next service, i.e., the headway of the next service,
wj,s,p+1 . In order to correctly calculate the total travel time, the total waiting time should include an
additional term where the number of passengers left behind is multiplied by the next duration of headway.
However, this becomes nonlinear and not solvable by our solver. Instead, the additional waiting time forthese passengers is approximated by the normal headway, H, of the conventional system. The additionalterm for the waiting time is given in Equation 2.
X
rpi,j,s,k,p H(2)
i,j,s,k,pSince the system takes over from the conventional system at the beginning of peak hours, there willprobably be passengers already waiting at different stops when the peak hours start. The decisions thatare made on the first services performed during peak hours will therefore affect these passengers as well.
Thus, the total waiting time should include an additional term for the passengers that have arrived attheir origin stops before the peak hours start and served by the first service during peak hours. Suppose
stfj,s equals the departure time of the first service during peak hours departing from stop j and serving
also stop s. Then, the total waiting time for the passengers already waiting at different stops is calculated
as given in Equation 3, where µj,s equals to the mean demand per min from stop j to s outside peak
hours, and tpj,s equals to the time passed until the beginning of peak hours since the last bus departed
from stop j and served also stop s before the peak hours.
X tp2j,s µj,sj,s2

+ tpj,s µj,s stfj,s(3)

Due to the shorter express route on the way back, the number of passengers using an express service
should be identified to reflect their gain in in-vehicle time. Other than these passengers, the in-vehicle
time is the same for the conventional system. This is given below in Equation 4 where π equals the
TRISTAN XI Symposium

Original abstract submittal

Aktas D., Vansteenwegen P., Sörensen K.

3duration of the peak hours, ttj,s and tej,s equal the in-vehicle time from stop j to stop s with regular andexpress route, respectively, wej,s,p equals the headway wj,s,p if it is an express service and 0 otherwise,and ef equals to 1 if the first service away from the city center is an express service and 0 otherwise.
XXX
π λj,s ttj,s −wej,s,p λj,s (ttj,s − tej,s ) +tpj,s µj,s (ttj,s − ef (ttj,s − tej,s ))
(4)
j,s

j,s,p

j,s

Then, the objective is to minimize the total travel time as the sum of total waiting time and total invehicle time given in Equations 1, 2, 3, and 4. Since the order of the buses might change on the way, to beable to find the variable headway between each consecutive service from one stop to another, the service
departure times should be ordered. Suppose sti,j,s,k denotes the service departure time of bus i from stop
j and also serving stop s in its k th service, then oi,j,s,k,p equals to 1 if bus i in its k t h service departs
from stop j as the pt h service serving stop s. Equations 5a, 5b, 5c make sure that qi,j,s,k,p equals tosti,j,s,k,p if oi,j,s,k,p equals to 1 and 0 otherwise. Equation 5d makes sure that only one service departuretime can be considered for the position of being the pth service, and Equation 5e makes sure that eachservice departure time should be assigned to exactly one position p. Then the ordered service departure
times are used to determine the headway between the pth and p − 1th service departing from stop j andserving stop s, wj,s,p in Equation 5f.
qi,j,s,k,p ≤ oi,j,s,k,p M(5a)sti,j,s,k − M (1 − oi,j,s,k,p ) ≤ qi,j,s,k,p(5b)qi,j,s,k,p ≤ sti,j,s,kXoi,j,s,k,p = 1

(5c)
(5d)

p

X

oi,j,s,k,p = 1(5e)qi,j,s,k,p−1 = wj,s,p

(5f)

i,k

X

qi,j,s,k,p −

i,k

X
i,k

In the rest of the model, we have several groups of constraints to make sure that everything works asintended. A group of constraints ensures that the vehicles that are on the road first continue theirservices until they reach the terminal or the city center for the first time. Then, based on the service
type and departure time decisions, the service departure times, sti,j,s,k , are determined for each service.
However, the number of services that will be completed by each bus is unknown and also depends onthese decisions. Thus, we include some constraints that allow us to tackle this issue. We also have thenecessary inventory balance type of constraints to keep track of the number of passengers that can andcannot get on a service due to vehicle capacity. Lastly, and only for scenario 2, the final locations of
the vehicles should correspond to those locations that make it possible to start running the conventional
system again immediately after the peak hours.

3

RESULTS

In order to evaluate the performance of the system, three different lines are considered to design benchmark instances: S (small), M (medium), L (large) lines with 2, 8, and 14 stops and a city center,
respectively. More details can be found in Table 1.
Table 1 – Instance Characteristics

Instance,S
M
L# of Stops
Regular Express
1
1
4
4
7
7

One-way driving time (min)Regular
Express
10
5
20
10
30
15

Peak Hours
π, (mins)
30
40
60

Fleet
Size, m2
2
2

We consider a demand scenario where the mean demand to travel to the city center is 20 times the mean
demand to travel from the city center during peak hours and the mean demand in both directions outside
peak hours. For each line, three different types of vehicles with capacities of 85, 70 and 60 are considered.
The models are solved by the solver CPLEX version 12.7 with GAMS IDE on a computer equipped witha processor AMD Ryzen 7 PRO 2700U w/Radeon Vega Mobile Gfx 2.20 GHz. The optimal solutions
obtained by the mathematical models for Scenario 1 and 2 are reported with the upper-bounds when the
optimal solution is not found within given computational time. Since the objective function used in themodel approximates the waiting time for the passengers that are left behind, the actual total travel timeis also reported. Table 2 below summarizes the results.
TRISTAN XI Symposium

Original abstract submittal

Aktas D., Vansteenwegen P., Sörensen K.

Line
S
S
S
Average
M
M
M
Average
L
L
L
AverageC(people)
85
70
60
85
70
60
85
70
60
-

CS
(min)
3156
3616
4016
3596
3647
3870
4070
3862
5640
6095
6395
6043

NP-CS
(people)
80
70
60
82
70
60
85
70
60
-

DRS-1
(min)
2818
2818
3078
2905
3370
3528
3528
3475
5547
5531
5531
5824

Table 2 – Overall Results
Scenario 1
Imp-1 OBJ-1 CPU-1
NP-1
%
(min)
(s)
(people)
11%
2818
97
66
22%
2818
66
23%
3073
352
60
19%
2903
225
8%
3370
3600
77
9%
3528
3600
59
13%
3528
3600
59
10%
3475
3600
2%
5547
10800
63
9%
5531
10800
59
13%
5531
59
8%
5824
10800
-

4

DRS-2
(min)
3032
3032
3123
3062
3531
3531
3531
3531
5493
5493
6395
5794

Imp-2
%
4%
16%
22%
14%
3%
9%
13%
8%
3%
10%
4%

Scenario 2
OBJ-2 CPU-2
(min)
(s)
3032
85
3032
3117
124
3061
105
3531
3600
3531
3531
3531
3600
5493
10800
5493
6395
5794
10800

NP-2
(people)
66
66
60
59
59
59
63
63
60
-

C: Capacity, CS: Total travel time in conventional system, NP-CS: Maximum number of passengers on bus in CS, DRS1(2): Total travel time of proposed system for scenario 1(2), Imp-1(2): Improvement of DRS-1(2) over CS, OBJ-1(2):Objective function value scenario 1(2), NP-1(2): Maximum number of passengers on bus in DRS-1(2)According to the results given in Table 2, for all instances, the proposed system improves the total
travel time when other vehicles take over the system immediately after peak hours (Scenario 1), comparedto Scenario 2, where the current vehicles are required for the conventional system to take over. This is
obviously expected. For those instances where the bus capacity is set to 85 people, the results of theconventional system in fact correspond to a capacity that is large enough to accommodate all passengers
arriving at a stop. For the other cases where the capacity is smaller, the improvement increases further
since the bus capacity is insufficient for the conventional system. However, in the proposed system,
passengers accumulate less at their origin stops as a result of the higher frequency. It is also observedthat the actual total travel time and the approximated objective function values are very close in all of
the experiments. When the demand-responsive system operates such that no passengers are left behind,both are equal, in the other cases, the difference is rather small. Overall, compared to the conventional
system, the proposed system improves the total passenger travel time about 12% and 9% on averagein case of Scenario 1 and 2, respectively. It should be also noted that passengers traveling towards thecity center and the express stops benefit from the system while the passengers traveling between regularstops have to wait longer. Since those passengers are low in number, the demand-responsive system still
outperforms the conventional system when all the passengers are considered. Due to the computation
time, to benefit more from this system, an algorithm that finds good quality of solutions within reasonable
time is required for large instances.

4

CONCLUSIONSIn this study, we present a new demand-responsive system which can be operated during peak hours
when passenger flows in both directions are very different. We focus on the morning peak hours where
the passenger flows towards a city center are much larger than the flows in the opposite direction. Basedon the expected demand and for a single line, it is decided which services can skip some stops when
departing from the city center. This way, total passenger travel time improves as the frequency of service
towards the city center is increased and more passengers are served despite the vehicle capacities.
The experimental results show that the demand-responsive system potentially improves the total passenger travel time up to 10% for large instances. The results also confirm that the improvement increases
when other vehicles are available at the end of the peak hours (Scenario 1) and when smaller vehicles
are used. In order to be able to benefit from this system to its full extend, an algorithm that finds goodquality of solutions within reasonable time for larger instances is considered as future work.

References
Furth, P. G. and Day, F. B. (1985), ‘Transit routing and scheduling strategies for heavy demand corridors’,Transportation Research Record 1011, 23–26.
Osuna, E. and Newell, G. F. (1972), ‘Control strategies for an idealized public transportation system’, Transportation Science 6(1), 52–72.
Vansteenwegen, P., Melis, L., Aktaş, D., Montenegro, B. D. G., Vieira, F. S. and Sörensen, K. (2022), ‘A survey on
demand-responsive public bus systems’, Transportation Research Part C: Emerging Technologies 137, 103573.

TRISTAN XI Symposium

Original abstract submittal