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

The Half Open Multi-depot Vehicle Routing Problem

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

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.