# Shareability Network Based Decomposition Approach for Solving Large-scale
Multi-modal School Bus Routing Problems

Xiaotong Guo<EMAIL_ADDRESS>Samitha Samaranayake<EMAIL_ADDRESS>Department of Civil and Environmental Engineering, Massachusetts Institute of
Technology, Cambridge, MA 02139, USA  School of Civil and Environmental
Engineering, Cornell University, Ithaca, NY 14853, USA

###### Abstract

We consider the classic School Bus Routing Problem (SBRP) with a multi modal
generalization, where students are either picked up by a fleet of school buses
or transported by an alternate transportation mode, subject to a set of
constraints. The constraints that are typically imposed for school buses are a
maximum fleet size, a maximum walking distance to a pickup point and a maximum
commute time for each student. This is a special case of the Vehicle Routing
Problem (VRP) with a common destination. We propose a decomposition approach
for solving this problem based on the existing notion of a shareability
network, which has been used recently in the context of dynamic ridepooling
problems. Moreover, we simplify the problem by introducing the connection
between the SBRP and the weighted set covering problem (WSCP). To scale this
method to large-scale problem instances, we propose i) a node compression
method for the shareability network based decomposition approach, and ii)
heuristic-based edge compression techniques that perform well in practice. We
show that the compressed problem leads to an Integer Linear Programming (ILP)
of reduced dimensionality that can be solved efficiently using off-the-shelf
ILP solvers. Numerical experiments on small-scale, large-scale and benchmark
networks are used to evaluate the performance of our approach and compare it
to existing large-scale SBRP solving techniques.

###### keywords:

School Bus Routing Problem , Shareability Network , Decomposition Approach.

††journal:

##  1 Introduction

According to the American School Bus Council, nearly 480,000 school buses
transported 25 million children to and from school and school-related
activities every school day in 2010 [1]. Meanwhile, based on a recent report
from Nation Center for Education Statistics, 23 billion dollars were spent on
public school transportation during the academic year 2013-2014, which is
nearly 5 percent of the total expenditures for public schools [2]. Every
dollar spent on transporting students is a dollar lost for direct spending to
improve the education of the students. Therefore, the efficient and economical
operation of school bus systems is of significant importance to school
districts that are trying to make the most of their limited education budgets.

The major costs associated with operating a school bus service are the capital
and operational cost of the buses and the wages of the drivers. Thus, an
efficient solution will serve the students by using the fewest buses
possible111minimizing the total distance traveled is a secondary objective..
This needs to be done subject to getting everyone to school on time and not
making some students spend a very long time sitting on a bus (e.g. one hour
maximum in Boston). This leads to the so-called school bus routing problem
(SBRP).

The SBRP is a generalization of the metric Traveling Salesman Problem (TSP)
and a special case of Vehicle Routing Problem (VRP), both of which are NP-hard
problems [3]. While the metric TSP has a number of good approximation
techniques for obtaining provable guarantees on the solution accuracy, the VRP
and SBRP problems are harder to approximate and typically solved using
heuristic techniques. Therefore, the state-of-art methods for solving SBRP can
only solve small-scale problems optimally. To solve the SBRP at scale, the
problem is typically formulated as an Integer Linear Programming (ILP) and
solved using different heuristics techniques [4, 5, 6]. One limitation of
these approaches is that they lead to high dimensional ILP problems that have
a extreme large decision space, and are hard to solve well at-scale even with
very sophisticated heuristic techniques.

This paper proposes a new approach for solving the SBRP using a decomposition
techniques based on the notion of a shareability network[7]. Compared to
classical SBRP approaches, our decomposition leads to a much simpler ILP
problem that can be solved more efficiently at scale. Our approach utilizes
the following steps:

  * 1.

Decoupling the bus routing and student matching problems via the construction
of a shareability network and student-trip assignment graph.

  * 2.

Using a node compression technique for the shareability network by assigning
students to bus stops subject to maximum walking constraints.

  * 3.

Using a set of heuristic-based edge compression techniques for the
shareability network to delete edges and compress the feasible bus routing
set.

Steps described above lead to a much simpler ILP. For extreme large-scale
problems, node and edge compression techniques for the shareability network
can be combined with the traditional large-scale ILP heuristics to obtain
solutions more efficiently (column generation for instance).

Furthermore, our approach also naturally allows for incorporating alternate
transportation modes in the SBRP. For example, we can model allowing some
students to use an dedicated vehicle to travel (transport via contract with
TNC, subsidize students driving etc.), when this leads to a more efficient
school bus schedule and in particular can reduce the number of buses needed.

The contributions of this article can be summarized as follows:

  1. 1.

Modeling the SBRP using the shareability network framework (used in high-
capacity ridepooling), defining the corresponding student-trip graph and
formulating the corresponding ILP problem.

  2. 2.

Connecting SBRP with the weighted set covering problem (WSCP) and simplifying
the ILP for solving the SBRP.

  3. 3.

Showing that techniques used in high-capacity ridepooling with the
shareability network can not be applied to the SBRP directly, due to the
density of the resulting shareability network, and developing network
compression techniques to improve the tractability of the problem.

  4. 4.

Generalizing the standard SBRP to a multi-modal SBRP and showing how our
approach naturally extends to this setting. Showing how the multi-modal
approach can lead to system wide savings.

  5. 5.

Numerical results that validate the performance of our approach in solving
large-scale SBRPs efficiently. Conducting benchmark tests against two
different state-of-the-art approaches for solving SBRPs and showing the
relative performance of our methods.

The remainder of the article is organized as follows. Section 2 reviews the
related literature. Section 3 provides basic definitions for the SBRP and the
generalization to multiple modes. The model formulation for our decomposition
approach via a compressed shareability network is shown in Section 4. Section
5 describes the numerical experiments, benchmark tests and sensitivity
analyses for our approach. Finally, Section 6 recaps the main ideas of this
work and lists future research directions.

##  2 Literature Review

The SBRP has been studied since 1969 when Newton and Thomas first proposed a
method to generate school bus routes and schedules [8]. A comprehensive review
of the SBRP can be found in Park and Kim [9], where the SBRP is decomposed
into five steps including data preparation, bus stop selection, bus route
generation, school bell time adjustment and route scheduling. This article
focuses on solving the bus stop selection and bus route generation aspects of
the SBRP, which is we refer to as the SBRP (a slight abuse of notation that is
common in the literature).

Bekta’s et al. [10] proposed an ILP model based on the open vehicle routing
problem (OVRP), in which vehicles do not return to the depot after serving the
last demand, to solve the real-life SBRP for transporting the students of an
elementary school throughout central Ankara, Turkey. They considered a
capacity constraint for vehicles and a maximum travel distance constraint for
each student, and an objective of minimizing the bus operating cost. This
paper provides the basic mathematical formulation of the SBRP.

Different constraints and objectives for the SBRP have been considered
throughout the literature. Park et al. [4] developed a mixed load algorithm
for the SBRP, where students from different schools can be served using the
same bus. The problem is modeled using an ILP and solved by a post-improvement
algorithm applied to a single load solution. The algorithm proposed is an
improvement on the mixed load algorithm given by Braca et al. [11], which
addressed the New York City school bus routing problem. Shafahi et al. [12]
proposed a new formulation of the SBRP with a homogeneous fleet that maximized
trip compatibility (two trips are compatible if they can be served by the same
bus) while minimizing the total travel time, and generated eight mid-size data
sets to test the performance of the model.

The literature on solving large-scale SBRPs is dominated by heuristic
approaches. Riera-Ledesma and Salazar-Gonzalez [5] solved the large-scale
SBRPs by modeling it as an ILP of the multi-vehicle traveling purchaser
problem, which is a generalization of the VRP. The LP-relaxation method was
used to efficiently solve the high dimensional ILP and a heuristic algorithm
was proposed to round the fractional results. This approach was tested by
using synthetic data and shown to solve instances with up to 125 students.

Schittekat et al. [6] proposed a sophisticated ILP considering both the bus
stop selection and bus route generation simultaneously and used a
metaheuristic approach to solve the problem. The metaheuristic approach
contains two steps i) a route construction phase that uses a greedy randomized
adaptive search procedure to compute sub-optimal initial solutions and ii) an
improvement phase where a variable neighborhood descent method is used to
ensure a local optimum in all neighborhoods. The method can produce generally
high quality solutions within one hour for problems of up to 80 stops and 800
students. Therefore, we use the generated instances from this article as one
of the benchmarks for testing our approach.

More recently, Bertsimas et al. [13] proposed an optimization model for the
School Time Selection Problem (STSP), which is a generalization of the school
bus routing problem that includes reusing the same bus fleet over multiple
rounds of trips (e.g. school with 7:30am start time followed by one with a
8:30am start time). A state-of-art school bus routing algorithm, named BiRD
(Bi-objective routing decomposition), was proposed. The BiRD algorithm
consists of generating single-school bus routes as sub-problems and combining
sub-problems via mixed-integer optimization to identify a trip-by-trip
itinerary for each bus in the fleet. The implementation of their approach led
to a $\$$5 million annual cost saving in Boston. The BiRD algorithm will serve
as a second benchmark to test our shareability network based decomposition
approach in the experiments section.

In summary, most of recent papers use ILP as a basic approach and concentrate
on proposing heuristic techniques to improve efficiency for solving the ILP.
To improve the efficiency and accuracy of current approaches, this work
proposes a shareability network based decomposition approach to solve large-
scale SBRPs and conducts real-world experiments of Boston public schools. Our
approach for modeling the SBRP is an extension of the technique used for the
dynamic high-capacity ridepooling problem [14], which is a special case of
dynamic open capacitated VRP with time windows. In the ridepooling context,
[14] proposed a decomposition approach via the shareability network to get a
lower dimensional ILP that is computationally tractable, and this approach is
adapted to the SBRP. The notion of the shareability network, first described
by Santi et al. [7], is utilized to efficiently compute optimal sharing
strategies on a large dataset.

A preliminary version of this work was presented at the 2018 Intelligent
Transportation Systems Conference [15]. In this extended article, we introduce
the following new contributions: i) More advanced network compression
techniques. In particular, we propose an algorithm to compensate for the
optimality loss induced by the edge compression technique; ii) A
generalization that allows for solving the multi-modal SBRP; iii) The
connecting between the weighted set cover problemm(WSCP) and SBRP; and iv) A
significantly extended section on real-world experiments and comparisons to
demonstrate the performance of our methods.

##  3 Problem Formulation

Table 1: Notations used in this paper Problem Formulation |
---|---
$G_{r}=(V_{r},E_{r})$ | Road network $G_{r}$ with vertex set $V_{r}$ representing locations, and edge
| set $E_{r}$ representing road segments
$d_{ij},t_{ij}$ | Shortest path distance and travel time between vertices $i,j\in V_{r}$
$S$ | Set of students
$B$ | Set of vehicles
$M$ | Set of potential bus stops
$D$ | Set of students residence locations
$A$ | Set of alternate transportation modes
$C$ | Capacity of school buses
$t^{max}$ | Maximum travel time for students
$v_{0},v_{d}$ | Bus depot vertex and school vertex
$d_{s}^{max}$ | Maximum walking distance for student $s$
$N_{s}$ | Set of reachable bus stops for student $s$
$N$ | Union of bus depot location, school location, bus stops locations and
| student residence locations
$\alpha_{C_{1}}^{b}$ | Cost for operating (owning or leasing) a bus per day including labor
$\alpha_{C_{2}}^{b}$ | Cost for operating a bus per mile
$\alpha_{C}^{a}$ | Cost for taking an alternate mode $a$ per mile
$x_{ijk}$ | Binary variable for whether bus $k$ travel from vertex $i$ to $j$
$y_{ik}$ | Binary variable for whether bus $k$ visits vertex $i$
$z_{isk}$ | Binary variable for whether bus $k$ picks up student $s$ at vertex $i$
$u_{sa}$ | Binary variable for whether student $s$ takes mode $a$ to school
Decomposition |
$G=(V,E)$ | Shareability network with vertex set $V$ representing requests, and
| edge set $E$ representing shareability between requests
$G_{ST}=(V_{ST},E_{ST})$ | Student-Trip graph with vertex set $V_{ST}$ representing the union of
| students and feasible trips, and edge set $E_{ST}$ representing whether
| students are involved in trips
$\tau\in T,\tau_{b}\in T_{b},\tau_{a}^{s}\in T_{a}$ | Set of feasible trips, feasible bus trips and feasible trips for an
| alternate mode $a$
$S(\tau)$ | Set of students who participate in the trip $\tau$
$C_{\tau}$ | Travel cost (distance) for any feasible trip $\tau\in T$
$L(\tau)$ | Number of students in a feasible trip $\tau\in T$
$x_{s\tau}$ | Binary variable for whether student $s$ chooses trip $\tau$
$y_{\tau}$ | Binary variable for whether trip $\tau$ is chosen in the optimal trip set
Network Compression |
$x_{m}$ | Binary variable for whether picking the potential bus stop $m\in M$
$\bar{t}_{ij}$ | Adjusted travel time between any two nodes $i$ and $j$
$\delta_{ij}$ | Detour factor for any two nodes $i$ and $j$
$n(m)$ | Number of students at any bus stop $m\in M$
$\beta$ | Heuristic parameter for the edge compression technique
$\gamma$ | Heuristic parameter for the $\gamma$-quasi-clique process

We first provide a formal definition of the school bus routing problem (SBRP).
The problem description will be consistent throughout the paper and the
notation used is listed in Table 1.

Let $G_{r}(V_{r},E_{r})$ denote the road network. For any pair of nodes
$i,j\in V_{r}$, $d_{ij}$ represents the shortest path distance between $i,j$,
and $t_{ij}$ the corresponding travel time. Consider a set of students $S$ who
need to be transported to a single destination (school) $v_{d}\in V_{r}$ with
a homogeneous fleet of school buses $B$, in which school buses have capacity
$C$. Without loss of generality, we define that each student $s\in S$ is
located at some location222The graph can be augment to model pickups (bus
stops) between vertices if needed. $v_{s}\in V_{r}$ and the set $D$ indicates
students pickup locations, $D\subseteq V_{r}$. Moreover, we let $M$ represent
the set of potential bus stops, where $M\subseteq V_{r}$ . Finally, to model
multi-modal travel, we define a set of alternate modes $A$, each student $s\in
S$ can either take a school bus or an alternate transportation mode $a\in A$
to the school.

Let $\alpha_{C_{1}}^{b}$ be the cost for leasing (or amortized capital cost of
owning) a bus per day including the labor cost for drivers333The driver labor
is a fixed cost that is independent of distance traveled per bus and is
typically a dominating expense., $\alpha_{C_{2}}^{b}$ be the operating cost
per bus per mile, and $\alpha_{C}^{a}$ be the cost for taking alternate mode
$a$ per mile444For the simplicity, we assume the cost for the alternate mode
$a$ has a linear relation with the trip distance. This can easily be replaced
by a more complex cost function.. The objective of this problem is to minimize
the total cost for the school bus scheduling. Figure 1 illustrates an instance
of the SBRP.

Figure 1: Instance of a feasible solution for the SBRP considering the
dedicated vehicle with bus capacity $C=9$. Left figure gives the input for
SBRP and right figure gives the results of the problem, which contains the bus
routes and bus stops for each student. Circles represent the students with
door-to-door pickup.

We enforce the following constraints in the SBRP formulation:

  1. 1.

The maximum travel time any student $s$ can be on the school bus is
$t^{\text{max}}$.

  2. 2.

Each student $s\in S$ has a maximum walking distance $d_{s}^{\text{max}}$ from
their residence to the assigned bus stop. This distance can be student
specific and equal to zero if the students need a door-to-door pickup. We let
$N_{s}$ represent the set of reachable stops for a student $s$, i.e.,
$N_{s}=\\{m\in M|d_{v_{s}m}\leq d_{s}^{max}\\}$.

  3. 3.

All school buses start at a single pre-specified location $v_{0}\in V_{r}$.

We let $N=D\cup M\cup\\{v_{0},v_{d}\\}$ denote the set of pickup locations
combined with potential bus stops, bus depot and school location. The decision
variables for this problem are $x_{ijk}$, $y_{ik}$, $z_{isk}$ and $u_{s}$,
where $x_{ijk}=1$ if bus $k$ travels from vertex $i$ to $j$ through the
shortest path, $y_{ik}=1$ if bus $k$ visits vertex $i$, $z_{isk}=1$ if student
$s$ is picked up by bus $k$ at vertex $i$ and $u_{sa}=1$ if student $s$ takes
an alternate mode $a$ to the destination. Assuming each bus stop or student
residence can be visited by at most one bus, the ILP formulation for the SBRP
considering alternate modes can be formulated as follows:

$\displaystyle\min\quad$ $\displaystyle\alpha_{C_{1}}^{b}\cdot
K+\alpha_{C_{2}}^{b}\cdot\sum_{i\in N}\sum_{j\in N}d_{ij}\sum_{k\in
B}x_{ijk}+\sum_{a\in A}\alpha_{C}^{a}\cdot\sum_{s\in S}u_{sa}d_{v_{s}v_{d}}$
(1) s.t. $\displaystyle\sum_{j\in N}x_{ijk}=\sum_{j\in
N}x_{jik}=y_{ik}\quad\forall i\in N\setminus\\{v_{0},v_{d}\\},\forall k\in B$
(2) $\displaystyle\sum_{j\in
N\setminus\\{v_{0},v_{d}\\}}x_{v_{0}jk}=\sum_{i\in
N\setminus\\{v_{0},v_{d}\\}}x_{iv_{d}k}\quad\forall k\in B$ (3)
$\displaystyle\sum_{i,j\in Q}x_{ijk}\leq|Q|-1\quad\forall Q\subseteq N,\forall
k\in B$ (4) $\displaystyle\sum_{i,j\in N\setminus\\{v_{0}\\}}t_{ij}\cdot
x_{ijk}\leq t^{max}\quad\forall k\in B$ (5) $\displaystyle\sum_{i\in
N}\sum_{s\in S}z_{isk}\leq C\quad\forall k\in B$ (6) $\displaystyle
z_{isk}\leq y_{ik}\quad\forall i\in N,\forall s\in S,\forall k\in B$ (7)
$\displaystyle\sum_{a\in A}u_{sa}+\sum_{i\in N_{s}\cup\\{v_{s}\\}}\sum_{k\in
B}z_{isk}=1\quad\forall s\in S$ (8) $\displaystyle\sum_{k\in B}\sum_{i\in
N\setminus\\{v_{d}\\}}x_{iv_{d}k}=K\leq|B|$ (9) $\displaystyle
x_{ijk}\in\\{0,1\\}\quad\forall i,j\in N,\forall k\in B$ (10) $\displaystyle
y_{ik}\in\\{0,1\\}\quad\forall i\in N,\forall k\in B$ (11) $\displaystyle
z_{isk}\in\\{0,1\\}\quad\forall i\in N,\forall s\in S,\forall k\in B$ (12)
$\displaystyle u_{sa}\in\\{0,1\\}\quad\forall s\in S,\forall a\in A$ (13)

The objective function (1) minimizes the overall school bus scheduling cost
considering the number of buses, vehicle miles travel and alternate modes
cost. Constraints (2) ensure that if bus $k$ visits pickup location $i$, then
there will be a flow entering $i$ and a flow leaving $i$ for bus $k$.
Constraints (3) impose that a bus entering the destination should also have
left the depot. Constraints (4) enforces sub-tour elimination, i.e. ensures a
single connected route for bus $k$. Constraints (5) consider the maximum
travel time for each student by restricting the total travel time for each bus
route starting from picking up the first student. Constraints (6) enforce that
the number of students in bus never exceed the capacity $C$. Constraints (7)
ensure that student $s$ will not be picked up by bus $k$ at vertex $i$ unless
bus $k$ visits vertex $i$. Constraints (8) impose that student $s$ either
takes an alternate mode or is picked up by a school bus. Constraint (9)
enumerates the number of non-idle buses and enforces the maximum number of
available buses $|B|$. Constraints (10) - (13) make sure that the decision
variables are binary.

This ILP formulation solves for the optimal school bus routing schedules for a
single school. The single school setting reduces the problem complexity, and
moreover, also corresponds to the real-world problem setting. Even though most
school buses are operated by a school district, there are a number of
practical and legal reasons for not mixing students across multiple schools in
a single bus. While the problem can be formulated as an ILP, solving large-
scale instances of this SBRP is intractable even when using state-of-art ILP
solvers. Therefore, solving the problem at scale in a computationally
tractable manner requires utilizing some decomposition and heuristic methods.
The following section describes our new approach and the corresponding
heuristics for solving the SBRP efficiently.

##  4 Methodology

In this section, we propose a decomposition method based on the notional of a
shareability network [7] and its application to ridepooling problems [14], to
solve the SBRP. Furthermore, we simplify the ILP for solving the SBRP by
identifying its connection with the WSCP. Finally, we improve the tractability
for large-scale instances by introducing network compression techniques that
effectively prune the shareability network, as the network can get intractably
large for offline problems like the SBRP.

###  4.1 Decomposition through the shareability network

In order to reduce the complexity and dimensionality of the ILP for solving
the SBRP, we propose a decomposition method via the shareability network,
which consists of several steps leading to an assignment problem that yields a
much-simplified ILP.

The shareability network [7] is an undirected graph $G_{S}=(V_{S},E_{S})$,
where $V_{S}$ corresponds to the set of trips and each edge $(i,j)\in E_{S}$
indicates that trip $i$ can share a vehicle with trip $j$ under some
compatibility constraints. The shareability network under the SBRP setting is
constructed as follows. The vertex set $V_{S}$ designates the set of student
locations and each edge $(s_{i},s_{j})\in E_{S}$ reflects the fact that
students $s_{i}$ and $s_{j}$ can share the same school bus (under a desired
set of quality of service constraints). For example, in our setting, students
$s_{i}$ and $s_{j}$ can share the same bus if both students can be transported
to the destination (school) $v_{d}$ within maximum travel time $t^{max}$ using
the same bus. Figure 2(a) shows an instance of a shareability network for four
students.

(a) Shareability network (b) Student-trip graph

Figure 2: Instance of the shareability network and ST-graph with 4 students.
Each student can be assigned their personal bus, share the bus with others or
take dedicated vehicle to school (represents by $\bar{S}$ in the graph). In
this instance, there are five feasible pairings of two students and two
feasible pairings of three students.

Next, we establish a bipartite graph $G_{ST}=(V_{ST},E_{ST})$ where $V_{ST}$
contains a the set of students and the set of all possible trips
configurations (school bus or alternate modes assignment) based on the
shareability network. This bipartite graph is referred as the student-trip
graph (ST-graph). The set of feasible trip configurations $T$ includes bus
trips $T_{b}$ and trips $T_{a}$ for an alternate mode $a$ , i.e.,
$T=\bigcup_{a\in A}T_{a}\cup T_{b}$. Let $S(\tau_{b})$ denote the set of
students who participate in a feasible bus trip $\tau_{b}\in T_{b}$. A bus
trip $\tau_{b}\in T_{b}$ is feasible if the total travel time for each student
is less than or equal to the maximum allowed ($t_{s}\leq t^{max},~{}\forall
s\in S(\tau_{b})$) and the total number of students in the bus is small than
its capacity ($|S(\tau_{b})|\leq C$). For each student $s\in S$,
$\tau_{a}^{s}\in T_{a}$ represents a non-school bus trip that student $s$
directly takes via alternate mode $a$ to the school. The node set $V_{ST}$ is
the union of the set of students and the set of feasible trips, i.e.
$V_{ST}=S\cup T$, and there will be an edge $e(s,\tau_{b})\in E_{ST}$ if
$\tau_{b}\in T_{b}$, $s\in S(\tau_{b})$, and an edge $e(s,\tau_{a}^{s})\in
E_{ST}$ for every $\tau_{a}^{s}\in T_{a}$. Figure 2(b) shows an instance of
ST-graph corresponding to the shareability network in Figure 2(a).

The set of feasible bus trip $T_{b}$ is generated using the shareability
network. The following observation is typically made to efficiently compute
the feasible bus trips in $T_{b}$ based on the shareability network $G$ [14].

###### Lemma 1

($Lemma\;\text{1}$ in [14]) A trip configuration $\tau_{b}$ can only be
feasible if the set of students $s$ in the trip configuration $\tau_{b}$ form
a clique in the shareability network $G$ (i.e. $\forall s_{i},s_{j}\in
S(\tau_{b}),e(s_{i},s_{j})\;\text{exists}$). This is a necessary (but not
sufficient) condition.

Given this observation, a potential trip configuration is not feasible if any
pair of students in the trip configuration are not connected by edge in the
shareability graph $G_{S}$. Thus, if a set of $n$ students ($s_{1},\cdots
s_{n}$) can not form a feasible trip configuration, we know that any trip
configuration that includes these students plus another $s_{n+1}$ will
certainly not be feasible. Therefore, as in [14], we construct the set of
feasible trip configurations $T_{b}$ by first considering trips that consist
of one student, and progressively consider larger sets only when the smaller
set is feasible. Algorithm 1 describes the details for generating the feasible
trip list $T_{b}$. The input function $\textsf{{PathTsp}}(\cdot)$ is a
blackbox for solving the path traveling salesman problem (path-TSP). As this
problem is NP-Hard [16], we utilize an insertion heuristic based approach for
solving the path-TSP problem. Details are provided in the A. We note that any
other efficient Path-TSP heuristic can be substituted for this.

Algorithm 1 Generating the set of feasible bus trips. Input: the shareability
network $G$, the set of students $S$, maximum travel time $t^{max}$, bus
capacity $C$, path-TSP solver for any trip $\tau$ with optimal travel time
$t^{*}$ as the output, i.e., $t^{*}=\textsf{{PathTsp}}(\tau)$

1:function BusTripGeneration($G=(V,E),S,t^{max},C,\textsf{{PathTsp}}(\cdot)$)

2: $T_{b},T_{b}^{1}\leftarrow\emptyset$

3: for $s\in S$ do $\triangleright$ Generate the trip list with one student

4: $\tau\leftarrow\\{s\\}$

5: $T_{b}^{1}\leftarrow T_{b}^{1}\cup\\{\tau\\}$

6: $T_{b}\leftarrow T_{b}\cup T_{b}^{1}$

7: $k\leftarrow 2$ $\triangleright$ Iterate from trips with two students

8: while true do

9: $T_{b}^{k}\leftarrow\emptyset$ $\triangleright$ Initialize the trip list
with $k$ students

10: for $\tau\in T_{b}^{k-1}$ do

11: for $s\in S$ and $s\notin\tau$ do

12: $\tau^{\prime}\leftarrow\tau\cup\\{s\\}$ $\triangleright$ Add one more
student to the trip with $k-1$ students

13: if $\textsf{{CliqueCheck}}(\tau,s,G(V,E))=true$ then

14: if
$\textsf{{FeasibilityCheck}}(\tau^{\prime},t^{max},C,\textsf{{PathTsp}}(\cdot))=true$
then

15: $T_{b}^{k}\leftarrow T_{b}^{k}\cup\\{\tau^{\prime}\\}$ $\triangleright$
Add feasible trips with $k$ students into the list

16: if $|T_{b}^{k}|=0$ then $\triangleright$ Break when there are no feasible
trips with $k$ students

17: break

18: $T_{b}\leftarrow T_{b}\cup T_{b}^{k}$; $k\leftarrow k+1$

19: return $T_{b}$

20:function CliqueCheck($\tau,s,G(V,E)$)

21: for $s^{\prime}\in S(\tau)$ do

22: if $e(s,s^{\prime})\notin E$ then

23: return false

24: return true

25:function FeasibilityCheck($\tau,t^{max},C,\textsf{{PathTsp}}(\cdot)$)

26: $t^{*}\leftarrow\textsf{{PathTsp}}(\tau)$

27: if $t^{*}\leq t^{max}$ and $|S(\tau)|+1\leq C$ then

28: return true

29: else

30: return false

The last step of our approach is to compute the optimal student-trip
assignment given the ST-graph $G_{ST}$, which is formalized as an ILP. The
total travel cost $C_{\tau}$ for each trip $\tau\in T$ is calculated from the
ST-graph $G_{ST}$, as this is given by the solution to the Path-TSP problem
for any feasible trip configuration. This gives us all the information needed
to formulate an assignment problem based on $G_{ST}$, which assigns all
students to trips (if a feasible solution exists) while minimizing the overall
school bus scheduling cost. Recall that the total cost consists of the number
of buses, vehicle miles traveled and the cost for transporting student via
alternate modes. This student-trip assignment problem can be treated as a
special case of the Weighted Set Cover Problem (WSCP). In the following
section, we will establish the connection between the SBRP and the WSCP, and
give a simplified ILP formulation for solving the SBRP.

###  4.2 Connection between SBRP and WSCP

######  Definition 1 (WSCP)

Given a set of $n$ elements $\mathcal{U}=\\{e_{1},e_{2},...,e_{n}\\}$ and $m$
subsets of $\mathcal{U}$, $\mathcal{S}=\\{S_{1},S_{2},...,S_{m}\\}$ with a
cost function $c:\mathcal{S}\longrightarrow\mathbb{R}^{+}$, $c(S_{j})$ that
denotes the cost of subset $S_{j}$, the objective is to find a set
$\mathcal{A}\subseteq\mathcal{S}$ such that:

  1. 1.

All elements in $\mathcal{U}$ are covered by the set $\mathcal{A}$, and

  2. 2.

The sum of the costs of the subsets in $\mathcal{A}$ is minimized.

Let $x_{S}$ be the binary variable for selecting subset $S\in\mathcal{S}$ in
the solution $\mathcal{A}$. The WSCP can be formulated as the following ILP:

min $\displaystyle\sum_{S\in\mathcal{S}}c(S)\cdot x_{S}$ (14) s.t.
$\displaystyle\sum_{S:e\in S}x_{S}\geq 1\quad\forall e\in\mathcal{U}$ (15)
$\displaystyle x_{S}\in\\{0,1\\}\quad\forall S\in\mathcal{S}$ (16)

In the special case of the WSCP where the set $\mathcal{A}$ is a collection of
disjoint subsets in $\mathcal{S}$, i.e.

$\forall S_{i},S_{j}\in\mathcal{A},S_{i}\cap S_{j}=\emptyset,$

the problem becomes the weighted set partitioning problem (WSPP). For the ILP
above, constraints (15) become

$\sum_{S:e\in S}x_{S}=1\quad\forall e\in\mathcal{U},$ (17)

which imply that each element in $\mathcal{U}$ will be covered by
$\mathcal{A}$ exactly once.

In order to build the connection between the SBRP and the WSCP, we first show
the correspondence between the SBRP and WSPP. In the ST-graph of the SBRP,
each student $s\in S$ can be treated as an element and the set of elements is
$\mathcal{U}=S$. Each trip configuration $\tau$ serves as a subset of $S$ with
trip cost $C_{\tau}$. The feasible trip configurations $T$ is the collection
of subsets $\mathcal{S}$, and the SBRP is equivalent to the WSPP as we are
finding a collection of subsets of $\mathcal{S}$ with the minimum cost.
Additionally, the SBRP is a special case of WSPP with two extra conditions on
the feasible bus trip configuration list $T_{b}$.

###### Claim 1

The SBRP is a special case of the WSPP with the following conditions for the
bus trip configuration list $T_{b}$:

  * 1.

Downward closed:  $\forall\tau_{b}\in
T_{b},\\{\tau_{b}^{\prime}:\tau_{b}^{\prime}\subseteq\tau_{b}\\}\subseteq
T_{b}$.

  * 2.

Monotonic cost function:
$\forall\tau_{b}^{\prime}\subseteq\tau_{b},c(\tau_{b})\geq
c(\tau_{b}^{\prime})$.

  * Proof.

When generating the feasible bus trips $\tau_{b}\in T_{b}$, let $\tau_{b}\in
T_{b}$ be a feasible bus trip and
$T_{b}^{sub}=\\{\tau_{b}^{\prime}:S(\tau_{b}^{\prime})\subseteq
S(\tau_{b})\\}$ be the collection of sub-trips for $\tau_{b}$, which
$S(\tau_{b})$ represents the set of all students in the bus trip $\tau_{b}$.
Because students in the trip $\tau_{b}$ should form a clique in the
shareability network, students in the trip $\tau_{b}^{\prime}$ also form a
clique. Also, the trip cost for $\tau_{b}^{\prime}$ is smaller than the cost
for $\tau_{b}$. Thus, $\forall\tau_{b}^{\prime}\in T_{b}^{sub}$,
$\tau_{b}^{\prime}\in T_{b}$, and we have downward closed and monotonic cost
function conditions for bus trip configuration list $T_{b}$.

The following claim shows the relationship between the WSPP and the WSCP when
the collection of subsets $\mathcal{S}$ is downward closed and has monotonic
cost function.

###### Claim 2

The WSPP with the following conditions on $\mathcal{S}$ can be solved by the
ILP (14) - (16) for the WSCP.

  * 1.

Downward closed:  $\forall S\in\mathcal{S},\\{S^{\prime}:S^{\prime}\subseteq
S\\}\subseteq\mathcal{S}$.

  * 2.

Monotonic cost function:  $\forall S^{\prime}\subseteq S,c(S)\geq
c(S^{\prime})$.

  * Proof.

We prove this claim by the contradiction. Let $\mathcal{A}$ be the optimal
solution for the WSCP, and suppose there exits two subsets
$S_{1},S_{2}\in\mathcal{A}$, $S_{1}\cap S_{2}\neq\emptyset$.

Let $S^{\prime}=S_{1}\cap S_{2}$, $S^{\prime}_{1}=S_{1}\setminus S^{\prime}$
and $S^{\prime}_{2}=S_{2}\setminus S^{\prime}$. According to the downward
closed condition, $S^{\prime}_{1},S^{\prime}_{2}\in\mathcal{S}$ since
$S^{\prime}_{1}\subseteq S_{1}$ and $S^{\prime}_{2}\subseteq S_{2}$. With the
monotonic cost function, we have $c(S^{\prime}_{1})\leq c(S_{1})$ and
$c(S^{\prime}_{2})\leq c(S_{2})$. We can reduce the total cost for
$\mathcal{A}$ by replace either $S_{1}$ with $S^{\prime}_{1}$ or $S_{2}$ with
$S^{\prime}_{2}$ in the optimal set $\mathcal{A}$ while still covering all
elements. Thus, the optimal set $\mathcal{A}$ should be a collection of
disjoint subsets in $\mathcal{S}$, and the optimal set $\mathcal{A}$ is also
optimal for the set partitioning problem with same $\mathcal{U}$ and
$\mathcal{S}$.

Then we give the simplified ILP for solving the SBRP which is generalized from
ILP (14) - (16) for solving the WSCP.

###### Corollary 1

The SBRP can be solved by the following ILP:

min $\displaystyle\sum_{\tau_{b}\in
T_{b}}(\alpha_{C_{1}}^{b}+\alpha_{C_{2}}^{b}\cdot C_{\tau_{b}})\cdot
y_{\tau_{b}}+\sum_{a\in A}\sum_{\tau_{a}\in T_{a}}\alpha_{C}^{a}\cdot
C_{\tau_{a}}\cdot y_{\tau_{a}}$ (18) s.t.
$\displaystyle\sum_{\tau:s\in\tau}y_{\tau}\geq 1\quad\forall s\in S$ (19)
$\displaystyle y_{\tau}\in\\{0,1\\}\quad\forall\tau\in T$ (20)

  * Proof.

Combining Claim 1 and Claim 2, the SBRP can be transformed into a WSCP and
solved by the corresponding ILP.

By building the connection between the WSCP and the SBRP, we simplify the ILP
(1) - (13) to the ILP (18) - (20). However, this simplified ILP is still
intractable when considering the large-scale SBRP instances, since the size of
the feasible trip configuration list $T_{b}$ increases exponentially in $|S|$.
While in theory this happens in the ridepooling setting as well, in practice
the shareablity network is sparse due to the quality of service constraints of
the system (e.g. low passenger waiting times and detour limitation) [14].
However, in the SBRP context, the shareability network is considerably more
dense because of the looser quality of service constraints. For example, there
is no waiting time constraint (students do not specify a pickup time) and the
maximum travel detour can be large due to the only limitation being the total
trip length $t^{max}$ (usually 1 hour). The denser shareability network
induces many large cliques and thus potential trip configurations to evaluate,
which can become computationally challenging. In order to address this issue,
we propose some network compression techniques that induce sparsity in the
SBRP shareability network, and thereby improve the computational tractability
of the problem.

###  4.3 Network compression techniques

As mentioned above, our shareability network based approach is still
intractable for large-scale instances as the size of the feasible bus trip
list $T_{b}$ can be very large (in the order of billions for real-world
instances). Generating the feasible trip configuration list $T$ is a time-
consuming process (requires solving a Path-TSP for each candidate
configuration). Furthermore, even if the trip configurations were known,
solving the student-trip assignment ILP (18) - (20) with a large number of
variables ($O(|T|)$) becomes a challenging task for even state-of-the-art ILP
solvers.

To address this computation bottleneck of the proposed decomposition approach,
we develop network compression techniques that induce sparsity in the
shareability network. The techniques we present reduce the time it takes to
compute the feasible trip configurations $T$, while retaining all (or most of
the) useful information that is embedded in the network (i.e. retaining good
trip configurations). We present compression techniques from two perspectives
that work by either pruning the nodes or the edges of the shareability
network. A sparse shareability network leads to a shorter feasible trip
configuration list and makes even large-scale SBRPs tractable to solve.

####  4.3.1 Node compression technique

For the node compression technique, we reduce the number of nodes in the
shareability network by generating bus stops and allowing students to walk to
bus stops within a maximum walking distance. The school buses will pick up
students at bus stops instead of students’ residence, and the shareability
network will be constructed based on bus stops555Due to various reasons, some
students might require door to door travel without walking to a bus stop. In
these settings, we can create a bus stop at the students residence..

Given a predefined set of candidate bus stops $M$, we first formulate the
following ILP to assign the students to a minimum number of bus stops. The
binary decision variable $x_{m}$ (for $m\in M$) denotes whether bus stop is to
be selected.

min $\displaystyle\sum_{m\in M}x_{m}$ (21) s.t. $\displaystyle\sum_{m\in
N_{s}}x_{m}\geq 1\quad\forall s\in S$ (22) $\displaystyle
x_{m}\in\\{0,1\\}\quad\forall m\in M$ (23)

The objective function (29) minimizes the total number of bus stops that are
needed. Constraints (30) ensure that each student has at least one bus stop
within their maximum walking range. Constraints (31) impose that decision
variables are binary. This ILP generates the minimum number of bus stops
needed to cover all the students.

Even if some students need door-to-door pickups ($d_{s}^{max}=0$ and
$N_{s}=\emptyset$), the above node compression technique can still be used by
assigning the student to the nearest station and adding a penalty
corresponding to the vehicle having to move from the station to the student
residence and back. This penalty is bounded by the distance of a round-trip
between the assigned bus stop and door-to-door students’ residence. The
penalty will be incorporated in the function $\textsf{{PathTsp}}(\cdot)$ when
considering the feasibility of trips. For cases with considerable number of
students who need door-to-door pickups, this heuristic substantially reduces
the computational complexity. Figure 3 shows an example of the shareability
network before and after applying the node compression technique with above
heuristic for students with door-to-door pickups (this example uses a virtual
walking distance of 0.5 miles, which is an independent parameter from the
maximum walking distance).

(a) The original shareability network

(b) The shareability network after applying node compression technique

Figure 3: An instance of applying the node compression technique for the
shareability network. These figures are generated using data corresponding to
the Tommy Harper School from synthetic Boston Public Schools dataset [17]. The
school has 51 students including 7 students with door-to-door pickups
(considering a virtual walking distance 0.5 miles). The red star is the
location for school and the blue graph is the shareability network. The number
of nodes (bus stops) in the shareability network decreases from 51 to 19 after
applying the node compression technique.

The node compression technique reduces the maximum number of effective
students for any trip $\tau_{b}\in T_{b}$, since each bus stop now aggregated
multiple students as a single request with a larger capacity. Nonetheless,
even with the corresponding reduction in the number of nodes in the
shareability network, the shareability network might still not be sparse
enough for the computational tractability of large-scale problem instances.
Therefore, we also adopt a heuristic-based edge compression technique that
deletes edges that are unlikely to induce shared trips. This compression can
in theory lead to a sub-optimal solution because we will eliminate feasible
sharing possibilities. Our aim is to generate a heuristic set of rules that
only eliminate pairings that are very unlikely to occur in practice.

####  4.3.2 Edge compression technique

For the edge compression technique, we reduce edges in the shareability
network following some mechanisms. The main idea behind pruning edges in the
shareability network is to go beyond the technical feasibility of a pairing
and introduce additional constraints that in some way embed the realism of a
pair of nodes being shared. The travel time between two nodes is not the only
factor corresponding to the likelihood of sharing trips, the relative position
of the school and nodes also matters. For example, it is unlikely for a
student 5 miles north of the school to share a ride with a student 5 miles
south of the school, if there are enough students to fill a bus from north of
the school. On the other hand, two students could share the same trip if they
are on the same side of the school even if they are relatively far away from
each other.

To incorporate both factors, we define the adjusted travel time
$\bar{t}_{ij}=\delta_{ij}\cdot t_{ij}$ between any two nodes $i$ and $j$ in
the shareability network, where
$\delta_{ij}=\frac{t_{ij}+t_{jv_{d}}}{t_{iv_{d}}}$, represents the detour
factor ($\delta_{ij}\geq 1$). The detour factor is a measure of how much of a
detour node $i$ has to incur to share a trip with node $j$, as opposed to node
$i$ being connected to the destination directly.

With the definition of the adjusted travel time, we apply a mechanism that a
node only share trips with adjusted nearby nodes in the shareability network.
More formally, the adjusted nearby nodes for any node $i$ are generated by
calculating the adjusted travel time between node $i$ and all other nodes
$V\setminus\\{i\\}$, sorting the nodes in ascending order by the adjusted
travel time, and choosing the $k$ closest nodes such that $k\leq\beta\cdot C$,
where $\beta$ is a pruning parameter that is greater than 1. If nodes
correspond to bus stops with multiple students as a result of the node
compression, we consider the k closest nodes such that the sum of students is
less than $\beta\cdot C$. Note that $\sum_{j=1}^{k}n(m_{j})\leq\beta\cdot C$,
where $m_{j}$ represents the bus stop and $n(m_{j})$ is the number of students
at stop $m_{j}$.

The number of edges decreases as $\beta$ decreases, so the number of feasible
bus trips $|T_{b}|$ also decreases. We tune $\beta$ to generate an appropriate
sized set of feasible bus trips $T_{b}$ that maintain tractability (size of
$|T_{b}|$) while being large enough to provide diverse set of bus routes.
Intuitively, if $\beta$ is too small, many feasible trips that belong to the
optimal solution might be eliminated. On the other hand, if $\beta$ is too
large and only a few edges are eliminated in the shareability network, the
trip list will be too large and large-scale SBRPs will remain intractable.
Therefore, $\beta$ provides a balance between computability and optimality.
The appropriate value of $\beta$ (minimum necessary for good solutions) will
in practice be different for different problem instances and spatial
distributions of the students. Figure 4 shows an example of the shareability
network before and after applying the edge compression technique.

(a) The shareability network after applying node compression

(b) The shareability network after applying node and edge compression
($\beta=2$)

Figure 4: Instance of applying edge compression for the shareability network.
These figures are generated using data from the Dennis Eckersley School in
synthetic Boston Public School data set. The instance has 403 students (75
students with door-to-door pickups - we consider a vitual walking distance 0.5
miles). The red star denotes the school location and the blue graph shows the
shareability network. The node compression generates 45 bus stops. After
applying edge compression with $\beta=2$, the shareability network becomes
very sparse with a much smaller number of cliques.

Once again, we note that the edge compression technique is a heuristic
approach and does not provide any guarantee regarding the loss of optimality.
In particular, when the size of an SBRP instance becomes larger, in order to
make problems tractable we have to use a small value of $\beta$ and restrict
the size of feasible bus trip configuration list $|T_{b}|$. By the criterion
of finding a feasible trip in Lemma 1, all students in a feasible trip form a
clique in the shareability network. Experimental results show that the edge
compression can lead to unsatisfactory results when $\beta$ is too small. In
order to compensate for this side-effect, we propose a relaxation of the
necessary condition from Lemma 1. We introduce the $\gamma$-quasi-clique
process based on the Algorithm 1 to find groups of students who form quasi-
cliques in the shareability network. More precisely, the $\gamma$-quasi-clique
is a sub-graph similar to a clique defined by a heuristic parameter $\gamma$,
which indicates the connection between quasi-cliques and cliques. A
$\gamma$-quasi-clique of size $k+1$ is a sub-graph built from adding a new
node $i$ to a $\gamma$-quasi-clique of size $k$ where node $i$ connects with
at least a $\gamma$ proportion of nodes in the size-$k$ $\gamma$-quasi-clique.
Note that $\gamma$ is upper bounded by 1 by definition.

The $\gamma$-quasi-clique process replaces the function
$\textsf{{CliqueCheck}}(\tau,G(V,E))$ in the Algorithm 1 and details are shown
in the Algorithm 2.

Algorithm 2 $\gamma$-quasi-clique process. Input: the shareability network
$G$, a feasible bus trip $\tau\in T_{b}$, a student $s\notin\tau$, heuristic
parameter $\gamma$.

1:function $\gamma$-QuasiCliqueProcess($\tau,s,G(V,E),\gamma$)

2: $x\leftarrow 0$

3: for $s^{\prime}\in S(\tau)$ do

4: if $e(s,s^{\prime})\notin E$ then

5: $x\leftarrow x+1$

6: if $x>\gamma\cdot|\tau|$ then

7: return false

8: return true

Introducing the $\gamma$-quasi-clique process in the Algorithm 1 improves the
objective function by augmenting the bus trip configuration list $T_{b}$ given
a fixed $\beta$ and produces satisfying results in practice. The
$\gamma$-quasi-clique process can be thoughts as a greedy sampling algorithm
to get partial trip configurations from the bus trip configuration list
$T_{b}$ before applying edge compression technique. The $\beta$ edge
compression approach dramatically shrink the trip configure list while
$\gamma$-quasi-clique process partially keeps the deleted trips. One major
drawback for $\beta$ edge compression approach is that the length of trip
configuration list grows exponentially when $\beta$ is increasing. There are
cases that the current $\beta$ leads to unpleasant results and increasing the
value of $\beta$ make the problem intractable. The $\gamma$-quasi-clique
process could add additional trips to the compressed trip configuration list
and compensate for the optimality loss. Moreover, the additional computation
time induced by $\gamma$-quasi-clique process can be ignored compared to the
feasible trip configuration list generation procedure.

##  5 Experiments

To test the applicability of our proposed algorithms to large-scale SBRPs, we
conducted a number of numerical experiments using some publicly accessible
benchmark problem instances. All the experiments were run on a 2.7 GHz Intel
Core i7 Processor with 16 GB Memory using Python 3.6.

###  5.1 Boston Public Schools (BPS) synthetic school bus data

The first data set we use is from the Transportation Challenge held by Boston
Public Schools (BPS), which contains 22420 simulated students addresses (to
protect student privacy) from 134 public schools. The data set was created
with the same aggregate pickup location distributions as in the real-world
[17]. The spatial distribution of this dataset is shown in the Figure 5.

Figure 5: Simulated data from Boston Public School (BPS). Blue dots represent
student locations and red circles denote school positions.

The Boston road network $G_{r}=(V_{r},E_{r})$ is obtained from Open Street
Maps (OSM) [18] using the open source Python library OSMnx [19]. All the
visualizations of the results are generated using the Python library NetworkX
[20] and Matplotlib. The implementation used for the PathTsp function is shown
in A. We use the state-of-the-art ILP solver Gurobi 7.5.2 [21] for solving the
assignment problem in the experiments (with a 3600 second maximum computation
time). We also make the following assumptions based on the BPS data, school
district requirements, and reasonable system parameters:

  * 1.

School buses can start at any location in the network.

  * 2.

The delay time $d$ (in seconds) for buses at each bus stop $m$ follows a
function $d=15+5\cdot n(m)$ , where $n(m)$ is the number of students at the
bus stop $m$.

  * 3.

Each door-to-door student has the same vitual maximum walking distance
$d_{s}^{max}=0.5$ miles.

  * 4.

There is no restriction on the bus fleet size and the school bus capacity
$C=72$.

  * 5.

The maximum travel time for students is $t^{max}=3600$ seconds.

  * 6.

The set of potential bus stops $M$ is same to the set of nodes in the road
network $V_{r}$.

  * 7.

The set of alternate modes $A$ only contains dedicated single occupancy
vehicles (e.g. single student by taxi/ride-hail).

  * 8.

The cost of owning a bus is $\alpha_{1}=200$ dollars per day and the cost for
operating a bus is $\alpha_{2}=1$ dollar per mile [22]. This implies that the
capital cost for ownership is much larger than the operational cost, which
leads to solutions that minimize the number of buses needed. The cost for
taking a dedicated vehicle is $\alpha_{3}=2$ dollars per mile [23].

Numerical experiments were conducted for ten representative schools from the
BPS data set that span the range of school sizes and complexity of the student
spatial distributions. The relevant metrics from the results are shown in
Table 2 and the optimal school bus schedules can be found in B.

Table 2: Computational results for the ten representative schools from the BPS data set. The total students and door-to-door students are denoted by $N_{S}$ and $N_{S_{d2d}}$, the number of bus stops is given by $N_{M^{*}}$, and $N_{T_{b}}$ designates the length of the feasible trip configuration list. The objective value for the shareability network based decomposition approach is given by $SND$ and $N_{B}$ stands for the number of buses. The number of students who are assigned to dedicated vehicles is given by $N_{U}$ and $T$ denotes the overall computation time (in seconds). The dash ($-$) in the $\beta$ and $\gamma$ columns indicates that the edge compression heuristic was not used. School |  $N_{S}$ |  $N_{S_{d2d}}$ |  $N_{M^{*}}$ |  $N_{T_{b}}$ |  $\beta$ |  $\gamma$ |  SND |  $N_{B}$ |  $N_{U}$ |  $T$
---|---|---|---|---|---|---|---|---|---|---
Tommy Harper |  51 |  7 |  19 |  62632 |  - |  - |  342.00 |  1 |  24 |  13.76
Craig Kimbrel |  71 |  11 |  20 |  107253 |  - |  - |  461.39 |  2 |  2 |  26.77
Deven Marrero |  91 |  14 |  22 |  100021 |  - |  - |  527.03 |  2 |  13 |  21.76
Frank Malzone |  160 |  30 |  30 |  333994 |  1.2 |  0.3 |  760.93 |  3 |  11 |  84.58
Dick Williams |  183 |  28 |  22 |  71672 |  - |  - |  622.07 |  2 |  42 |  18.36
Dick Bresciani |  208 |  40 |  35 |  760551 |  1.3 |  0.4 |  790.47 |  3 |  23 |  191.25
Dutch Leonard |  243 |  42 |  42 |  1951866 |  2 |  0.4 |  942.85 |  3 |  36 |  515.85
Christian Vazquez |  344 |  66 |  35 |  553380 |  3 |  0.4 |  1109.87 |  5 |  0 |  3730.93
Dennis Eckersley |  403 |  75 |  45 |  322566 |  2 |  0.4 |  1312.87 |  5 |  44 |  4194.26
Rick Ferrell |  573 |  109 |  55 |  546319 |  2.5 |  0.4 |  1781.92 |  8 |  2 |  151.26

###  5.2 Benchmark testing

To further evaluate the performance and scalability of this approach, we
compared our approach with two state-of-art methods for solving the SBRP [6,
13].

####  5.2.1 BiRD (Bi-objective Routing Decomposition) algorithm

First we compare against the BiRD (Bi-objective Routing Decomposition)
algorithm for the SBRP [13]. In particular, we implemented the single-school
routing algorithm from [13] and compared results using the BPS synthetic data.
In the comparison, we set $\alpha_{1}=500,\alpha_{2}=1$ and
$\alpha_{3}=\infty$ (to consider the objective of minimizing the number of
school buses needed and eliminte alternative models). In the BiRD algorithm,
the quality of the solution is a function of the number of feasible trips $N$
covering each bus stop. In the application described in Bertsimas et al. [13],
$N$ was set to be 400. Because the BiRD algorithm includes a randomized trip
generation step and we are not able to exactly replicate the trips that were
generated, we consevatively set $N$ equal to 1000 (instead of 400) and also
run the 10 times take the best result that we obtain. A comparison of the
results is shown in the Table 3. The corresponding optimal school bus
schedules can be found in C.

Table 3: Comparison results with $BiRD$ algorithm [13]. $BiRD$ stands for the objective value for the Bi-objective Routing Decomposition algorithm, $Improv$ implies the improvement of objective value for $SND$ compared to $BiRD$. $\Delta$ indicates the difference of the number of buses needed between $SND$ and $BiRD$. School |  $N_{S}$ |  $N_{S_{d2d}}$ |  $N_{M^{*}}$ |  $N_{T_{b}}$ |  $\beta$ |  $\gamma$ |  SND |  BiRD |  $\Delta$ |  Improv
---|---|---|---|---|---|---|---|---|---|---
Tommy Harper |  51 |  7 |  19 |  62632 |  - |  - |  1549.16 |  1553.44 |  0 |  0.28$\%$
Craig Kimbrel |  71 |  11 |  20 |  107253 |  - |  - |  1548.97 |  1554.28 |  0 |  0.34$\%$
Deven Marrero |  91 |  14 |  22 |  100021 |  - |  - |  1553.94 |  1558.34 |  0 |  0.28$\%$
Frank Malzone |  160 |  30 |  30 |  333994 |  1.2 |  0.3 |  2080.18 |  2081.9 |  0 |  0.08$\%$
Dick Williams |  183 |  28 |  22 |  71672 |  - |  - |  1559.98 |  1560.32 |  0 |  0.02$\%$
Dick Bresciani |  208 |  40 |  35 |  760551 |  1.3 |  0.4 |  2083.13 |  2083.91 |  0 |  0.04$\%$
Dutch Leonard |  243 |  42 |  42 |  1951866 |  2 |  0.4 |  2614.7 |  3120.28 |  -1 |  16.20$\%$
Christian Vazquez |  344 |  66 |  35 |  553380 |  3 |  0.4 |  2609.87 |  3113.03 |  -1 |  16.16$\%$
Dennis Eckersley |  403 |  75 |  45 |  548316 |  2.3 |  0.4 |  3127.26 |  3632.52 |  -1 |  13.91$\%$
Rick Ferrell |  573 |  109 |  55 |  124257 |  2 |  0.4 |  4669.67 |  4673.46 |  0 |  0.08$\%$

####  5.2.2 Metaheuristic algorithm with neighbourhood search

An alternative approach in Schittekat et al. [6] uses a metaheuristic
algorithm (greedy search procedure with neighborhood search) to simultaneously
solve both the bus stop selection and school bus routing problem. In contrast,
we solve these two problems sequentially. To compare our method with this
approach, we used the Euclidean space instances given in [6] (instead of
network instances with shortest path distances) and adopted our algorithm to
the settings used in their experiments. In particular, by first assigning
students to bus stops and then solving for the optimal bus route. The
comparison results are shown in Table 4. For synthetic instances generated by
Schittekat et al. [6] we limited our comparisons to instances with a maximum
walking distance of 5 units (which was the minimum considered), since larger
distances led to fewer pickup points and simpler routing problems. Such
instances could be solved without the new techniques that we propose.

Table 4: Comparison results with metaheuristic method [6]. $ID$ corresponds to the instance number, $stop$ denotes the number of bus stops, $stud$ represents the number of students, $cap$ indicates the bus capacity, $wd$ is the maximum walking distance for students in Euclidean space, $beta$ and $\gamma$ are parameters for the edge compression techniques, $N_{T_{b}}$ stands for the number of feasible bus trips, $MH$ is the objective value for metaheuristic method [6], $SND$ indicates the objective value for the shareability network based decomposition approach, $Improv$ implies the improvement of objective value for $SND$ compared to $MH$. ID |  stop |  stud |  cap |  wd |  $\beta$ |  $\gamma$ |  $N_{T_{b}}$ |  MH |  SND |  Improv
---|---|---|---|---|---|---|---|---|---|---
73 |  40 |  200 |  25 |  5 |  3 |  0.3 |  2776 |  831.94 |  804.4 |  $+3.31\%$
74 |  40 |  200 |  50 |  5 |  1.5 |  0.3 |  127211 |  593.35 |  585.08 |  $+1.39\%$
81 |  40 |  400 |  25 |  5 |  - |  - |  575 |  1407.05 |  1428.2 |  $-1.5\%$
82 |  40 |  400 |  50 |  5 |  3 |  0.3 |  6514 |  858.80 |  848.8 |  $+1.16\%$
89 |  40 |  800 |  25 |  5 |  - |  - |  40 |  2900.14 |  3085.11 |  $-6.38\%$
90 |  40 |  800 |  50 |  5 |  - |  - |  726 |  1345.70 |  1404.61 |  $-4.38\%$
97 |  80 |  400 |  25 |  5 |  3 |  0.4 |  5928 |  1546.23 |  1494.38 |  $+3.35\%$
98 |  80 |  400 |  50 |  5 |  1.5 |  0.4 |  40583 |  1048.56 |  1025.62 |  $+2.19\%$
105 |  80 |  800 |  25 |  5 |  - |  - |  1410 |  2527.96 |  2623.77 |  $-3.79\%$
106 |  80 |  800 |  50 |  5 |  5 |  0.4 |  45252 |  1530.58 |  1499.88 |  $+2.01\%$
Table 5: Comparison results with metaheuristic method [6] with bus stops separation. $N^{max}$ represents the maximum number of students for each bus stop. ID |  stop |  stud |  cap |  wd |  $N^{max}$ |  $\beta$ |  $\gamma$ |  $N_{T_{b}}$ |  MH |  SND |  Improv
---|---|---|---|---|---|---|---|---|---|---|---
73 |  40 |  200 |  25 |  5 |  - |  3 |  0.3 |  2776 |  831.94 |  804.4 |  $+3.31\%$
74 |  40 |  200 |  50 |  5 |  - |  1.5 |  0.3 |  127211 |  593.35 |  585.08 |  $+1.39\%$
81 |  40 |  400 |  25 |  5 |  5 |  2.5 |  0.3 |  48983 |  1407.05 |  1316.2 |  $+6.46\%$
82 |  40 |  400 |  50 |  5 |  - |  3 |  0.3 |  6514 |  858.80 |  848.8 |  $+1.16\%$
89 |  40 |  800 |  25 |  5 |  5 |  2.5 |  0.3 |  59789 |  2900.14 |  2783.77 |  $+4.01\%$
90 |  40 |  800 |  50 |  5 |  10 |  3 |  0.3 |  385814 |  1345.70 |  1335.56 |  $+0.75\%$
97 |  80 |  400 |  25 |  5 |  - |  3 |  0.4 |  5928 |  1546.23 |  1494.38 |  $+3.35\%$
98 |  80 |  400 |  50 |  5 |  - |  1.5 |  0.4 |  40583 |  1048.56 |  1025.62 |  $+2.19\%$
105 |  80 |  800 |  25 |  5 |  5 |  2.5 |  0.3 |  112016 |  2527.96 |  2474.6 |  $+2.11\%$
106 |  80 |  800 |  50 |  5 |  - |  5 |  0.4 |  45252 |  1530.58 |  1499.88 |  $+2.01\%$

However, our approach yields worse solutions for instance 81, 89, 90 and 105
because of the optimality limitations induced by splitting the bus stops
selection and bus routing problem. Buses in these instances visits fewer stops
than other instances. Schittekat et al. [6] made an assumption that each bus
stop is visited by only one bus. We relaxed this assumption by splitting each
stop into several bus stops with the maximum number of students $N^{max}$
after the bus stops selection. We picked the value of $N^{max}$ with respect
to the number of stops and the school bus capacity for different instances to
balance the tractability and optimality. A small value of $N^{max}$ could
produce a satisfying solution, but the problem would be hard to solve since
the number of bus stops becomes larger. Table 5 shows the results after we
separate each bus stop into several stops with a students cap $N^{max}$. By
splitting the bus stops with large number of students into several stops, our
shareability network-based decomposition approach gets better solutions.

Figure 6: Sensitivity analysis for $\beta$. We calculate the objective value,
number of buses, running time and number of feasible bus trips corresponding
to different $\beta$ values.  Figure 7: Sensitivity analysis for $\gamma$. We
calculate the objective value, number of buses, running time and number of
feasible bus trips corresponding to different $\gamma$ values.

###  5.3 Sensitivity analyses

Finally, we conduct a sensitivity analyses for network compression techniques
using the large-scale BPS instance of Christian Vazquez School with 344
students, where 66 students need door-to-door pickup. We set
$\alpha_{1}=500,\alpha_{2}=1$ and $\alpha_{3}=\infty$ (consider the school bus
as the only transportation mode).

For measuring the sensitivity to the control parameter $\beta$ for the edge
compression technique, we choose $\beta$ values ranging from 1 to 4 with a
step size of 0.2 and keep the $\gamma$ equal to 0.4. The sensitivity analyses
results are shown in Figure 6. The objective value and number of buses
required decrease in unison as $\beta$ increased, since a larger set of
sharing options are made available via the shareability network and can be
potentially fit into a smaller number of buses. As $\beta$ decreases, fewer
options are available and more buses maybe needed leading to a higher
objective function value. In contrast, both the running time and length of the
feasible trip list increase exponentially with respect to $\beta$, since the
shareability graph grows exponentially in size with respect to $\beta$. The
fluctuation of the running time is induced by the uncertainty for solving the
ILP.

For measuring the sensitivity to the control parameter $\gamma$ for the edge
compression technique, we consider a range from 0 to 0.9 with a step size of
0.1 meters and keep the beta parameter fixed at $\beta=2$. The sensitivity
analyses results are shown in Figure 7. Unsurprisingly, we notice that the
objective value will decrease when $\gamma$ increases. The running time and
the number of the feasible bus trips increases when $\gamma$ increases. The
number of buses required does not change because we can get 5 buses even
without applying $\gamma$-quasi-clique process, which is the minimum number of
buses for this instance.

##  6 Discussion

This paper proposes a shareability network based approach for solving large-
scale SBRP considering alternate modes. We simplify the ILP for solving the
SBRP by building the connection between SBRP and the WSCP by decomposition
through the shareability network. Moreover, we present a node compression
technique and heuristic edge compression techniques to obtain a simplified ILP
and enable tractable computation of the SBRP at-scale. The node compression
technique uses an ILP to generate bus stops while satisfying maximum walking
constraints for all students and decreases the number of nodes in the
shareability network. In contrast, the edge compression techniques are
heuristics that are applied to reduce the density of the shareability network,
and work well in practice. We evaluate our solution using synthetic data-sets
from BPS and show that our approach can compute decent solutions for large-
scale problems. To further evaluate the performance for our approach, two
benchmark tests are conducted with state-of-art SBRP sovling techniques.
Finally, a sensitivity analysis of the parameters used for network compression
techniques is provided to get insights into how they influence the trade-off
between solution quality and computation time.

This work is the first attempt to adapt techniques from the ridepooling
literature on the shareability networks to the SBRP, consider alternate modes
in SBRP and connect SBRP with the WSCP. The key extension for enabling these
techniques to work in practice for large-scale instances for the SBRP is the
compression of the shareability network. One important future direction is to
develop more sophisticated and nuanced edge compression schemes that more
precisely target the edges that are unlikely to be relevant to the optimal
solution. Moreover, the simplified ILP we present can be combined with state-
of-art ILP solving techniques (e.g. column generation) to solve the extreme
large-scale SBRP instances or allow for larger $\beta$ values. This is also an
area to be explored.

## Acknowledgements

The contents of this report reflect the views of the authors, who are
responsible for the facts and the accuracy of the information presented
herein. This document is disseminated in the interest of information exchange.
The report is funded, partially or entirely, by a grant from the U.S.
Department of Transportation’s University Transportation Centers Program.
However, the U.S. Government assumes no liability for the contents or use
thereof. The authors would also like to thank Yang Liu for his comments on the
paper.

## References

  * American School Bus Council [2013] American School Bus Council, Environmental benefits, http://www.americanschoolbuscouncil.org/issues/environmental-benefits, 2013\.
  * DIG [2017] Digest of Education Statistics: 2016, U.S. Department of Education. Institute of Education Sciences, National Center for Education Statistics., 2017.
  * Toth and Vigo [2002] P. Toth, D. Vigo, The vehicle routing problem, Society for Industrial and Applied Mathematics, Philadelphia, 2002.
  * Park et al. [2012] J. Park, H. Tae, B.-I. Kim,  A post-improvement procedure for the mixed load school bus routing problem,  European Journal of Operational Research 217 (2012) 204 – 213.
  * Riera-Ledesma and Salazar-GonzÃÂ¡lez [2012] J. Riera-Ledesma, J.-J. Salazar-GonzÃÂ¡lez,  Solving school bus routing using the multiple vehicle traveling purchaser problem: A branch-and-cut approach,  Computers & Operations Research 39 (2012) 391 – 404.
  * Schittekat et al. [2013] P. Schittekat, J. Kinable, K. SÃÂ¶rensen, M. Sevaux, F. Spieksma, J. Springael,  A metaheuristic for the school bus routing problem with bus stop selection,  European Journal of Operational Research 229 (2013) 518 – 528.
  * Santi et al. [2014] P. Santi, G. Resta, M. Szell, S. Sobolevsky, S. H. Strogatz, C. Ratti,  Quantifying the benefits of vehicle pooling with shareability networks,  Proceedings of the National Academy of Sciences 111 (2014) 13290–13294.
  * Newton and Thomas [1969] R. M. Newton, W. H. Thomas,  Design of school bus routes by computer,  Socio-Economic Planning Sciences 3 (1969) 75 – 85.
  * Park and Kim [2010] J. Park, B.-I. Kim,  The school bus routing problem: A review,  European Journal of Operational Research 202 (2010) 311 – 319.
  * Bektaş and Elmastaş [2007] T. Bektaş, S. Elmastaş,  Solving school bus routing problems through integer programming,  Journal of the Operational Research Society 58 (2007) 1599–1604.
  * Braca et al. [1997] J. Braca, J. Bramel, B. Posner, D. Simchi-levi,  A computerized approach to the new york city school bus routing problem,  IIE Transactions 29 (1997) 693–702.
  * Shafahi et al. [2017] A. Shafahi, Z. Wang, A. Haghani,  Solving the school bus routing problem by maximizing trip compatibility,  Transportation Research Record: Journal of the Transportation Research Board 2667 (2017) 17–27.
  * Bertsimas et al. [2019] D. Bertsimas, A. Delarue, S. Martin,  Optimizing schools’ start time and bus routes,  Proceedings of the National Academy of Sciences 116 (2019) 5943–5948.
  * Alonso-Mora et al. [2017] J. Alonso-Mora, S. Samaranayake, A. Wallar, E. Frazzoli, D. Rus,  On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment,  Proceedings of the National Academy of Sciences 114 (2017) 462–467.
  * Guo et al. [2018] X. Guo, Y. Liu, S. Samaranayake,  Solving the school bus routing problem at scale via a compressed shareability network,  in: 2018 21st International Conference on Intelligent Transportation Systems (ITSC), pp. 1900–1907.
  * Laporte [1992] G. Laporte,  The traveling salesman problem: An overview of exact and approximate algorithms,  European Journal of Operational Research 59 (1992) 231–247.
  * Boston Public School [2017] Boston Public School, Transportation challenge, https://www.bostonpublicschools.org/transportationchallenge, 2017\.
  * OpenStreetMap contributors [2017] OpenStreetMap contributors, Planet dump retrieved from https://planet.osm.org , https://www.openstreetmap.org, 2017.
  * Boeing [2017] G. Boeing,  Osmnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks,  Computers, Environment and Urban Systems 65 (2017) 126 – 139.
  * Hagberg et al. [2008] A. A. Hagberg, D. A. Schult, P. J. Swart,  Exploring network structure, dynamics, and function using networkx,  in: G. Varoquaux, T. Vaught, J. Millman (Eds.), Proceedings of the 7th Python in Science Conference, Pasadena, CA USA, pp. 11 – 15.
  * Gurobi Optimization, Inc. [2016] Gurobi Optimization, Inc., Gurobi optimizer reference manual, 2016.
  * Alleghany county public schools [2016] Alleghany county public schools, School bus per-mile operating cost analysis, 2016.
  * Ridester Staff [2018] Ridester Staff, The comprehensive guide: How much does uber cost?, https://www.ridester.com/uber-rates-cost, 2018.

##  Appendix A Heuristic Insertion Path-TSP Solver

One of the most time-consuming parts in our decomposition method through the
shareability network is generating the bus trip list $T_{b}$. In Algorithm 1,
we need to solve a path-TSP every time we find a clique in the shareability
network to determine the feasibility of this trip. The path-TSP itself is NP-
hard and it takes an off-the-shelf solver seconds to solve even with small
amount of students as the input. The problem becomes intractable if we have to
check millions of cliques in the Algorithm 1. Therefore, we propose a
heuristic insertion path-TSP solving technique to decrease the computation
time while outputting the satisfying feasible bus trip list $T_{b}$.

Algorithm 3 Trips feasibility check with the heuristic inserting path-TSP
solving technique. Input: a feasible bus trip $\tau\in T_{b}$, the optimal
route $p_{\tau}^{*}$ for the trip $\tau$, the optimal travel time
$t_{\tau}^{*}$ for the trip $\tau$, a student $s$, maximum travel time
$t^{max}$, bus capacity $C$, travel time function between any two vertices in
the road network $\\{t_{ij}|\forall i,j\in V_{r}\\}$

1:function
HeuristicFeasibilityCheck($\tau,p_{\tau}^{*},t_{\tau}^{*},s,t^{max},C,\\{t_{ij}|\forall
i,j\in V_{r}\\}$)

2: $n\leftarrow|S(\tau)|$

3: $p_{\tau}^{*}:=[s_{1},s_{2},...,s_{n}]$

4: $t^{*}\leftarrow\infty,p^{*}\leftarrow\emptyset$

5: for $i$ in $[0,1,...,n]$ do

6: if i = 0 then

7: $t^{\prime}\leftarrow t_{v_{s}v_{s_{1}}}+t_{\tau}^{*}$

8: if $t^{\prime}<t^{*}$ then

9: $t^{*}\leftarrow t^{\prime};p^{*}\leftarrow[s,s_{1},s_{2},...,s_{n}]$

10: else if i = n then

11: $t^{\prime}\leftarrow
t_{v_{s_{n}}v_{s}}+t_{v_{s}v_{d}}-t_{v_{s_{n}}v_{d}}+t_{\tau}^{*}$

12: if $t^{\prime}<t^{*}$ then

13: $t^{*}\leftarrow t^{\prime};p^{*}\leftarrow[s_{1},s_{2},...,s_{n},s]$

14: else

15: $t^{\prime}\leftarrow
t_{v_{s_{i}}v_{s}}+t_{v_{s}v_{s_{i+1}}}-t_{v_{s_{i}}v_{s_{i+1}}}+t_{\tau}^{*}$

16: if $t^{\prime}<t^{*}$ then

17: $t^{*}\leftarrow
t^{\prime};p^{*}\leftarrow[s_{1},...,s_{i},s,s_{i+1},...,s_{n}]$

18: if $t^{*}\leq t^{max}$ and $|S(\tau)|+1\leq C$ then

19: return true

20: else

21: return false

The essential idea of this heuristic insertion path-TSP solving technique is
that if we know the optimal path $p^{*}$ for a set of $k$ students $S_{k}$, we
generate a sub-optimal path for $k+1$ students $S_{k}\cup\\{s\\}$ by fixing
$p^{*}$ and inserting the student $s$ into the order of $p^{*}$ where yields a
path with the minimal travel time. To be specific, we modified the function
$\textsf{{FeasibilityCheck}}(\tau,t_{m}ax,C,\textsf{{PathTsp}}(\cdot))$ to
Algorithm 3. For the input of Algorithm 3, we need the optimal path and travel
time for a feasible trip $\tau$. We can store the optimal routes and travel
time once we generate a feasible trip $\tau$ with $k$ students, which will be
used when considering trips with $k+1$ students.

Algorithm 3 yields a sub-optimal route and travel time within linear time. The
experiment results in the section 5 show the routes computed by Algorithm 3
are decent.

##  Appendix B Experiment Results: Boston Public Schools (BPS) Synthetic
Benchmark Data

This section shows the experiment results for best school bus schedules given
synthetic data from Boston Public School (BPS). For figures in the following,
the red star denotes the school location, blue dots represent student
locations and red crosses indicate students who take dedicated vehicles.

Figure 8: School bus schedules for Tommy Harper (Optimal) Figure 9: School bus
schedules for Craig Kimbrel (Optimal) Figure 10: School bus schedules for
Deven Marrero (Optimal) Figure 11: School bus schedules for Frank Malzone
(sub-optimal with $\beta=1.2$, $\gamma=0.3$) Figure 12: School bus schedules
for Dick Williams (Optimal) Figure 13: School bus schedules for Dick Bresciani
(sub-optimal with $\beta=1.3$, $\gamma=0.4$) Figure 14: School bus schedules
for Dutch Leonard (sub-optimal with $\beta=2$, $\gamma=0.4$) Figure 15: School
bus schedules for Christian Vazquez (sub-optimal with $\beta=3$, $\gamma=0.4$)
Figure 16: School bus schedules for Dennis Eckerley (sub-optimal with
$\beta=2$, $\gamma=0.4$) Figure 17: School bus schedules for Rick Ferrell
(sub-optimal with $\beta=2.5$, $\gamma=0.4$)

##  Appendix C Benchmark Results

This section states the school bus schedules comparisons between the
shareability network based decomposition approach and BiRD algorithm. For
figures in the following, red stars represent school locations and blue dots
denote student locations.

(a) SND

(b) BiRD

Figure 18: Bus routes comparison for Tommy Harper

(a) SND

(b) BiRD

Figure 19: Bus routes comparison for Craig Kimbrel

(a) SND

(b) BiRD

Figure 20: Bus routes comparison for Deven Marrero

(a) SND

(b) BiRD

Figure 21: Bus routes comparison for Frank Malzone

(a) SND

(b) BiRD

Figure 22: Bus routes comparison for Dick Williams

(a) SND

(b) BiRD

Figure 23: Bus routes comparison for Dick Bresciani

(a) SND

(b) BiRD

Figure 24: Bus routes comparison for Dutch Leonard

(a) SND

(b) BiRD

Figure 25: Bus routes comparison for Christian Vazquez

(a) SND

(b) BiRD

Figure 26: Bus routes comparison for Dennis Eckerley

(a) SND

(b) BiRD

Figure 27: Bus routes comparison for Rick Ferrell