A systematic heuristic rules analysis methodology for routing problems

Heuristic constructive algorithms have been widely and successfully applied to the solution of routing problems. Since they generally consist of an iterative insertion of nodes to construction routes, prioritization rules for assignments is critic for algorithm´s performance. Developing these rules is time consuming and relies much on researcher skills and knowledge on problem features. This paper proposes a systematic methodology for a widespread exploration of prioritization rules aiming at reducing human effort on its development. A general model for prioritization is achieved by means of an artificial neural network. Parameters are tuned for the specific problem by an evolutionary strategy search. The methodology is formulated for generic routing problems and applied to VRPTW to illustrate its operation and as a preliminary assessment of its capabilities. Neural networks are evolved for Solomon´s benchmark instances and analyzed to gain knowledge on underlying rules.