A school bus scheduling problem

Full paper: B. Kim, J. Park, S. Kim and S. Sahoo, "A school bus scheduling problem,” Working paper

1. Introduction

We consider a school bus scheduling problem in which route segments for each school are given. A route segment consists of a sequence of bus stops and their designated school. Based on the bus stops, the number of students of them, and the school in a route, the route’s required service time is given. Each school has its fixed time window such that all the routes to the school should be completed at the school within the time window. A school bus can serve multiple routes for multiple schools. The school bus scheduling problem of this paper is to make an optimal bus schedule to serve all the given routes with consideration of the school time windows.

Figure 1 shows an example of the school bus scheduling problem. Let r_i be a route segment consisting of a sequence of bus stops and their destination school. Let s_m be a school. In the figure, there are 3, 3, and 4 route segments for school s_a, s_b, and s_c, respectively. Let [s_m_st, s_m_et] be the time window for school m. All the students attending a school should arrive at the school within the bell time window. When two route segments can be served by the same bus without violating the bus capacity constraint and the time window of their designated schools, they can be scheduled to the same bus. Figure 2 shows a solution example of the problem of Figure 1. {r₂, r₆, r₉}, {r₁, r₄, r₈}, {r₃, r₇}, and {r₅, r₁₀} are served by bus 1, 2, 3, and 4, respectively. It is assumed that s_a_et ≤ s_b_st and s_b_et ≤ s_c_st ≤ s_j_st.

Figure 1. An example problem

Figure 2. A solution example

2. Benchmark Problems

Since there are no publicly available benchmark problems for the bus scheduling problem, several problems were generated as benchmark problems and put on http://logistics.postech.ac.kr/Bus_Scheduling_benchmark.html for other researchers. Some summary statistics of the problems are shown in Table 1. The data set consists of 15 homogeneous fleet problems and 15 heterogeneous fleet problems. Each file has Route# number of records and each record has the following attributes:

ID: route segment identity index

start_x, start_y: coordinate of the first stop of the route segment

student_num: number of students that served by the route segment

service_duration: service time of the route segment. It includes students’ pick-up time, traveling time, and unloading time at the destination

school_x, school_y: coordinate of the destination school of the route segment

school_tw_st, school_tw_end: time window of the school. Route segment’s service should be completed within the time window.

Travel time between two locations (stop or school) is assumed to be an integer number that is calculated by Euclidean distance between their coordinates and truncate the fraction.

Each problem also has its corresponding vehicle file that has the Route# number of vehicles. For example, homo_test_file2.txt has its corresponding vehicle file homo_vehicle_file2.txt that has the information of 13 vehicles. All the vehicles are assumed to start from the same location (depot). For homogeneous fleet problems, all the vehicles’ capacity is assumed to be 70. For heterogeneous fleet problems, capacity of each vehicle was randomly chosen from 40, 50, or 70.

Table 1. Experimental benchmark problems

File name	School#	Route#	Student#	Vehicle file	File name	School#	Route#	Student#	Vehicle file
homo_test_file1.txt	1	3	143	homo_vehicle_file1.txt	hetero_test_file1.txt	1	7	335	hetero_vehicle_file1.txt
homo_test_file2.txt	2	13	611	homo_vehicle_file2.txt	hetero_test_file2.txt	2	13	596	hetero_vehicle_file2.txt
homo_test_file3.txt	3	20	975	homo_vehicle_file3.txt	hetero_test_file3.txt	3	21	1012	hetero_vehicle_file3.txt
homo_test_file4.txt	4	23	1154	homo_vehicle_file4.txt	hetero_test_file4.txt	4	24	1199	hetero_vehicle_file4.txt
homo_test_file5.txt	5	29	1448	homo_vehicle_file5.txt	hetero_test_file5.txt	5	32	1610	hetero_vehicle_file5.txt
homo_test_file10.txt	10	49	2405	homo_vehicle_file10.txt	hetero_test_file10.txt	10	58	3002	hetero_vehicle_file10.txt
homo_test_file20.txt	20	106	5097	homo_vehicle_file20.txt	hetero_test_file20.txt	20	120	6012	hetero_vehicle_file20.txt
homo_test_file30.txt	30	161	8155	homo_vehicle_file30.txt	hetero_test_file30.txt	30	187	9415	hetero_vehicle_file30.txt
homo_test_file40.txt	40	234	11528	homo_vehicle_file40.txt	hetero_test_file40.txt	40	239	12136	hetero_vehicle_file40.txt
homo_test_file50.txt	50	309	15238	homo_vehicle_file50.txt	hetero_test_file50.txt	50	286	14352	hetero_vehicle_file50.txt
homo_test_file60.txt	60	372	18551	homo_vehicle_file60.txt	hetero_test_file60.txt	60	345	17350	hetero_vehicle_file60.txt
homo_test_file70.txt	70	430	21554	homo_vehicle_file70.txt	hetero_test_file70.txt	70	408	20723	hetero_vehicle_file70.txt>
homo_test_file80.txt	80	461	23066	homo_vehicle_file80.txt	hetero_test_file80.txt	80	469	23686	hetero_vehicle_file80.txt
homo_test_file90.txt	90	514	25736	homo_vehicle_file90.txt	hetero_test_file90.txt	90	514	25736	hetero_vehicle_file90.txt
homo_test_file100.txt	100	562	28175	homo_vehicle_file100.txt	hetero_test_file100.txt	100	562	28175	hetero_vehicle_file100.txt

You may download the zip file here.