In routing special-education students in an urban environment, the students must be picked up at home and delivered to selected schools which meet their specific educational needs. In addition to the many-to-several problem structure, special sequencing restrictions and route duration limitations exist. Heuristics can achieve significant savings for both route distance and route duration, and a shuttle system is also found to be effective.

Federal guidelines require that transportation be provided by public school systems to allow all students an equal opportunity for an education. The implication for transportation planners of public school systems is that school bus routes must be maintained for special-education students as well as nonspecial-education students.

The geographic dispersion of special-education schools and students tends to make their routes significantly longer than neighborhood routes for nonspecial-education students. Typically, a special-education student is picked up at home and delivered to a school specializing in the student’s particular disability. The diversity of student needs often causes special-education routes to have several destination schools. Nonspecial-education students are picked up at grouped locations typically in a given neighborhood and usually delivered to only one local school. Most of the literature on school bus routing has focused on the general education routing problem. A scientific analysis of special-education routes could lead to more efficient routes with reduced operating costs to the school system and a higher level of service for the students. This scientific analysis should also be applicable to many private school systems that have two or more school locations.

The Tulsa Public School System in Tulsa, Oklahoma has approximately 850 special-education students whose special needs are served by 66 different schools in the Tulsa area. The many-to-several nature of the routing problem derives from the fact that many students are picked up and delivered to several schools on the route. The maximum daily total ride time for a student is limited to three hours, but the school system strives for a limit of 45 minutes ride time per trip. The 45-minute goal is not always achieved in the current system of bus routes; elementary and secondary students are sometimes served by the same bus even though elementary and secondary schools starting times are staggered by 45 minutes.

We present two heuristic methods for generating efficient special-education bus routes. A heuristic approach is necessary given the computational complexity and the large-scale nature of the problem. Recent advances in optimization-based techniques (see Crowder and Padberg [1980]) for the symmetric traveling salesman problem are promising but do not yet offer a practical alternative for large-scale problems with side conditions.

Previous Work

A significant body of literature exists on the general school-bus-routing problem, and several commercial software packages are available. The general school-bus-routing problem is usually many-to-one in that many students in a local neighborhood are delivered to one school. Several researchers have developed specialized computer-assisted methods; to our knowledge, however, none has addressed the many-to-several nature of the special-education routing problem.

The many-to-several problem can be viewed as a special case of two types of routing problems which have appeared in the literature. The general vehicle dispatch or vehicle-routing problem [1959] has received too much attention in the literature to completely enumerate. The many-to-several problem can be viewed as an extension of the vehicle-routing problem in which not all collection points have the same destination, and special sequencing restrictions exist. The many-to-several problem can also be viewed as a special case of the subscriber dial-a-ride problem. The dial-a-ride problem first addressed by Wilson et al. [1976] is generally a many-to-many type of problem. Wilson et al. employ a relatively simple tour-building insertion-type procedure. Sexton and Bodin [1981] have developed an integer programming model with an associated heuristic for a more complex single vehicle many-to-many problem with desired delivery times. Their approach was successful on the Baltimore, Maryland paratransit system, involving up to 97 customers.

Problem Specifics

The special-education routing problem of the Tulsa Public School System is a multiple vehicle problem which has a relatively static demand pattern. Student demand varies slightly on a daily basis because of absences, residence changes, and new students moving into the school district. There are two types of special-education routes. The first type involves severely handicapped students who require a special school because they cannot function at a nonspecialized public school. The majority of these students are elementary students. However, approximately 14 percent are emotionally disturbed secondary students who are segregated from the elementary students and require separate routes. The buses are specially equipped with a hydraulic lift and must accommodate wheelchairs. In the spring of 1985, the transportation department was responsible for transporting 148 severely handicapped students.

The other types of routes involve special-education students who are less disabled but require transportation to a school that has a program for their special needs. Both elementary and secondary students are transported via the regular special-education routes. Approximately 700 students required 35 routes.

The school system currently generates special-education routes manually. An experienced transportation planner spends approximately two weeks before the beginning of each school year developing routes. Her only tools are her experience, the students’ and schools’ addresses, and a large city map. Initially, the routes are conservatively designed to accommodate future student moves into and out of the school district. As the school year progresses, the routes are modified slightly to better accommodate these changes.

Two Heuristics

In developing computer-based solutions to the many-to-several routing problem, a modified “savings” type heuristic was employed. The Clarke-Wright savings algorithm [1964] is well known and reasonably efficient in tackling large-scale problems. The Clarke-Wright algorithm is a savings/insertion algorithm in that at each step an existing pair of routes are combined into a singe route yielding a specified distance savings. Initially, it is assumed that every two demand points i and j are served by different vehicles. The basic Clarke-Wright savings algorithm is modified for the many-to-several problem by observing that two points (students) i and j have a destination (school) that is not the vehicle depot. The details of the modification are presented in the appendix. The goal is to create routes that are compact and have as few school destinations as possible. Having few school destinations on a given route facilitates distance and time minimization since each stop takes time, and the schools are geographically dispersed.

The original Clarke-Wright algorithm is a lockstep procedure that fixes the sequence of students and schools as students are combined on routes. However, in our modification we choose to resequence the relative positions of the schools on the route after the routes are combined. Furthermore, we use a modified 3-opt traveling salesman heuristic to resequence the students and schools on all final routes. This 3-opt modification improves solution quality but also significantly reduces computational efficiency.

The second approach is an adaptation of the M-TOUR algorithm that Russell [1977] developed for the general vehicle dispatch problem with side conditions. M-TOUR generalizes the highly effective Lin and Kernighan [1973] traveling salesman algorithm to include multiple vehicles and various side conditions. M-TOUR is an improvement/exchange type of heuristic in that it begins with a feasible solution and successively attempts to exchange links between points that are currently not in a route with those that are in order to achieve a distance reduction. The algorithm stops when no link exchanges can be found that yield an improvement.

The M-TOUR algorithm has been very effective in generating “near optimal” solutions to routing problems. It is flexible in that it can address a variety of side conditions.

To Shuttle or Not to Shuttle

In the spring of 1985, the Tulsa Public School special-education routing problem was examined in the context of a faculty-student research project. New management of the transportation operations was interested in ways to improve operations and reduce costs. Procedures and data bases were being computerized, and microcomputers were available to help design and develop school bus routes. The transportation management was interested in experimenting with the smaller routes for severely handicapped students. If the results were successful, the routing analysis was to be applied to the regular special-education routes in the following year.

One significant change in 1985 was that a shuttle system was instituted to help reduce student ride time and the number of schools to which each bus must deliver students. In the shuttle system, the buses picked up students and then traveled to one of two special-education schools. Those students who were at the appropriate destination school were unloaded. The remaining students were reallocated among the buses depending upon the next designated destination of each bus. In the shuttle, no bus had to travel to more than two schools. In the shuttle system, compact routes could be developed without concern for putting students with “similar destinations” on a given bus. The disadvantage was that timing had to be more precise because dependencies were created between buses.

Both the modified Clarke-Wright and M-TOUR algorithms can be applied in the context of a pure many-to-several problem or a many-to-several problem with a shuttle system. In order to determine the most effective approach to the special-education routing problem, we compared the four methods together with the school system’s existing manual solution. When the initial data were collected, 148 severely-handicapped students traveled on 11 bus routes. Eight of the buses were garaged at the central transportation warehouse and three were stationed at an elementary school on the west side of the city; this school was not a special-education school. We addressed the multiple-depot aspect of the problem by determining which students were best served by each depot. This analysis resulted in seven routes emanating from the central facility and four from the western depot.

The results of the routing analysis are shown in Table 1. The route distance corresponds to computer estimated route miles based on the rectangular distance metric. All methods assumed a bus capacity of 18 students in order to limit the maximum duration of the routes and used eleven buses. No attempt was made to reduce the number of buses since management was more interested in reducing ride time and improving the level of service. However, because bus driver turnover is high, reducing the number of required buses might be considered in the future.

The 3-opt heuristic proved to be a worthwhile enhancement to the Clarke-Wright approach. The modified Clarke-Wright heuristic was able to cluster students and schools more effectively than the manual approach. Also, given the Clarke-Wright generated solution, the M-TOUR algorithm was able to make a slight improvement in the route design. Most routes were generated with one, two, or three school destinations. Management favored routes having no more than two school destinations unless the schools were located in close proximity. For this reason, a shuttle system was developed manually for four of the buses on the M-TOUR generated routes.

We presented listings of the routes together with illustrative graphs to the transportation department management. During their evaluation, they decided to eliminate the western depot and start all routes from the central depot because gasoline storage tanks could not be located at the western depot. We reformed the entire routing analysis again for the one central depot. The transportation planner also requested that the two routes for severely handicapped emotionally disturbed students be left intact and removed from the analysis. Demographic changes caused these routes to be redefined to consist of 140 students and nine buses.

Given the updated student data file and management’s preference for a shuttle system, we tried a pure shuttle approach. In this approach, the destination schools are initially ignored, and each route is forced to end at one of the two shuttle locations. The two shuttle locations are approximately five miles apart and are the two schools with the most student demand. The pure shuttle approach was more effective in generating compact routes and reducing the number of destination schools for some of the routes. The shuttle approach can be implemented with the many-to-several heuristics by artificially specifying the student destination as the shuttle location. The shuttle system can also be implemented with other vehicle-routing methods in which destinations other than the central depot can be specified.

To complete the shuttle system the buses must be assigned to a final destination school from the shuttle location. Additionally, many students must be reassigned to a different bus at the shuttle location. The bus and student assignment process is relatively straightforward and can be done manually (once each semester). In this case the routing methodology serves as a decision support tool, but does not provide a “turnkey” solution to the entire shuttle decision problem.

The shuttle system that was designed limited the number of school destinations to two per route. It also required staggered route starting times and introduced interdependencies among the routes. However, the shuttle system offered an effective solution to a difficult problem. Given the newer data with the single depot, 140 students and nine buses, the routing analysis was able to achieve a 12.4 percent projected distance reduction compared to the manually derived solution. We hypothesized that the routes generated from the earlier multiple depot routing analysis facilitated a “learning phenomenon” on the part of the transportation planner. The manually derived routes for the single depot problem were significantly better than the manual routes for the earlier multiple depot problem.

Actual Results

In order to measure the actual success of the routing analysis, we collected data pertaining to route distances and duration prior to implementation of the computer generated routes. In April of 1985, the Transportation Department implemented the new routes in two stages. Initially the bus drivers were given only the student names, addresses, and the sequence in which to pick them up and no further directions.

This change in the middle of the school year resulted in some negative reactions from both the drivers and the parents of the students. Some drivers resisted the shorter routes that could reduce their driving time and their wages. Other drivers had made special pick-up and delivery arrangements with some parents to accommodate their work schedules. Drivers complained legitimately about routes that ignored natural barriers such as rivers and other pitfalls such as one-way and dead-end streets. After four days, the drivers were given the opportunity to offer their own refinements to the routes (Table 2).

The actual mileage reduction of 10.9 percent was very close to the computer predicted 12.4 percent. Additionally, the Transportation Department had adjusted the shuttle system so that buses were only pairwise dependent. This resulted in less wait time for buses to deliver shuttled students. The 15.8 percent improvement figure is relative to the single depot phase of the routing analysis. The total savings since analysis of the original multiple depot problem is significantly greater.

Previous experience suggests that the potential for savings is much greater on the larger 700 student regular special-education routes. Generally accepted accounting procedures specify a standard operating cost of $0.38 per mile for school buses. Given an estimated annual driving distance of 800,000 bus miles per year for special-education students, we estimate that the Tulsa Public School System has the potential to save from $50,000 to $100,000 through the special-education routing analysis.

Since the 700 student regular special-education routes will require significantly more computer resources, a streamlined version of the Clarke-Wright algorithm as well as the modified Clarke-Wright algorithm (as described in the appendix) has been coded in FORTRAN IV and installed on the school system’s IBM PC. Execution times (with an 8087 math coprocessor) for the 140 student problem are approximately three and 17 minutes respectively.

Preliminary analysis of the larger problem indicates that effective routes can be generated using only the modified Clarke-Wright algorithm. Routes are limited to a maximum of five destination schools. Enforcing a limit of five destination schools per route yields an effective solution that potentially eliminates four buses. It appears feasible to implement these routes without the aid of a shuttle system. However, in future applications a shuttle system could be used to revise those computer generated routes that are unsatisfactory either because of excessive length or duration.

On the regular special-education routes, elementary and secondary students will sometimes ride the same bus. This introduces a sequencing complication in that classes for secondary students start and finish 45 minutes earlier than for elementary students. Thus, secondary students should be delivered before elementary students in the morning and picked up before elementary students in the afternoon. The shuttle system offers a partial solution to this problem. The many-to-several heuristics also have the capability to distinguish between elementary and secondary schools. If necessary, a sequencing constraint can be specified which requires delivery to secondary schools prior to delivery to elementary schools.

These routing methodologies can be implemented on a stand-alone basis or in the context of a shuttle system. In either case they can be readily implemented by a transportation planner on a relatively low-cost personal computer system. The Transportation Department of the Tulsa Public School System has gained an appreciation for the value of a systematic management science approach.

Actual Results

We thank Karen Bartholomew and Robert Haddox of the Tulsa Public School System for their cooperation and the data they provided. We also thank John Musgrove for his help in earlier efforts on this project.

APPENDIX

We will briefly indicate how the Clarke-Wright savings algorithm is modified to accommodate the several destination schools at the end of a route. Denoting students by circular nodes and schools by triangular nodes, Figure 1 shows two students i and j who have school k as a common destination.
The initial route structure in Figure 1a illustrates the individual route for each student consisting of a delivery at his respective school before the bus returns to the depot. Figure 1b illustrates the route sequence when i and j are combined on one route and delivered to a common destination. The resulting savings are calculated as:

Equation 1: Sij = djk + dkl + dljdij

Whenever two students do not share the same destination, the savings calculation is slightly different. Assume that student i attends school k and student j attends school m. The savings calculation is:

Equation 2: Sij = Max[(dik + dkl + dlj + djmdijdjkdkm), (dik + dlj + dmldijdmk)]

Figure 2 illustrates the two combined route alternatives.

The savings calculations illustrated by Figures 1 and 2 are only applicable to initial pair combinations. As points are combined into routes, a more complex set of alternatives is generated. After each linking of students, the sequence of the destination schools on the newly formed route is changed if an improvement would result. Finally, once all the routes are formed, a 3-opt traveling salesman heuristic is used to resequence the students and schools on a given route.

References

Clarke, G. and Wright, J. 1964, “Scheduling of vehicles from a central depot to a number of delivery points,” Operations Research, Vol. 12, No. 4 (July-August), pp. 568-581.

Crowder, H. and Padberg, M. W. 1980, “Solving large-scale symmetric traveling sales problems to optimality,” Management Science, Vol. 26, NO. 5 (May), pp. 495-509.

Dantzig, G. B. and Ramser, J. H., 1959, “The truck dispatching problem,” Management Science, Vol 6, No. 1 (October), pp. 80-91.

Lin, S and Kernighan, B. 1973, “An effective heuristic algorithm for the traveling salesman problem,” Operations Research, Vol. 21, No. 2 (March-April), pp.498-516.

Russell, R. 1977, “An effective heuristic for the M-TOUR traveling salesman problem with some wide conditions,” Operations Research, Vol. 25, No. 3 (May-June) pp.517-524.

Sexton, T. R. and Bodin, L. D. 1981, “The single vehicle many-to-many routing and scheduling problem with desired delivery times,” working paper.

Wilson, N. H. M. et al. 1976, “Advanced dial-a-ride algorithms research project: Final report,” Massachusetts Institute of Technology, Department of Materials Science and Engineering, Technical Report R76-20 (March).

A letter from Bob Haddox, Supervisor of Transportation, Tulsa Public Schools, states: “Nine developmental special-education routes were tested using the computer program provided and the results were as follows:
1. A mileage reduction of approximately 11 percent occurred on the routes tested.
2. Based upon 11 percent times the 800,000 annual miles driven by the special-education department, we calculated a potential savings of 80,000 miles per year was possible.
3. Based upon a 0.38 cents per mile cost factor, potential savings of over $30,000 was possible.
Additionally, if use of the existing computer program tested by our department were expanded to other suitable routes, potential savings of between $30,000 to $80,000 was possible.”

Table 1: A comparison of five approaches to the many-to-several problem.
Method Manual with Shuttle Clarke-Wright Clarke-Wright with 3-opt M-TOUR M-TOUR with Shuttle
Route Distance 509 409.0 354.0 344.0 364.0
Improvement 19.7% 30.4% 32.4% 28.5%

 

Table 2: The total daily route mileage and durations based on actual odometer readings for the refined routes
Method Manual with Shuttle M-TOUR with Shuttle
Route Distance 375 miles 334 miles
Route Duration 26 hours 21.9 hours
Improvement: miles 10.9%
Improvement: time 15.8%

A PDF reprint of the article is available HERE.