A GENETIC ALGORITHM FOR SERVICE LEVEL BASED VEHICLE SCHEDULING

In many practical applications, vehicle scheduling problems involve mo re complex evaluation criteria than simple distance or travel time min imization. Scheduling to minimize delays between the accumulation and delivery of correspondence represents a class of vehicle scheduling pr oblems, where: the evaluation of candidate solutions is costly, there are no efficient schemes for evaluation of partial solutions or pertur bations to existing solutions, and dimensionality is limiting even for problems with relatively few locations. Several features of genetic a lgorithms (GA's) suggest that they may have advantages relative to alt ernative heuristic solution algorithms for such problems. These includ e ease of implementation through efficient coding of solution alternat ives, simultaneous emphasis on global as well as local search, and the use of randomization in the search process. In addition, a GA may rea lize advantages usually associated with interactive methods by replica ting the positive attributes of existing solutions in the search proce ss, without explicitly defining or measuring these attributes. This st udy investigates these potential advantages through application of a G A to a service level based vehicle scheduling problem. The procedure i s demonstrated for a vehicle scheduling problem with 15 locations wher e the objective is to minimize the time between the accumulation of co rrespondence at each location and delivery to destination locations. T he results suggest that genetic algorithms can be effective for findin g good quality scheduling solutions with only limited search of the so lution space.