关于同城配送最短时间-最大运量的改进研究

王敬斋

(商丘学院,河南 商丘 476113)

关于同城配送最短时间-最大运量的改进研究

王敬斋

(商丘学院,河南 商丘 476113)

同城配送的效果决定着顾客满意度和配送企业未来的发展,配送企业要考虑配送成本,同时也要考虑配送时间．对最短时间的最大运量进行研究非常有必要,通过优化配送路径,可以实现提高物流企业盈利能力和客服服务水平的目的．

同城配送;最短时间最大运量;加权网络;增广链

0 引言

随着需求扩大的加快和商品流通的频繁,城市变得日益拥堵．作为物流过程末端的同城配送,正面临着配送成本上升和顾客满意度下降的问题．由于人们具有需求驱动的本性,即使采取了限行、征收拥堵费用等措施,作用也显得非常有限．因此,配送企业需要在既定条件下,充分利用现有设施,并注意开发新的潜能,对配送进行一些优化．

从20世纪90年代后期以来,服务差异化的趋势发展成为本世纪物流服务典型特征．配送服务变得更加重要,但是服务和成本之间存在着悖反关系,即要想提高服务水平,服务成本将迅速上升,这是企业头疼的问题[1]．配送企业应在满足顾客要求的前提下进行配送,在满足顾客要求的前提下,通过配送优化,降低成本,不断改进利润目标．而顾客的要求,其中一个很重要的方面,就是配送的及时性．研究配送的时间最短并且运输量最大,是非常有意义的．

1 最短时间-最大运量模型的假设

当前关于同城配送路径的研究,对时间和运量的组合研究的并不太多．配送企业可以在现有条件下,通过对时间和运输量的组合分析,使得配送时间最短,运量最大,这样就可以提高配送企业的效益,也能够增加顾客对物流企业服务的满意程度．

假定一个运输公司要将产品送到客户,该公司有个运输网络,利用此网络将货物运送到消费者那里,在不同路线上单位重量货物运输时间并不相同,那么要将产品从配送中心送到客户,用什么方法可以使时间最短,同时使运输量最大.

要解决这个问题,可以通过构建一个有向图D=(V,A,C),在图上进行求解,如图1所示．其中,D表示有向图,V表示点集,A表示弧集,C表示边容量．

图1中括号中的数字分别表示(单位重量运输时间,边容量,运量),用符号可表示为(Tij,Cij,fij)．Vs是发点,即配送中心所在位置,Vt是收点,即顾客位置．V1,V2,V3,V4,V5表示中间结点,两点之间的连线表示一条道路,配送中心要通过多个可以选择的道路,使得配送货物数量最大,同时保证总时间最短．这个问题即最短时间-最大运量问题．

2 最短时间-最大运量模型的建立和求解

2.1模型的建立

最短时间-最大运量求解过程实际上是线性规划问题的一种特殊求法,在不至于误解的情况下,“运量”可以用术语“流量”代替．其常见的线性规划模型如下所示:

公式中Z为目标,即最大运量所需要的时间,(Vi,Vj)表示有向图的边．在本模型里,即运量最大的情况下要求时间最短．Si为某一节点的净流量,即流出量和流入量的差．

2.2模型的求解改进思路

传统求解的方法是:始终保持网络中的可行流量是最短时间流量,然后不断调整,使流量逐步增大,最终成为最短时间流量．这种方法在20世纪60年代提出,也称作迭代法,这种方法计算步骤较多,随着结点数的增加,求解过程会变得非常繁琐．

实际上,如果始终保持可行流是最大流,检查边的时间,保持流量平衡的前提下,通过不断调整边的流量,使得时间逐步减少,也可以最终成为最大流量的最短时间流．以下将采取第二种方法求解．

第一步是先求出最大运量,即有向图的最大流．

将各种截集的容量求出来,找出其容量最小者,图2和图3中各种截集容量如表1所示．

这样,在表中,截集容量最小者,即为最大流量．在本例中,最大流量,即最大运输量为8．

第二步,求最短时间．

先把有向图中,所有流量为8的路径标出,然后再保持流量为8的前提下,不断调整边流量,使得时间缩短．流量为8的路径在图中用粗线表示,如图4所示．本例中,流量为8的方案只有一种．

因此,可求得最短时间为:3×3+5×4+3×4+3×2+1×1+2×9+2×2+4×2+4×3=90

因此,配送中心最多能够将8单位的货物从V0到客户Vn．运送8单位的货物最短时间为90．

3 结论

通过构建最短时间-最大流量模型,同城配送的路径问题进行了优化,关注配送数量固定下的时间问题,为同城配送工作提供了一个新的思路,使得配送企业更加专注客户的需求,站在客户的角度思考问题,从而赢得客户信赖,获得长期的利润．

[1] 温卫娟.物流配送管理[M].上海：上海交通大学出版社，2008

[2] 韩伯棠.管理运筹学[M].北京：高等教育出版社，2010

The Further Study of City Distribution Shortest Time-the Maximum Flow

WANG Jingzhai

(Shangqiu University,Shangqiu 476113, China)

Effect of city distribution determines customer satisfaction and the development of distribution enterprise in the future; distribution companies should consider distribution costs, and also consider the delivery time. It is necessary to study the shortest time-the maximum flow. By optimizing the distribution path, the goal of elevating the level of distribution enterprise’s profitability and customer service can be achieved.

city distribution;shortest time-the maximum flow;weighted network;augmented Chain

2015-08-14

基本项目：中国物流学会2015年度课题《基于“懒人经济”的同城配送问题研究》(2015CSLKT3-139).

王敬斋(1981-),男,河南洛阳人,硕士,商丘学院讲师,主要从事物流管理研究．

1672-2027(2015)03-0055-03

F279.23

A