您好!欢迎访问J9集团官方网站官方网站!

营业时间
MON-SAT 9:00-18:00

全国服务热线

公司门店地址
荔湾区中山八路新虹街58号

J9集团官方网站

j9集团

物流配送车辆路径优化方法

来源:网络日期:2026-10-22 浏览:

  物流配送路径优化问题,即是车辆路径问题(Vehicle Routing Problem, VRP),是Dantzig和Ramser于1959年提出的。具体来说,就是根据物流配送的已知条件和目标约束条件,寻找一般最符合条件的配送路线,使物流配送成本最小化。随着市场经济的发展与繁荣,物流配送在货物运输成本中占比重也越来越高。因而,如何降低物流运输成本,提高物流运输效率等问题,日益凸显重要,成为影响物流业发展中的重要--环。特别是,商业竞争的残酷性,使得客户对时间的要求更为苛刻。因此,如何解决有时间窗物流配送路径优化问题,也相应地凸显迫切。目前,物流配送路径问题应用范围十分广泛,物流运输、交通建设、通信等。随着物流业的发展,根据现代物流业发展的需求,车辆路径问题又进一步发展了有时间窗车辆路径问题(Vehicle Routing Problem With Time Windows, VRPTW),或有时间窗物流配送路径优化问题,也即是在物流配送路径优化问题....匕增加客户对配送时间的要求,目标仍然是求解问题的最优解,使得物流配送成本最小化。 目前,对物流配送路径优化问题的研究,部分趋于成熟,但多数还集中在利用传统算法来解决问题。其中,取得效果比较好的,有Thangiah等人采用遗传算法来解决物流配送路径优化问题,及有时间窗约束的物流配送路径优化问题。也有很多学者利用蚁群算法、禁忌算法等来求解同样问题,往往很多算法在求解该问题时,会遇到陷入局部最优等问题。在国内,研究比较有限,主要是在遗传算法基础上,提出各自的见解与主张。除此之外,也有很多学者在积极地研究新的算法来解决问题,效果也各有优劣,但还是没有传统算法那么成熟。因而,当前对物流配送路径优化问题的研究,处在一个比较缓慢的地歩。

  当前国内对物流配送路径优化问题研究,主要以传统算法为主。其主要存在以下不足之处(1)、求解物流配送路径优化问题的算法研究的单一性,使得问题的解决也具体单-一性;(2)、求解物流配送路径优化问题的算法中,有的效果好,但计算复杂度偏高;有的计算复杂度低,但效果不够理想;(3)、很多算法求解物流路径优化问题时,往往容易遇到陷入局部最优等问题。

  —种物流配送车辆路径优化方法,包括下述步骤 步骤1 ,参数设置及初始化物流配送路径优化的方案数目NT ;循环迭代次数N。=1,最大迭代次数N,;当前参与并购操作的车辆标识CarMark = oneS(NT, 1) , CarMark的选择顺序是根据步骤5中单个车辆配送路径方案成本从高到低排列;当前由车辆CarMark完成配送的客户标识CustomerMark = ones(NT, 1) , CustomerMark的选择顺序受步骤3中的并购操作中some函数影响;MACustSum表示由车辆CarMark完成车辆配送路径方案中临 时选定参与并购操作客户的最大值,也受步骤3中的并购操作中some函数影响;Dist表示 Nt个物流配送方案;Cars表示参与物流配送方案的配送车辆的数目;MAType = zeros (NT, 1)表示并购操作类型;先随机生成NT条物流配送方案,每一条物流配送方案有n个配送客 户个体;其中,ones是赋值为1的函数,zeros是赋值为0的函数; 歩骤2 :若N。《NMX,判断迭代次数是否达到最大迭代次数,如果是,就结束循环, 执行步骤7 ;否则,执行步骤3 ;

  再对物流配送路径进行调整操作 物流配送方案i中当前参与并购操作的车辆CarMark(i),由它完成配送的客户个 体Cust匿rMark(i),记作Temp,分别调至到除其以外的所有车辆中进行配送,分别计算出 调整后的每一个车辆配送路径方案成本,按步骤5的单个车辆配送路径方案成本方法求 取最小成本minCost (1,2,, Cars),选择配送成本最小的车辆k,最终确认把配送客户个 体Temp调至到由车辆k完成配送,同时消去车辆CarMark(i)对其的配送任务;

  户i , 选择其中一个客户个体Temp分别插入由每--个车辆配送路径方案中的适当位 置,按步骤5的单个车辆配送路径方案成本方法求取最小成本minCost. (1, 2,…,Cars), 选择配送成本最小的车辆k,最终确认把配送客户个体Temp调至到由车辆k完成配送,同时 把客户个体Temp从待配送客户集合T删除,继续再选择一个客户个体,做同样操作,直到待 配送客户集合T为空为止; 其中,some函数定义为提取每一个车辆配送路径方案中的一定客户,组成一个 临时客户个体集合,一定客户的选择原则是按步骤5的配送客户个体在单个车辆配送路 径方案中的成本方法求取最小成本raincost(1,2,, x),选择最小的成本隶属客户个体 p,以p为临界,选择包括p内的左侧(或右侧)所以客户中的不大于二分之一个客户个体 集,而这个客户个体集的数目就是MACustSum ;

  对于每-一个车辆j配送路径方案作如下操作 由车辆j完成的配送路径方案中,按步骤5的配送客户个体在单个车辆配送 路径方案中的成本方法求取最小成本mincost(1,2,…,x),选择最小的成本隶属客户 个体p,以p为临界,选择包括p内的左侧(或右侧)所以客户中的不大于二分之一个客 户个体集T = some(CarDist(j)),依次把T中的每-一个客户个体先后插入由车辆j完 成配送路径方案中,同时保证当前车辆j的单个车辆配送路径方案成本为最小成本 min(Cost(CarDist(j))),使得当前由车辆j完成配送路径方案的成本也是最小的;

  调整操作 对于每-一个车辆j配送路径方案作如下操作 先后依次取出由车辆j完成配送路径方案中的每一个配送客户,再插入车辆j 完成配送路径方案中,同时保证当前车辆j的单个车辆配送路径方案成本为最小成本 min (Cost (CarDist (j))),使得当前由车辆j完成配送路径方案的成本也是最小的; [,] 步骤5,成本评估 计算每一个物流配送路径方案的成本,成本包括三部分,分别是配送客户个体在 单个车辆配送路径方案中的成本,单个车辆配送路径方案成本和物流配送方案成本;

  配送客户个体在单个车辆配送路径方案中的成本包括距离成本Cs、等待时间成本 Ce和迟到时间成本q,即为(cs+ce+Cl); 单个车辆配送路径方案成本,包括四部分,分别是又单个车辆完成配送任务所需 的运输距离成本cs,运输超载成本cq,各个客户个体的等待时间成本之和ce和迟到时间成 本之和q,即为(Cs+Ce+c》exp (cq); 物流配送路径方案成本,也包括四部分,分别是由完成所有客户配送所需的运输

  和c丄,即为(Cs+C;+C》e邓(Cq); 步骤6,选择最优物流配送路径方案 对于任意一个物流配送路径方案i,则有若MAType (i) = 0,执行以下步骤 根据得到最新物流配送路径方案成本,如果低于旧的物流配送路径方案成本,则

  路径方案,继续执行步骤2; 若MAType (i) = 1,执行以下步骤 根据得到最新物流配送路径方案成本,如果低于旧的物流配送路径方案成本,则 更物流配送路径方案,MAType(i) = 0, CarMark (i) = 1,继续执行步骤2 ;否则,继续执行步 骤2 ; 步骤7,获得最优物流配送车辆路径方案 对于任意一个物流配送方案,按步骤5的物流配送路径方案成本方法求取最小 成本minCost(1,2,…,NT),成本最低的物流配送路径方案即为最优物流配送车辆路径方案。 本发明中,配送客户个体在单个车辆配送路径方案中的距离成本,和其它运输距

  7离成本的定义不同。运输距离成本就是完成配送任务所需的车程成本,而配送客户个体在 单个车辆配送路径方案中的距离成本,则是当前配送客户个体和当前车辆配送路径方案中 的其它客户个体之间距离,以及当前配送客户个体和当前车辆配送路径方案中的相邻客户 个体之间距离的综合距离成本。 本发明的物流配送路径优化方法是通过抽象企业并购行为,由并购操作,重组操 作等组成的并购方法,提高物流配送路径优化的收敛性,可以高效地得到最优物流配送路 径方案。

  下面通过附图和具体实施例对本发明的技术方案做进一步地详细地描 述,但本发明的保护范围并不限于此。 —种物流配送车辆路径优化方法,包括下述步骤 步骤1,参数设置及初始化物流配送路径优化的方案数目NT ;循环迭代次数Nc = l,最大迭代次数N,皿;当前参与并购操作的车辆标识CarMark = ones(NT, 1) , CarMark的选 择顺序是根据步骤5中单个车辆配送路径方案成本从高到低排列;当前由车辆CarMark 完成配送的客户标识CustomerMark = ones(NT, 1) , CustomerMark的选择顺序受步骤3中 的并购操作中some函数影响;MACustSum表示由车辆CarMark完成车辆配送路径方案中临 时选定参与并购操作客户的最大值,也受步骤3中的并购操作中some函数影响;Dist表示 Nt个物流配送方案;Cars表示参与物流配送方案的配送车辆的数目;MAType = zeros (NT, 1)表示并购操作类型;先随机生成NT条物流配送方案,每一条物流配送方案有n个配送客 户个体;其中,ones是赋值为1的函数,zeros是赋值为0的函数; 歩骤2 :若Ne《NMX,判断迭代次数是否达到最大迭代次数,如果是,就结束循环, 执行步骤7 ;否则,执行步骤3 ;

  再对物流配送路径进行调整操作 物流配送方案i中当前参与并购操作的车辆CarMark(i),由它完成配送的客户个 体CustomerMark(i),记作Temp,分别调至到除其以外的所有车辆中进行配送,分别计算出 调整后的每一个车辆配送路径方案成本,按步骤5的单个车辆配送路径方案成本方法求 取最小成本minCost (1,2,…,Cars),选择配送成本最小的车辆k,最终确认把配送客户个 体Temp调至到由车辆k完成配送,同时消去车辆CarMark(i)对其的配送任务;

  ■ J=i 选择其中一个客户个体Temp分别插入由每-一个车辆配送路径方案中的适当位 置,按步骤5的单个车辆配送路径方案成本方法求取最小成本minCost. (1, 2,…,Cars), 选择配送成本最小的车辆k,最终确认把配送客户个体Temp调至到由车辆k完成配送,同时 把客户个体Temp从待配送客户集合T删除,继续再选择一个客户个体,做同样操作,直到待 配送客户集合T为空为止; 其中,some函数定义为提取每一个车辆配送路径方案中的一定客户,组成一个 临时客户个体集合,一定客户的选择原则是按步骤5的配送客户个体在单个车辆配送路 径方案中的成本方法求取最小成本raincost(1,2,, x),选择最小的成本隶属客户个体 p,以p为临界,选择包括p内的左侧(或右侧)所以客户中的不大于二分之一个客户个体 集,而这个客户个体集的数目就是MACustSum ;

  配送路径方案,则有插入操作对于每一个车辆j配送路径方案作如下操作 由车辆j完成的配送路径方案中,按步骤5的配送客户个体在单个车辆配送 路径方案中的成本方法求取最小成本mincost (1, 2,…,x),选择最小的成本隶属客户 个体P,以P为临界,选择包括P内的左侧(或右侧)所以客户中的不大于二分之一个客 户个体集T = some(CarDist(j)),依次把T中的每一个客户个体先后插入由车辆j完 成配送路径方案中,同时保证当前车辆j的单个车辆配送路径方案成本为最小成本 min (Cost (CarDist (j))),使得当前由车辆j完成配送路径方案的成本也是最小的;

  调整操作 对于每一个车辆j配送路径方案作如下操作 先后依次取出由车辆j完成配送路径方案中的每一个配送客户,再插入车辆j 完成配送路径方案中,同时保证当前车辆j的单个车辆配送路径方案成本为最小成本 min(Cost.(CarDist.(j))),使得当前由车辆j完成配送路径方案的成本也是最小的;

  Ce和迟到时间成本C],即为(Cs+Ce+C]); 单个车辆配送路径方案成本,包括四部分,分别是又单个车辆完成配送任务所需 的运输距离成本cs,运输超载成本cq,各个客户个体的等待时间成本之和ce和迟到时间成 本之和c!,即为(cs+ce+Cl) exp (cq); 物流配送路径方案成本,也包括四部分,分别是由完成所有客户配送所需的运输

  和+Ce+C》exp (Cq); 步骤6,选择最优物流配送路径方案 对于任意一个物流配送路径方案i ,则有 若MAType (i) = 0,执行以下步骤 根据得到最新物流配送路径方案成本,如果低于旧的物流配送路径方案成本,则

  路径方案,继续执行步骤2; 若MAType (i) = 1,执行以下步骤: 根据得到最新物流配送路径方案成本,如果低于旧的物流配送路径方案成本,则更物 流配送路径方案,MAType (i) = 0, CarMark(i) = l,继续执行步骤2 ;否则,继续执行歩骤2 ;

  步骤7,获得最优物流配送车辆路径方案 对于任意一个物流配送方案,按步骤5的物流配送路径方案成本方法求取最小 成本minCost(1,2,…,NT),成本最低的物流配送路径方案即为最优物流配送车辆路径方案。 实验采用Solomon于1987年所设计的Solomon Benchmark problems的数据集。 其中,每一个问题类型都有l()()个客户,一共有Cl、 C2、 Rl、 R2、 RCl、 RC2等六大类的56种 问题类型,每个类型的数据集合包含有7个到12个不等的带有100个配送点的问题数据。 而且C问题类型的客户分布较聚群或集中,R问题类型的客户分布较均匀,RC问题类型是C 问题类型和R问题类型的混合;C1、R1、RC1等I类问题的特点,车辆多,容量小,车程时间较 短;C2、 :R2、 RC2等II类问题的特点,则与前者恰好相反。 实验参数说明(RT, EC, Wq, Wd, We, Wl)=(迭代次数,企业生态链数目,单位超载 载量成本惩罚权重,单位距离成本惩罚权重,等待时间惩罚权重,迟到时间惩罚权重)。

  R问题类型和RC问题类型R问题类型特点是客户分布比较均匀,RC问题类型是 C问题类型和R问题类型的混合。Rl和RC1问题类型都是有部分在第一 目标上获得了最优 解,但还是有几个问题类型不能达到最优解,不过在第二目标上效果也不错,接近最优解。 主要原因是因为R和RC问题类型中客户分布比较均匀,所需车辆较多,而且时间窗宽窄不 一,使得在本专利方法下所求得的解与目前最优解相比,还有进一步提高的空间。R2和RC2 问题类型在第一 目标上都获得到了最优解,而且第二目标也接近最优解,效果比较好。

  和有效性,而且可有效地解决其它方法在求解物流配送路径优化问题上遇到的陷入局部 最优问题,同时也丰富了求解物流配送路径优化问题的方法。 Solomon几个常见问题类型详细实验结果 Solomon几个常见问题类型一般指Cl()l、 C201 、 R101 、 R2(H、 RCl()l、 RC201问题类型。①C101问题类型得到的最优解路程长度为TD = 828. 9396KM,等待时间ET = Omin,迟到时间LT = Omin,如图1所示;C201问题类型得到的最优解路程长度为TD = 591. 5566KM,等待时间ET = Orain,迟到时间LT = Omin,如图2所示。

  一种物流配送车辆路径优化方法,其特征在于包括下述步骤步骤1,参数设置及初始化物流配送路径优化的方案数目NT;循环迭代次数Nc=1,最大迭代次数Nmax;当前参与并购操作的车辆标识CarMark=ones(NT,1),CarMark的选择顺序是根据步骤5中“单个车辆配送路径方案成本”从高到低排列;当前由车辆CarMark完成配送的客户标识CustomerMark=ones(NT,1),CustomerMark的选择顺序受步骤3中的并购操作中some函数影响;MACustSum表示由车辆CarMark完成车辆配送路径方案中临时选定参与并购操作客户的最大值,也受步骤3中的并购操作中some函数影响;Dist表示NT个物流配送方案;Cars表示参与物流配送方案的配送车辆的数目;MAType=zeros(NT,1)表示并购操作类型;先随机生成NT条物流配送方案,每一条物流配送方案有n个配送客户个体;其中,ones是赋值为1的函数,zeros是赋值为0的函数;步骤2若Nc≤Nmax,判断迭代次数是否达到最大迭代次数,如果是,就结束循环,执行步骤7;否则,执行步骤3;步骤3,并购操作对于任意一个物流配送方案i,令CarDist=Dist(i),CarDist(j)表示车辆j的配送路径方案,则有若MAType(i)=0,执行以下步骤先对参与并购操作的配送对象的位置重定位若CustomerMark(i)>MACustSum(i),则CarMark(i)=CarMark(i)+1;若CarMark(i)>Cars,则MAType(i)=1,跳出当前操作;其中,MACustSum(i)=sum(some(CarDist(j))),表示客户个体集的数目;再对物流配送路径进行调整操作物流配送方案i中当前参与并购操作的车辆CarMark(i),由它完成配送的客户个体CustomerMark(i),记作Temp,分别调至到除其以外的所有车辆中进行配送,分别计算出调整后的每一个车辆配送路径方案成本,按步骤5的“单个车辆配送路径方案成本”方法求取最小成本minCost(1,2,…,Cars),选择配送成本最小的车辆k,最终确认把配送客户个体Temp调至到由车辆k完成配送,同时消去车辆CarMark(i)对其的配送任务;若MAType(i)=1,执行以下步骤提取由每一个车辆完成配送路径方案中的部分配送客户,组成一个待配送客户集合mrowmiT/mimo=/momunderovermi/mimrowmij/mimo=/momn1/mn/mrowmiCars/mi/munderovermisome/mimrowmo(/momiCarDist/mimrowmo(/momij/mimo)/mo/mrowmo)/mo/mrowmo;/mo/mrow选择其中一个客户个体Temp分别插入由每一个车辆配送路径方案中的适当位置,按步骤5的“单个车辆配送路径方案成本”方法求取最小成本minCost(1,2,…,Cars),选择配送成本最小的车辆k,最终确认把配送客户个体Temp调至到由车辆k完成配送,同时把客户个体Temp从待配送客户集合T删除,继续再选择一个客户个体,做同样操作,直到待配送客户集合T为空为止;其中,some函数定义为提取每一个车辆配送路径方案中的一定客户,组成一个临时客户个体集合,一定客户的选择原则是按步骤5的“配送客户个体在单个车辆配送路径方案中的成本”方法求取最小成本min cost(1,2,…,x),选择最小的成本隶属客户个体p,以p为临界,选择包括p内的左侧(或右侧)所以客户中的不大于二分之一个客户个体集,而这个客户个体集的数目就是MACustSum;步骤4,重组操作对于任意一个物流配送方案i,令CarDist=Dist(i),CarDist(j)表示j车辆的配送路径方案,则有插入操作对于每一个车辆j配送路径方案作如下操作由车辆j完成的配送路径方案中,按步骤5的“配送客户个体在单个车辆配送路径方案中的成本”方法求取最小成本min cost(1,2,…,x),选择最小的成本隶属客户个体p,以p为临界,选择包括p内的左侧(或右侧)所以客户中的不大于二分之一个客户个体集T=some(CarDist(j)),依次把T中的每一个客户个体先后插入由车辆j完成配送路径方案中,同时保证当前车辆j的“单个车辆配送路径方案成本”为最小成本min(Cost(CarDist(j))),使得当前由车辆j完成配送路径方案的成本也是最小的;调整操作对于每一个车辆j配送路径方案作如下操作先后依次取出由车辆j完成配送路径方案中的每一个配送客户,再插入车辆j完成配送路径方案中,同时保证当前车辆j的“单个车辆配送路径方案成本”为最小成本min(Cost(CarDist(j))),使得当前由车辆j完成配送路径方案的成本也是最小的;步骤5,成本评估计算每一个物流配送路径方案的成本,成本包括三部分,分别是配送客户个体在单个车辆配送路径方案中的成本,单个车辆配送路径方案成本和物流配送方案成本;配送客户个体在单个车辆配送路径方案中的成本包括距离成本cs、等待时间成本ce和迟到时间成本cl,即为(cs+ce+cl);单个车辆配送路径方案成本,包括四部分,分别是又单个车辆完成配送任务所需的运输距离成本cs,运输超载成本cq,各个客户个体的等待时间成本之和ce和迟到时间成本之和cl,即为(cs+ce+cl)exp(cq);物流配送路径方案成本,也包括四部分,分别是由完成所有客户配送所需的运输距离成本Cs、运输超载成本之和Cq、各客户个体的等待时间成本之和Ce和迟到时间成本之和Cl,即为(Cs+Ce+Cl)exp(Cq);步骤6,选择最优物流配送路径方案对于任意一个物流配送路径方案i,则有若MAType(i)=0,执行以下步骤根据得到最新物流配送路径方案成本,如果低于旧的物流配送路径方案成本,则更物流配送路径方案,CarMark(i)=1,继续执行步骤2;否则,不更新,CustomerMark(i)=CustomerMark(i)+1,并在保存成本最小的物流配送路径方案,暂时作为当前最佳物流配送路径方案,继续执行步骤2;若MAType(i)=1,执行以下步骤根据得到最新物流配送路径方案成本,如果低于旧的物流配送路径方案成本,则更物流配送路径方案,MAType(i)=0,CarMark(i)=1,继续执行步骤2;否则,继续执行步骤2;步骤7,获得最优物流配送车辆路径方案对于任意一个物流配送方案,按步骤5的“物流配送路径方案成本”方法求取最小成本minCost(1,2,…,NT),成本最低的物流配送路径方案即为最优物流配送车辆路径方案。

  本发明涉及一种物流配送车辆路径优化方法,包括下述步骤步骤1,参数设置及初始化;步骤2若Nc≤Nmax,判断迭代次数是否达到最大迭代次数,如果是,就结束循环,执行步骤7;否则,执行步骤3;步骤3,并购操作,再对物流配送路径进行调整操作;步骤4,重组操作,插入操作,调整操作;步骤5,成本评估;步骤6,选择最优物流配送路径方案;步骤7,获得最优物流配送车辆路径方案。本发明的物流配送路径优化方法是通过抽象企业并购行为,由并购操作,重组操作等组成的并购方法,提高物流配送路径优化的收敛性,可以高效地得到最优物流配送路径方案。

j9集团 丨NEWS