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

《改进节约法下的物流配送路径优化问题》由会员分享，可在线阅读，更多相关《改进节约法下的物流配送路径优化问题（3页珍藏版）》请在金锄头文库上搜索。

1、改进节约法下的物流配送路径优化问题作者：天天论文网 日期： 2016-3-16 10:21:38 点击： 3 摘 要： 为满足现实生活中一些客户在物流配送过程中的时间要求， 在节约法的基础上加入了客户对时间的约束，提出改进的节约法，构建模型，提出模型假设和约束条件，列出目标函数，并给出求解过程，以阜新市 A 蔬菜批发中心为例进行分析，提出优化方案.结果表明，此种方法能够在满足关于时间约束的情况下有效的节约配送时间，缩短配送距离，进而节约成本.这种方法优化了之前的路径优化方法，加入了时间约束，更具有现实意义，有助于此类路径问题的求解.关键词：车辆路径问题；节约法；改进节约法；时间窗；物流配送0

2、引言节约法作为一种经典的启发式算法，在求解小规模车辆运输路线优化问题上存在一定优势 .但在 实际生活中，有一些商品如生鲜等需要在一定的时间内送到客户手中，为了满足客户实际需求，将商品及时、准确、高效、经济地将配送到，还要考虑客户对服务时间的要求1. 所以，不能利用节约法直接求解配送车辆路径优化问题.因此，为解决此类问题，提出改进的节约法，不仅考虑配送的总路程还考虑配送的时间约束，即能够满足实际问题中客户对于配送时间的要求.1 模型构建本文中要解决的配送线路的优化问题是典型的起点和终点相同的单车场非满载有时间窗约束的车辆路径优化问题，即在满足车辆容量限制、货物需求量要求、时间限制、运输里程限制等

3、约束条件的前提下，以某配送中心为据点，组织合适的行车路线，使配送车辆可以有序的通过一系列的需求量和位置已知的目标顾客，并达到一定的目标 . 模型假设及约束条件设立如下模型假设2-4 ：（ 1）配送中心以及每个客户的所在地理位置是确定的；（ 2 ）已知每个客户的需求量和时间约束；（3）已知配送车辆规格；（4 ）在配送方案中的每一条配送路径上，每个客户的需求量总和不能超过配送车的总装载容量限制；（5）每一客户所需求商品由一辆配送车进行配送；（6 ）在配送中心能力范围内安排配送，配送车辆数目不超过配送中心车辆总数目； （ 7 ）配送车辆需从配送中心出发，结束配送后要返回配送中心；（ 8 ）满足客户是

4、对配送时间的要求.模型描述a0 为配送中心顶点， ai为第i个客户的需求点，其中（i=1,2,M）.配送中心有k辆配送车，每台车辆的载容量为bk （k=1,2,2 ,每辆车装载的商品箱数不能超过其最大装载容量.每个客户的需求量为ri ， 客户 i 到客户 j 的运输距离为dij ，配送中心到客户i的距离为doi,每一段距离的运输都会产生一定的配送成本，”为单位距离的运输配送费 用 .要求配送车辆在客户要求的时段完成配送任务，目标函数为总成本最小5-6. 将模型中的参数和相关变量进行如下定义：a0为配送中心顶点；ai为第i个需求点；”为单位距离所花费的运输配送费用；M为客户数目的集合；dij 为

5、客户 i 到客户 j 之间的距离； ri 为第 i 个客户的货物需求箱数； K 为配送中心的车辆数； bk 为第 k 辆配 送车所装载的箱数； sij 为客户 i 和客户 j 之间路程的节约量； ETi 为允许配送车辆到达客户 i 的最早时间；LTi为允许配送车辆到达客户i的最晚时间；Tij为配送车辆从客户i到客户j所用行驶时间；RTi为配送车辆 到达客户i的时间；WTi为配送车辆离开客户i的时间；UT为配送车辆途中货物卸货时间；0为违反客户 所规定的送货时间而产生的单位惩罚成本系数；。为运输盈利的系数，元/吨/公里.为了满足客户i对于配送时间的约束条件，配送车辆抵达客户的时间RTi应满足ET

6、K RTK LTi,那么配送车辆到达下一个客户j的时间即为：RTi=WTi+UT+Tij如果令CTj为将客户i与客户j纳入同一配送路径后，配送车辆到达客户j的时间变化量，则CTj=RTi+UT+Tij-RTj其中RTi=0为配送车辆到达客户j的时间延后，CTj=0为配送车辆抵达客户j的 时间没有发生变化，CTj0为配送车辆提前到达客户j.为了方便对问题的描述，设 b为在同一条线路上客户 j和客户j以后的各个客户， j-为配送车辆到达客户j且均不违反客户j后面各客户时间约束所允许的最大 时间提前量， j-=minRTb-ETb; j+为配送车辆到达客户j且客户j后面各点的时间都没有超过最大延迟

7、量，j+=minLTb-RTbj-定义为线路上客户j后各点均不需要等待时，到达客户j的时间提前量，）-j-;定义 j+为线路上客户j后各点均不违反时间约束的到达客户j的时间延迟量，Vj+w j+.为了方便模型的建立，将二进制变量作如下定义：上述模型的表述如下，式（1）为目标函数，为配送总费用最少，其中第一项为运输成本，第二项为惩罚成本；式（ 2）为保证配送车辆的数量不超过配送车辆的总数量；式（ 3）为保证每个客户的商品需求只能由一台配送车辆满足；式（4）和式（5 ）为整数约束；式（ 6 ）为如不能按客户所要求的时间送货而引起的单位时间惩罚成本的系数；式（ 7）保证每条配送路径上各客户的商品需求

8、总数不超过配送车辆最多能够容纳的数量；式（ 8）、式（ 9 ）为配送车辆从配送中心出发最后仍回到配送中心；式（10）为商品在客户要求的配送时间约束内到达；式（11）为配送车辆是否在客户要求时间内到达， 如不在取 1 ， 否则取 0；式（ 12） 为当商品没能按照客户时间送达时， 惩罚成本小于等于其运输成本7-10.2求解过程（ 1）输入配送中心和各个客户之间的距离dij ；（ 2）将任意两个客户 i 和 j 连接在一起，利用 ij oioj ij s=d+dd,（i,j=1,2,m）计算节约值，得 S=s（i,j）|s（i,j）0（i,j=1,2,m）.如果有 m 个客户，则节约值的个数为 2

9、mC； （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的时间变化量

10、j i ij j CT=RT+UT+TRT）如果 =0j CT,即配送车辆整点到达，则转为步骤（7）;如果0j CT,即配送车辆提前到达，则计算提前量 j,jj）CT则转为步骤（7）,否则转为步骤（8）;如果0j CT,即配送车辆延迟到达，则计算延迟量 j+, jj+CT则转为步骤（7）,否则转为步骤（8） ; （7）将客户i和客户j连接成一条配送线路；（8）删 除集合 S 中的元素，且客户 i 和客户 j 不能作为配送车辆的最初或者最终的线路点.继续搜索其余各点，将全部的 2mC 个节约值考察完毕，找到最佳的运输路径.3 实例分析基础数据分析 A 为阜新市蔬菜批发中心，和市内 14 家大型超

11、市签订合约， 每天早晨根据前一日订单及到货的时间要求向各家超市配送货物， 蔬菜批 发中心到各超市以及各超市间距离的具体情况见表不同超市每天的平均需求量和时间约束的具体情况见表2.表 2 不同门店每天的平均需求量和时间约束different stores average demand and timeconstraints ofeach day门店要求时间窗/h编号 需求量/（箱天-1）卸货时间UT/hETi LTi1 1085127911107496128 配送车辆在进行配送的过程中，如果配送车辆从配送中心到达某个超市i 的时间满足，即配送车辆按照客户要求时间到达了门店，则取，若车辆提前到达，

12、则取 .如果车辆在配送过程中没能满足门店的时间约束，则设定惩罚系数0为无限大.配送车辆的平均行驶速度取值为28 km/h.车辆在完成配送任务之后返回配送中心，运输过程中各路段的情况相同，运输盈利系数。设为1元/吨/公里.车内有效装载面积最佳可容纳公司配送过程中标准尺寸的包装箱27个.Matlab软件求解通过对车辆路径问题模型的建立和改进节约算法分析，本文选用 Matlab 软件进行配送线路选择的优化求解.节约里程表和行驶时间表见表3 和表 4. 将相关数据、 参数及编程语言输入到 Matlab 中进行求解， 即可求得配送路径的最优解.根据求解结果，最终得到的配送方案为配送中心向 14 个超市配

13、送的 5 条线路，见表5、图1,优化得到的配送方案的总成本为元，总行驶距离为km,总配送时间约为h.具体信息如下：（ 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 优化后配送路线信息information of distribution route after optimization 路线 配送路线 行驶距离 /km） 行驶时间 /h1 0-3-2-9-10-0 0-14-12-13-00-8-11-5-00-1-7-00-4-6-0 合计 图 1 配送路径 distributio

14、n route 结果分析 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 优化前配送路线信息information of distribution routebeforeoptimiz

15、ation 路线 配送路线 行驶距离 /km 行驶时间 /h1 0-10-11-12-00-2-9-00-1-5-6-00-4-13-00-14-3-00-8-7-0 合计 通过将以上信息与利用改进节约法求得配送线路方案进行比较分析，我们可以发现，改进后的车辆配送路径方案能够有效的节约配送时间，缩短总配送里程，降低配送成本，提高公司的经济效益.4 结论本文提出了有时间窗约束的改进的节约法，建立了起讫点相同的单车场、非满载、有时间窗约束的车辆路径优化问题模型，以运输成本最小为优化目标，提出求解方法，并引入 A 公司 实例，通过计算，证明该方法具有实际意义.参考文献：1成榕,吴先锋.最小时间路径算法模糊结构元改进J.辽宁工程技术大学学报(自然科学版),2014,33(5):683-686. doi: Rong,WU of minimum-time pathalgorithm based on structured element theoryJ.Journal of LiaoningTechnical University(Natural Science),2014,33(5):683-686. doi: 郑英,孟志青.基于节约算法的烟草物流配送线路优化J.中国管理信息化，2010,13(23): Ying,MENG on conservation oftobacco