In the scheduling situation considered here, we are given a set of routes, each associated with a particular school. A single bus is assigned to each route, picking up the students and arriving at their school within ...
详细信息
In the scheduling situation considered here, we are given a set of routes, each associated with a particular school. A single bus is assigned to each route, picking up the students and arriving at their school within a specified time window. The scheduling problem is to find the fewest buses needed to cover all the routes while meeting the time window specifications. We present two integerprogramming formulations of the scheduling problem and apply them to actual data from New Haven, Connecticut for two different years, as well as to 30 randomly generated problems. linearprogrammingrelaxations of these integerprograms were found to produce integer solutions more than 75 percent of the time. In the remaining cases, we found that the few fractional values can be adjusted to integer values without increasing the number of buses needed. Our method reduces the number of buses needed by about 25 percent compared to the manual solutions developed by the New Haven school bus scheduler.
暂无评论