Evolution of vehicle routing problem heuristics with genetic programming

Increasingly complex variants of the vehicle routing problem with time windows (VRPTW) are coming into focus, alleviated with advances in the computing power. VRPTW is a combination of the classical traveling salesman and bin packing problems, with many real world applications in various fields - from physical resource manipulation planning to virtual resource management in the ever more popular cloud computing domain. The basis for many VRPTW approaches is a heuristic which builds a candidate solution that is subsequently improved by a search or optimization procedure. The choice of the appropriate heuristic may have a great impact on the resulting quality of the obtained schedules. In this paper we use genetic programming to evolve a suitable heuristic to build initial solutions for different objectives and classes of VRPTW instances. The results show great potential, since this method is applicable to different problem classes and user-defined performance objectives.