一类半开放式车辆路径问题及其禁忌算法研究

对半开放式车辆路径问题进行了描述,提出了核心路径的概念和理论,并根据问题的特点设计了基于核心路径的禁忌算法.算法分为初始优化、核心路径的提取和连接以及后期优化三部分,采用自然数编码,用GENI插入法构造初始路径和进行邻域操作,设计了三种邻域以扩大搜索空间,用能力约束控制单条路径的配送点数,以增加惩罚的方式加入配送距离约束.算法利用核心路径的特点阻碍不良路径的生成,并在后期优化的第二阶段拆开核心路径,进行优化路径的调整.最后采用多组数据进行计算并对结果进行了分析,证明了基于核心路径禁忌算法对优化有能力和距离约束半开放式车辆路径问题的有效性.

Semi-open Vehicle Routing Problem and Study on Its Tabu Search Algorithm Based on Kernel Route

A semi-open vehicle routing problem was proposed. The concept and principium of kernel route were proposed. Based on kernel route,a tabu search algorithm was designed to solve SOVRP. The algorithm was composed of three parts: initial optimization,pick-up and link of kernel routes and final optimization. Based on nature number,the algorithm used three kinds of neighborhoods to extend the search space. The GENI insertion was used to construct the initial solution and the operation of neighborhood. The algorithm used capacity limit to control the number of distribution points in each route. The distance limit was solved by adding penalty function to the object function. The properties of kernel route blocked the building of ill-route. In the second phase of final optimization,kernel routes were disconnected to adjust the optimal route. Many representative results and the analysis were given. The experiment indicates the validity of the algorithm to the SOVRP with the above-mentioned conditions.