Optimization based planning of Pedibus lines: An arc based approach

Pedibus, also known as the Walking School Bus, is a popular system in Western countries aimed at increasing the percentage of children walking to school, reducing vehicular congestion at school gates, and legitimating walking as a mobility mode. In its simplest version, a Pedibus line is a sequence of stops starting from a child home, visiting a sequence of other children's home, and ending at the school. The service is usually run by volunteers, according to common sense based rules. This paper aims at providing optimization based methodological support to decision makers. The line design problem can be described as follows: given the school location, the children home addresses, and the distance between each pair of locations, we have to design a minimum number of lines rooted at the school so that each location belongs to one line and the distance from school to each location along the line is below a given threshold. The objective function is due to the need for adults supervising each line, whose limited availability may hamper the service long term viability. A secondary objective encourages line merging before destination. Heuristic solution approaches to the design of Pedibus lines have been proposed in the literature, considering Pedibus as a mere application of the school bus routing problem. We propose a new arc-based model tailored on the Pedibus features, i.e., allowing lines merging, which yields a constrained spanning tree network structure. Tests on real and realistic networks show that small and medium size instances are solved to optimality, while the weak linear relaxation of the proposed arc model prevents fast convergence so that largest instances with longest walking distances are solved heuristically. This work paves the way to further studies on path based models to speed up convergence to optimality and to encompass different Pedibus variants.