Walking Bus Challenge¹

Problem Description

An elementary school want to setup a walking bus system for its students.

A walking bus (pedibus in Italian) is a form of student transport for schoolchildren who,
chaperoned by two adults (usually a driver leads and a conductor follows), walk to school, in
much the same way a school bus would drive them to school. Like a traditional bus, walking
buses have a fixed route with designated bus stops in which they pick up children (The walking
bus definition is courtesy of Wikipedia).

The routes of the walking bus system must serve all students joining the initiative. A route
starts form a bus stop, goes through other bus stops and ends at the school. All students on the
route must be picked-up. Routes can merge but cannot split after merging. No student must
travel more than alpha times the shortest path from his bus stop to the school. The design of
the routes should ensure students’ safety minimizing the risk involved in the path from home to
school.

It is your duty as manager of the school to define all the routes for the walking bus system
taking into account all requirements and minimizing the number of chaperons involved. In other
words, the number of routes composing the walking bus system must be minimized.

From a more abstract point of view: consider a complete graph G = (N, A). Set N = {0..n}
is the set of nodes, node 0 is the school and all other nodes represent bus stops. Set A =
(i, j) : i ∈ N, j ∈ N is the set of arcs representing connections among nodes. For each pair of
nodes i ∈ N, j ∈ N : (i, j) ∈ A the length and the dangerousness of the shortest path, c_i,j, d_i,j,
from node i to node j is known; c_0,j = ∞ ∀j ∈ N \ {0}.

For the purpose of this challenge we only take into account graphs in which the length of
the shortest path c ij is equal to the euclidean distance from node i to node j (the triangular
inequality holds).

The walking bus problem can be seen as a special case of spanning tree problem. In this
problem we want to find the feasible spanning tree, rooted in 0, for graph G with the minimum
number of leaves (primary objective function). A spanning tree is consider as feasible in the
walking bus problem if no node is distant from 0 more than alpha times the shortest path from
the node to 0 (that is c_0,j). The walking bus problem takes also into account an additional
objective function that is the minimization of the total dangerousness of the paths selected as
routes for the walking bus (secondary objective function). The total dangerousness is computed
as the sum of the risk (d_i,j) associated with all the arcs composing the walking bus network.
This objective function is less important than the minimization of the number of leaves and it
is only used in order to differentiate among solutions with the same number of leaves.

Results evaluation criteria

Solvers will be evaluated and ranked using a set of 10 instances. This evaluation set is not the
same as the test set provided to the participants. However instances in the evaluation set have
the same structure and size of the instances in the test set.
Three different criteria will be considered for the evaluation. From the most to the less
important:

1. Number of leaves. Minimizing the number of adults supervisors (number of leaves) required for the walking
   bus is the main goal. Given two feasible solutions S₁ and S₂ for the same instance lets call
   L₁ and L₂ the number of leaves in the spanning tree defined by S₁ and S₂ respectively. If
   L₁ < L₂ then S₁ is better than S₂.
2. Risk. If two feasible solutions S₁ and S₂ have the same number of leaves then the solution
   described by the less dangerous (in terms of d_ij) spanning three prevails. Lets call D₁ and
   D₂ the sum of d_ij for all arcs (i, j) used in solutions S₁ and S₂ respectively. If L₁ = L₂
   and D₁ < D₂ then S₁ is better than S₂.
3. Computational time. The faster the better. If L₁ = L₂ and D₁ = D₂ then the solving time is considered. Lets
   call T₁ and T₂ the time required in order to obtain S₁ and S₂ respectively. If L₁ = L₂ and
   D₁ = D₂ and T₁ < T₂ then S₁ is better than S₂.

1: project for Foundations of Operations Research course at Politecnico di Milano