模糊环境下基于改进节约算法的路径优化
2017-11-30贺书杰
贺书杰
摘要：基于循环取货理论和背景，从TPL角度研究汽车零部件运输路径优化问题。由于需求量及成本这些变量在一个范围内波动，因此在模糊的条件下，建立最小化运输成本模糊规划模型，并运用模糊理论知识将模糊模型转化成确定型模型，并采用改进的节约算法求解满载和非满载的路径成本。
Abstract： Based on the background of cycle picking theories， from the perspective of TPL， the optimization of auto parts transportation route is studied. As the demand and cost of these variables fluctuated in a range， in the fuzzy condition， it is to establish the fuzzy programming model for minimizing transportation cost， and uses the fuzzy theory knowledge to transfer fuzzy model into the determined model， and uses the modified saving algorithm to solve fully loaded and non loaded path cost.
关键词：模糊环境；循环取货；路径优化；改进节约
Key words： fuzzy environment；cycle picking；path optimization；improved saving
中图分类号：F274 文献标识码：A 文章编号：1006-4311（2017）34-0098-03
0 引言
随着经济的快速发展，人们生活质量的不断提高，汽车从高昂的奢侈品变成了日常的消费品进入了千家万户。汽车制造企业也面临挑战，当经济市场上占有的份额达到规定的利润饱和点，企业将新的利润增长点放在物流费用上，尤其是入场物流。目前，传统的入场模式已经无法满足物流产业发展的需求，循环取货作为在JIT供应和精益思想指导下一种新型的入场物流模式逐渐被采用。因此，TPL采取循环取货模式具有理论意义和现实意义。
1 研究现状
邰晓红，李璐[1]加入了客户对时间的约束，提出改进的节约法；郭荣[2]对Milk Run模式下配送的多周期问题进行了研究；孙洋等[3]通过构建车辆路径优化的模型，运用蚁群算法对模型进行求解；王小会[4]考虑了软时间窗的约束条件，建立车辆行驶的费用和罚函数之和最小的模型；吴健，倪伟等[5]本文主要选取沃尔沃汽车的入厂物流案例研究路径规划问题。从文献来看，大多数对确定的模型进行研究，对不确定模糊模型研究相对更少，由于需求量及成本在一个范围内波动，所以模糊环境下研究路径优化具有参考价值。对于不确定的运输研究多集中在找出统计规律的的随机车辆路径问题，但物流系统受到不可控因素的影响而具有模糊不确定性。因此，本文主要集中在模糊环境下基于循环取货路径优化研究。
2 模型
2.1 问题的描述
问题描述：一个汽车制造厂和若干个供应商，TPL通过与供应商和制造工厂签订协议的条件下，从配送中心出发，在供应商处取货运至配送中心。每个供应商的位置一定，时间窗一定，每辆车装载容量一定，车辆的单位运输成本和固定成本、需求量为三角模糊数，并且不允许缺货，TPL取货的同时要归还供應商的容器。
2.2 模型建立
①d每辆车单次派遣费用d=（C，C，C）；
②f单位行驶费用f=（C，C，C）；
③i表示整车厂对零部件i的单次需求量，i=（Q，Q，Q）；
④dij供应商i到供应商j的距离；
⑤[ET，LT]为客户要求最佳送货时间范围；在[A，ET]和[LT，B]范围内客户会收货，产生等待成本a和延误成本b；在[A，B]时刻之外到达产生一个无穷大的惩罚成本l。p（t）是惩罚成本；ti到达供应商的时间；tij从供应商i到j的运输时间；si表示在供应商i处停留时间。
p（ti）=l→+∞ ti？燮A或ti？叟Ba（ETi-ti） A？燮ti？燮ETi0 ETi？燮ti？燮LTib（ti-LTi） LTi？燮ti？燮B
⑥xijm=1 车辆m从供应商i到供应商j；0 否则
⑦yim=1 供应商i的任务由车辆m完成；0 否则
运输成本包括车辆启动的固定成本和运输费用。实际中供应商会设置时间约束，考虑实际中突发状况的存在采取软时间窗约束。
模型为：
min=ddijxijm+fx0im+P（ti）（1）
iyim？燮？鄣m* （2）yim=1 （3）xijm=yim （4）xijm=yim （5）ti+si+tij-M（1-xijm）？燮tj （6）ETi？燮ti？燮LTi （7）xijm？燮U-1 （8）
（1）目标函数运输成本最低；（2）每条线路上车辆载容量的限制；（3）只有一辆车m到供应商i处取货；（4）车辆m最多能从某一个取货点出发；（5）车辆m最多到达某一个取货点一次；（6）在配送路线中相继到达两客户的时间关系；（7）表示要求到达供应商的时间范围；（8）消除子回路。
3 模型求解
单目标机会约束规划可以表示为：
minf
s.t. Pos{f（x，ξ）？燮f}？叟β
Pos{gj（x，ξ）？燮0，j=1，2，…，p}？叟αendprint
其中β和α分别是事给定的目标和约束的置信水平，是一种minmax模型。
设三角模糊数（q1，q2，q3），则对任意给定的置信水平α（0？刍α？刍1），当且仅当z？叟（1-α）q1+αq2时有pos{q？燮z}？叟α成立。
三角模糊数的数乘和加法运算规则：
①1？茌2=（l1+l2，m1+m2，μ1+μ2）；
②1？茚2≈（l1l2，m1m2，μ1μ2）；
③λ？茌1≈（λl1，λm1，λμ1）；
④（1）-1≈（1/μ1，1/m1，1/l1）
目标函数模糊部分转化为清晰的函数可得：
令=ddijxijm+fx0im
pos{？燮z}？叟α1
则posddijxijm+fx0im？燮z？叟α1
posiyim？燮？鄣m*？叟α2
则min z
dijxijm[（1-α1）C+α1C]+x0im[（1-α1）C+α1C]？燮z
（（1-α2）Q+α2Q）yim？燮？鄣m*
节约算法是解决车辆路线优化问题一个简单易行的方法，但随着各种具体约束的衍生，必须将传统的节约算法进行适当修改。改进节约算法非满载和满载步骤如下：
非满载时：
Step1：配送中心0为起点，起点与各点相连，有n-1条线路，0-j-0（j=1，2，...，n）；
Step2：计算所有可连接点对（i，j）节约值s（i，j）=C0i+C0j-Cij，将计算出的s（i，j）按从大到小的顺序进行排列；
Step3：初始化参数：路线n=0，集合S=？覫；
Step4：选择时间窗最早的客户点i（i？埸S），将i加入集合S中，q=0；
Step5：依次选择距离i距离节约值最大的点j，j？埸S；并做以下判断：若Q>q+qj，（q为车载货运量，Q为额定载重量），转到step6；否则不连接i，j，选择下一个节约值；
Step6：软时间窗设计：主要考虑i和j连接后所产生的惩罚函数，将产生的惩罚函数和所节约的里程费用进行比较判断是否实现连接。具体判断准则为：
①减少的里程费用为：
Fij=Wij*d=Wij*
②时间变化引起的惩罚成本：
p（ti）=l→+∞ ti？燮A或ti？叟Ba（ETi-ti） A？燮ti？燮ETi0 ETi？燮ti？燮LTi b（ti-LTi） LTi？燮ti？燮B
③若p（ti）>Fij，说明惩罚成本大于节约成本，则不连接，转到step5；若p（ti）=Fij，可连可连；若p（ti） Step7：是否客户点均在集合S中，若是，结束，否则令n=n+1，转Step4。 满载时： Step1-Step4，Step7：同非满载； Step5：依次选择距离i距离节约值最大的点j，j？埸S；并做以下判断：若Q>q+qj，（q为车载货运量，Q为额定载重量），转到step6；若当第一次Q Step6：软时间窗设计：主要考虑i和j连接后所产生的惩罚函数，将产生的懲罚函数和所节约的里程费用进行比较判断是否实现连接。具体判断准则为： ①减少的里程费用为： Fij=Wij*d=Wij* ②时间变化引起的惩罚成本： p（ti）=l→+∞ ti？燮A或ti？叟Ba（ETi-ti） A？燮ti？燮ETi0 ETi？燮ti？燮LTi b（ti-LTi） LTi？燮ti？燮B ③若p（ti）>Fij，说明惩罚成本大于节约成本，则不连接转到step5；若p（ti）=Fij，可连可连；若p（ti） 具体流程如图1。 4 总结 针对模糊环境下运输问题，本文建立了一个最小化运输模糊规划模型，以运输成本最小为目标。在运算的过程中，仅对供应链的上游就行了研究，对于三级供应链的研究可作为进一步研究的方向。 参考文献： [1]邰晓红，李璐.改进节约法下的物流配送路径优化问题[J].辽宁工程技术大学学报（自然科学版），2016，35（6）：667-672. [2]郭荣.MilkRun模式下汽车零部件配送的多周期ITIO问题研究[D].武汉理工大学，2014. [3]孙洋，严伟.基于蚁群算法的循环取货车辆路径优化[J].物流工程与管理，2015，37（7）：85-86. [4]王小会.多车场带时间窗车辆路径问题的粒子群优化算法[J]，兰州工业学院学报，2015，22（2）：52-55. [5]吴健，倪伟，等.面向循环取货路径优化问题的改进遗传算法研究[J].物流工程与管理，2015，10（39）：31-34.
