应急物流配送路径优化问题研究

摘要：文章通过对应急物流配送路径优化问题进行分析，建立了应急物流配送路径优化问题的模型，在此基础上提出了模型的求解方法，最后通过实例应用对应急物流配送路径优化问题求解过程进行了说明，并对结果进行了进一步讨论。

Abstract: Through the analysis of path optimization of emergency logistics distribution, the article establishes its model, proposes the solving method on this basis. Finally, through an example application of path optimization of emergency logistics distribution, the solving process are described, and the results are further discussed.

关键词：物流；应急配送；路径优化

Key words: logistics；emergency distribution；path optimization

中图分类号：F253 文献标识码：A 文章编号：1006-4311（2011）28-0025-02

0 引言

随着市场经济的发展和竞争的加剧，市场呈现多品种、小批量产品多样化、消费多样化的趋势，物流配送就是为适应这种趋势而产生的一个重要环节，它是指对局域范围内的客户进行的多客户、多品种的按时联合送货活动。配送的“送”就是送货运输。从这个角度来看，物流配送中送货路线的选择，是影响物流成本的一项重要因素。从降低物流成本的途径来看，提高物流速度，可以减少资金占用和，缩短在物物流周期，降低储存费用，从而节省物流成本。所以，在应急物流配送过程中，要使得各物资需求点能在最短时间内得到物资补充，物流中心就需要选择最优的保障方式，将物资送达各个需求点。

1 影响物流中心选址的因素及物资需求问题描述

在整个物流系统中，配送中心地点的选择更是物流系统优化的一个具有战略意义的问题。传统意义上的物流配送中心（或分销中心）是商品从供应商（制造商）至零售商之间的中间储存点，具有集中和分散物资，促进商品迅速流转的功能。物流中心的位置的选择，根本目的应以费用低、服务好、社会效益高为目标，以物资运输合理、方便用户、投资少、有利于适应经济发展的需要为基本原则。物流中心的选址需要对多种因素综合考虑包括：自然资源的特点、客户的分布、运输服务条件、建设费用、城市建设的整体规划、外部环境因素等，此外对物流中心未来的发展应仔细研究，使决策具有前瞻性。它包括物流中心在此处有没有发展前途和大的作为，以及一定时期内城市经济发展的变化，以便使物流中心能适应未来发展的需要。

在满足物流中心开设地点要求和综合各物资需求点之间距离的前提下，物流中心与各物资需求点之间就不可避免地存在一定的距离。由于各物资需求点的周围客户量不同，物资的销售情况也必然不同，必然会导致物资需求产生的偶然性，而物资需求点相对分散。物流中心收到来自这些分散的位置的物资配送申请后，对这些物资需求点进行物资配送，模型就是要解决在物流中心现有运输力量前提下，以最优的方式将物资送达每一个需求点，由此产生了物资需求问题。

2 应急物流配送路径优化问题建模

2.1 物流中心与物资需求点的实际关系 由于物资需求点产生的偶然性，使得物流中心和物资需求点关系如图1所示。以五个物资需求点的情况为例，各点编号分别为1、2、3、4、5，物流中心编号为0。现实情况是这样的，各需求点之间以及需求点与物流中心之间，可能是可以不经过第三点直达的（如需求点1、需求点2及物流中心之间都是可直达），也可能是必须经过第三点才可以到达（如需求点5与物流中心之间）。若可以直达，则以连线表示两点之间的支路。无论怎样，需求点与物流中心之间总可以找到一条路，即是可达的。若某个需求点与物流中心之间没有路，则表明该点与物流中心不可达，则该点也就没有存在的必要。

2.2 现实情况的完全加权图表示 将图1所示的现实情况转化为完全加权图形式后得到如图2所示的关系形式。图2中0点为物流中心，其他为物资需求点，实线为实际支路，虚线表示虚拟支路。则物流中心应急物流配送问题可以描述为：找到从0点出发不重复的遍历所有节点的最短闭合回路。由此，可以看出物流中心物资输送问题实质上为一个TSP问题。

2.3 所求最优回路中的组成支路的权值的确定 解决该问题的目标是找到从0点出发不重复的经过所有节点的最短闭合回路。也就是使得这条闭合回路的组成支路的权值之和最小。所以，求得最优路径的问题依赖于各条组成支路的权值的确定。在现实情况下，各路径的权值是综合考虑物流中心到各需求点间的距离、道路状况以及各道路安全性等因素得出的结果，因此在对实际支路赋权的过程中，会出现违背三角不等式的情况，在此对具体的赋权规则不做研究，而假设各实际支路的权值已得出。在对实际支路赋权完毕后，进行虚拟支路的赋权，各虚拟支路的权值均为实际支路权值之和的m倍，m为无穷大的自然数，即虚拟支路不可通行。

2.4 设计求解最优路径问题的流程 物流中心应急物流配送问题抽象后实质为一个N个节点的TSP问题。因此，总能找到一条最优路径。现在假设找到了此问题的一条最优路径L。L若不包含虚拟支路，则表示从物流中心出发，确实存在一条最优的配送路径，从距离、路况及安全性角度综合分析是最优的配送路径；若L中包括至少一条虚拟路径，则表示在现有路径下不存在符合条件的最优路径。即现有条件下的最短路径中某些节点至少需要经过两次。因此，为求得较优路径对图作如下处理。

假设L中某一虚拟路径为（a，b），则总可以从点a到点b找到（a，K1，K2，…，Kn，b）这样一条最短路，其中ki为最初的N个节点之一，且路（a，K1，K2，…，Kn，b）必不含虚拟路径路，称路（a，K1，K2，…， Kn，b）为虚拟路径（a，b）的最短代替路径。在已有节点之外新增加k个节点（A1，A2，…，Ak），新增节点的规则是节点Ak与Ki具有完全相同的属性，即Ak到任何节点的权值与Ki到任何节点权值相同，特别的Ak到与Ki具有相同属性的节点的权值为0。对L中每条虚拟路径都按照（a, b）的方式处理。

完毕后则全部节点数目增加到N+A，其中N个是最初的实际节点，A个为新增节点。此时，对于N+A个节点来说已经找到了一条回路L*，L*只包括这N+A个节点，且这N+A个节点在L*上出现且仅出现一次，同时L*上不含虚拟路径。说明这N+A个节点的TSP问题存在最优解。

根据以上分析，对物流中心应急物流配送问题设计的求解流程如图3。

3 模型的实例应用

3.1 实例分析 以四个需求点为例进行实例说明。假设需求点与物流中心的完全加权图表示如图4所示，各支路权值已给出。

①求这四个点的TSP问题，最优解为（0，2，1，4，3，0），路的长L=12+M，其中包含虚拟路径（2，3）。

②寻找（1，4）的最短代替路径为（1，2，0，3，4）。

③增加点A，B，C，则原图变为图5。

④求这八个点的TSP问题，最优解为（0，2，1，C，B，3，4，A，0）。

3.2 关于求得的解的讨论和实际意义解释 以上通过增加虚拟点的方法建立的求解模型，最终求得的最优路径L可以分为两种情况。情况一：最优路径L中除起点和终点外，不包含其它与起点具有相同属性的点，说明在实施应急物流配送过程中，运输车队从物流中心出发后经过路径L所示的各个需求点，物资送达完毕返回物流中心，各个需求点都得到供应。选择该运输路径，可以减少运输车队的使用，只组织一支物资运输车队，就可以达到完成运输任务的目的，有效地节约了运输资源。情况二：最优路径L中除起点和终点外还包含其它与起点具有相同属性的点。这说明在实施应急物流配送过程中，运输车队从物流中心出发后，中途要返回物流中心，再到其他未配送的需求点，最后遍历所有需求点后回到物流中心。解决此种情况的办法的，根据中途回到物流中心的次数n，在可行的情况下，将整体运输力量分成n+1支配送小分队，各小分队对相应的若干需求点进行物流配送，完毕后返回物流中心。这样，在总路径不增加的前提下，对所有物资需求点展开了并行的物流配送，使得对所有需求点的最长物流配送时间减少，配送的效率更高。

4 结束语

物流中心是物资供应体系中的一个重要的环节。研究应急物流配送路径优化问题，对提高物流中心配送效率具有重要意义。文章对物流中心应急物流配送路径问题进行了分析研究，建立了应急物流配送路径优化问题的模型，设计了模型的求解流程，最后通过实例对应急物流配送路径优化问题求解过程进行了详细说明。并结合现实情况，对求得的解进行了进一步分析讨论，提出了物流中心应急物流配送策略可能的改进意见，供物流中心决策参考。

参考文献：

[1]殷剑宏，吴开亚．图论及其算法[M]．北京：中国科技大学出版社，2003．

[2]刑文训，谢金星．现代优化计算方法[M]．北京：清华大学出版社，2001．

[3]《运筹学》教材编写组．运筹学[M]．北京：清华大学出版社，2005．