A post-improvement procedure for the mixed
load school bus routing problem
Junhyuk Park(a),
Hyunchul Tae(b), Byung-In Kim(b)
(a) Institute of
Information Technology, Inc., Magnolia, TX 77354, USA
(b) Department of Industrial
and Management Engineering, Pohang University of Science and Technology
(POSTECH), Pohang, Kyungbuk 790-784, Republic of Korea
Full paper: European Journal of Operational Research 217 (2012), 204–213
Note: A set of benchmark instances (with
solutions) is available (here)
A set of real world instances (with
solutions) is available (here)
* notice: the data sets were updated on Aug
10, 2012
1. Introduction
The school bus
routing problem (SBRP) seeks to find optimal routes for a fleet of vehicles
where each vehicle transportsstudents between their homes and schools while satisfying
various constraints. Each bus must pick up students from their home (or bus
stop) and transfer them to their schools while satisfying various
constraints such as vehicle capacity, student¡¯s maximum allowable riding time
in a bus and the time windows of the schools. In this document, we present a
set of benchmark problem instances. Note that there are no known benchmark
problem sets for the SBRP up to the present.
We say ¡°mixed
load is allowed¡± if students from different schools can be put on the
same bus at the same time. When mixed load is not allowed, the problem is
called the single load problem. Most studies on the SBRP do not
allow mixed load. Although several papers briefly considered the problem
of mixed load, only Braca et al. (1997) actually developed an algorithm
for the mixed load. They modified the Location Based Heuristic
of Bramel and Simchi-Levi (1995) which uses a simple insertion
rule. Their algorithm sequentially constructs routes one by one by
iteratively inserting minimum cost stops and their corresponding schools to a
route until no more stop can be inserted. Although their algorithm can
generate a set of routes which allows mixed load but the effects of allowing
mixed load were not measured in their research.
While Braca et
al. (1997) considered mixed load in their route construction procedure, our
approach considers mixed load in a post improvement procedure. First, we
generate a set of routes without consideration of mixed load, which we call a
single load plan. The word ¡®single load¡¯ is used as an antonym of ¡®mixed load¡¯.
Note that any algorithms that generate a single load plan can be used in our
approach. In the next step, the mixed load improvement algorithm is applied to
the single load plan to convert it to a mixed load plan using a simple
relocation operator.
2. Problem Description
Let V be
a vertex set consisting of a set of schools S, a set of bus
stops B, and a set of depots D. Each vertex has its
position (xi, yi) in the
two-dimensional space. Let G = (V, A) be a
directed graph where V = {vi: vi ¡ô S ¡ú B ¡ú D} is the vertex
set and A = {(vi, vj): vi, vj ¡ô V, i ¡Á j} is
the arc set having cost cij associated with arc (vi, vj).
In our benchmark instances we set cij to
the rectilinear distance between vi and vj,
i.e., cij = |xi – xj|
+ |yi – yj|. In real world
cases, cij can be calculated using a geographic
information system. We assume that each bus k (k ¡ô K) has the same capacity Q.
Each bus stop has
service time ti and its designated school. We
set ti (in seconds) using following regression
model, which is developed by Braca et al. (1997), for the
benchmark instances:
ti = 19.0 + 2.6ni
where ni is
the number of students at bus stop i. We also use the following
regression model to set the time to drop off students at their school:
DT = 29.0 + 1.9N
where DT is the drop-off
time at the school, and N is the number of students to be
dropped at that school. The times are given by different formula in the
real world SBRPs.
Each school s ¡ô S has earliest and latest possible
arrival time es and ls and
the students attending school s should arrive attheir
school between es and ls.
The student¡¯s maximum allowable riding time in a bus is given by L. A
bus can visit several schools but each stop should be visited by a single bus. The SBRP aims to find a set of feasible
routes with minimum number of vehicles and minimum total travel distance.
3. Benchmark Problem
Since there are no
publicly available benchmark problems of the SBRP, we generated benchmark problem sets. We
referred to various real world instances and the literature and made 48 test
instances. These instances have different numbers of students, bus stops, and
schools.
By referring to
the real world instances, we found that the schools and bus stops tend
to be clustered in specific regions. Therefore, we decided to
classify benchmark instances into two types depending on scattering of
schools and bus stops. We assumed that schools and bus stops could be either
dispersed randomly in a region or gathered into several
clusters. R and C stand for random and
clustered dispersion, respectively. We also use abbreviations S and B for
schools and bus stops. For example, instances of type RSRB have
randomly distributed schools and bus stops while instances of type CSCB have
schools and bus stops which are gathered together in several clusters (see
Figure 1). In this paper, we consider instances of type RSRB and CSCB.
Figure 1. A schematic view of
type RSRB (left) and CSCB (right)
The number
of schools and bus stops were selected among {6, 12, 25, 50, 100} and {250,
500, 1000, 2000}, respectively.Schools and bus stops are located in the
two-dimensional plane and each coordinate is within [0, 211200]. A school
district is assumed to have a region of 20 mile by 20 mile rectangle. Note that
211200 feet corresponds to 40 mile. Time windows at the schools were
randomly generated in a range [7:00, 11:00] and the length of time window was
randomly chosen between 10 and 30 minutes. The maximum allowable riding time of
a student in a bus is set to 2700 seconds (45 minutes) or 5400 seconds (75
minutes). The capacity of vehicle is set to 66 and its average speed is 20 mile
per hour. Since we set the average speed of a vehicle to 20 mile per hour, a
student should live within 15 miles (or 25 miles) from his/her school to
satisfy the maximum allowable riding time constraint. And we assumed that there
exists a single depot which is located in the center of the coordinate range.
4. Results (Updated on Aug 10, 2012)
4.3. Results for
the Benchmark Instances
(section 4.3. in
EJOR paper should be updated with this)
Table 1 shows the
computational results for 16 benchmark instances of type RSRB. As described
above, these instances have randomly distributed schools and bus stops, where m
and n denote the number of schools and bus stops. The maximum riding time is
set to either 2700 or 5400 seconds. Note that the first 8 instances and the
next 8 instances have the same geographical information, and the only
difference is the maximum riding time in a bus. The lower bound for v*m-TSPTW
is also presented as a lower bound of v*SBRP-ML in the table. ZSingle,
ZMixed, and ZBraca denote the number of required vehicles
by the single load plan, our proposed mixed load plan, and Braca¡¯s algorithm,
respectively. TSingle, TMixed, and TBraca are
CPU times measured on a Pentium IV 3.0GHz with 1GB RAM PC using a computer
program written in the C++ language. The gap1 column shows the percentage
difference between ZMixed and ZSingle, which is computed
as (ZSingle - ZMixed)/ZSingle. Similarly, the
gap2 column is computed as (ZBraca - ZMixed)/ZBraca.
The result shows that our mixed load algorithm outperforms the others for all
16 instances. On average, our mixed load algorithm requires 16.0% and 20.3%
fewer vehicles than the single load plan and Braca¡¯s algorithm, respectively.
Note that even a single load plan gives better results than Braca¡¯s algorithm
for 10 instances out of 16.
Tables 2 and 3
summarize the computational results for the benchmark instances of types
CSCB(m/4, m/2) and CSCB(m/2, m), respectively. For both types, our mixed load
improvement algorithm always outperforms Braca¡¯s algorithm. The average
deviations of ZMixed over ZSingle and ZBraca
are 16.5% and 22.0% for instances of type CSCB(m/4, m/2). Even a single load
plan gives better results than Braca¡¯s algorithm for 11 instances of type
CSCB(m/4, m/2). For instances of type CSCB(m/2, m), the average deviations of ZMixed
over ZSingle and ZBraca are 16.5% and 18.6%. The single
load plan requires fewer vehicles than Braca¡¯s algorithm for 9 instances of
type CSCB(m/2, m).
Results presented
in Tables 1-3 indicate that our mixed load algorithm can reduce the number of
required buses compared with Braca¡¯s algorithm. The overall average reduction
is 19.9%. Compared with the single load plan, our mixed load algorithm can save
3% ~ 31.4% of buses and on average 16.3%. The average deviation is larger for
clustered cases. This is because students for different schools can be picked
up more easily as they live close to each other. The deviation tends to increase
when the maximum riding time in a bus is longer. The reason is that the longer
maximum riding time gives more flexibility for improvement. In addition, our
algorithm performs well on large instances with 2000 bus stops as well as
small-sized instances. We conclude that our algorithm is more efficient than
Braca¡¯s algorithm with regard to the solution quality as well as the
computational time.
The quality of the
lower bound for v*m-TSPTW is poor. The difference between the lower bound and ZMixed
is large. However, the time complexity of the procedure is polynomial and
gives bounds for the largest problem in minutes. Note that even the linear
relaxation of the original mathematical formulation takes much more time than
this procedure while giving a looser lower bound.
As shown above,
Braca¡¯s algorithm performs worse than our mixed load improvement algorithm. Its
poor performance is mainly due to its greedy nature. In Braca¡¯s algorithm, bus
stops located close each other have a higher chance to be inserted to routes,
whereas remote stops may be difficult to be added to routes. Therefore, at the
late stage of the algorithm, the stops that tend to be distant to each other
are left, and thus the routes generated in the late stage usually include only
1 or 2 stops per route. As a result, Braca¡¯s algorithm generates an
ill-balanced set of routes and uses an excessive number of vehicles. Figure 9
shows the number of stops visited by each vehicle for the instance CSCB08 with
a maximum riding time 5400 seconds. As shown in the figure, the routes
generated in the early stage of Braca¡¯s algorithm tend to visit more bus stops
than those generated in the late stage. Unlike in our algorithm, there is a
strong tendency that the number of visited stops decreases as the algorithm
proceeds. In addition, the average number of visited stops is only 10.8 in
Braca¡¯s algorithm, whereas the vehicles in our algorithm visit 19.2 stops on
average.
4.4. Results for
the Real World Instances
We also applied
our algorithm to 7 real world instances collected from some school districts in
the US. These real world instances have different sizes in the range of
200–2000 bus stops and from 5–90 schools. They are more complex than artificial
benchmark instances in many aspects, such as consideration of heterogeneous
fleet, multiple depots, and different maximum riding time over schools. In the
real world instances, the service time at each stop is given. For the drop-off
time at schools, the formulation in Section 4.1 is used. The travel time between
two locations is calculated using the rectilinear distance and the speed given
in the last column of Table 4.. We also assume that each school has its
collapse code. Schools having the same collapse code are merged into a single
school if their time windows overlap each other.
Table 4 summarizes
the computational results for the real world instances. Current, Single, and
Mixed represent the number of required vehicles in current practice, single
load plan and mixed load plan. Compared with the number of buses currently in
use, our mixed load algorithm can reduce 20.9% of buses. The average percent
difference between the single load plans and mixed load plans are 19.8%.
Table 1. Computational results for the instances of
type RSRB
|
Instance |
Max. Ride. Time |
#.school (m) |
#.stops (n) |
#. Students |
Lower Bound |
#. Required Vehicles |
CPU Time (Seconds) |
||||||
|
ZMixed |
ZSingle |
gap1 |
ZBraca |
gap2 |
TMixed |
TSingle |
TBraca |
||||||
|
RSRB01 |
2700 |
6 |
250 |
3409 |
4 |
30 |
35 |
14.3% |
36 |
16.7% |
0.9 |
0.6 |
26.6 |
|
RSRB02 |
2700 |
12 |
250 |
3670 |
8 |
29 |
32 |
9.4% |
34 |
14.7% |
0.9 |
0.5 |
32.2 |
|
RSRB03 |
2700 |
12 |
500 |
6794 |
8 |
56 |
66 |
15.2% |
77 |
27.3% |
3.2 |
0.8 |
123.8 |
|
RSRB04 |
2700 |
25 |
500 |
6805 |
18 |
59 |
68 |
13.2% |
78 |
24.4% |
2.2 |
1 |
121.1 |
|
RSRB05 |
2700 |
25 |
1000 |
13765 |
17 |
98 |
124 |
21.0% |
118 |
16.9% |
5 |
1.6 |
574.7 |
|
RSRB06 |
2700 |
50 |
1000 |
12201 |
36 |
89 |
103 |
13.6% |
106 |
16.0% |
5.8 |
1.7 |
695.5 |
|
RSRB07 |
2700 |
50 |
2000 |
26912 |
55 |
154 |
185 |
16.8% |
201 |
23.4% |
40.7 |
2.6 |
3296.1 |
|
RSRB08 |
2700 |
100 |
2000 |
31939 |
93 |
157 |
178 |
11.8% |
212 |
25.9% |
18.2 |
3.1 |
3455.6 |
|
RSRB01 |
5400 |
6 |
250 |
3409 |
6 |
27 |
31 |
12.9% |
31 |
12.9% |
0.9 |
0.5 |
46.2 |
|
RSRB02 |
5400 |
12 |
250 |
3670 |
5 |
23 |
30 |
23.3% |
29 |
20.7% |
0.7 |
0.5 |
43.3 |
|
RSRB03 |
5400 |
12 |
500 |
6794 |
12 |
47 |
61 |
23.0% |
61 |
23.0% |
3.4 |
0.8 |
166.8 |
|
RSRB04 |
5400 |
25 |
500 |
6805 |
20 |
46 |
56 |
17.9% |
60 |
23.3% |
2.1 |
0.9 |
183.7 |
|
RSRB05 |
5400 |
25 |
1000 |
13765 |
22 |
79 |
106 |
25.5% |
86 |
8.1% |
5.6 |
1.5 |
866.9 |
|
RSRB06 |
5400 |
50 |
1000 |
12201 |
44 |
72 |
82 |
12.2% |
81 |
11.1% |
5.8 |
1.6 |
760.8 |
|
RSRB07 |
5400 |
50 |
2000 |
26912 |
44 |
134 |
159 |
15.7% |
163 |
17.8% |
43.1 |
2.4 |
4422.7 |
|
RSRB08 |
5400 |
100 |
2000 |
31939 |
83 |
142 |
158 |
10.1% |
186 |
23.7% |
26.4 |
2.9 |
5728.4 |
|
Average |
4050.0 |
35.0 |
937.5 |
13186.9 |
29.7 |
77.6 |
92.1 |
16.0% |
97.4 |
20.3% |
10.3 |
1.4 |
1284 |
Table 2. Computational results for the instances of
type CSCB(m/4, m/2)
|
Instance |
Max. Ride. Time |
#.school (m) |
#.stops (n) |
#. Students |
Lower Bound |
#. Required Vehicles |
CPU Time (Seconds) |
||||||
|
ZMixed |
ZSingle |
gap1 |
ZBraca |
gap2 |
TMixed |
TSingle |
TBraca |
||||||
|
CSCB01 |
2700 |
6 |
250 |
3907 |
3 |
30 |
39 |
23.1% |
39 |
23.1% |
1 |
0.5 |
26.9 |
|
CSCB02 |
2700 |
12 |
250 |
3204 |
7 |
30 |
33 |
9.1% |
38 |
21.1% |
0.9 |
0.5 |
31.1 |
|
CSCB03 |
2700 |
12 |
500 |
6813 |
11 |
55 |
66 |
16.7% |
69 |
20.3% |
4.4 |
0.8 |
154.3 |
|
CSCB04 |
2700 |
25 |
500 |
7541 |
15 |
62 |
72 |
13.9% |
84 |
26.2% |
1.7 |
1 |
109 |
|
CSCB05 |
2700 |
25 |
1000 |
16996 |
30 |
116 |
135 |
14.1% |
157 |
26.1% |
10.6 |
1.8 |
560.8 |
|
CSCB06 |
2700 |
50 |
1000 |
18232 |
50 |
120 |
138 |
13.0% |
138 |
13.0% |
10.4 |
2 |
627.8 |
|
CSCB07 |
2700 |
50 |
2000 |
27594 |
59 |
175 |
201 |
12.9% |
229 |
23.6% |
12 |
2.9 |
4773.3 |
|
CSCB08 |
2700 |
100 |
2000 |
27945 |
100 |
175 |
183 |
4.4% |
226 |
22.6% |
24.1 |
3.4 |
6125.7 |
|
CSCB01 |
5400 |
6 |
250 |
3907 |
7 |
24 |
35 |
31.4% |
33 |
27.3% |
1.1 |
0.5 |
77 |
|
CSCB02 |
5400 |
12 |
250 |
3204 |
10 |
22 |
27 |
18.5% |
26 |
15.4% |
0.8 |
0.5 |
82.4 |
|
CSCB03 |
5400 |
12 |
500 |
6813 |
10 |
41 |
52 |
21.2% |
50 |
18.0% |
3.9 |
0.7 |
544.4 |
|
CSCB04 |
5400 |
25 |
500 |
7541 |
20 |
43 |
57 |
24.6% |
67 |
35.8% |
1.7 |
0.9 |
395 |
|
CSCB05 |
5400 |
25 |
1000 |
16996 |
21 |
97 |
115 |
15.7% |
134 |
27.6% |
9.9 |
1.6 |
1269.6 |
|
CSCB06 |
5400 |
50 |
1000 |
18232 |
37 |
102 |
123 |
17.1% |
110 |
7.3% |
13.2 |
1.9 |
1411.6 |
|
CSCB07 |
5400 |
50 |
2000 |
27594 |
38 |
133 |
164 |
18.9% |
179 |
25.7% |
16.7 |
2.6 |
8266.2 |
|
CSCB08 |
5400 |
100 |
2000 |
27945 |
79 |
141 |
156 |
9.6% |
174 |
19.0% |
27.8 |
2.9 |
5943.8 |
|
Average |
4050.0 |
35.0 |
937.5 |
14029.0 |
31.1 |
85.4 |
99.8 |
16.5% |
109.6 |
22.0% |
8.8 |
1.5 |
1899.9 |
Table 3. Computational results for the instances of
type CSCB(m/2, m)
|
Instance |
Max. Ride. Time |
#.school (m) |
#.stops (n) |
#. Students |
Lower Bound |
#. Required Vehicles |
CPU Time (Seconds) |
||||||
|
ZMixed |
ZSingle |
gap1 |
ZBraca |
gap2 |
TMixed |
TSingle |
TBraca |
||||||
|
CSCB09 |
2700 |
6 |
250 |
4148 |
5 |
27 |
32 |
15.6% |
36 |
25.0% |
1 |
0.4 |
69.2 |
|
CSCB10 |
2700 |
12 |
250 |
4217 |
10 |
32 |
33 |
3.0% |
39 |
17.9% |
1 |
0.6 |
22.9 |
|
CSCB11 |
2700 |
12 |
500 |
5996 |
9 |
51 |
58 |
12.1% |
68 |
25.0% |
2.1 |
0.7 |
97 |
|
CSCB12 |
2700 |
25 |
500 |
6098 |
34 |
68 |
77 |
11.7% |
79 |
13.9% |
1.7 |
1 |
133.3 |
|
CSCB13 |
2700 |
25 |
1000 |
14163 |
37 |
130 |
165 |
21.2% |
158 |
17.7% |
6.1 |
2 |
471.9 |
|
CSCB14 |
2700 |
50 |
1000 |
16294 |
51 |
113 |
137 |
18.4% |
133 |
16.5% |
5.1 |
2.1 |
695.9 |
|
CSCB15 |
2700 |
50 |
2000 |
27428 |
64 |
200 |
247 |
19.0% |
253 |
20.9% |
14.9 |
3.3 |
3223 |
|
CSCB16 |
2700 |
100 |
2000 |
24051 |
98 |
184 |
208 |
11.5% |
213 |
13.6% |
37.8 |
3.6 |
3049.3 |
|
CSCB09 |
5400 |
6 |
250 |
4148 |
5 |
23 |
26 |
11.5% |
30 |
23.3% |
0.9 |
0.4 |
61.2 |
|
CSCB10 |
5400 |
12 |
250 |
4217 |
7 |
25 |
30 |
16.7% |
32 |
21.9% |
0.7 |
0.5 |
36 |
|
CSCB11 |
5400 |
12 |
500 |
5996 |
10 |
39 |
50 |
22.0% |
50 |
22.0% |
2.2 |
0.7 |
288.8 |
|
CSCB12 |
5400 |
25 |
500 |
6098 |
21 |
46 |
55 |
16.4% |
57 |
19.3% |
1.5 |
0.9 |
169.8 |
|
CSCB13 |
5400 |
25 |
1000 |
14163 |
24 |
102 |
135 |
24.4% |
124 |
17.7% |
6.3 |
1.7 |
890.3 |
|
CSCB14 |
5400 |
50 |
1000 |
16294 |
37 |
89 |
117 |
23.9% |
109 |
18.3% |
5.8 |
1.9 |
1291.6 |
|
CSCB15 |
5400 |
50 |
2000 |
27428 |
43 |
166 |
215 |
22.8% |
199 |
16.6% |
18.2 |
2.8 |
4095.3 |
|
CSCB16 |
5400 |
100 |
2000 |
24051 |
83 |
137 |
158 |
13.3% |
148 |
7.4% |
32 |
2.9 |
5659.1 |
|
Average |
4050.0 |
35.0 |
937.5 |
12799.4 |
33.6 |
89.5 |
108.9 |
16.5% |
108.0 |
18.6% |
8.6 |
1.6 |
1265.9 |
Table 4. Computational results
for the real world instances
|
SITE |
#. Required Vehicle |
Current - Mixed |
(Current
– Mixed) /Current (%) |
Single- Mixed |
(Single
– Mixed) /Single (%) |
Speed (MPH) |
||
|
Current |
Single |
Mixed |
||||||
|
SITE1 |
104 |
111 |
79 |
25 |
24.0% |
32 |
28.8% |
20 |
|
SITE2 |
15 |
14 |
13 |
2 |
13.3% |
1 |
7.1% |
16 |
|
SITE3 |
17 |
12 |
10 |
7 |
41.2% |
2 |
16.7% |
20 |
|
SITE4 |
70 |
82 |
50 |
20 |
28.6% |
32 |
39.0% |
21 |
|
SITE5 |
37 |
40 |
33 |
4 |
10.8% |
7 |
17.5% |
26 |
|
SITE6 |
87 |
81 |
69 |
18 |
20.7% |
12 |
14.8% |
26 |
|
SITE7 |
68 |
74 |
63 |
5 |
7.4% |
11 |
14.9% |
20 |
|
Average |
56.9 |
59.1 |
45.3 |
11.6 |
20.9% |
13.9 |
19.8% |
21.3 |
4. Results (Originally Reported in EJOR: Should be
replaced with above)
4.3. Results for
the Benchmark Instances
Table 1 shows the
computational results for 16 benchmark instances of type RSRB. As described
above, these instances have randomly distributed schools and bus stops, where m
and n denote the number of schools and bus stops. The maximum riding time is
set to either 2700 or 5400 seconds. Note that the first 8 instances and the
next 8 instances have the same geographical information, and the only
difference is the maximum riding time in a bus. The lower bound for v*m-TSPTW
is also presented as a lower bound of v*SBRP-ML in the table. ZSingle,
ZMixed, and ZBraca denote the number of required vehicles
by the single load plan, our proposed mixed load plan, and Braca¡¯s algorithm,
respectively. TSingle, TMixed, and TBraca are
CPU times measured on a Pentium IV 3.0GHz with 1GB RAM PC using a computer
program written in the C++ language. The gap1 column shows the percentage
difference between ZMixed and ZSingle, which is computed
as (ZSingle - ZMixed)/ZSingle. Similarly, the
gap2 column is computed as (ZBraca - ZMixed)/ZBraca.
The result shows that our mixed load algorithm outperforms the others for all
16 instances. On average, our mixed load algorithm requires 10.0% and 13.2%
fewer vehicles than the single load plan and Braca¡¯s algorithm, respectively.
Note that even a single load plan gives better results than Braca¡¯s algorithm
for 10 instances out of 16.
Tables 2 and 3
summarize the computational results for the benchmark instances of types
CSCB(m/4, m/2) and CSCB(m/2, m), respectively. For both types, our mixed load
improvement algorithm always outperforms Braca¡¯s algorithm. The average
deviations of ZMixed over ZSingle and ZBraca
are 12.8% and 18.7% for instances of type CSCB(m/4, m/2). Even a single load
plan gives better results than Braca¡¯s algorithm for 11 instances of type
CSCB(m/4, m/2). For instances of type CSCB(m/2, m), the average deviations of ZMixed
over ZSingle and ZBraca are 14.7% and 17.0%. The single
load plan requires fewer vehicles than Braca¡¯s algorithm for 9 instances of
type CSCB(m/2, m).
Results presented
in Tables 1-3 indicate that our mixed load algorithm can reduce the number of
required buses compared with Braca¡¯s algorithm. The overall average reduction
is 17.1%. Compared with the single load plan, our mixed load algorithm can save
3% ~ 38% of buses and on average 13.1%. The average deviation is larger for
clustered cases. This is because students for different schools can be picked
up more easily as they live close to each other. The deviation tends to
increase when the maximum riding time in a bus is longer. The reason is that
the longer maximum riding time gives more flexibility for improvement. In
addition, our algorithm performs well on large instances with 2000 bus stops as
well as small-sized instances. We conclude that our algorithm is more efficient
than Braca¡¯s algorithm with regard to the solution quality as well as the
computational time.
The quality of the
lower bound for v*m-TSPTW is poor. The difference between the lower bound and ZMixed
is large. However, the time complexity of the procedure is polynomial and gives
bounds for the largest problem in minutes. Note that even the linear relaxation
of the original mathematical formulation takes much more time than this
procedure while giving a looser lower bound.
As shown above,
Braca¡¯s algorithm performs worse than our mixed load improvement algorithm. Its
poor performance is mainly due to its greedy nature. In Braca¡¯s algorithm, bus
stops located close each other have a higher chance to be inserted to routes,
whereas remote stops may be difficult to be added to routes. Therefore, at the
late stage of the algorithm, the stops that tend to be distant to each other
are left, and thus the routes generated in the late stage usually include only
1 or 2 stops per route. As a result, Braca¡¯s algorithm generates an
ill-balanced set of routes and uses an excessive number of vehicles. Figure 9
shows the number of stops visited by each vehicle for the instance CSCB08 with
a maximum riding time 5400 seconds. As shown in the figure, the routes generated
in the early stage of Braca¡¯s algorithm tend to visit more bus stops than those
generated in the late stage. Unlike in our algorithm, there is a strong
tendency that the number of visited stops decreases as the algorithm proceeds.
In addition, the average number of visited stops is only 10.8 in Braca¡¯s
algorithm, whereas the vehicles in our algorithm visit 19.2 stops on average.
4.4. Results for
the Real World Instances
We also applied
our algorithm to 7 real world instances collected from some school districts in
the US. These real world instances have different sizes in the range of
200–2000 bus stops and from 5–90 schools. They are more complex than artificial
benchmark instances in many aspects, such as consideration of heterogeneous
fleet, multiple depots, and different maximum riding time over schools. Table 4
summarizes the computational results for the real world instances. Current,
Single, and Mixed represent the number of required vehicles in current
practice, single load plan and mixed load plan. Note that unlike the previous
results that were obtained using the rectilinear distance and the default
vehicle speed, the results of Table 4 were obtained using the real
origin-destination (OD) matrix calculated on a geographic information system. Compared
with the number of buses currently in use, our mixed load algorithm can reduce
22.0% of buses. The average percent difference between the single load plans
and mixed load plans are 20.8%.
Table 1. Computational results for
the instances of type RSRB
Instance |
Max. Ride. Time |
#.school (m) |
#.stops (n) |
#. Students |
Lower Bound |
#. Required Vehicles |
CPU Time (Seconds) |
||||||
|
ZMixed |
ZSingle |
gap1 |
ZBraca |
gap2 |
TMixed |
TSingle |
TBraca |
||||||
|
RSRB01 |
2700 |
6 |
250 |
3409 |
4 |
32 |
35 |
9% |
36 |
11% |
11.0 |
3.5 |
26.6 |
|
RSRB02 |
2700 |
12 |
250 |
3671 |
8 |
27 |
32 |
16% |
34 |
21% |
10.1 |
3.5 |
32.2 |
|
RSRB03 |
2700 |
12 |
500 |
6844 |
8 |
58 |
69 |
16% |
77 |
25% |
27.4 |
6.5 |
123.8 |
|
RSRB04 |
2700 |
25 |
500 |
6867 |
18 |
65 |
76 |
14% |
78 |
17% |
32.5 |
9.2 |
121.1 |
|
RSRB05 |
2700 |
25 |
1000 |
13765 |
17 |
90 |
124 |
27% |
118 |
24% |
93.2 |
12.0 |
574.7 |
|
RSRB06 |
2700 |
50 |
1000 |
12201 |
36 |
82 |
103 |
20% |
106 |
23% |
67.4 |
10.5 |
695.5 |
|
RSRB07 |
2700 |
50 |
2000 |
26934 |
55 |
139 |
198 |
30% |
201 |
31% |
292.6 |
20.7 |
3296.1 |
|
RSRB08 |
2700 |
100 |
2000 |
32048 |
93 |
143 |
201 |
29% |
212 |
33% |
362.8 |
43.3 |
3455.6 |
|
RSRB01 |
5400 |
6 |
250 |
3409 |
6 |
27 |
31 |
13% |
31 |
13% |
7.9 |
2.4 |
46.2 |
|
RSRB02 |
5400 |
12 |
250 |
3671 |
5 |
27 |
30 |
10% |
29 |
7% |
8.8 |
2.7 |
43.3 |
|
RSRB03 |
5400 |
12 |
500 |
6844 |
12 |
47 |
60 |
22% |
61 |
23% |
25.1 |
5.3 |
166.8 |
|
RSRB04 |
5400 |
25 |
500 |
6867 |
20 |
42 |
59 |
29% |
60 |
30% |
26.9 |
5.5 |
183.7 |
|
RSRB05 |
5400 |
25 |
1000 |
13765 |
22 |
73 |
106 |
31% |
86 |
15% |
77.9 |
9.6 |
866.9 |
|
RSRB06 |
5400 |
50 |
1000 |
12201 |
44 |
54 |
85 |
36% |
81 |
33% |
78.3 |
9.8 |
760.8 |
|
RSRB07 |
5400 |
50 |
2000 |
26934 |
44 |
119 |
171 |
30% |
163 |
27% |
259.1 |
16.9 |
4422.7 |
|
RSRB08 |
5400 |
100 |
2000 |
32048 |
83 |
114 |
186 |
39% |
186 |
39% |
317.9 |
25.0 |
5728.4 |
|
Average |
4050.0 |
35.0 |
937.5 |
13217.4 |
29.7 |
71.2 |
97.9 |
23.2% |
97.4 |
23.3% |
106.2 |
11.7 |
1284.0 |
Table 2. Computational
results for the instances of type CSCB(m/4, m/2)
|
Instance |
Max. Ride. Time |
#.school (m) |
#.stops (n) |
#. Students |
Lower Bound |
#. Required Vehicles |
CPU Time (Seconds) |
||||||
|
ZMixed |
ZSingle |
gap1 |
ZBraca |
gap2 |
TMixed |
TSingle |
TBraca |
||||||
|
CSCB01 |
2700 |
6 |
250 |
3932 |
3 |
29 |
40 |
28% |
39 |
26% |
10.7 |
3.3 |
26.9 |
|
CSCB02 |
2700 |
12 |
250 |
3208 |
7 |
24 |
32 |
25% |
38 |
37% |
9.3 |
3.0 |
31.1 |
|
CSCB03 |
2700 |
12 |
500 |
6861 |
11 |
54 |
67 |
19% |
69 |
22% |
21.4 |
5.4 |
154.3 |
|
CSCB04 |
2700 |
25 |
500 |
7605 |
15 |
51 |
81 |
37% |
84 |
39% |
41.3 |
7.1 |
109.0 |
|
CSCB05 |
2700 |
25 |
1000 |
17161 |
30 |
105 |
158 |
34% |
157 |
33% |
130.9 |
13.1 |
560.8 |
|
CSCB06 |
2700 |
50 |
1000 |
18232 |
50 |
94 |
139 |
32% |
138 |
32% |
98.6 |
13.0 |
627.8 |
|
CSCB07 |
2700 |
50 |
2000 |
27755 |
59 |
144 |
245 |
41% |
229 |
37% |
509.8 |
24.9 |
4773.3 |
|
CSCB08 |
2700 |
100 |
2000 |
28005 |
100 |
140 |
200 |
30% |
226 |
38% |
378.8 |
39.3 |
6125.7 |
|
CSCB01 |
5400 |
6 |
250 |
3932 |
7 |
26 |
35 |
26% |
33 |
21% |
10.8 |
3.0 |
77.0 |
|
CSCB02 |
5400 |
12 |
250 |
3208 |
10 |
18 |
26 |
31% |
26 |
31% |
7.1 |
2.7 |
82.4 |
|
CSCB03 |
5400 |
12 |
500 |
6861 |
10 |
45 |
57 |
21% |
50 |
10% |
22.4 |
5.0 |
544.4 |
|
CSCB04 |
5400 |
25 |
500 |
7605 |
20 |
46 |
63 |
27% |
67 |
31% |
29.9 |
6.4 |
395.0 |
|
CSCB05 |
5400 |
25 |
1000 |
17161 |
21 |
96 |
133 |
28% |
134 |
28% |
132.1 |
13.4 |
1269.6 |
|
CSCB06 |
5400 |
50 |
1000 |
18232 |
37 |
91 |
124 |
27% |
110 |
17% |
91.0 |
13.4 |
1411.6 |
|
CSCB07 |
5400 |
50 |
2000 |
27755 |
38 |
119 |
197 |
40% |
179 |
34% |
371.6 |
21.9 |
8266.2 |
|
CSCB08 |
5400 |
100 |
2000 |
28005 |
79 |
104 |
169 |
38% |
174 |
40% |
300.3 |
22.8 |
5943.8 |
|
Average |
4050.0 |
35.0 |
937.5 |
14094.9 |
31.1 |
74.1 |
110.4 |
30.3% |
109.6 |
29.8% |
135.4 |
12.4 |
1899.9 |
Table
3. Computational results for the instances of type CSCB(m/2,
m)
Instance |
Max. Ride. Time |
#.school (m) |
#.stops (n) |
#. Students |
Lower Bound |
#. Required Vehicles |
CPU Time (Seconds) |
||||||
|
ZMixed |
ZSingle |
gap1 |
ZBraca |
gap2 |
TMixed |
TSingle |
TBraca |
||||||
|
CSCB09 |
2700 |
6 |
250 |
4159 |
5 |
27 |
31 |
13% |
36 |
25% |
8.3 |
3.0 |
69.2 |
|
CSCB10 |
2700 |
12 |
250 |
4221 |
10 |
30 |
36 |
17% |
39 |
23% |
8.7 |
3.2 |
22.9 |
|
CSCB11 |
2700 |
12 |
500 |
6006 |
9 |
49 |
65 |
25% |
68 |
28% |
22.2 |
5.6 |
97.0 |
|
CSCB12 |
2700 |
25 |
500 |
6098 |
34 |
56 |
78 |
28% |
79 |
29% |
31.4 |
6.3 |
133.3 |
|
CSCB13 |
2700 |
25 |
1000 |
14242 |
37 |
118 |
165 |
28% |
158 |
25% |
124.6 |
12.3 |
471.9 |
|
CSCB14 |
2700 |
50 |
1000 |
16318 |
51 |
99 |
137 |
28% |
133 |
26% |
100.3 |
14.8 |
695.9 |
|
CSCB15 |
2700 |
50 |
2000 |
27482 |
64 |
157 |
258 |
39% |
253 |
38% |
386.7 |
23.8 |
3223.0 |
|
CSCB16 |
2700 |
100 |
2000 |
24051 |
98 |
155 |
207 |
25% |
213 |
27% |
292.3 |
32.0 |
3049.3 |
|
CSCB09 |
5400 |
6 |
250 |
4159 |
5 |
25 |
29 |
14% |
30 |
17% |
6.1 |
2.8 |
61.2 |
|
CSCB10 |
5400 |
12 |
250 |
4221 |
7 |
25 |
32 |
22% |
32 |
22% |
8.6 |
3.0 |
36.0 |
|
CSCB11 |
5400 |
12 |
500 |
6006 |
10 |
36 |
50 |
28% |
50 |
28% |
24.0 |
4.8 |
288.8 |
|
CSCB12 |
5400 |
25 |
500 |
6098 |
21 |
37 |
55 |
33% |
57 |
35% |
24.6 |
5.5 |
169.8 |
|
CSCB13 |
5400 |
25 |
1000 |
14242 |
24 |
95 |
132 |
28% |
124 |
23% |
124.1 |
11.1 |
890.3 |
|
CSCB14 |
5400 |
50 |
1000 |
16318 |
37 |
79 |
115 |
31% |
109 |
28% |
99.2 |
12.3 |
1291.6 |
|
CSCB15 |
5400 |
50 |
2000 |
27482 |
43 |
145 |
221 |
34% |
199 |
27% |
377.5 |
21.9 |
4095.3 |
|
CSCB16 |
5400 |
100 |
2000 |
24051 |
83 |
103 |
158 |
35% |
148 |
30% |
238.0 |
20.6 |
5659.1 |
|
Average |
4050.0 |
35.0 |
937.5 |
12822.1 |
33.6 |
77.3 |
110.6 |
26.8% |
108.0 |
26.9% |
117.3 |
11.4 |
1265.9 |
Table 4. Computational results for
the real world instances
|
SITE |
#. Required Vehicle |
Current - Single |
(Current – Single) /Current |
Current - Mixed |
(Current – Mixed) /Current |
Rectlinear Distance Results |
||||
|
Current |
Single |
Mixed |
Average Speed |
Single |
Mixed |
|||||
|
SITE1 |
104 |
85 |
64 |
19 |
18.3% |
40 |
38.5% |
20 MPH |
102 |
77 |
|
SITE2 |
15 |
11 |
10 |
4 |
26.7% |
5 |
33.3% |
16 MPH |
14 |
12 |
|
SITE3 |
17 |
10 |
9 |
7 |
41.2% |
8 |
47.1% |
20 MPH |
12 |
10 |
|
SITE4 |
70 |
59 |
38 |
11 |
15.7% |
32 |
45.7% |
21 MPH |
81 |
51 |
|
SITE5 |
37 |
33 |
27 |
4 |
10.8% |
10 |
27.0% |
26 MPH |
40 |
30 |
|
SITE6 |
87 |
78 |
66 |
9 |
10.3% |
21 |
24.1% |
26 MPH |
86 |
70 |
|
SITE7 |
68 |
68 |
58 |
0 |
0.0% |
10 |
14.7% |
20 MPH |
80 |
63 |
|
Average |
56.9 |
49.1 |
38.9 |
7.7 |
17.6% |
18.0 |
32.9% |
21.3 |
59.3 |
44.7 |