图论某企业在浙江省的物流配送应用研究

王庆泽

【摘要】物流业在我国得到了迅速的发展，尤其近年来，第三方物流企业和电子商务平台的逐渐兴起更是使得国家和政府对物流企业予以了重视。然而，由于我国地域跨度大，物流尚处于初中期发展阶段，物流路线并没有得到很好的规划。论文应用图论的方法，以X物流企业在浙江省各个城市的配送路线规划为例，介绍了最小树算法和最邻近算法在对物流配送路线规划中的应用，并对其优缺点进行了评价。

【关键词】物流配送；最小树算法；最邻近算法

中图分类号：F27 文献标识码A： 文章编号：1006-0278（2014）05-071-02

一、引言

物流是供应链活动的一部分，是为了满足客户需要而对商品、服务以及相关信息从产地到消费地的高效、低成本流动和储存进行的规划、实施与控制的过程。现代物流作为一种先进的组织方式和管理技术，已成为世界经济发展的热点之一。

物流有七个基本职能：运输、包装、信息处理、装卸搬运、流通加工、仓储和配送。物流配送是指按照客户的要求，经过分货、拣选等货物配备工作，把最终产品从生产线的末端到消费者手中的移动和存储过程。在物流配送中，最为关键的是物流配送路线的设计与规划。合理确定配送路线就是用最少的动力，走最短的里程，花最少的费用，经最少的环节，以最快的速度把货物运至用户手中。合理规划配送路线对配送成本的影响要比一般运输大得多，所以必须在全面计划的基础上，制定高效的运输路线，选择合理的运输方式和运输工具。

据统计，在我国，物流费用占了货品总成本的30%，运输成本比西方发达国家高出3倍。另外，从产品的供应链结构来看，90%的时间消耗在流通环节，在生产环节的时间只占10%。另据统计，2011年，全国社会物流总额达158.4万亿元，同比增长12.3%。国内现代物流业实现增加值3.2万亿元，同比增长13.9%。全国社会现代物流总费用为88.4万亿元，同比增長18.5%，但第三方物流在整个物流需求中所占的份额不足4%，远低于发达国家。另外，我国实际完成的货运总量远少于需要运输的实物量，使货物在途时间延长，压港、压航、压库严重。同时在我国的外包物流服务中，85%来自基础性服务，其中53%来自运输管理，32%来自仓储管理，增值服务及物流信息的财务收益只占15%。而在美国，来自基础性服务的收益占62%，增值服务的比例已达38%。因此我们不难看出：尽管目前我国社会物流需求持续高速增长，物流业增加值稳步上升，物流服务在我国仍占主导地位，但物流发展的总体水平还比较低，问题比较突出。

二、图论应用

（一）图论应用方法介绍

1.背景介绍。图论是应用十分广泛的运筹学分支，它很好地应用于物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域。在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。例如，完成工程任务的时间最少、距离最少、距离最短、费用最省等。图论受到数学、工程技术及经营管理等各个方面越来越广泛的重视。

在物流配送中，由于配送成本主要受到运输路程的影响，因此对配送路线的合理规划与设计显得尤其重要。本文以某物流企业在浙江省的配送情况为例，对该企业在浙江省几个城市的物流配送路线进行了规划设计。

2.基本概念。首先将论文中所用到的基本概念简单介绍如下：（1）圈：任选一个顶点为起点，沿着不重复的顶点为途径，之后又回到起点的闭合途径称为圈。（2）树：一个无圈的连通图称为树。（3）支撑树：设图T=（V，E）是图G=（V，E）的支撑子图，如果图T=（V，E）是一个树，则称T是G的一个支撑树。（4）连通图：在图G中，若任何两点之间至少有一条链，则称G是连通图，否则称为不连通图。（5）最小支撑树：假设连通图中每个边都有一个权，如果支撑树T上所有边的权之和是所有支撑树中权的最小者，则称T是G的最小支撑树。

（二）论文数据来源及前提假设

1.数据来源。物流运输费用包括货车的燃油费用、收费路段的路桥费、运输人员的工资、车辆维修费用等，由于本论文侧重于从减少整个物流配送网络的运输距离，从而减少路费，因此主要用到的数据是浙江省各城市之间的距离，数据来源《中国交通地图册》。所选取的城市有杭州、湖州、嘉兴、舟山、宁波、绍兴、衢州、金华、丽水、温州、台州。因此本文选取了11个城市进行分析与计算。各城市间距离如图1所示：假设除舟山外，浙江省各城市均可以直接相连，而舟山仅与宁波直接相连。汇总浙江省各城市间直接到达距离如表1所示（单位：公里）：

2.前提假设.物流配送是一个复杂的过程，需要考虑的问题很多。本文重点考虑图论在物流配送路线规划中的作用，因此论文有如下前提假设：（1）论文假设使用的交通工具只有货车（因此舟山是一个悬挂点，只与宁波直接相连）；（2）在计算路桥费的时候，虽然每条路线都是部分路段是收费路段，但论文为了简化计算过程，没有细分哪些是收费路段；（3）论文假设设定的线路上货车可以装载所有的货物，与车型和车辆数无关，因此运输费用只与运输距离相关；（4）论文假设往返运货量和运输距离是等量的，例如，从杭州到温州和从温州到杭州的运货量和运输距离是相同的；（5）论文假设每配送到一个城市，都会对货物进行整合。

（三）避圈法在某企业浙江省主要城市中物流配送的路线研究

1.方法介绍

由上述假设可以看出，如果只考虑运输距离，那么对于运输费用最小化的求解恰是一个典型的求解最小支撑树的问题。

求解支撑树有两种简单而又常用的方法：