改进模拟退火算法在物流优化中的应用

唐 琼，伍星华，张振文

（衡阳师范学院 经济与管理学院，湖南 衡阳 421002）

在物流优化中，物流设施选址、库存决策和车辆路径决策一直是三个关键问题，以前，学者们分别对这三个领域进行研究，并取得了很多的研究成果。但事实上，在设施、货物配送、以及运输货物的车辆路线决策之间却存在密切的相互依赖的关系，物流优化应该要根据这种依赖关系来开展［1］。根据这一思想，学者们对物流优化相关问题展开了研究。早期的研究主要集中在三个决策要素的两两集成，如选址路径问题、库存路径问题、选址库存问题等，近年来学者们开始关注三者综合集成的选址－库存－路径问题的研究［2－6］。Liu和Lee最早研究LIRP，他们给出了一个考虑库存决策的选址－路径问题的模型，同时针对模型提出了一个两阶段的启发式算法［7］。进一步的，Liu和Lin针对［7］文两阶段的启发式算法容易陷入局部最优的缺陷，提出了一种基于模拟退火算法的全局优化启发式算法［8］。国内，崔广彬和李一军首先对选址库存路径问题进行了研究［9］。而在最近的研究工作中，Shen和Qi建立了一个以选址、库存及运输成本最小为目标函数的非线性规划模型，同时提出了内嵌分枝定界法的拉格郎日算法求解该模型［10］。唐琼等基于二层规划建立了一个选址库存路径问题模型，并设计了双层模拟退火算法求解该模型［11］。

另一方面，整个市场需求的特征发生改变，逐渐趋向个性化、多样化，这样导致市场需求变得更随机，产品生命周期越来越短，企业的成功也越来越取决于其对客户订单的响应能力，时间已经成为影响企业竞争优势的一种新的核心资源［12］。尤其是在路径安排时，时间已成为影响决策的重要因素。Solomon［13］和 Desrosires等学者［14］最早将时间因素加入到一般车辆路径问题中，对带时间窗的车辆路径问题进行了研究。

本文在前人研究的选址－库存－路径模型基础上，考虑客户对送货物时间的要求，引入软时间窗，建立了带软时间窗的选址－库存－路径问题（Location Inventory Routing Problem with Soft Time Window，LIRPTW）模型，即如果配送车辆无法将货物在客户要求的时间窗内将货物送达，那么必须按照违反时间窗的长短对配送中心施以相应的惩罚成本。

1.带软件时间窗的选址库存路径模型

本文研究的LIRPTW是基于集成物流系统的供应链二级分销网络系统，系统中有一个生产基地，多个配送中心，多个客户，客户的库存策略为多周期随机存贮策略，从生产基地到各个配送中心的网络定义为一级网络，网络配送中心与客户构成的网络定义为二级，配送方式采取循环路线配送的方式。本文模型将同时对以下几个问题进行决策：（1）选址决策：即从备选配送中心中选出最佳数量的配送中心；（2）分配决策：即将客户分配给某个已选定的配送中心；（3）路径决策：即确定每条路线上车辆经过客户的顺序；（4）库存决策：即确定每条路线上所有客户的最佳订货点及最佳订货量。

1.1 模型假设。文中LIRPTW是基于如下假设：（1）客户需求为单一产品，潜在的配送中心有多个，每个客户只分配给一个配送中心；（2）建立和经营各备选配送中心的费用为固定值，且已知；（3）客户的需求是确定性的，同时提前期内需求的分布已知；（4）车辆为同一类型，且每辆货车在完成配送任务后要求返回到出发点。

1.2 符号说明。J为备选配送中心集合 ｛j｜j＝1，2，…，J｝；K为客户集合 ｛k｜k＝1，2，…，K｝；V为车辆集合 ｛v｜v＝1，2，…，V｝；Setv表示路线v上客户的集合；F j为配送中心j的固定投资和管理费用，其中j∈J；C j为从已知生产基地到备选配送中心j的单位产品运输费用，其中j∈J；C u为使用每一辆货车的固定成本；DM k为客户k在一定时期内的总需求量，其中k∈K；f k（t）为客户k在订货提前期L内的需求概率密度函数，其中k∈K；C h为单位商品的存贮费用；C o为每次订货的固定费用；C s为单位商品的缺货费用；d gh表示点g到点h的距离，其中g，h∈J∪K；C t为单位距离货物的运输费用；Mup为货车的最大载重量；Max为货车的最大服务能力；ET k为达到k点的最早时间，时间窗的上限，其中k∈K；LT k为到达k点的最迟时间，时间窗的下限，其中k∈K；P E表示没按客户要求提前将货物送到客户平均单位时间的惩罚成本；P L表示没按客户要求延迟将货物送到客户平均单位时间的惩罚成本；T k为到达k点的时间，其中k∈K；S k为在k点服务时间，其中k∈K；t gh表示从g点到h点所需要的运输时间，其中g，h∈J∪K；D v为巡回路线v上所有客户的总需求量，其中v∈V；u v为巡回路线v上所有客户在提前期L内的平均需求，其中v∈V；r v为巡回路线v上客户的订货点，其中v∈V；Q v为巡回路线v上客户的订货量，其中v∈V；S（r v）为路线v上客户缺货数量的期望值，其中v∈V；表示是否选中备选配送中心j，选中y j＝1，没选中y j＝0，其中j∈J；z jv表示配送中心j是否在巡回路线v上，是取1，否取＝0，其中j∈J，v∈V；X vQh表示第v辆货车是否经过客户g到客户h，则为1，否则为0，其中；表示路线v上客户k是否由配送中心j服务，是取1，否则取0，其中j∈J，k∈K，v∈V。

1.3 数学模型。LIRPTW模型的目标函数是最小化设施选址、库存和车辆运输三成本以及违反时间窗付出的惩罚成本之和，这个问题的数学模型为：

模型中，式（1）使物流系统总成本最少，总成本包括设施选址成本、库存成本和车辆运输成本以及货车违反时间窗要承担的惩罚成本。约束条件（2）表示至少要在备选的配送中心（已知数量）选择一个配送中心；约束条件（3）任巡回路线上货车的一次配送过程的配送量不能大于其载重量；约束条件（4）任一货车的总配送量不能大于其最大的服务能力；约束条件（5）保证每个客户有且仅能由一个配送中心为其进行配送货物；约束条件（6）表示任意两个选定的配送中心之间不存在有路线连接；约束条件（7）保证运输路线的连续性，货车不能在停留在客户处；约束条件（8）保证只有运输路线经过了该客户，该客户才能被指派给其对应的配送中心；等式（9）表示每条路线上配送车辆到达各个客户的时间；式（10）－（13）0－1为决策变量的约束。

2.模型求解

本文使用两阶段启发式算法对LIRPTW模型进行求解，即将问题分解成选址和带软时间窗的库存路径两个子问题，因此本节介绍求解LIRPTW模型的改进模拟退火算法求解子问题，而在确定车辆路线安排的情况下可用文献［7］的算法计算最佳订货量与订货点的方法。选址改进阶段通过调整配送中心的布局改进解，侧重于选址及分配决策，而库存路径阶段通过调整路线上的客户从而达到改进解的作用，侧重于路径和库存决策。

2.1 初始化。利用就近原则，快速构造初始解。针对每个客户选择一个离它最近的配送中心，以直送的形式构成初始路线V t（1＜＝t＜＝v）及初始解X0，并将初始解作为当前解，同时将初始解作为当前最优解，即令X＊＝X0，SC（X＊）＝SC（X0）。初始化最大迭代次数max＿count，禁忌表Tabu，令当前迭代次数count＝0。

2.2 选址改进阶段。Step0.初始化初始温度T，停止温度T s，温度下降系数r，最大接受解的次数max＿reci＿iter，连续未找到更好解的最大次数max＿unchang＿iter，最大候选解个数max＿cand＿count。令当前接受解的次数reci＿iter，当前连续未找到更好解的累计次数unchang＿iter，当前候选解数cand＿count都为0。

Step1.利用DROP和SWAP＿LOCATION两种领域操作在X0的基础上产生max＿cand＿count个满足容量限制的解X，将X加入到领域集N（X0）作为候选解。

DROP操作：随机选择路线V j，设该路线上的客户由配送中心D j负责配送货物，此时D j的状况为开放的。再选择一个离路线V j比较近的开放配送中心D i，关闭D i，将V i路线上由D i负责配送的客户分配给D j。

SWAP＿LOCATION操作：随机分别选择两条路线V i和V j，其中V i上的配送中心为D i，V j上的配送中心为D j，交换两条路线上的配送中心，即路线V i上客户由D j服务，路线V j上客户由D i服务。

Step2.选出领域集N（X0）中最好的解X1，判断解X1是否在禁忌表中，如果是，转Step1；不是，则接受X1为当前解，且更新X0＝X1，SC（X0）＝SC（X1），判断X1是否优于最优解X＊，如SC（X1）＜SC（X＊），接受X1为当前解，X＊＝X1，SC（X＊）＝SC（X1），以及更新禁忌表，转Step3。

Step3.利用DROP和SWAP＿LOCATION两种领域操作在解X0的基础上产生满足容量限制的解X1。判断X1是否在禁忌表，如果是，转Step1，不是，转Step4。

Step4.令△SC＝SC（X1）－SC（X0），如果△SC＜＝0，则接受X1为当前解，并令X0＝X1，SC（X0）＝SC（X1），unchang＿iter＝0，reci＿iter＝reci＿iter＋1，更新禁忌表。进一步，判断X1是否优于当前最优解X＊，如果是，则X＊＝X1，SC（X＊）＝SC（X1）。如果exp（－△SC/T）＞random（0，1），接受X1为当前解，并令X0＝X1，SC（X0）＝SC（X1），unchang＿iter＝0，reci＿i ter＝reci＿iter＋1，更新禁忌表。否则，unchang＿iter＝unchang＿iter＋1。

Step5.如果reci＿iter＞max＿reci＿iter或者unchang＿iter＞max＿unchang＿iter，令T＝T＊r，同时判断程序是否达到选址改进阶段终止条件，即判断T＜T s，如果是，X0＝X＊，SC（X0）＝SC（X＊），转 Step6；否则转Step1。

2.3 库存路径改进阶段。Step6.重复过程Step0至Step5，在这个阶段的领域操作为INSERT和SWAP＿ROUTING。INSERT操作：随机选取两条路线V i和V j，在路线V i上随机选取客户C1，在路线V j上选取离C1距离较近的客户C2和C3，将C1插入到路线V j上，放在C2和C3中间，顺序为C2，C1，C3，并将路线V i上的客户C1删除。SWAP＿ROUTING操作：随机选取两条路线V i和V j，然后随机从路线V i上选取客户C1，从路线V j上随机选取客户C2，交换C1和C2。

Step7.判断当前迭代次数是否达到最大迭代次数，即count＞＝max＿count，如果是，程序终止，输出最优解X＊和SC（X＊），否则，count＝count＋1，转Step6。

3.算例分析

3.1 与模拟退火、禁忌算法对比。假定在供应链二级分销网络系统中，有1个工厂，4个备选的配送中心，15个客户，且配送中心和客户分别在一个边长为20km的正方形地域内，Mup＝150，Max＝1000，车辆平均行驶速度为20km/h，C t＝1，C u＝20，C o＝15，C h＝1，C s＝2，PE＝5，PL＝10。4个备选配送中心的坐标分别为：（18.9，15.2），（8.6，8.4），（7.4，1.0），（13.2，15.1），其他相关的参数：C j分别为：2，3，2，4，F j分别为：250，430，150，240。15个客户的坐标分别为：（12.8，8.5），（18.4，3.4），（15.4，16.6），（15.5，11.6），（10.6，7.6），（12.5，2.1），（13.8，5.2），（14.8，2.6），（1.8，8.7），（17.1，11.0），（0.2，2.8），（11.9，19.8），（6.4，5.6），（9.6，14.8），（6.7，16.9）；要求提供服务的时间窗分别为：（4.7，10.5），（1.5，6.0），（4.7，10.2），（3.7，8.9），（6.7，12.3），（0.6，5.7），（2.6，6.8），（4.1，10.1），（3.4，8.1），（2.0，6.0），（2.1，6.3），（6.8，12.0），（6.0，10.4），（5.4，9.6），（2.5，8.1）；总需求量分别为：245，345，360，451，523，396，589，450，360，389，461，574，326，465，492；在周期内需求服从均匀分布，下限都为0，上限分别为：5，4，8，9，6，7，6，5，8，7，5，6，8，7，9。用 Matlab6.5编程，算法中涉及的参数值：T＝90，r＝0.9，T s＝10，禁忌表长为7，max＿cand＿count＝5，max＿count＝5，max＿reci＿iter＝20，max＿unchang＿iter＝20。本实验将本文算法与禁忌搜索和模拟退火算法分别进行了对比，对上述实例，三种算法各执行算法20次，取得到的最好解，其对应的迭代过程中最优解收敛图如下图1所示。

图1 运行收敛图

本文算法内嵌具有较强的“爬山”能力的禁忌搜索算法来搜索领域解，因此搜索解时能够跳出局部的最优解，转向领域解的其他区域，进而获得更佳的全局最优解。其次为了能快速地跳出局部最优解以及减少不必要的迭代次数，修改了模拟退火算法的收敛准则。再次，为了保证算法在迭代过程中不丢失最优解，利用了禁忌搜索算法的记忆功能。图1表示本算法在初期的收敛速度非常快，后期也只需要较少的迭代次数就能找出最优解，且最优解比单独使用禁忌搜索和模拟退火算法所找到的最优解要好。

3.2 与文［8］算法对比。这一节将本章算法与Liu文算法［8］进行对比，本节构造了小、中和大15组不同问题规模的随机数例进行测试。算法的有效性主要通过三个指标来衡量：解的质量（算法能寻找到的最优成本）、求解效率即CPU时间和惩罚成本。

3.2.1 实验的设计。本节的随机实例构造方法如下：F j服从均匀分布U ［2500，5000］；C j服从均匀分布 U［2，6］；备选配送中心和客户的坐标都服从均匀分布U［0，100］；客户k的一年内总需求DMk服从均匀分布U［600，1000］；客户在提前期L内的需求服从均匀分布U［0，5］；时间窗的上限ET服从均匀分布U ［1，3］；而时间窗的下限则根据上限而随机确定。设Mup＝300，Max＝4000；车辆平均行驶速度为30，C t＝1，C u＝20，C o＝15，C h＝1，C s＝2，PE＝0.2，PL＝2，Sg＝0.25。本节中的实例规模大小，用m表示备选配送中心的个数，n代表所有客户的个数。

3.2.2 算法对比分析。在IntelPenitum2.20GHZ内存1GB的联想计算机上，操作系统为 WindowsXP，用 Matlab6.5编程。算法中涉及的参数值分别为：当10＜＝n＜＝40，max＿reci＿iter＝10；当50＜＝n＜＝100，max＿reci＿iter＝20；当110＜＝n＜＝150，max＿reci＿iter＝30，其余参数同4.1部分。

对每组随机数据执行算法10次，取运行得到的最优解，得到实验结果如表1所示。

表1 算法对比结果

表中第3、4和5列表示运行两种算法得到的最优成本以及改进率，第6、7和8列表示两种算法寻找最优成本程序所需要的时间以及改进率，第9、10和11列表示两种算法寻找到的最优解对应的时间惩罚成本及改进率。对于第5列总成本的改进率，可以发现对于小规模问题成本改进率不高，但是随着问题规模增大，成本改进率越来越大，平均成本改进率为15.5%。对于第8列的算法执行时间改进率，最低是38.4%，最高为61.2%，平均的改进率为56.2%。对于时间惩罚成本的改进率最低为61.2%，最高为95.9%，平均改进率为81.5%。因此，与Liu［8］文相比，本文的算法在执行时间上大约能节约一半的时间并且也能在一定程度上节约总成本。同时，能节约一半以上的时间惩罚成本，说明利用本文算法能大量缩短对客户的响应时间，由此可见，本文算法能对解的性能作较大的提高。

本文研究了带软时间窗的选址－库存－路径问题（LIRPTW），建立了LIRPTW模型，并提出了一种改进的结合禁忌搜索和模拟退火算法用于问题求解，最后通过实例演算以及算法对比，结果说明模型和算法的有效性。

本文在库存方面本问没有考虑配送中心的周期库存和安全库存成本，另一方面本文在处理软时间窗的问题上，比较简单，是在考虑选址－库存－路径三成本之和最小的前提下，以惩罚成本的方式处理违反时间窗的配送中心。在进一步的研究中，将会在考虑三成本之和的同时，考虑时间因素，同时将模型拓展，并改进本文算法。

［1］ Watson－Gandy C，Dohrn P.Depot location with van salesmen：a practical approach［J］.Omega Journal of Management Science，1973，1（3）：321－329.

［2］Perl J.，Sirisiponsilp S.Distribution networks：facility location，transportation and inventory［J］.International Journal of Physical Distribution ＆ Materials Management，1989，18（5）：18－26.

［3］Jayaraman，V.Transportation，facility location and inventory issues in distribution network design：an investigation［J］.International Journal of Operations ＆ Production Management，1998，18（5）：471－494.

［4］Nozick，L.K.，Turnquist，M.A.Integrating inventory impacts into a fixed－charge model for locating distribution centers［J］.Transportation Research E，1998（34）：173－186.

［5］Nozick，L.K.，Turnquist，M.A.Inventory，transportation，service quality and the location of distribu－tion centers［J］.European Journal of Operational Research，2001，129（2）：362－371.

［6］Ambrosino，D.，Scutella，M.G.Distribution network design：New problems and related models［J］.European Journal of Operational Research，2005，165（3）：610－624.

［7］Liu，S.C.，Lee，S.B..A two－phase heuristic method for the multi－depot location routing problem taking inventory control decisions into consideration［J］.International Journal Advanced Manufacturing Technology，2003，22（11）：941－950.

［8］Liu，S.C.，Lin，C.C..A heuristic method for the combined location routing and inventory problem ［J］.International Journal Advanced Manufacturing Technology，2005，26（4）：372－381.

［9］崔广彬，李一军 .基于双层规划的物流系统集成定位－运输路线安排－库存问题研究［J］.系统工程理论与实践，2007，27（6）：49－55.

［10］Shen，Z.－J.，Lian，Q..Incorporating inventory and routing costs in strategic location models［J］.European Journal of Operational Research，2007，179（2）：372－389.

［11］唐琼等 .基于二层规划的选址库存路径问题研究［J］.物流技术，2011（13）：137－142.

［12］Stalk G J.Time－the next source of competitive advantage［J］.Harvard Business Review，1988，66（4）：41－51.

［13］Solomon M.M..Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints［J］.Operations Research，1987（35）：254－264.

［14］ Desrosiers，J.， Soumis， F.，and Desrochers，M.Routing with Time Windows by Column Generation［J］.Networks，1988（14）：545－565.