An Approximation Algorithm for Vehicle Routing Problems with Hierarchized Traffic Network

Efficient delivery planning for freight transport is required for reducing environmental load and logistical costs. By using an actual traffic condition, a more realistic delivery plan, increased delivery work efficiency, and CO2 reduction will be possible. An algorithm for quickly obtaining a best solution is required to solve actual vehicle routing problems of large-scale networks and fluctuating delivery costs. The purpose of our research was to solve vehicle routing problems on a large-scale road network that can be applied to actual vehicle routing problems. Our proposed algorithm uses a hierarchical traffic network model composed of two layers according to the frequency of road use. The algorithm is based on tabu search, and the hierarchical traffic network is applied to a generation strategy of the neighborhood solution. Specifically, priority of movement of neighborhood solutions for generating a neighborhood solution is given to delivery points connected in frequently used roads. By using travelling salesman and simple vehicle-routing benchmark problems as a first step in our computing, we confirmed that the proposed algorithm can quickly provide a better solution than the non-application of the proposed algorithm. Furthermore, the effectiveness of the proposed algorithm is discussed by using a virtual vehicle routing problem based on an actual road network.