An Approximation Algorithm for Vehicle Routing Problems with Hierarchized Traffic Network
- 作者：Mariko Okude ; mariko.okude.uh@hitachi.com ; Eiichi Taniguchi
- 关键词：Logistics ; vehicle routing problems ; tabu search ; traffic network
- 刊名：Procedia - Social and Behavioral Sciences
- 出版年：2012
- 期刊代码：P145_18770428
- 类别：soc
- 出版时间：2012
- 卷：39
- 期：Complete
- 页码：369-386
- 文件大小：1295 K
摘要
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.