同城配送最短时间-最大流量问题分析

张 瑞

(西安交通工程学院,西安 710300)

同城配送是一种特殊的物流方式,适用于小范围内的分拣、配货及运输,可以在短时间内将物品准确高效地送给客户,提高客户满意度,但其适用范围有限,需要进一步改进。陈琳琳等研究构建了多供货点智能配送VRP模型,得出最优配送方案[1]。吴桦研究了蚁群算法在时间窗物流配送路径问题中的应用[2]。本研究基于某超市分店的送货上门服务选取10个需求点调研配送需求量和配送路线,并建立最短时间-最大流量模型。该模型利用时间为长度,计算最短路径,求出第1条增广链,不断增广直至达到最大流量。使用LINGO软件求解,优化超市货物配送线路,使其运输量最大化的同时所需时间最短。

1 最短时间-最大流量模型的构建

1)目标函数。以每条路线能够承受的最大货流量通过时间最短为优化目标构建目标函数,详见式(1)。

(1)

2)约束条件。由表1可得模型的约束条件,详见式2。

表1 模型中的参数和变量

(2)

3)模型在案例中的应用。客户需求点位置坐标分布如图1所示。假定超市把商品货物运输到需求点J,运用其代号可以将数据整理成网络图,括号中数字依次代表容量、时间、流量。详见图2。

图1 超市及各需求点的直角坐标系分布

图2 最短时间-最大货流量原始网络图

图3 修订后的最短时间-最大货流量网络图

在图3中的每一条弧(Vi,Vj)上添加一条方向相反的弧(Vj,Vi),得到赋权网络。详见图4。将时间当作长度,继续求解最短路径,得出增广链,其增加流量相应的时间也会增加,按照规则继续构造赋权网络图,直至求不出最短路径时,算法停止,得到最大流量和最短时间。

图4 最短时间-最大货流量赋权网络图

2 基于LINGO算法的模型求解

1)最大货流量模型求解。运行源程序代码,结果表明,整个有向图的最大货流量为14,即配送中心最多能运送14 t的货物。详见图5。

图5 最大流求解状态

2)最短时间-最大货流量模型求解。以最大货流量的结果分析得出最大货流量f=14为模型中的约束条件,将运输总成本费用最少作为目标函数,得到整个有向图的最短时间为215,即运送最短时间为215 min。详见图6。

图6 最短时间求解状态

3 结论

由程序的运行结果可知,从A到J最大流量为14,运输方案详见表2,流量运输网络详见图7。

图7 货流量运输网络

表2 运输方案

求出最大流量后,将其作为约束条件求出最短时间,最终选取费用最少的运输方案。与表2的运输方案相比,C→F由4变为6,E→G由1变为3。改正后的运输流量时间详见图8。

图8 改正后的货物运输流量时间

超市向需求点J最多可以配送14 t的货物,用时215 min。优化网络图去掉了路线A→B、E→F、H→I,能够使运输流量最大化,运输时间最小化,大大提高了配送效率,避免了资源浪费。