论文部分内容阅读
对半开放式车辆路径问题进行了描述,提出了核心路径的概念和理论,并根据问题的特点设计了基于核心路径的禁忌算法。算法分为初始优化、核心路径的提取和连接以及后期优化三部分,采用自然数编码,用GENI插入法构造初始路径和进行邻域操作,设计了三种邻域以扩大搜索空间,用能力约束控制单条路径的配送点数,以增加惩罚的方式加入配送距离约束。算法利用核心路径的特点阻碍不良路径的生成,并在后期优化的第二阶段拆开核心路径,进行优化路径的调整。最后采用多组数据进行计算并对结果进行了分析,证明了基于核心路径禁忌算法对优化有能力和距离约束半开放式车辆路径问题的有效性。
The semi-open vehicle routing problem is described, the concept and theory of the core routing are proposed, and a tabu search algorithm based on the core routing is designed according to the characteristics of the problem. The algorithm is divided into three parts: initial optimization, extraction and connection of core paths, and post-optimization. By using natural number coding, the initial path and neighborhood operation are constructed by GENI insertion method. Three kinds of neighborhoods are designed to expand the search space, A single path of delivery points, to increase the penalty to join the delivery distance constraints. The algorithm uses the characteristics of the core path to hinder the generation of the bad path, and disassembles the core path and adjusts the path of optimization in the second phase of post-optimization. Finally, using multiple sets of data to calculate and analyze the results, it is proved that the algorithm based on the core path tabu search is effective in optimizing the semi-open vehicle routing problem with capability and distance constraints.