Browse Prior Art Database

School Bus Scheduling with Several Objectives

IP.com Disclosure Number: IPCOM000074979D
Original Publication Date: 1971-Jul-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 3 page(s) / 55K

Publishing Venue

IBM

Related People

Bennett, BT: AUTHOR [+2]

Abstract

A procedure is described for the designing of school bus routes by computer. The objectives include the reduction of student travel time, U-turns and bus overloading as well as the reduction of bus travel time. The procedure can also handle one way streets, a bus garage other than at the school site, and the requirement that at certain stops the bus must pick up children from one particular side of the road. The procedure is an extension of the Clarke and Wright algorithm for scheduling delivery vehicles.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

School Bus Scheduling with Several Objectives

A procedure is described for the designing of school bus routes by computer. The objectives include the reduction of student travel time, U-turns and bus overloading as well as the reduction of bus travel time. The procedure can also handle one way streets, a bus garage other than at the school site, and the requirement that at certain stops the bus must pick up children from one particular side of the road. The procedure is an extension of the Clarke and Wright algorithm for scheduling delivery vehicles.

The objectives are combined to define a total cost of a set of routes as the sum over all routes of: bus travel time + alpha x student travel time + beta x the number of bus stops which are incorrectly approached or involve a U-turn. + delta x the bus overloading (over recommended capacity) where alpha, beta and delta are arbitrary weights. Routes are further constrained by a maximum bus capacity, an absolute time limit and a time limit for the journey of the first child picked up.

The overall process consists of four phases.

1) Distance and speed data for every usable road between adjacent intersections and between bus stops, schools and garages and their adjacent intersections is processed by a shortest path routine.

For every pair of bus stops, every bus stop and school, every garage and bus stop. the shortest travel time and the first and last intersections on the route other than the bus stops themselves are recorded.

2) For each set of bus stops serviced by one school and one garage, a savings file is created. For each pair (i,j) of bus stops, the savings S(ij) in bus travel time accomplished by connecting a route whose last stop is stop i to a route whose first stop is stop j is S(ij) = T(is) + T(gj) - T(ij) where T(is) is the travel time between i and the school, T(gj) is the travel time between the garage and stop j and T(ij) is the travel time from i to j. Included in the record for each pair are the last intersection on the route from garage to stop i and the first intersection on the route f...