基于送收的物流配送车辆路径优化问题研究

中图分类号:TP312 文献标识码:A

内容摘要:文章在提出区域物流送收概念的基础上,建立了考虑回程收货的单物流配送中心多网点的车辆路径问题(VRP)的数学模型,运用遗传算法求解模型,并通过实例进行验证。该模型能够为企业在物流配送中的车辆路径选择问题提供决策上的支持。

关键词:送收物流配送 车辆路径问题(VRP)

物流配送是现代物流管理中的一个重要环节,只有“有组织、有计划”地“配”,才能实现现代物流管理中所谓的“低成本、高速度”地“送”,进而有效满足顾客的需求。同时,随着配送的程度深入,现在的区域配送不但需要“送”,还要在“送”的过程中进行动态地“收”即“区域物流送收”,从而实现相对动态地送收结合,起到节约成本、提高配送效率的作用。

在已有的车辆路径问题(VRP)研究中,大多数文献利用蚁群算法、遗传算法、神经网络法对VRP进行研究,但基本上都是单纯的针对配送求解VRP,而没有考虑回程车辆的空闲容量,导致配送费用的增加。本文研究的是在一定的配送信息平台上,根据已知的待服务客户的网点布局、物流配送中心的位置、车辆的最大负荷和客户需求的前提下,建立了考虑回程收货的单配送中心多网点的路径选择模型,利用遗传算法实现最短路径的求解,并通过实例验证能使每辆车的工作量达到均衡。上述模型的建立有利于物流企业降低实际配送成本,提高网点服务质量,具有推广应用价值。

问题描述及模型建立

(一)基本假设

单配送中心且运送网点已经过系统在某时间点确认,数目确定;各网点的需求量固定且已知;配送中心与任一网点的最短距离已知;任一网点的邻接点已知(根据邻接矩阵);配送车辆为有限几种(本文假定只有一种),车容量一致;在不同时间段的路面状况服从不同的正态分布;送货计为正值,收货计为负值。

(二)限制条件

每条线路的总货运量不超过车辆的容量,并且在收货期间每个网点的车上货物量不会超过最大容量,最终回到配送中心时也不会出现收量大于最大容量的情况;每条配送路径的长度不超过车辆一次配送的最大行驶距离;每个客户的需求必须满足,且一个客户的需求只能由一台车辆送货,即一次送收每个网点只能服务一次;一辆车只能服务一条线路;目标函数是求配送成本最低的方案,即固定成本、作业成本及损失成本之和最低;所有车辆均由同一配送中心出发,完成服务后返回配送中心;每条线路有最大工作量限制。

(三)单配送中心多网点的路径选择模型建立

1.变量参数说明。设配送中心有K辆汽车,每辆汽车的载重量为Qk(k=1,2,…,K),其一次配送的最大行驶距离为Dk,需要向L个需求点送货,每个需求点的需求量为qi(i=1,2,…,L),qrk0为车辆在物流中心时的载质量,需求点i到j的运距为dij,配送中心到各需求点的距离为d0j(i、j=1,2,…,L),nk为第k辆汽车配送的需求点数(nk=0表示未使用第k辆汽车),用集合Rk表示第k条路径,其中的元素rki表示需求点rki在路径k中的顺序为i(不包括配送中心),令rk0=0表示配送中心。配送中心的预设工作量为Wo,Wk是第k辆车的工作量,sign(nk)为是否使用该辆汽车进行配送(若等于1则表示参与配送,0表示没有参与)。

该模型在一条路径上只允许由一辆车进行配送,而且保证车辆的正常行驶并在配送完所有网点后返回配送中心。目标函数是配送总里程最短,约束条件为:不同送货线路之间达到工作量均衡;保证每条送收线路的长度不超过车辆一次配送的最大行驶距离;每条路径上的需求点数不超过总需求点数;每个需求点都得到配送服务;第K条路径的需求点集合;每个用户的货物需求必须满足,有且只能由一台配送车辆送货;保证送收在每个节点的车辆的单次送收量累计值不超过车辆的最大载质量;车辆出配送中心时的载质量不超过车辆的最大载质量。最后要结合分析模型的长期前提数据的积累(例如:送货距离权值、送货量权值、网点数权值),经过数据挖掘后得到一定的权值,用以加强模型的实用性。

遗传算法求解模型

本文采用遗传算法求解模型,但由于遗传算法不能直接处理解空间的数据,因此必须通过编码将它们表示成遗传空间的基因型串结构数据。其代码如下:

{输入单配送中心车辆调度问题的已知条件;

输入算法的运行参数,包括个体的适应度F,目标函数值Z,失效路径数为M等;//编码方法的确定

for(k=1;k≤L+k-1;k++)//求解单配送中心车辆调度问题

{导入配送中心有k辆车及其服务的客户的位置,需求量信息;

//由于在配送中心有K辆汽车,则最多存在K条配送路径

//每条配送路径都始于配送中心,也终于配送中心

for(L=k;L≥0;L--)

{初始群体的确定};//通过随机产生N个这样的个体

while(n

{if(F=1/(Z+M×V)){//个体的适应度,V为每条路径的权重

{根据目标函数的取值范围取一个相对较大的正数;}

else

for(k=1;k

kmax=k;//排在第一位的个体性能最优,将它复制一个直接进入下一代,并排在第一位。}

{计算上代群体中所有个体适应度的总和(ΣF);

计算每个个体的适应度所占的比例(F/ΣF);}//选择操作}

for(k=1;k

{个体按交叉概率P进行配对交叉重组;}//交叉操作

// 这种方法在两父代个体相同的情况下仍能产生一定程度的变异效果,这对维持群体的多样化特性有一定的作用。

for(n=0;n

{if(P=Pm)//以概率Pm发生的连续多次对换

{ZN=ZJ;}// 变异操作}

导出Z对应的配送路径方案及其目标函数值;}

输出单配送中心车辆调度问题的计算结果;}

实例计算

根据上述算法,本文用一个实例进行分析,配送中心使用2辆汽车对8个需求点(0表示配送中心)进行送货的物流配送路径优化问题实例进行了实验计算。用货物需求的正数表示送货任务,货物需求的负数表示收货任务且收货是收回到配送中心。每次配送的最大行驶距离是80千米。配送中心与各需求点之间、各需求点相互之间的距离及各需求点的需求量如表1所示。

约束条件:群体规模:20;交叉概率:0.95;变异概率:0.05;进化代数:50;变异时基因次数:10;对失效路径惩罚权重取200千米。利用计算机随机求解10次,结果如表2所示。

结合表1和表2的结果来看,第5次得到该问题的最优解67.5km,其对应的配送路径方案为:路径1:0-4-7-6-0;路径2:0-2-8-5-3-1-0。工作量达到均衡。

综上所述,文章在单配送中心多网点的研究中,将送收货集中考虑的思路,更符合现代物流配送的实际情况,采用遗传算法求解模型,提高了求解的速率。但在系统建模时,并没有考虑时间窗的限制,要提高服务质量,必须对客户的需求实时响应,即考虑时间的约束,例如:时间限制、客户需求的缓急程度、服务承诺等。因此,如何在优化路径的条件下,更好的服务客户是下一步研究的重点。

参考文献:

1.方金城,张岐山.物流配送车辆路径问题(VRP)算法综述.沈阳工程学院学报(自然科学版),2006,10

2.成萌,姜建国,王宇.基于遗传算法的多台贴片机物料调度问题.微计算机信息,2008,9-3

3.杨瑞臣,周永付,云庆夏.寻找车辆最优路径的混合算法[EJ].交通运输工程学报,2005,5(1)

4.Ohbyung Kwon, Ghi Paul Im, Kun Chang Lee. A multi-agent and case-based reasoning collaboration mechanism for supply chain management under supply and demand uncertainties [J]. Science Direct. 2007

5.李向阳.遗传算法求解VRP问题.计算机工程与设计,2004,2

6.贺竹磬,孙林岩.动态交通下车辆路径选择模型及算法.交通运输工程学报,2007,2-7(1)