基于运输网络的配送路线问题模型

基于运输网络的配送路线问题模型

有很多方法可以解决订单领域优化问题，通常包括物流教育法、动态规划法、经济法、扫描法、区域配送法、方案评估法等。相关研究中,王会云等研究了旅行商法在配送路线优化问题中的应用,并利用Matlab和遗传算法对该问题进行了求解。陈彦军等利用旅行商模型研究了物流配送问题。王勇等利用动态规划法对配送路线及配送时间的优化问题进行了研究分析。张学志等提出了一种改进节约算法,并利用该算法对配送路线问题进行了研究。杨文霞等采用改进扫描算法解决配送路线优化问题,并结合实际案例分析了该优化方法的工作性能。霍亮利用分区配送法研究了基于GIS的物流配送问题。此外,文献[8-11]研究了相关智能优化算法在配送路线优化问题中的应用,包括免疫算法、遗传算法、禁忌搜索算法和模拟退火算法。WANG和LU研究了利用遗传算法及其改进算法求解具有容量限制的路径优化问题,其基本思想是将遗传算法与其他算法(例如扫描法)相结合,用来改进算法的求解质量及计算速度。LEUNG等将二维装箱问题及配送路线问题结合起来考虑,并采用模拟退火算法对该问题进行求解,而针对同一问题,FUELLERER等则考虑采用蚁群算法进行求解。LIN等采用了一种模拟退火算法与禁忌搜索算法的混合算法对容量限制的路径规划问题进行求解,并通过大规模的算例实验验证了算法的有效性。LECLUYSE等考虑了更加复杂的情况,如考虑了行程时间会随时间随机变化的车辆路径问题,并对行程时间可靠性进行了分析。由于客户需求可能产生在区域内的任意位置,确定出客户与配送中心以及客户之间的最短运输距离就十分必要。传统的配送优化模型往往假设配送中心及各客户之间的运输距离为两点之间的直线距离,并简单地利用勾股定理进行计算,这导致模型的优化结果与实际最优路线相差甚远。因此,在对配送路线进行优化时,必须考虑运输网络对配送计划的影响。1配送路线编码及约束条件式考虑到客户与配送中心以及客户之间行车距离在实际配送中的重要性,将配送优化问题描述为:配送中心负责某一特定区域内的货物配送任务,满足该区域内随机产生的客户需求,需要确定配送方案,使送货车辆行走的总路程最短。结合配送问题的实际运作,建立如下数学模型:目标函数:约束条件:模型中各数学符号的意义如下:I为需求点的数目;i为需求点编号,i=1,2,…,I,i=0为配送中心编号;W为配送车辆的容量上限;wi为需求点i的货物需求量,i=1,2,…,I;k为配送路线序号;dij为点i到点j的运输距离(受运输网络限制的最短路程),i,j=0,1,2,…,I;M为一个较大的整数。决策变量:yki为当配送路线k满足客户i的需求时,yki=1,否则,yki=0;xkij为当配送路线k满足i和j的需求,且j的访问顺序紧随i之后时,xkij=1,否则xkij=0;uki为0-1变量,用于消除配送路线模型中可能产生子回路的情况。目标函数式(1)表示多条配送路线的总路程最短;约束条件式(2)表示单条配送路线装载的货物必须小于配送车辆的容量上限;约束条件式(3)表示客户需求有且只有一条配送路线为其服务;约束条件式(4)和式(5)保证了配送路线进出需求点的流量平衡;约束条件式(6)限定只有从配送中心出发的回路才是有效的配送路线;约束条件式(7)用来消除可能存在的子回路。2运营算法的计算由于客户需求是在特定区域内随机产生的,考虑到运输网络的限制,不能简单地用两点之间的直线距离作为运输距离。图1为某实际的运输网络,0为配送中心所在位置,位置固定,1~10为客户所在位置(客户所在位置位于既定路网),在绝大多数情况下,两点之间没有直线道路连接,且由于运输网络较为复杂,当两个点相距较远时,可供选择的路径较多,两点之间的最短路程很难通过观察得知。针对实际运输网络中任意两点之间最短路程未知的情况,笔者采用弗洛伊德算法计算不同点之间的最短路程。在利用弗洛伊德算法进行计算时,首先需要将运输网络转化为一个距离矩阵,该矩阵包含了运输网络的所有空间信息。对于如图1所示的运输网络,需要对其中所有的节点(即实际交通网络中所有的丁字路口和十字路口)编排序号。此外,配送中心和各客户需求点也需要编排序号。用G(V,E)表示如图1所示的无向连通图,用vi表示点i,(vi,vj)表示连接i和j的弧,d(vi,vj)表示弧的长度。图1中共有101个路口,1个配送中心和10个客户需求点,则需要构建一个112×112的初始距离矩阵D(0)={aij(0)}112×112。当运输网络中的两点之间有弧直接连接时,弧的长度即为初始距离矩阵中对应元素的值;当两点重合时,对应元素(矩阵主对角线上的元素)的值为零;当两点不重合且没有弧直接连接时,初始矩阵中对应元素的值则为无穷大,在进行运算时,取一个足够大的整数M即可。对于k=1,2,…,n,计算:当k=n时,D(n)={aij(n)}112×112为任意两点之间的最短路程。利用LINGO能够方便地实现弗洛伊德算法,可以将初始距离矩阵D(0)从EXCEL导入到LINGO,求解结果则可以从LINGO导入到EXCEL。对于如图1所示的运输路网,可以在3秒之内求出最短路程矩阵,该矩阵即为配送路线优化模型中需要的距离矩阵。LINGO中的程序代码如下所示:最短运输距离矩阵的求解结果如表1所示,可以发现运输距离矩阵是对称矩阵,该距离矩阵将作为后续配送路线优化的输入量。3最优条件下的配送回路个数利用上述求最短路程矩阵的方法和建立的整数线性规划模型,可以对配送路线问题的算例进行求解。利用图1中随机生成的10个客户点,设配送车辆的容量上限为24,随机生成10个客户点的需求量,这些需求量为3~8之间的整数,且服从均匀分布,如表2所示。利用LINGO及相关数据,可以求出该算例的最优解,在一般笔记本电脑上的求解时间为38min。LINGO中的程序代码如下所示:其中,路线1完成的货运量为21,路线2为17,路线3为15。最优解下的目标函数值为30.736(地图上距离)。需要注意的是,在定义路线集合时无法精确预知最优条件下的配送回路个数。为此,在LINGO编程时,综合考虑车辆容量和客户点总需求量,路线集合元素设置为一个足够大的值。算例中设置为4个,大于最优解的配送回路个数(3个),设置合理。4配送路线优化问题的模拟仿真及试验结果模拟退火算法是一种基于蒙特卡罗迭代求解策略的随机寻优算法。模拟退火算法与初始解状态无关,具有渐进收敛性。模拟退火算法的求解流程如图2所示。模拟退火算法的功能模块主要包括:设置控制参数,生成初始解,变换生成新解,Metropolis准则和降温模块。其中控制参数的设置对算法的求解质量有较大影响,主要控制参数包括初始温度、降温速率、迭代步长和终止准则(笔者限定温度下降次数超过500次时停止运算)。利用C语言编写配送路线优化问题的模拟退火算法程序,对算例进行多次求解。通过多次试验得到求解质量较高的算法控制参数,如表3所示。在设定的控制参数下,随机运行程序12次,由于程序以降温次数作为终止准则,在一般笔记本电脑上程序每次的运行时间为9.89s,记录每次试验的运行结果,包括目标函数值以及首次得到该函数值的降温次数等,如表4所示。从表4可以看出,算法程序在12次试验中,有6次收敛到了全局最优解,5次收敛到相对误差仅为0.228%的局部最优解,最差的局部最优解为第9次试验结果,相对误差也仅为0.309%。LINGO及模拟退火算法的求解结果表明,模拟退火算法能够有效地解决所提出的路线配送优化问题。笔者利用弗洛伊德算法和模拟退火算法对配送路线优化问题进行求解,得到的配送路线图更加符合配送活动的生产实际,如图3(a)所示。相关文献由于没有考虑运输网络的约束,配送路线的优化结果通常如图3(b)所示。5l软件的应用笔者基于实际运输网络考虑物流配送路线优化问题,针对运输距离受限于运输网络,而不能简单利用勾股定理以直线距离作为运输距离的实际情况,利用弗洛伊德算法以及LINGO和EXCEL软件计算运输网络中任意两点之间的最短路程,并以此构造配送路线优化模型中的距离矩阵。利用求得的运输距离矩阵以及所提出的用于解决配送路线优化问题的整数线性规划模