物流模糊动态问题的模拟退火算法研究

崔 健，钱枫林，王利光

（江南大学a.商学院；b.理学院，江苏 无锡 214122）

0 引 言

在大型的物流配送问题中，配送车辆的优化调度是物流系统优化中的关键一环，物流企业针对配送车辆路线进行合理的规划，可以提高物流经济效益，减少了物流成本，实现了物流的科学化。车辆路径问题VRP（Vehicle Routing Problem）最初是由Dantzing和Ramser[1]提出的，是指在客户需求已知的条件下，确定车辆在各个客户之间的行程路线，可以使得运输路线最短或者运输成本最低。关于求解车辆路径问题的算法有大量的研究成果[2－3]，但这些研究方法绝大多数是建立在确定性的条件基础之上的。而在现实中，有关VRP的许多参数可能是不确定的，如车辆在两地的行驶时间约20min、顾客的需求约为20单位等。对于这类具有模糊性质的不确定性VRP问题，所做的研究较少。针对随机车辆调度问题[4－5]，有少数的不确定研究集中在通过对长期记录的资料进行分析从而得到其统计规律。Wang和Wen[6]提出了采用模糊理论对中国邮路问题进行研究，由此建立了最大化服务水平和最小化任务完成时间的数学模型；张建勇[7－8]等对具有模糊预约时间的多对多货物收发情况下的车辆调度问题进行了探讨；Tang[9]等在分析模糊时间窗实际应用性的基础上构建了该类问题的数学模型，并设计了求解多目标整数规划模型的两阶段算法。

虽然VRP问题的诸多理论和方法有着比较广泛应用，但是目前物流企业的运作效率普遍不高，运作成本较高。针对现行的大型物流企业的实际问题，以提高配送效率和降低成本为目标，本文首先通过聚类的方法，由模糊数学的理论将模糊的顾客需求转化为实际的需求，进而根据实际的需求量将物流配送单元进行划分。在此基础之上引入决策者主观偏好，建立模糊需求条件下的VRP模型，设计并运用模拟退火算法进行车辆路径的设计，讨论在模糊需求信息条件下，在每一个已经划分的物流区域内，决策者偏好对车辆行驶的最短路径有何影响，进而为物流企业在配送过程中给出优化方案。

1 根据需求量对物流区域进行聚类

在实际问题中，针对不同需求量的地区往往需要进行分类，使需求相似程度较高的几个区域划分为一类。物流区域划分问题可以确定一套车辆派送的方案，用以解决中转站选址及不同载运量的车辆安排[10]，使得总的物流费用最低，配送效率最高。区域划分前的示意图见图1，区域划分后的示意图见图2。其中，根据区域划分的类别不同分别派以不同载运量的车辆进行配送，从而大大减少了配送时间和行驶车程，降低了物流成本。在本文中，设每个节点的需求量为一模糊数（1，2，…，n），各节点的实际需求量采用三角模糊变量（di1，di2，di3）的期望值：来表示[11]。

聚类分析的基本思想[12]是，从一批样本中定义能够度量样本间或变量间相似程度的统计量，在此基础上求出各样本之间的相似程度度量值，按相似程度的大小，把变量逐一归类，关系密切的类聚集到一个小的分类单位，关系疏远的聚合到一个大的分类单位，直到所有的变量都聚集完毕。利用这种思想，运用谱系聚类法中的最短距离法将需求量不同的各个物流区域进行分类，利用SPSS统计工具进行聚类分析，使具有相似需求量的节点归为一类，利用不同载运量的车辆针对需求不同的区域进行有效率的配送。

2 模糊需求信息下的VRP数学模型

对模糊需求的车辆路径问题的描述如下：有一个配送中心，用0表示；n个顾客（即需要配送的节点），用1，2，…，n表示。车辆从配送中心出发，载有一定数量的货品，根据以上聚类分析得到的划分好的物流区域，服务一定数量的节点后返回货运中心。已知每辆车的运输能力为Vi（i＝1，2，3，…，w）。设每个节点的需求量为一模糊数～Di（1，2，…，n），Q为所有节点的最大需求量，且假设Vi≥Q。节点i与节点j之间的距离为cij。由于之前所做的聚类分析工作，已将车辆的配送方向划分好，假设将需要配送的节点划分为K类，K＝1，2，…，且K＜n。则本文研究在其中一类区域Ki中分配k辆车的条件下，决策者的偏好性如何选择，使车辆总的行驶距离最小。

目标函数为：

其中nk表示第k辆车所包含的节点数；rk，i表示节点在路径k中的顺序为i。

令P＊（P＊∈ [0，1]）表示决策者是否安排车辆继续完成下一任务的可能性临界值[13]，或者称为决策者主观偏好值。因此，车辆能否服务第m＋1个节点，取决于P＝pos｛｝≥P＊是否成立。显然，P越大，完成配送的可能性越大。但对于决策者来说，P＊反映了其决策时的风险偏好，追求风险型的决策者会倾向于较小的P＊，这时他希望能够充分利用车辆的剩余载运量，以追求车辆的最优利用率，而风险规避型的决策者会选择较大的P＊，此时他要保证车辆可以满足下一个节点的需求量。

3 物流区域单元内的模拟退火算法

模拟退火算法是一种通用概率算法，由Metropolis于1953年提出，其思想源于固体的退火过程，即将固体加热至足够高的温度，再缓慢冷却。加热时，固体内部粒子随温度升高变为无序状，内能增大，而缓慢冷却时粒子又逐渐趋于有序。在冷却过程中，任一温度时固体都能达到热平衡，当温度降至结晶温度后，液体凝固成固体的晶态，退火过程完成。

从上述VRP模型来看，求解该问题的关键是合理确定各车辆与各节点的关系，在满足车辆的载运量和节点的需求条件下使得目标函数即车辆行驶总路径最小。由此构造以下的模拟退火算法：

1）令初始值T＝T0，随机生成一个初始解x0，并计算相应的目标函数L（x0）。

2）令T等于冷却进度表中的下一个值Ti。

3）根据当前解xi进行扰动，产生一个新解xj，计算相应的目标函数值L（xj），得到ΔL＝L（xj）－L（xi）。

4）若ΔL＜0，则新解xj被接受，作为新的当前解；若ΔL＞0，则新解xj按概率exp（－ΔL／Ti）接受，Ti为当前值。

5）在当前值Ti下，重复lk次的扰动和接受过程，即执行步骤3）和4）。

6）判断T是否已到达Tf，是，则终止算法；否，则转到步骤2）继续执行。

P＊的引入对于所安排的车辆计划有很大的影响。P＊值越小，则所派车辆的载重量能够被充分利用，预计的行驶距离越短；同时，小的P＊值也使配送失败的可能性增大，从而产生较多的额外行驶距离。反之，大的P＊值相应减少了配送失败的可能性，额外行驶距离也相应减小。因此，在考虑模糊需求信息条件的车辆路径安排问题中，加入了决策者的风险偏好这一控制参数，通过观察P＊值研究对最终的VRP决策有何影响。

4 数据实验及结果分析

4.1 模糊需求条件下的聚类分析

一配送中心负责对12个地区的分销点进行配送，各个地区的实际需求量见表1，根据此基础，对12个地区进行区域划分，从而决定车辆的配送路径。

应用谱系聚类法中的最短距离法，对下表问题进行聚类。其模型[12]为：以i，j等分别表示样品xi，xj，以dij简记样品i与j之间的距离d（xi，xj），用Gp和Gq表示两个类，它们所包含的样品个数分别记为np和nq，类Gp和Gq之间的距离用D（Gp，Gq），表示，则 D（Gp，Gq）＝min｛dij，即定义Gp与Gq中最邻近的两个样本的距离为这两个类之间的距离。

表1 各地需求量Table1 Demand all over

根据需求量，用SPSS的聚类分析得到以下结果（表2）：

表2 分销点的相关系数矩阵Table2 Correlation coefficient matrix of distributions ／t

从图3可以看出整个聚类过程及相应的水平，其为分销点的谱系图。

根据谱系图，将这12个分销点分为4类比较合适，即F、J、D、C、G、K为一类，H、I为一类，B、L为一类，A、E为一类。由此可见，物流公司可以建立4个配送中心，分别派送相应载运量的车辆对4类分销点进行配送。在此基础之上，可以进一步将分销点划分的更为接近，如F、J、D为一类，C、G为一类，H、I为一类，B、L为一类，A、E为一类，K自成一类。从而使配送中心可以安排车辆对其需求进行配送，针对不同的需求量，发送相应载运量的货车进行指定的配送，从而提高了配送效率，节约配送时间，减少物流成本。

图3 分销点最小距离谱系图Fig.3 Minimum distances dendritic diagram of distributions

4.2 应用模拟退火算法求解最短路径问题

表3为根据聚类分析得到的F、J、D、C、G、K区域中共50个城市的坐标位置，根据不同的P＊值，根据模拟退火算法逐步求得每个P＊值下的最短路径及车辆的配送路径。

表3 50座城市的坐标Table3 Coordinates of 50Cities

在参数的选择中，令P＊＝0.01T，通过控制参数T的变化进而推断出决策者偏好值P＊对决策的影响。

Markov链长度的选取原则是在控制参数T的衰减函数已定的前提下，lk应能使在控制参数T的每一个取值上达到准平衡。

在实际运行中，各参数取值见表4。

表4 各参数取值Table4 Value of parameter

由Matlab运行得到如下结果：

即决策者的主观偏好P＊值与实际运行中车辆所行驶的最短距离的关系见表5。

由图4可见，优化后路径长度得到很大的改进，并且，随着P＊逐渐减小，所分配车辆行驶的距离越短，即优化的结果越来越好。但从理论上分析，P＊逐渐减小会使任务失败的可能性增加。因此，在大型的物流企业中，决策者的偏好往往决定了运输策略的优劣。在实际的车辆调度中，若以车辆行驶距离最短为目标函数来看，企业应该选择风险偏好型的决策，即越小的P＊值会带来越低的物流成本。P＊＝0.03时优化过程图见图5。

表5 P＊与实际运行中车辆所行驶的最短距离的关系Table5 Relation between P＊and the actual operation of the vehicle traveling on the shortest distance

5 结 论

在引入决策者偏好的基础之上，把客户的模糊需求进行实际需求模拟，用简单的聚类分析的方法对物流区域进行划分，使具有相似需求的节点归为一类，从而使物流企业在面对大型的物流配送问题时可以分类解决，减少了物流成本，提高了配送效率。在每个物流区域内部根据节点的位置坐标利用模拟退火算法进行车辆路径安排，其中将决策者的主观偏好P＊值作为一个控制参数，观察P＊值的大小对车辆行驶的最短路径有何影响，通过运用

Matlab进行最短路径的安排实验，从所产生的最短路径情况来看，在越小的P＊值下，车辆的行驶路径最短，这一结论为决策者在模糊需求的问题上所做决策时提供了参考标杆，有助于决策者在动态的车辆路径安排上做出更好的决策，从而减少了物流成本和风险。

[1]Dantzig G B，Ralnser J H.The truck dispatching problem [J].Management Science，1959，6（1）：80-91.

[2]Holland J H.Adaptations in natural and artificial systems[M].AnnAror：University of Michigan Press.1976.

[3]Gillett B，Miller L.A heuristic algorithm for the vehicle dispatch problem [J].Operations Research，1974，22：340-349.

[4]Moshe D，Gilbert L，Pierre T.Vehicle routing withstochastic demands：Properties and solution frameworks[J].Transportation Science，1989，23（3）：166-176.

[5]Michel G，Gilbert L，Rene S.An exact algorithm for the vehicle routing problem with stochastic demands and customers[J].Transportation Science，1995，29（2）：143-155.

[6]Wang Hsiao-Fan，Wen Yu-Pin.Time-constrained Chinese postman problems [J].Computers ＆ Mathematics with Applications，2002，44（34）：375-387.

[7]张建勇，李 军，郭耀煌.具有模糊预约时间的VRP混合遗传算法 [J].管理科学学报，2005，8（3）：64-71.

[8]张建勇，李 军，郭耀煌.带模糊预约时间的动态VRP的插入启发式算法 [J].西南交通大学学报，2008，43（1）：108-114.

[9]Tang Jia-fu，Pan Zhen-dong，Fung Richard Y K，et a1.Vehicle routing problem with fuzzy time windows[J].Fuzzy Setsand Systems，2009，160（5）：683-695.

[10]王 勇，毛海军，刘 静.带时间窗的物流配送区域划分模型及其算法 [J].东南大学学报，2010，40（5）：1077-1083.

[11]于 波，丁 源.带模糊需求的多类型车辆路径问题研究 [J].兰州交通大学学报：自然科学版，2006，25（3）：134-140.

[12]梅长林，周家良.实用统计方法 [M].北京：科学出版社，2002.

[13]张建勇，郭耀煌，李 军.模糊需求信息条件下的车辆路径问题研究 [J].系统工程学报，2004，19（1）：74-78.