A Heuristic Algorithm for School Bus Routing with Bus Stop Selection

In this paper a heuristic algorithm is proposed for a school bus routing problem which is formulated as a capacitated and time-constrained open vehicle routing problem with a homogeneous fleet and single loads. The algorithm determines the selection of bus stops from a set of potential stops, the assignment of students to the selected bus stops, and the routes along the selected bus stops. Its goals are to minimize the number of buses used, the total route journey time and the student walking distances. It also aims at balancing route journey times between buses. The performance of the algorithm is evaluated on a set of twenty real-world problem instances and compared against solutions achieved by a mixed integer programming model. Reported results indicate that the heuristic algorithm finds high-quality solutions in very short amounts of computational time.

The research work disclosed in this publication is supported by the Tertiary Education Scholarships Scheme (TESS, Malta).

Authors and Affiliations

1. School of Mathematics, Cardiff University, Cardiff, CF24 4AG, Wales

   Monique Sciortino, Rhyd Lewis & Jonathan Thompson

Corresponding author

Correspondence to Monique Sciortino .

Editors and Affiliations

1. Aberystwyth University, Aberystwyth, UK

   Christine Zarges

2. Université du Littoral Côte d'Opale, Calais, France

   Sébastien Verel

Appendix

The MIP model presented here produces solutions consisting of cycles that start and end at the school. The arc from the school to the first bus stop in each route is then excluded. This is possible by assuming that the driving time from the school to any stop is zero.

The decision variables of our model are as follows. Binary variable \(x_{uvR}\) indicates whether route \(R \in \mathcal {R}\) travels from \(u \in V_1\) to \(v \in V_1 \setminus \{u\}\). Binary variable \(y_{vR}\) indicates whether route \(R \in \mathcal {R}\) visits \(v \in V_1\). Also, binary variable \(z_{wv}\) indicates whether students in address \(w \in V_2\) walk to stop \(v \in V_1 \setminus \{v_0\}\). Variable \(s_{vR} \in \{0,1,\ldots ,C\}\) gives the number of students boarding route \(R \in \mathcal {R}\) from stop \(v \in V_1 \setminus \{v_0\}\). Moreover, variable \(l_{vR} \in \{0,1,\ldots ,C\}\) gives the total load of route \(R \in \mathcal {R}\) just after visiting stop \(v \in V_1 \setminus \{v_0\}\). Finally, variable \(t_R \in [0,m_{t }]\) specifies the total journey time of route \(R \in \mathcal {R}\). The MIP formulation is as follows:

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(19)

Objective function (8) minimizes the total journey time of all routes. Constraints (9)–(11) relate to stop and school visits. Constraints (9)–(10) guarantee that if route \(R \in \mathcal {R}\) visits \(v \in V_1\), then route R should enter and leave v exactly once. Next, Constraints (11) force each route \(R \in \mathcal {R}\) to visit school \(v_0\) whenever it visits at least one stop \(v\in V_1 \setminus \{v_0\}\). Constraints (12)–(14) relate to student walks and pickups. Constraints (12) ensure that students living in each address \(w \in V_2\) walk to exactly one stop within walking distance \(m_{w }\). Constraints (13) assure that no student walks to an unvisited stop, while Constraints (14) guarantee that the total number of students boarding from stop \(v \in V_1 \setminus \{v_0\}\) is equal to the total number of students walking to that stop. Constraints (15)–(16) relate to student boardings. These constraints force the number of students boarding route \(R \in \mathcal {R}\) from stop \(v \in V_1 \setminus \{v_0\}\) to be 0 if route R does not visit stop v. If route R visits stop v, then (15) also updates the lower bound on the number of boarding students to 1. In addition, Constraints (17)–(18) relate to route loads and also serve as subtour elimination constraints as proposed in [14]. Note that \(l_{v_0R} = 0 \; \forall R \in \mathcal {R}\). These constraints guarantee that no route contains a subtour disconnected from school \(v_0\) and that each route load increases in accordance to the number of students boarding the bus on that route. In fact, if route \(R \in \mathcal {R}\) goes from \(u \in V_1\) to stop \(v \in V_1 \setminus \{u,v_0\}\), then the load of route R just after visiting stop v is set equal to the sum of the load of route R just after visiting u and the number of students boarding route R from stop v. Finally, Constraints (19) calculate the total journey time of each route \(R \in \mathcal {R}\).

Reprints and permissions

© 2021 Springer Nature Switzerland AG

Policies and ethics