A Construction Heuristic for the Split Delivery Vehicle Routing Problem

• 作者: Joseph Hubert Wilck IV Tom M. Cavalier
• 来源期刊: 美国运筹学期刊(英文)
• 学科: 数学
• 关键词: Vehicle ROUTING Problem TRANSPORTATION CONSTRUCTION HEURISTICS
• 年，卷（期）: 2012,（2）
• 页码范围: 153-162
• 页数: 10页
• 分类号: O1

摘要

The Split Delivery Vehicle Routing Problem (SDVRP) is a relaxation of the Capacitated Vehicle Routing Problem (CVRP) where customers may be assigned to multiple routes. A new construction heuristic is developed for the SDVRP and computational results are given for thirty-two data sets from previous literature. With respect to the total travel distance, the construction heuristic compares favorably versus a column generation method and a two-phase method. In addition, the construction heuristic is computationally faster than both previous methods. This construction heuristic could be useful in developing initial solutions, very quickly, for a heuristic, algorithm, or exact procedure.