GIDEON: a genetic algorithm system for vehicle routing with time windows

Abstract

Addresses the vehicle routing problem with time windows (VRPTW). The VRPTW involves routing a fleet of vehicles, of limited capacity and travel time, from a central depot to a set of geographically dispersed customers with known demands within specified time windows. The authors describe GIDEON, a genetic algorithm system to heuristically solve the VRPTW. GIDEON consists of two distinct modules: a global clustering module that assigns customers to vehicles by a process called genetic sectoring (GENSECT) and a local route optimization module (SWITCH-OPT). On a standard set of 56 VRPTW problems obtained from the literature, GIDEON did better than the alternate methods on 41 of them, with an average reduction of 3.9% in fleet size and 4.4% in distance traveled for the 56 problems. GIDEON took an average of 127 CPU seconds to solve a problem on the Solbourne 5/802 computer.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>