Helicopter Routing for Maintaining Remote Sites in Alaska using a Genetic Algorithm

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 20

Student Abstracts

The Department of Fish and Game keeps observational sites in remote locations for such purposes as counting fish, measuring weather, and various research projects. In Alaska, fishing and natural tourism are vital to the economy of the state, making these measurements all the more important. However, due to large geographic spread with little transportation infrastructure (none, between many villages), helicopters must be used to visit these sites. It is extremely expensive, primarily in fuel costs, to fly helicopters all over the state, so optimal or near-optimal routing of these helicopters is paramount. Currently, the "by-eye" technique is used, in which a route is chosen that simply looks like it would have the lowest total distance. The well-known underlying problem at hand is the Vehicle Routing Problem (or VRP) in which a fleet of vehicles with a given capacity must make deliveries to a set of sites (Toth and Vigo 2001); this variant, however, only includes a subset of the problem specification. The primary changes from the basic VRP problem are the existence of multiple depots and the use of a single vehicle to visit all sites. A real-valued fuel constraint replaces the bin-packing constraints, essentially relaxing the bin-packing aspect of the problem. The particular variant described above is not addressed specifically in previous research; therefore, in this project, a genetic algorithm (GA) was created with a simple genome and a novel crossover technique in an attempt to produce better solutions for this simpler variant. Good results were achieved for ten and twenty-node graphs (reasonable and better than the "by-eye" technique). Further testing and fine-tuning is required before testing the algorithm against a standard algorithm for the more general problem, to see if this solution in fact outperforms standard algorithms for this simpler variant.