R-Tree Based Path Representation for Vehicle Routing Problem

Vehicle routing problem (VRP) is a problem to find the minimum path length for a fleet of vehicles which deliver goods from the depot according to demands. Some specific methods for the VRP include evolutionary approaches such as genetic algorithms. A naive data structure (i.e., chromosome) for the evolutionary approaches is called path representation (PR) which is an ordered list structure which represents a single path. On the other hand, we propose a novel data structure called R-tree based path representation (R-PR). R-PR is a tree structure based on a spatial indexing structure called R-tree. Each node of R-PR represents a sub-path (i.e., a partial solution) for VRP, and its parent node represents a set of the sub-paths, hierarchically. We compare R-PR with PR by using some of VRP instances by Augerat et al, and the results show that R-PR outperforms PR in large scale instances.