图论在物流管理中的应用

张烨培　李星野

摘要：物流行业是当今世界发展最迅猛的行业之一，它涉及订购、仓储、运输、销售等多个环节。本文针对运输环节进行研究并以邮政运输问题为例探讨物流运输问题的一般解题思路。通过对邮政网点分布图和相关数据的分析，在满足时间限制和货物装载要求的条件下，求解出使空车率引起的损失费尽可能少的最短路线。本文采取分类讨论的方法，综合使用Floyd算法、TSP算法和动态规划法寻求最优邮路。

关键词：Floyd算法；TSP算法；邮递员问题；动态规划法

物流管理被媒体誉为“21世纪最大的行业”，是提高企业经济效益的重要源泉。它凭借以高新技术为基础的先进经营方式和管理方式，有效地整合资源、降低成本、提高效率，从而大大提高了整个社会生产力和市场竞争力。物流管理的各种理论深入我们的日常生活，邮政运输问题就是最好的实例。下面我们将以此为例，讨论Floyd算法、TSP算法及动态规划算法在物流领域的运用。

一些符号说明如下。W（i，j）：赋权临街矩阵；R（i，j）：路径记录矩阵；D：总局；Di（i=1...3）：虚拟总局；Zi（i=1...16）：第i个支局。其他符号在文中给出说明。

我国的邮政运输网络采用邮区中心局制，即以邮区中心局作为基本封发单元和网络组织的基本节点。首先由总局将邮件分发到各个支局，再有支局分发到更低级的邮政网点，以此逐层向下，最终到达收件人的手中。

图1是某地区的邮政网点分布图。

D是邮政总局，Zi（i=1...16）是该地区的16个邮政支局。若每辆邮车最多容纳65袋邮件，行驶速度均为30km/h，为了加强邮车的保养，规定一天最多行驶6个小时。邮车在各支局卸装邮件耗时5分钟。各邮政网点间的路线长度和各自装卸的邮包量数据见附录1。试问最少需要多少辆邮车才能满足该县的邮件运输需求？同时，为提高邮政运输效益，应如何规划邮路和如何安排邮车的运行？其中，空车率=（邮车最大承运的邮件量（袋）-邮车运载的邮件量（袋））/邮车最大承运的邮件量（袋），单车由于空车率而减少的收入为（空车率*2元/公里）。

一、模型分析

根据物流管理的知识我们知道，该题的目标是在满足工作时间小于6小时，完成所有邮件收发任务的前提下，寻求最短路径和花费最优的邮递运送方案。

根据题意，问题可归纳为如下数学模型

minC（

p，

p，…，

p）

min1g（

p，

p，…，

p）

s.t.（p，p，…，p）∈P

其中（p，p，…，p）表示邮路方案，C（p，p，…，p）表示空车损失费，1g（p，p，…，p）表示方案的总路径，表示邮路集合。

通过对题中数据的处理我们发现，寄达16个支局的邮包量为176袋，而收寄的邮包量为170袋。考虑到每辆邮车最多可以装载65袋邮包，因此从总局D至少发出3趟邮车。我们运用分类思想的方法，分别对下列四种情况加以讨论，根据最短路问题，综合运用Floyd算法和动态规划法，最终给出满足问题要求的最优方案

二、模型的建立与求解

通过题目给出各个邮政网点间的距离，我们给出17个邮政网点是直达矩阵A17×17，运用Floyd算法，基本思想是：直接在图的带权邻接矩阵中用插入顶点的方法依次构造出v个矩阵L1，L2，...Lv，使最后得到的矩阵Lv成为图的最短距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。

此算法的主要程序流程如下。

1.输入赋权邻接矩阵W（i，j）。

2.赋初值：对所有i、j，L1（i，j）←W（i，j），ri，j←j，k←1。

更新L（i，j），R（i，j）：对所有i，j，若L（i，k）+L（k，j）

若k=v，停止，输出L（i，j）、R（i，j）。

否则k←k+1，重复第一步。

通过上述方法求解得各个邮政网点的最短路径（如表1所示）。

通过上面的分析，我们知道由于寄达16个支局的邮包量为176袋，而收寄的邮包量为170袋，考虑到每辆邮车最多可以装载65袋邮包，总局D至少发出3趟邮车。为了节约成本，最多发3辆车。

我们分如下几种情况讨论。

方案一：出动1辆，车发3趟

我们观察图形发现该题类似一个旅行商问题，即从一点出发，通过所有的节点一次且仅有一次，最终回到起点。但该题又与旅行商问题存在一些区别，为了方便问题求解，我们提出“虚拟中转站”的概念。因为运送方案可以总结为

我们把总局D虚化成三个虚拟的总局D1，D2，D3，三个虚拟的总局和其他16个支局的关系继承了总局D与16个支局的关系（如图2）.

我们假设邮车从D1出发，经过包括D2，D3和其他16个支局的18个点，最终回到D1。这就将16个支局分成了3个划分，每个划分里构成一条邮路。从而将该问题简化成“中国邮递员问题”。

对于“中国邮递员问题”，我们提出下面2种解决方案。

（一）表上作业法

观察网络图，若图中不存在奇点，则过每条边一次且仅有一次的欧拉圈就是最短路线。若图种有奇点，就必须在某些边上重复一次或多次。

1.将途中的奇点两两配对，把每一对奇点之间的一条链的所有边作为重复边加到途中，这样新图种必无奇点，给出一个初始可行方案。

2.观察图中的每个圈，调整方案，使得在最优方案中，图的每一条边上最多一条重复边，且各个圈上的重复边总权不大于该权总权的一半。

（二）动态规划法

我们经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。

为了节约重复求相同子问题的时间，本文引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。

设计一个标准的动态规划算法，通常可按以下几个步骤进行。

1.划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或是可排序的（即无后向性），否则问题就无法用动态规划求解。

2.选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

此外还有很多解决此类问题的方法，如遗传算法、粒子群算法、蚁群算法等。鉴于篇幅的限制我们不一一说明，只具体叙述了上面两种求解“中国邮递员问题”的经典算法。

鉴于该问题改进后的网络图存在一定的复杂度，我们运用动态规划编程求解得到该方案的最短里程数为279公里。因为邮车速度是30km/h，时间至少需要9小时，不满足题中最多行驶6小时的要求，所以此方案不可行。

方案二：出动2辆车，各发2趟

该种方案即将16个支局分成4个划分。同样运用方案一中阐述的算法，求解得到该方案的最短里程数是334km。考虑进装卸货所有的时间，得到每辆车的行驶时间为6.4小时，超过了6小时的时间限制，故此方案不可行。

方案三：出动2辆车，1辆车发1趟，1辆车发2辆

运用以上同样的方法可以得到其最短里程数为313km，最高时速30km/h，可得需要626分钟；再加上16个支局的装卸时间为80分钟，以及其中一辆车在县局的装卸时间10分钟，共716分钟。因此平均每辆车耗时358分钟，恰好满足，时间的限制。再考虑2辆车要送16个支局的因素，则至少有1辆车需要送8个支局。通过运行自己编写的判断程序，可以得到的结论是：在6个小时的时间限制下，这样的邮路是不存在的，因此这种方案也不予考虑。

方案四：出动3辆车，每辆车各发1趟

本方案与方案三所需的最短里程数同为313km，总共需时716分钟，平均每辆车耗时不到239分钟。由于有3辆车，则至少有一辆车需要投送6个支局。再运行上述的判断程序则可以知道这样的邮路是存在的，因此本方案可行。

再根据题中给出的数据得到该问题的最优解（如表2）。

三、总结

通过邮政路线问题，我们给出了物流问题的一般思路，即通过先进的调度方案和合适的经营管理机制，达到获利最多、成本最小或损失最少的目标。图论中最短路问题、最小费用最大流、中国邮递员问题、最小生成树、计划网络图、关键路径、TSP问题等都给物流管理提供了很好的思路。图论在物流管理中的作用可见一斑。

通过本学期对运筹课程的学习，我们掌握了单纯性算法、动态规划法、线性规划、非线性规划、排队论、决策论等经典的运筹模型。通过本次论文我们发现运筹学的研究与生活中的实际问题有密切的关联，它帮助我们拓宽了思维，加深了对身边问题认识，运用数学的方法使统筹安排身边的事，达到事半功倍的目的。

参考文献：

[1]金钢，师群昌，刘小麟.邮政运输网络中的邮路规划和邮车调度[J].数学的实践与认识，2008（14）.

[2]费蓉，崔杜武.中国邮递员问题的动态规划算法研究[J].计算机研究与发展，2005（02）.

[3]谢金星，薛毅.优化建模与Lindo/Lingo软件[M].北京：清华大学出版社，2005.

[4]《运筹学》教材编写组.运筹学[M].北京：清华大学出版社，2012.