文章基本信息

标题：An Approximation Algorithm for Vehicle Routing Problems with Hierarchized Traffic Network
本地全文：下载
作者：Mariko Okude ; Mariko Okude ; Eiichi Taniguchi 等
期刊名称：Procedia - Social and Behavioral Sciences
印刷版ISSN：1877-0428
出版年度：2012
卷号：39
页码：369-386
DOI：10.1016/j.sbspro.2012.03.115
语种：English
出版社：Elsevier
摘要：AbstractEfficient 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.
关键词：Logistics;vehicle routing problems;tabu search;traffic network