Premium
Set partitioning based heuristics for interactive routing
Author(s) -
Cullen Frank H.,
Jarvis John J.,
Ratliff H. Donald
Publication year - 1981
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230110206
Subject(s) - heuristics , computer science , mathematical optimization , class (philosophy) , set (abstract data type) , point (geometry) , variety (cybernetics) , routing (electronic design automation) , vehicle routing problem , algorithm , artificial intelligence , mathematics , computer network , geometry , programming language
Abstract The set partitioning model is used as the basis for an interactive approach for solving a broad class of routing problems. A pricing mechanism is developed which can be used with a variety of methods in generating improving solutions. A version of the approach for delivery problems has been implemented via a colorgraphics display. The human aided optimization procedure was tested on the standard 50‐point, 75‐point, and 100‐point test problems of Eilon, Watson‐Gandy, and Christofides [6]. In the case of the first two test problems, the procedure was able to generate the best known solutions. In the 100‐point problem, a better solution was generated than the current best known solution.