需求可拆分车辆路径问题的三阶段禁忌算法

熊浩¹，鄢慧丽²

(1.海南大学经济管理学院，海南海口570228；2.海南大学旅游学院，海南海口570228；)

摘要: 需求可拆分车辆路径问题（SDVRP）是一类有待深入研究的车辆路径问题，其求解方法与需求不可拆分的VRP问题有较大的区别。针对该类问题，本文提供了一种新的求解思路——基于双层规划模型的三阶段禁忌算法。首先，将目标函数设定为大TSP路径成本加上切割增加路径成本，构建了SDVRP的双层规划数学模型；然后，根据双层规划的思路设计了三阶段禁忌启发式算法：先求包括车场和所有顾客的大TSP路径，再对大TSP进行切割和拆分，接着对备选方案进行子路径优化；最后，通过实验仿真，将所提出的三阶段禁忌算法与其他算法进行比较，结果表明了所提出的算法可以比较有效地求得需求可拆分车辆路径问题的优化解，是解决需求可拆分车辆路径问题的有效方法。

关键词: 车辆路径问题；需求可拆分；双层规划；禁忌算法

中图分类号：U492.3；TP13

基金项目：国家自然科学基金资助项目（71461006、71461007）；海南省自然科学基金（20157263）；海南省哲学社会科学规划课题（HNSK（QN）15-4）；海南省教育厅重点项目（Hnky2015ZD-7，Hnky2015ZD-2）。

A three-phase tabu search heuristic for the split delivery vehicle routing problem

Xiong Hao¹, Yan Huili²

(1. School of Economics and Management, Hainan University, Haikou 570228, China; 2．Tourism College, Hainan University, Haikou 570228, China.)

Abstract: The split delivery vehicle routing problem (SDVRP) is a kind of vehicle routing problem need to be further studied. And its solving method is much different with the traditional VRP’s. This paper provides a new heuristic to solve the SDVRP called three-phase tabu algorithm, which is based on the bi-level programming model of SDVRP. First, the bi-level programming mathematical model the SDVRP is given, which set the cost of a big TSP path and the increased cost of cutting and split as the objective function. Then, based on bi-level programming model, a three-phase tabu heuristic algorithm is designed. First phase, a big TSP path including the distribution depot and all the customers is constructed. Second phase, the big TSP is cut and split. And in the third phase, the sub-paths get from the second phase are re-optimization. Finally, through the experimental simulation, the proposed three-stage tabu algorithm compared with other algorithms. And the results show that the proposed algorithm can really solve the SDVRP effectively. And they also proved that the three-phase tabu algorithm is really a good method of SDVRP.

Key words:vehicle routing problem; the split delivery; bi-level programming model; tabu algorithm

1 引言

可拆分需求车辆路径问题是有容量限制的车辆路径问题的延伸，其与VRP之间只有1个约束条件的差异：允许顾客被多次访问。但是，该类问题的优化解却能提高车辆的装载效率和减少路径成本^[1-4]。并且，其求解算法都与VRP有较大的区别。

Archetti等^{[5, 6]}对SDVRP问题的复杂性进行了研究，其研究证明当车车辆容量大于2时，SDVRP为NP难题。因此，精确求解该类问题有一定的难度，需要探索有效的启发式算法。最早关于SDVRP的启发式算法由Dror和Trudreau提出^[1]，并给出了针对SDVRP的2种局域搜索的方法：k-split interchange和route addition。其后，出现三种比较主流的启发式算法研究：禁忌算法、混合遗传算法和混合整数规划法。首先，关于SDVRP问题的禁忌算法研究相对较多：Archetti等^[7]首先提出了SDVRP的简单邻域搜索禁忌算法；Aleman等^[8]提出了词汇构造禁忌搜索法（TSVBA），利用方案集群中的共同边、重要边调整节约值表，使用新节约值表构建新解取代原来解群中较差的解；Berbotto等^[9]提出了随机粒度禁忌搜索法(RGTBA)；Mota和Campos^[10]提出了散点搜索法（SS）；以及最近孟凡超等提出的多邻域搜索禁忌法^[11]。其次，也有一些遗传算法方面的研究：Wilck等^[12]提出的遗传算法，根据一定的概率择优选择符合条件的子路径作为新方案的子路径，将方案中剩余的顾客利用CH算法^[13]进行路径的构建；Mourad Boudia等^[14]提出了基于人口管理的基因算法（MA|PM），该方法在传统的遗传算法基础上增加了局域搜索（local search）和基于距离选择的跳跃控制策略作为新的变异方法。最后，还有一些其他的混合算法：Jin^[15]提出了SDVRP的列生成模型，并提出了边界限制搜索法（LSB）进行子问题的求解；Chen等^[16]提出了一种以VRP为基础的端点混合整数规划模型（EMIP）进行SDVRP求解；刘旺盛等^[17]提出的聚类算法。

综上所述，目前对于SDVRP问题已经有较多的启发式算法。但是，由于SDVRP问题自身的复杂性，目前已有的算法很难在两个方面取得平衡：计算时间和优化程度，即有些算法的优化效果好却需要花费较多的计算时间，有些算法计算较快但优化效果却不是很好。因此，为了能在让算法同时具有计算速度快且优化效果好，仍然需要探索研究新的算法。本文利用双层规划（或二阶段法）的思想，探索构造了一种三阶段的禁忌启发式算法。并通过大量的实验对比分析，验证了该启发式算法的确能在较短的计算时间内获得较好的优化解决方案，从而为该类问题的求解提供了新的研究思路和求解方法。