基于禁忌算法的带模糊需求集送一体化路径优化

汪浩祥，杨彦欢，冯 英

WANG Hao-xiang,YANG Yan-huan,FENG Ying

（南京农业大学 工学院，江苏 南京 210031）

(College of Engineering,Nanjing Agricultural University,Nanjing 210031,China)

0 引言

车辆路径问题（Vehicle Routing Problem，VRP） 最早是在1959年由Dantzig和Ramser[1]首先提出。是指对一系列客户的需求点，设计一组开始和结束于一个中心出发点的最小费用路径。每个顾客只能被服务一次，而且一个车辆服务的顾客数不能超过它的能力。针对VRP问题的提出，国内外学者们对不同背景的VRP问题做了大量的研究工作。针对物流配送，常见的车辆路径问题有以下几种类型：带容量约束的车辆路径问题；多车型车辆路径问题；带时间窗的车辆路径问题；带回程运输的车辆路径问题；相容性约束车辆路径问题和不确定性车辆路径问题等。对应于不同类型的配送问题，国内外很多的科学家、工程师和管理学者都对这一问题进行了探讨。先后涌现了大量的解决VRP问题的启发式、亚启发式算法。如Clark和Wright在1964提出的节约算法；Lin在1965年提出的2-opt和3-opt交换算法；Gillett和Miller在1974年提出的Sweep算法等，以及近年来出现的亚启发式算法，如遗传算法（Genetic Algorithm）、模拟退火算法（Simulated Annealing）、禁忌搜索算法（Tabu Search）、神经网络（Neutral Network） 等。

然而，在以往的绝大多数VRP问题中，人们一般在假定构造路径之前，所有的信息（包括顾客信息，车辆信息）都是确定的，而在实际应用的过程中，由于客观世界存在的不确定因素，以及人类主观因素的影响，车辆路径问题的某些参数可能是不确定的。近几年，不确定性路径问题引起各界学者的注意。Teodorovicc[2]等学者针对顾客需求不确定的车辆路径问题开展研究，其假设各个客户的需求是模糊的，并采用三角型模糊数来描述这一模糊的客户需求。侯玲娟[3]等学者针对一类不确定需求和旅行时间下的随机车辆路径问题，建立了一个随机规划模型，提出了一种带有自适应机制的改进遗传算法。邢占文[4]在前人的研究基础上，综合各种不确定因素，包括需求不确定，车辆不确定等。引入“假设客户”的概念，将动态问题转化为静态问题，并提出基于非精确距离矩阵的共轭优化算法进行优化。

在随机需求车辆路径问题（Vehicle Routing Problem with Stochastic Demands,VRPSD）提出以来，许多专家学者提出了有关求解本类问题的求解算法。其中D.Teodorovic和Pavkovic运用Gilett和Miller[5]提出的sweeping算法，甘勤涛，阳平华，童钟灵[6]提出禁忌搜索算法求解本问题。张建勇，李军[7]通过引入决策者主观偏好值的概念，提出了求解具有模糊特征的车辆路径问题的模糊机会规划模型问题的一种基于模糊模拟的混合遗传算法。

本文研究的集送货一体化车辆路径问题（Vehicle Routing Problem with Pick-up and Delivery,VRPPD）是允许同时集货和送货的混合作业，此类问题是假设某一顾客需求点同时存在集货需求和送货需求时，允许在该顾客点同时进行集货作业和配货作业问题的一个分类。郎茂祥[8-9]对具有多种类型车辆、具有行驶里程限制、同时考虑集货及送货过程的VRP问题，给出了基于货量参数的双下标数学模型。本文基于双下标集散一体化模型，结合模糊车辆路径问题（Fuzzy Vehicle Routing Problem，FVRP）引入三角模糊需求数。提出一种适合实际情况的车辆路径问题，并基于禁忌算法进行求解。

1 问题的描述及模型的建立

结合文献[7]建立带有模糊需求的集散一体化模型，将适用于本论文的模型描述如下：设配送中心有K辆车，其中车辆的载重量为（ k=1,2,3,…,K），其一次配送的最大行驶距离，需要向L个客户送货和取货。其中客户i的需求量为。供应量为ui（ i=1,2,3,…,L ）。客户i到客户j的距离为sij。配送中心到每个客户的距离为soj（ i,j=1,2,…,L ）设nk为第K台车辆配送的客户数（nk=0表示未使用第k个车辆），用Rk表示第k条路径，其中的元素rki表示客户rki在路程k中的顺序为i（不包括配送中心），令rki=0表示配送中心。本文考虑的目标是行驶距离最小化。

本文通过引用Zadeh[8]提出的模糊集的概念来建立适合本文的模型。模糊集即给定论域X上的一个模糊集，是指对任何x∈R，都有一个数μ（x）∈［0,1］与之对应。u（x）称为模糊集u的隶属函数，或称u（x）为x对模糊集u的隶属度。

设s和u分别为模糊数的下限和上限，m为可能性最大的值，那么模糊效用（s、m、u）表示。其隶属函数为：

1.1 解决问题的基本思路

任意给定的一个客户，都具有三个重要的属性，即自身的地理位置、需求量和供应量。就一个配送问题来说，随着某一车辆服务的节点数增加，由于该问题中需求量是模糊的，导致车的剩余装载能力也是模糊的。正是由于这种模糊性存在，很难确定在该车辆完成前k-1个节点的服务之后，是否还有能力继续服务第k个节点，只是能确定，当车辆的剩余运输能力越大，而第k个节点的供货量越大，需求量越小，该车能够服务第k个节点的机会就越大。为了解决这种模糊需求条件下的集收送一体化配送问题，本文引入三角模糊数来概率化服务第k个节点的可能性。对于给定节点的需求模糊数是~d=d1,d2,d3（ ），设某车辆服务完第k个节点之后，已装载的货物的货物量为：

（j=1,2,3,…,nk-1）设第k个节点可以被服务的可能性为p，运用三角模糊表示为：

很明显，P越大，该车能够服务第k个节点的可能性就越大，在此，设P*（P*∈ ［0,1］）表示决策者根据历史数据得到的，需求变动条件下给出的关于P的主观临界值。对于给定的P*值，若P≥P*，则可以服务k点，否则，派新车完成这一任务。重复以上过程，直到所有的客户都安排完毕。

1.2 模型的建立

综上所述，该模糊车辆调度问题的模型建立如下：

在此模型中，目标（1）表示最小化运行距离。约束（2）、（3）、（4） 表示配送过程中其载货量不超过其载重量。其中约束（3）表示模糊需求条件下，可以运载第K个客户的可能性大于给定的主观临界值。约束（5）表示配送过程中行驶距离不超过最大允许的行驶距离。约束（6）、（7）、（9）、（10）表示L个客户全部被服务，且每个客户只能由一辆车来服务。

2 基于模糊需求的禁忌搜索算法

本文在文献[6]所提出的配送车辆优化调度问题的禁忌搜索算法的基础上，结合本文所建的模型进行算法改进，修改客户可以被运输的可能性要大于给定的P*，同时在单配送的禁忌算法基础上改进适合本模型的为集送一体化的算法。

Step1：参数设置，输入各个参数。选取一个常数来确定禁忌长度。对于候选集的确定，从当前解的领域中随机选择若干个领域。设置迭代步数。

Step2：生成模糊需求。根据提供的历史数据，得到隶属度为1确定需求量，即d2。采用随机数的方式产生d1和d3。具体步骤是：随机生成一个［0,1］范围内和［1,2］范围内的数，根据实际历史数据，可以确定范围。重复上述步骤，直至生成所有的顾客的模糊需求量。

Step3：采用客户直接排列的方式，随机产生初始解。

Step4：对于某个解，按其排列方式进行约束检验。具体步骤是：先将第k个点加入到路线中，计算出加入k点之后的P值，与给定的主观临界值P*比较，如果满足条件再进行其他约束条件的检验。如果满足，就加入第k点，如果不满足，就将K点加入一台新的车辆。直至所有的客户点均被安排。

Step5：对于某个解，进行解的评价。具体步骤是：根据步骤3，对于超过配送中心提供的车辆的数目，设其为对应的配送路径方案中的不可行路径数M，给配送路径方案的目标函数值为Z，并设对每条不可行路径的惩罚权数为Pw。采用E=Z+M×Pw进行解的评价。

Step6：从当前解的领域中随机选择若干个领域。通过两交换法实现领域的操作，将每次迭代的最好解作为禁忌对象放在禁忌表中。进行禁忌操作。选择记录最好解。

Step7：直到进行了指定步数的迭代，终止程序。步骤流程图如图1所示。

3 实验计算及结果分析

本文采用文献[8]一书中的例6.1进行实验计算。设配送中心和20个客户分布在一个边长为20km的正方形区域内，每个客户的需求量与供应量以及客户在2t以下，配送有10台车，最大载重量为8t，车辆一次配送最大行驶距离为50km。作者用计算机随机产生的配送中心和20个客户位置坐标以及客户的货物需求量和供应量如表1。（配送中心的坐标为（3.2km，14.1km）X表示横坐标，Y表示纵坐标，Q表示隶属度为1需求量，U表示供应量）。

表1 客户信息表

根据本例的特点，采用了如下参数：对不可行路径的惩罚pw取300km，每次迭代共搜索当前解的40个邻居，禁忌长度取10，迭代步数取400，主观临界值P*取0.8。对实例6.1用禁忌算法随机求解10次，得到的结果见表2、路径迭代过程见图2。

从表2中可以看，在主观模糊需求下可提供服务临界值0.8概率的情况下，用禁忌搜索算法对实例的10次求解过程中，得到了质量很高的解，其配送总里程的平均值为116.47km平均使用的车辆是3辆，与实例6.1中不考虑需求模糊性相比，运输距离平均增加1.04km，也就是由于不确定性，导致运输距离增加。其中第9次解的质量最高，配送里程112.9km，对应的配送方案为：0-4-14-5-12-2-9-15-1-0,0-7-8-19-16-13-6-11-20-3-10-18-0,0-17-0。

表2 计算结果统计表

4 结束语

本文在对集收送一体化配送问题进行简单描述的基础上，结合实际终端配送过程中的实际需求不确定性，通过引入模糊数的概念，建立了具有模糊特征的集收送一体化路径问题的规划模型。给出了解决这一类终端配送问题的基本解题思路，提出了一种求解带有模糊需求的集散一体化的这类问题的禁忌搜索算法，并且通过实例验证这种算法的可行性。

[1] Bodin L,Golden B,Assad A,et al.Routing and scheduling of vehicles and crews:the st ate of the art[J].Computer and Operation Research,1983(10):62.

[2] Teodorovic D,Pavkovic G..The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain[J].Fuzzy Set and System,1996,82(3):307-317.

[3] 侯玲娟，周泓，梁春华.不确定需求和旅行时间下的车辆路径问题[J].计算机集成制造系统，2011,17(1):101-107.

[4] 邢占文.考虑不确定因素条件下带回程取货的车辆路径问题研究[D].西安：长安大学（博士学位论文），2011.

[5] Gillett B,Miller L.A heuristic algorithms for the vehicle routing dispatch problem[J].Operational Reserarch,1974,22(22):340-349.

[6] 甘勤涛，阳平华，童钟灵.模糊需求车辆路径问题的禁忌搜索算法研究[J].长春理工大学学报，2006,29(1):84-85.

[7] 张建勇，李军.模糊车辆路径问题的一种混合遗传算法[J].管理工程学报，2005(2):23-26.

[8] 郎茂祥.配送车辆优化调度模型预算法[M].北京：电子工业出版社，2009.

[9] 郎茂祥.装卸混合车辆路径问题的模拟退火算法研究[J].系统工程学报，2005(5):41-47.