A visual interactive approach to vehicle routing

摘要

This paper describes a graphical-user-interface and a heuristic based on a greedy randomised adaptive search procedure which have been developed to work in combination to tackle the basic vehicle routing problem (VRP). Customers of known demand are supplied from a single depot by vehicles which are subject to a weight limit and, in some cases, to a limit on the distance travelled. Only one vehicle is allowed to supply each customer. The system works in a Windows environment with a familiar look and feel for the majority of computer users. The best known results for benchmark VRPs have been obtained using tabu search or simulated annealing. However, most publications describe implementations that do not allow the user any control over the routes that are produced. In practice, users may have local knowledge concerning constraints on the route structure, together with insight and judgement that would be difficult to program in a heuristic for general application. The system described here allows the user to combine their special knowledge and insight with the power of the computer to perform modern heuristic techniques at high speed. Thus, the user retains control over the final routes, thereby ensuring that they will be acceptable in practice. Even for intensively researched benchmark problems, where there are no constraints on route structure other than load and distance restrictions, interactive sessions of at most 15 min produced total distances averaging ≤ 1 % above the best known values.