［提要］　目前，对配送车辆路径问题的研究已经比较成熟。本文运用禁忌搜索算法对车辆路径调度问题进行研究，先用节约里程法获得初始解，提出一种新的禁忌方法，大大缩短计算时间，提高运算效率。最后用实例研究，验证该算法的高效、快速与稳健，给车辆配送路径问题提供一定参考价值。

关键词：禁忌搜索；车辆调度；路径规划

本文为2017年中国物流学会、中国物流与采购联合会研究课题计划项目：“基于禁忌搜索算法的车辆协作与路径规划研究”（项目编号：2017CSLKT3-071）

中图分类号：F27 文献标识码：A

收录日期：2017年5月24日

引言

低碳物流体系体现在包装、运输、配送等方面，车辆在运输时优先规划配送路径能够充分缩短客户的服务时间，从而降低运输成本，增加企业效益。目前，许多学者对车辆路径调度问题做了研究，李文提出一种基于多个配送中心并可以同时取送货物的车辆配送模型。李相勇对配送车辆路径问题进行建模，用禁忌搜索算法进行计算。傅成红、符卓根据VRP问题提出一种基于邻域集合的动态候选集规模的禁忌搜索算法。Willard最早开始研究VRP的禁忌搜索算法，定义邻域结构为交换算子与逆序排列，并将VRP问题通过转化形成一个巨巡回。Pureza和Franga提出邻域结构，将一个客户点插入到另一条线路中或将两条线路中的客户点进行交换。本文提出一种改进的禁忌搜索算法，用节约里程法获得初始解，缩短搜索时间，更快获得最优解，通过仿真试验验证该模型和算法的有效性和适用性。

一、问题描述与模型建立

一般的车辆路径问题（VRP）是指给定几个约束条件并且符合约束，对所有客户分配合适的运输路线，使总运输距离最短。车辆路径问题（VRP）模型可以描述为：有一个配送中心0和n个待服务的客户点，客户集合C=｛1，2，…，n｝，运输车辆从配送中心出发，完成指定的运输路线后回到配送中心，车辆集合表示为A=｛1，2，…，m｝，Cm（Cm∈C）表示车辆m∈A所服务的客户点集合。设每辆车最多的装载量为Q，客户点i的需求量为qi，客户i与客户j之间的距离为cij，单位运输费用为a，每辆车的运输费用系数用l表示，设每个客户的成功运输概率为b。本文的模型目标定为总运输费用最小，在满足一定的约束条件下建立如下模型：

目标函数为：

Min■■■acijxijk+lm （1）

约束条件为：

■■xijk＝1，?坌h∈C （2）

pk（■qixki?燮Q）?叟b，?坌k∈A （3）

■x0jk=1，?坌k∈A （4）

■xihk-■xhjk=0，?坌k∈A，?坌h∈C （5）

■xi，n-1，k=1，?坌k∈A （6）

xijk=0，1 （7）

约束条件2表示每个客户点都能被访问且只能被访问一次；约束条件3表示将车辆发生运输失败的概率限制在b以内，而且每辆车在安排的运输路线中要满足车辆容量限制；约束条件4、5、6表示每辆车都是从配送中心出发，每个客户都能被服务且配送车辆在完成任务后最终返回配送中心；约束条件7表示每个客户服务情况只有两种，是对其整数化的约束。

二、算法设计

禁忌搜索算法（TS）是一种局部迭代搜索算法，TS主要使用一种侵略性的局部搜索机制，每迭代一次，算法都探索搜索空间，选择可能将当前解X推向邻域N（X）中最好解的移动。初始解的选取对计算过程有很大的影响，本研究先通过节约里程法获得初始解，再用禁忌搜索算法进行计算，这样将减少运算次数。本文中的禁忌搜索算法运用步骤为：

（一）初始解。设该客户为当前节点c，该运输车辆在此线路装载的货物量为demand=q（c），该车辆运输的长度为d，根据节约里程法求得一个初始解x0。

（二）邻域结构。邻域结构通过以下算子构成：交换算子N1（x0，i，j，Gj），换运输路线中客户点i和客户点j的位置；插入算子N2（x0，i，j，Gj），将客户点i插入到线路中客户点排j之后；2-opt交换算子N3（x0，i，j，Gj），将客户点i和客户点j之间的运输路线顺序逆转。

（三）候选集。候选集中一般存放邻域中的已经比较过的最优点，候选集的大小设定为一固定常数。

（四）禁忌移动。T表示一个禁忌表，表中记录被禁忌的元素，通过邻域结构选择不同的禁忌方式。

（五）特赦准则。当有一个要被禁忌的解的值比目前任何一个解都好，则释放该解，并将此解作为最好解。

（六）终止条件。可以设置一个数值，当运算次数达到该数时则结束，或者设置一个最优值，目标值达到或接近于最优值时则结束运算。

三、算例分析

实例描述：在某一物流企业，设某物流配送中心的坐标为（13.6km，25.4km），选取20个客户作为实验分析，目标函数为获取最短运输路径，在该物流中心共有4辆运输车，每辆车的型号都一样，一辆车最多装载10t货物，不允许超载。每个客户的需求信息与位置如表1所示。（表1）

设置其禁忌长度为10，迭代步数选取500，则对该算例计算10次，运用Matlab软件对其算法进行运行，得到的结果如表2所示。（表2）

通过计算结果可以得出：通过对该实例进行10次运算求解，解的质量都比较优异，求得最短运输距离为104.3km，最长运输距离为114.2km，平均运输距离为108.5km；第5次运算迭代步数最少，为256次。10次求解中第9次求的解最优，计算的配送总距离最短为104.3km，运输路线为：路线1：0-1-5-10-13-6-11-20-0；路径2：0-12-4-9-15-17-7-0；路径3：0-16-18-19-3-0；路径4：0-14-2-8-0。禁忌搜索算法比其他算法计算效率更高，收敛速度更快。初始解的选取先用节约里程算法获得，大大减少迭代次数，更快获得最优解。

四、结论

本文通过运用禁忌搜索算法对车辆配送路线进行规划，并运用实例进行了验证，禁忌搜索算法在路径规划方面取得广泛推广，计算效率快，得出的结果质量较高，很稳定。在对初始解的选取上先运用节约算法获得一个初始解，这样能够大大缩短运算时间，快速取得计算结果。

（作者单位：山东科技大学交通学院）

主要参考文献：

［1］Alan Laurence Erera.Design of Large-Scale Logistics Systems for Uncertain Environments［D］.California：University of colifomia，Berkeley，2000.

［2］李文.物流配送同时取送货低碳车辆调度模型及其QEA研究［D］.浙江工业大学，2015.

［3］李相勇.车辆路径问题模型及算法研究［D］.上海交通大学，2007.

［4］傅成红，符卓.一种毗邻信息改进的车辆路径问题禁忌搜索算法［J］.系统工程，2010.5.

［5］J.A.G.Willard.Vehieling Routiting Using r-Optimal Tabu Search.M.se.dissertation，ImPerial College，1989.

［6］V.M.Pureza and P.M.Franca.Vehicle routing problems via tabu search metaheuristic.Technical Report Techinical Report CRT-347，Centre for researeh on transportation，1991.

［7］刘霞，齐欢.带时间窗的动态车辆路径问题的局部搜索算法［J］.交通运输工程学报，2008.5.