改进节约法下的物流配送路径优化问题

改进节约法下的物流配送路径优化问题作者：天天论文网日期：2016-3-1610:21:38点击：3摘要：为满足现实生活中一些客户在物流配送过程中的时间要求，在节约法的基础上加入了客户对时间的约束，提出改进的节约法，构建模型，提出模型假设和约束条件，列出目标函数，并给出求解过程，以阜新市A蔬菜批发中心为例进行分析，提出优化方案.结果表明，此种方法能够在满足关于时间约束的情况下有效的节约配送时间，缩短配送距离，进而节约成本.这种方法优化了之前的路径优化方法，加入了时间约束，更具有现实意义，有助于此类路径问题的求解.关键词：车辆路径问题；节约法；改进节约法；时间窗；物流配送0引言节约法作为一种经典的启发式算法，在求解小规模车辆运输路线优化问题上存在一定优势.但在实际生活中，有一些商品如生鲜等需要在一定的时间内送到客户手中，为了满足客户实际需求，将商品及时、准确、高效、经济地将配送到，还要考虑客户对服务时间的要求[1].所以，不能利用节约法直接求解配送车辆路径优化问题.因此，为解决此类问题，提出改进的节约法，不仅考虑配送的总路程还考虑配送的时间约束，即能够满足实际问题中客户对于配送时间的要求.1模型构建本文中要解决的配送线路的优化问题是典型的起点和终点相同的单车场非满载有时间窗约束的车辆路径优化问题，即在满足车辆容量限制、货物需求量要求、时间限制、运输里程限制等约束条件的前提下，以某配送中心为据点，组织合适的行车路线，使配送车辆可以有序的通过一系列的需求量和位置已知的目标顾客，并达到一定的目标.1.1模型假设及约束条件设立如下模型假设[2-4]：（1）配送中心以及每个客户的所在地理位置是确定的；（2）已知每个客户的需求量和时间约束；（3）已知配送车辆规格；（4）在配送方案中的每一条配送路径上，每个客户的需求量总和不能超过配送车的总装载容量限制；（5）每一客户所需求商品由一辆配送车进行配送；（6）在配送中心能力范围内安排配送，配送车辆数目不超过配送中心车辆总数目；（7）配送车辆需从配送中心出发，结束配送后要返回配送中心；（8）满足客户是对配送时间的要求.1.2模型描述a0为配送中心顶点，ai为第i个客户的需求点，其中（i=1,2,…,M）.配送中心有k辆配送车，每台车辆的载容量为bk（k=1,2,…,K），每辆车装载的商品箱数不能超过其最大装载容量.每个客户的需求量为ri，客户i到客户j的运输距离为dij，配送中心到客户i的距离为doi，每一段距离的运输都会产生一定的配送成本，α为单位距离的运输配送费用.要求配送车辆在客户要求的时段完成配送任务，目标函数为总成本最小[5-6].将模型中的参数和相关变量进行如下定义：a0为配送中心顶点；ai为第i个需求点；α为单位距离所花费的运输配送费用；M为客户数目的集合；dij为客户i到客户j之间的距离；ri为第i个客户的货物需求箱数；K为配送中心的车辆数；bk为第k辆配送车所装载的箱数；sij为客户i和客户j之间路程的节约量；ETi为允许配送车辆到达客户i的最早时间；LTi为允许配送车辆到达客户i的最晚时间；Tij为配送车辆从客户i到客户j所用行驶时间；RTi为配送车辆到达客户i的时间；WTi为配送车辆离开客户i的时间；UT为配送车辆途中货物卸货时间；β为违反客户所规定的送货时间而产生的单位惩罚成本系数；θ为运输盈利的系数，元/吨/公里.为了满足客户i对于配送时间的约束条件，配送车辆抵达客户的时间RTi应满足ETi≤RTi≤LTi，那么配送车辆到达下一个客户j的时间即为：RTi=WTi+UT+Tij.如果令CTj为将客户i与客户j纳入同一配送路径后，配送车辆到达客户j的时间变化量，则CTj=RTi+UT+Tij-RTj，其中RTi=Toi.CTj0为配送车辆到达客户j的时间延后，CTj=0为配送车辆抵达客户j的时间没有发生变化，CTj0为配送车辆提前到达客户j.为了方便对问题的描述，设b为在同一条线路上客户j和客户j以后的各个客户，Δj-为配送车辆到达客户j且均不违反客户j后面各客户时间约束所允许的最大时间提前量，Δj-=min{RTb-ETb}；Δj+为配送车辆到达客户j且客户j后面各点的时间都没有超过最大延迟量，Δj+=min{LTb-RTb}.▽j-定义为线路上客户j后各点均不需要等待时，到达客户j的时间提前量，▽j-≤Δj-；定义▽j+为线路上客户j后各点均不违反时间约束的到达客户j的时间延迟量，▽j+≤Δj+.为了方便模型的建立，将二进制变量作如下定义：上述模型的表述如下，式（1）为目标函数，为配送总费用最少，其中第一项为运输成本，第二项为惩罚成本；式（2）为保证配送车辆的数量不超过配送车辆的总数量；式（3）为保证每个客户的商品需求只能由一台配送车辆满足；式（4）和式（5）为整数约束；式（6）为如不能按客户所要求的时间送货而引起的单位时间惩罚成本的系数；式（7）保证每条配送路径上各客户的商品需求总数不超过配送车辆最多能够容纳的数量；式（8）、式（9）为配送车辆从配送中心出发最后仍回到配送中心；式（10）为商品在客户要求的配送时间约束内到达；式（11）为配送车辆是否在客户要求时间内到达，如不在取1，否则取0；式（12）为当商品没能按照客户时间送达时，惩罚成本小于等于其运输成本[7-10].2求解过程（1）输入配送中心和各个客户之间的距离dij；（2）将任意两个客户i和j连接在一起，利用ijoiojijs=d+d−d，(i,j=1,2,�,m)计算节约值，得S={s(i,j)|s(i,j)0(i,j=1,2,�,m)}.如果有m个客户，则节约值的个数为2mC；（3）将集合S中的元素sij从大到小进行排序；（4）若S=Φ，则算法结束，否则考察集合S中的元素sij是否满足以下三个条件之一，若满足其中任一条件则转步骤（5），否则转步骤（8）；①客户i，j均不在已构造的线路上；②客户i，j有一个在已构造的线路上，一个不在已经构造的线路上，在构造线路上的客户是起点或者终点；③客户i和客户j在已构成的不同线路上，且一个为自身线路中的第一个客户，另一个为自身线路中的最后一个客户.（5）计算连接客户i和j之后，线路上的货运箱数rij，若,则转为步骤（6），否则转为步骤（8）；（6）计算客户i和j之后，车辆到达客户j的时间变化量jiijjCT=RT+UT+T−RT.①如果=0jCT，即配送车辆整点到达，则转为步骤（7）；②如果0jCT，即配送车辆提前到达，则计算提前量Δj−，jΔj−≥CT则转为步骤（7），否则转为步骤（8）；③如果0jCT，即配送车辆延迟到达，则计算延迟量Δj+，jΔj+≥CT则转为步骤（7），否则转为步骤（8）；（7）将客户i和客户j连接成一条配送线路；（8）删除集合S中的元素，且客户i和客户j不能作为配送车辆的最初或者最终的线路点.继续搜索其余各点，将全部的2mC个节约值考察完毕，找到最佳的运输路径.3实例分析3.1基础数据分析A为阜新市蔬菜批发中心，和市内14家大型超市签订合约，每天早晨根据前一日订单及到货的时间要求向各家超市配送货物，蔬菜批发中心到各超市以及各超市间距离的具体情况见表1.__不同超市每天的平均需求量和时间约束的具体情况见表2.表2不同门店每天的平均需求量和时间约束Tab.2differentstores‘averagedemandandtimeconstraintsofeachday门店要求时间窗/h编号需求量/(箱·天-1)卸货时间UT/hETiLTi1100.400.401.50280.380.201.50350.350.603.004120.500.201.00570.350.302.50690.400.105.007110.450.458.008100.400.604.00970.350.508.001040.300.405.001190.500.305.001260.500.506.0013120.550.402.501480.600.201.50配送车辆在进行配送的过程中，如果配送车辆从配送中心到达某个超市i的时间满足，即配送车辆按照客户要求时间到达了门店，则取，若车辆提前到达，则取.如果车辆在配送过程中没能满足门店的时间约束，则设定惩罚系数β为无限大.配送车辆的平均行驶速度取值为28km/h.车辆在完成配送任务之后返回配送中心，运输过程中各路段的情况相同，运输盈利系数θ设为1元/吨/公里.车内有效装载面积最佳可容纳公司配送过程中标准尺寸的包装箱27个.3.2Matlab软件求解通过对车辆路径问题模型的建立和改进节约算法分析，本文选用Matlab软件进行配送线路选择的优化求解.节约里程表和行驶时间表见表3和表4.将相关数据、参数及编程语言输入到Matlab中进行求解，即可求得配送路径的最优解.根据求解结果，最终得到的配送方案为配送中心向14个超市配送的5条线路，见表5、图1，优化得到的配送方案的总成本598.3为元，总行驶距离为119.6km，总配送时间约为4.27h.具体信息如下：（1）0-3-2-9-10-0（2）0-14-12-13-0（3）0-8-11-5-0（4）0-1-7-0（5）0-4-6-0表5优化后配送路线信息Tab.5informationofdistributionrouteafteroptimization路线配送路线行驶距离/km)行驶时间/h10-3-2-9-10-031.91.1420-14-12-13-030.11.0730-8-11-5-023.30.8340-1-7-018.40.6650-4-6-015.90.57合计119.64.27图1配送路径Fig.1distributionroutepicture3.3结果分析A公司在进行配送线路优化之前主要依靠司机的配送经验进行线路选择，按照顺路或者就近的原则将符合条件归为同一线路，以配送人员在送货过程中经常采用的一个配送线路方案为例，对优化前后的配送方案进行比较分析，见表6.优化前常采用的配送线路方案：（1）线路一：0-10-11-12-0；（2）线路二：0-2-9-0；（3）线路三：0-1-5-6-0；（4）线路四：0-4-13-0；（5）线路五：0-14-3-0；（6）线路六：0-8-7-0.表6优化前配送路线信息Tab.6informationofdistributionroutebeforeoptimization路线配送路线行驶距离/km行驶时间/h10-10-11-12-031.01.1120-2-9-027.30.9830-1-5-6-018.10.6440-4-13-024.10.8650-14-3-023.30.8360-8-7-023.20.82合计147.05.24通过将以上信息与利用改进节约法求得配送线路方案进行比较分析，我们可以发现，改进后的车辆配送路径方案能够有效的节约配送时间，缩短总配送里程，降低配送成本，提高公司的经济效益.4结论本文提出了有时间窗约束的改进的节约法，建立了起讫点相同的单车场、非满载、有时间窗约束的车辆路径优化问题模型，以运输成本最小为优化目标，提出求解方法，并引入A公司实例，通过计算，证明该方法具有实际意义.参考文献：[1]成榕,吴先锋.最小时间路径算法模糊结构元改进[J].辽宁工程技术大学学报(自然科学版),2014,33(5):683-686.doi:10.3969/j.issn.1008-0562.2014.05.023CHENGRong,WUXianfeng.Improvementofminimum-timepathalgorithmbasedonstructuredelementtheory[J].JournalofLiaoningTechnicalUniversity(NaturalScience),2014,33(5):683-686.doi:10.3969/j.issn.1008-0562.2014.05.023[2]郑英,孟志青.基于节约算法的烟草物流配送线路优化[J].中国管理信