上海交通大学学报

上海交通大学学报（自然版）

• 自动化技术、计算机技术 • 上一篇    下一篇

半开放式多车场车辆路径问题

刘冉，江志斌，耿娜，刘天堂
  

  1. （上海交通大学 机械与动力工程学院， 上海 200240）
  • 收稿日期:2010-01-14 修回日期:1900-01-01 出版日期:2010-11-30 发布日期:2010-11-30

The Half Open Multidepot Vehicle Routing Problem

LIU Ran，JIANG Zhibin，GENG Na，LIU Tiantang
  

  1. (School of Mechanical Engineering, Shanghai Jiaotong University, Shanghai 200240, China)
  • Received:2010-01-14 Revised:1900-01-01 Online:2010-11-30 Published:2010-11-30

摘要： 基于现代物流业发展的实际需要，提出半开放式多车场车辆路径问题，并建立了数学模型.由于半开放式多车场车辆路径问题具有NP-hard性质，为了有效求解，基于车辆路径问题中的经典路径构造算法和局域搜索算法，设计了求解所提出问题的节约算法、顺序插入算法和并行后悔插入算法.利用标准算例进行数值试验，分析了3种算法中的参数和所嵌入局域搜索方法对求解结果的影响，并对不同算法的求解结果进行了对比分析.
关

关键词: 车辆路径问题, 多车场, 半开放式, 启发式算法

Abstract: The half open multidepot vehicle routing problem (HOMDVRP) was proposed to meet the requirement of modern logistic industry in China. In terms of similarity and difference among HOMDVRP, multidepot vehicle routing problem and open vehicle routing problem, a mathematical model was built. In order to solve this new NPhard problem, the saving algorithm, the sequence insertion algorithm and parallel regretted insertion algorithm were proposed base on the classical heuristics for the vehicle routing problem. Meanwhile, three kinds of local search methods were adopted when the heuristics were designed. The results were analyzed by studying the impact of parameters and local search methods on the performance of the heuristics. Simultaneously, the performances of different heuristics were assessed by comparing them with benchmark instances.