配送中心车辆路径选择物流论文

刘孝配：配送中心车辆最短路径问题的研究山东交通学院毕业设计（论文）前言随着当今经济全球化的发展，现代物流扮演者越来越重要的角色，而配送中心作为物流网络一个重要子节点,显得尤其重要。物流配送作为现代化物流系统结构的一个核心环节。它是指按照顾客的订单要求,通过在配送中心中进行货物的分拣、配货,将配好的货物按时送交收货人的活动。在物流配送业务中,选择合理的车辆配送路径,可以提高货物的配送效率、提高企业服务质量、降低货物配送成本以及增加企业的经济利润。物流配送车辆最短路径是指货物由出发地向目的地的运输过程中,运输车辆所经过的距离最短(或者运输费用最少，或者运输时间最少,),因此,选择合理的车辆最短路径可以有效地降低配送成本，提高企业服务水平，增加企业的市场竞争力。经典的Dijkstra算法和Floyd算法思路清晰,方法简便,但随着网络节点数的增加,计算过程就会越来越复杂,并具有一定程度的主观性。经典的Dijkstra算法和Floyd算法思路清楚,方法简便,但随着配送点数的增加,计算的复杂性以配送点数的平方增加,并具有一定的主观性。本文详细分析了经典方法的利弊之后,提出了SPFA算法，并引入相关计算机的知识，介绍了最短路径在lingo软件上的实现过程，最后给出具体的模型，分别运用该算法和lingo软件进行求解。

1绪论1.1研究的背景及意义随着经济全球化的发展和市场竞争的日益激烈,人们的需求更加多样化和个性化,为了适应市场发展的需要,企业的釆购、生产和销售模式不断转变和拓展,这对物流提出了更高的要求。物流作为连接生产与消费之间的重要环节,在社会大生产中的作用日益突出物流为经济的快速发展提供了重要的保障,物流产业已经成为一个新的经济增长点[1]。作为物流网络一个重要子节点的物流配送中心,也逐渐引起社会和企业的广泛重视。配送是指在经济合理的区域范围内,根据客户的订货要求(包括在货物种类、数量和时间等方面的要求),在配送中心对货物进行拣选、加工、包装、组配、装车等作业,并将配装好的货物按时送达客户点的物流活动。配送是将货物从配送中心送达收货人的过程,它直接与消费者相连,是现代物流中一个重要的的环节,配送是物流的木端环节,实现了资源的最终配置。辆路径优化是配送中重要的部分,在配送过程中采用科学的、合理的方法来安排车辆的配送路线可以有效的提高车辆利用效率,缩短生产周期,降低配送成本,提高服务水平,提高企业的运营效率，提高市场响应速度，从而增强企业的竞争力。配送效率与很多因素有关，最短路径尤为重要。所以最短路径的选择就是核心问题，针对最短路径问题研究起源很久的年代，最短路问题是图论的核心问题之一，也是网络规划的一个基本问题，无向网络和有向网络都有对应的最短路径问题，是研究网络优化问题的一个最基本也最重要的分支，随着社会经济快速发展，信息时代来临，信息显得尤为重要，信息将会促进人类高速发展，人类掌握信息将会拥有人类社会的财富之源。最短路径这一基本问题作为选择网络最优问题的基础，在众多研究和应用领域如运输管理、管道铺设、交通网优化、物流调配、费用（成本）核算，工程进度等问题，都扮演者举足轻重的地位。实际中的许多问题都可以转化为一个特定的网络图模型，进一步转化为求解最短路径这一基本问题，现在，众多国内外学者已经深入研究最短路径问题。所谓最短路，是指从网络中一点寻求到其他点的最短的路。具体什么是最短路，简单地说，最短路就是从网络中某一点到另外一点的所有路中，所有边的权的代数和最小的路。把路中所有边的权的代数和称为路长。这里研究的最短路并不是我们生活中所理解的那种地理意义上的距离，而是能够涉及到其他层面的度量，比如时间、容量以及费用都可以纳入“路径”的范畴。实际中的许多网络最优化问题最终可转化为最短路径问题，或者可以运用最短路的算法作为其子程序。而目前的研究工作主要集中于算法的优化改进以及引用计算机技术。同时，最短路径问题在生产生活的很多方面得到了广泛的应用，比如工程进度、线路选择、石油运输、费用成本核算、网络铺设等问题。地理科学技术与计算机信息科学技术等许多热门研究都多多少少的涉猎最短路径优化问题。因此，研究最短路径优化问题具有重要的理论价值和实际价值，且应用前景广阔。1.2论文研究现状目前，求解最短路径优化问题需要用到图论研究中的经典算法理论，最短路径算法是求解网络模型图中任意两个节点之间的最短路径，并且相应的算法理论也在不断地推陈出新，科学完善进步。并随着信息科学技术的快速发展，最短路径优化问题已广泛应用于各社会学科领域，是进行分析与设计具有系统功能模型等不可缺少的理论基础，并与工程生产技术中很多具有实用价值的问题密切相关，近年来随着科技的发展，特别是计算机应用软件的开发，大大促进了其又快又好的发展。最短路径问题凭借着强大的实际应用，已成为近几十年来发展活跃的一门社会学科。对最短路径问题的研究要追溯到二十世纪六十年代,著名的荷兰计算机专家E.W.Dijksta开创性的提出了Dijkstra算法针对赋权图，该算法可以求出网络任一顶点到其他各点的最短路。该算法适用于所有权数均为非负（即一切）的网络。Dijkstra算法的复杂度为顶点数平方的数量级即O（），由此可知当针对较大规模的网络模型时，顶点数和边数较多，相应的算法的计算量则较大，花费时间更多。因此，Dijkstra算法在理论上是正确的，但在实际应用中就会不尽如人意。随着时间的推移，针对各种网络模型，相关研究学者也提出了一些新的算法，如解决含有负权边的网络——Ford算法。以及后来提出的更加高效的SPFA算法等。最短路的求解算法很多，主要有Dijksta算法、Floyd算法、Bellman-Floyd算法以及SPFA算法等等，这些算法是许多更深层算法的基础。目前，使用比较普遍而且得到公认的经典算法是Dijkstra算法和Floyd。无论哪一个算法，他们解决实际问题核心思想就是转化模型；运用图论的知识，将一个无向或有向图都看成一个网络，并把各点间的相关信息看成图的连接矩阵。经上述模型转化，解决最短问题转化为，以矩阵为工具，对图的各顶点穷尽，知道验证目标值为最优解。Dijkstra算法是求解网络图最短路径的基本方法,同时也是其他一些算法的理论基础。当前，求解赋权图中任意两顶点之间的最短路问题通常有以下两种方法：（1）Dijkstra算法。每次以一个结点为起点,重复n次算。（2）Floyd算法。时间复杂度为O（），该算法形式简洁易懂，广泛应用各种模型。最近几年来，互联网应用和科学信息技术的高速发展，人们对社会信息的需求日益膨胀。现实社会中，大量的复杂应用问题每时每刻都以各种各样的形式快速传播衍变，因此，要求人们对最短路径算法进行更深入的研究。计算机通信与网络、智能物流系统和大规模运输网络等的大热，自然而然的推动了这个古老的研究课题快速发展，目前来看最短路径问题常常都以非常复杂的网络图结构呈现。除此之外，当今的算法主要都是针对两点间的小规模网络，而对于大规模网络图如何解决成为重中之重。所以，最短路径优化问题的研究仍然具有重大的理论价值和实际价值，且发展应用前景广阔。1.3论文研究的内容本论文首先介绍最短路径优化问题的相关知识，以及图论和配送中心等理论。根据据已知经典算法知识，针对单源小规模无负权边网络最短路径这一问题，引出了Dijkstra算法以及相关的算法原理，步骤等。针对Dijkstra算法的缺点引出SPFA算法，并介绍该算法基本原理，基本步骤等，运用该算法求解具体的案例，并通过计算机lingo软件对其运算结果进行分析比较，最后给出科学的验证结果，最后得出SPF算法思想简洁、操作简单易懂，效率高效，是求解大规模网络模型最短路径问题的有效利器。本论文的具体展开内容如下所示：第一章绪论。本文主要论述了车辆配送中心最短路径问题的历史背景和意义，并且具体论述了最短路径问题的研究现状、研究目的，以及本论文主干内容和框架结构。第二章最短路径问题及其相关算法。介绍了配送中心相关概念以及功能特点，从而引出最短路径问题。紧接着详细介绍了最短路径问题的一些基本概念、图论的相关定义，并给出了求解小规模网络最短路径问题的经典算法——Dijkstra算法。详细介绍了Dijkstra算法的产生，Dijkstra算法的基本原理、Dijkstra算法基本步骤、Dijkstra算法缺陷等。第三章最短路径问题的SPFA算法。首先针对Dijkstra算法的缺陷只能求解给出单源、无负权、小规模网络图模型。在Dijkstra算法的基础上进而提出新算法——SPFA算法。详细介绍了SPFA算法的产生、SPFA算法的基本原理、Dijkstra算法基本步骤、之后给出此算法对运输模型的具体实现过程，并给出具体的最短路径问题案列例的求解结果，最终得出最短路径和路长等。在这一章引入计算机技术——lingo软件。详细介绍了lingo软件的相关基本概念，lingo语法，lingo模型等，并给出具体的最短路径问题的求解过程。第四章案例分析及其结果分析在本章主要是针对具体的最短路径问题案列求解。首先运用SPFA算法进行求解，并得出最后的最短路径和路长。然后针对同一问题运用计算机技术——lingo软件进行求解，并得出最后的最短路径和路长。最后对两种求解方法的最后结果进行分析比较，进而验证其算法的正确性。第五章总结。本章对全文做了一个系统性的针对总结，以及给出本文尚存在的不足，以及以后需要改进的地方。

2配送中心车辆最短路径问题概述2.1配送中心概述2.1.1配送中心的概念配送中心是组织配送性销售或供应，以执行实物配送为主要职能的流通型物流结点。日本《物流手册》定义：“配送中心是从供应者手中接受多种大量的货物，进行倒装、分类、保管、流通加工和信息处理等作业，然后，按照众多需要者的订货要求备齐货物，以令人满意的服务水平进行配送的设施[2]。”配送活动是在物流发展的客观过程中产生并不断发展的，这一活动随着物流活动的深入和物流服务社会化程度的提高，在实践中不断演绎和完善着其组织机构。我们将组织配送性销售或专门执行实物配送活动的流通机构称为配送中心。配送中心具有集货、分货、送货等基本功能，为了提供更完善的配送服务，配送中心有时还具有较强的流通加工能力[3]。配送中心是物流中心的一种主要形式，是在实践中产生并发展的，因此，国内外学者对配送中心的界定还不完全相同。例如，日本《市场用语词典》对配送中心的解释是：“是一种物流结点，它不以贮藏仓库的这种单一的形式出现，而是发挥配送职能的流通仓库。也称作基地、据点或流通中心[4]。”2.1.2配送中心的功能一般的仓库只重视商品的储存保管，传统的运输只是提供商品运输配送而已，而配送中心是重视商品流通的全方位功能，同时具有商品储存的功能。配送中心的功能全面完整，它把收货验货、储存保管、装卸搬运、拣选、流通加工、配送、结算和信息处理有机地结合起来，通过发挥配送中心的各项功能，大大地压缩整个连锁企业的库存费用，从而降低整个物流系统的成本，提高企业的服务水平。2.2最短路径问题介绍在实际问题中，经常会遇到一些大规模网络问题，如运输管理、管道铺设、交通网优化、物流调配、费用（成本）核算，工程进度等问题，这就需要解决出行距离最小、花费成本最低、距离最短、最优路径等一系列网络图的寻优问题。对这些类似问题，可以用“最短路径”来描述，有时简称为最短路。最短路径问题一般分为三类：第一，单源最短路径问题：包括确定起点的最短路径问题与确定终点的最短路径问题；第二，确定起点和终点的最短路径问题：即已知起点和终点，求两顶点之间的最短路径问题；第三，全网络最短路径问题：求图中所有顶点间的最短路径问题。用于解决最短路径问题的算法称作“最短路径算法”，有时被减称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford、Floyd算法、SPFA算法等。2.3最短路径问题的相关概念在日常生活中，经常会遇到各种各样的图或网络，如一个国家或地区的地图、国家铁路运输网、城市交通网、工程图、电信公司铺设的光纤网，自来水管道网等等。如果对某项工程的有关分析、决策等只在实体上进行，将会非常困难，因此需要把现实中的实体抽象成一种既简单又可以量化的图形。那么如何将现实中的实体抽象成可以量化的图或网络、如何对图或网络进行设计以及如何对图或网络进行分析等，这就用到下面要介绍的应用比较广泛的一个数学分支——图论。2.3.1图论相关定义图：自然语言的描述是，图是由表示具体事物的对象（顶点）集合和表示事物之间的关系（边）集合组成，例如针对铁路网，边表示区段，顶点表示区段间的车站；针对城市道路网，边表示道路，顶点表示交叉口。如果用G表示图，用表示点，用V表示所有点的集合，用表示边，用E表示所有边的集合，那么图的数学语言描述就是G=（V,E)其中，。另外，图G的顶点集合与边集合也可分别用V(G)和E(G)表示。根据边有没有方向，将图分为无向图、有向图和混合图。所有边都是无向边的图称为无向图，所有边都是有向边的图称为有向图，既有有向边又有无向边的图一般称为混合图。根据无向图的定义，无向图的数学语言描述为：存在图G=（V,E)，其中V是一个由n个顶点的非空集合，即，E是一个由m条边的非空集合，即，若E中任意一条边e是V的无序元素对（），其中i#j，即可以有()=（)，则称图G为无向图，如图2.1所示。图2.1无向图Fig.2.1undirectedgraph根据有向图的定义，有向图的数学语言描述为：存在图G=（V,E)，其中V是一个n个顶点的非空集合，即，E是一个由m条边的非空集合，即,若E中任意一条边e是V的有序元素对（），其中i#j，即（)#（)，则称图G为有向图，如图2.2所示。图2.2有向图Fig.2.2directedgraph如果把无向边用元素对表示，那么边（）和边（）是同一条边，和称为该无向边的端点，其中无向边与端点（顶点）和相关联，顶点和相邻，如图2.1中的边（）和（）属于同一条边，顶点和为该无向边的端点。如果把有向边用元素对表示，那么边（）和边（）就不是同一条边，针对边（）来说,顶点称为该有向边的起点，顶点称为该有向边的终点；但针对边（）来说，顶点为该有向边的起点，顶点为该有向边的终点，如图2.2中有向边（）和（）就不是同一条边，顶点和为边（）的起点和终点，但为边（）的终点和起点。赋权图:把图中的边或点赋上表示一定意义的数量指标，这个数量指标称为权，如果一个图中所有的边都具有权值，那么就称此图为赋权图，或者称为网络。2.3.2最短路径无向图相关术语链：无向图G中，两个端点之间的连接路径称为链。如图2.1中，和之间的连接路径即为链。一条链的起始端点和终止端点不为同一个端点的链称为开链，否则称为闭链，如图2.1中，链为开链，链为闭链。初等链：在无向图G中，如果一条链中没有重复的顶点，则此链称为初等链。如图2.1中，链不是初等链，因为有重复的顶点，而链是初等链。路：针对无向图G的一条链，若链中的每个点都不相同，则称这条链为连接链的起点和终点的路。如图2.1中链也称为路。回路：在一个无向图的闭链中，如果除了起始端点和终止端点相同外，没有相同的顶点和相同的边，则此闭链也称为回路。如图2.1中，闭链是回路，而闭链就不是回路，因为有相同的顶点和相同的边（）。有向图相关术语路：针对有向图G的一条链，若链中每个点都不相同，则称这条链为连接该链起点和终点的路。如图1中链称为路。回路：在网络图G(V,E)中，如果路径中的起始端点和终止端点重合，则称这样的路径为回路。无回路网络：如果该网络图不含任何一条回路，则称此网络为无回路网络。最短路径：在赋权图D中给定两节点，在两节点间的所有可行路径中，边权值最小的路径称为两节点间的最短路径。无向图的邻接矩阵：针对有m条边n个顶点的无向图G，G=（V,E），其中V={}，E=（），给定一个n行n列矩阵A=,在矩阵外的左侧对应每一行依次标上n个顶点，在矩阵外的上侧对应每一列依次标上n个顶点，形式如式2.1所示：

......(2.1)其中矩阵A中元素为连接顶点和顶点的数量。把矩阵A称为无向图G的邻接矩阵，邻接矩阵刻画了无向图G的顶点之间边的连接数量情况。有向图的邻接矩阵：有向图邻接矩阵的形式和无向图的邻接矩阵（2.1）一样，唯一不同的是，有向图的邻接矩阵中，的值是以顶点为起点，以顶点为终点的边的数量。加权有向图的带权邻接矩阵：如果有向图D(V,E)的每条弧都赋予一个权值，则称D为加权有向图；设D（V,E）是一简单加权有向图，，则D的邻接矩阵，其中： = (2.2)松弛：设边的权值为，如图2.3所示，如果边的引入会使得再减小，则要修改，即如果+<，则要将的值修改成+，将修改的运算称为一次松弛。

图2.3SPFA算法基本图Fig.2.3SPFAalgorithmbasicchart到的黑线表示，到的黑线表示2.4最短路径问题的常用解决方法——Dijkstra算法2.4.1介绍该法是狄克斯屈在1959年提出的，适用于所有权数均为非负（即一切0）的网络，能够求出网络的任一点到其他各点的最短路，为目前求这类网络最短路的最好算法。2.4.2Dijkstra算法思想在最短路的计算过程中，为了将已经求出最短路的点与尚未求的点分开，可以针对顶点给出两个子集合S和T，已经求出最短路的点置于集合S中，其他点置于集合T中。开始时把起点置于集合S中，把其他点置于集合T中；随着最短路计算过程的推移，集合S中的点逐渐增多，集合T中的点逐渐减少，当终点也被纳入到集合S中时，计算结束。2.4.3Dijkstra算法步骤第一步：设，，其中i=2，,n。在网络图中，把起点赋以标号（，即（0，），其余各点均为。第二步：检查起点，即将网络中的标号变为(0*,),表示已被检查，同时设集合。第三步：针对其他点，若与没有直接连线，的标号就保持不变；若与有直接连线，则点的标号就变为，其中第四步：计算。将对应点的第一个标号标上*，即变为*，表示已被检查，同时设集合，此时。第五步：再依次求，若与没有直接连线，的标号就保持不变；若与有直接连线，则计算。若来源于，则把的标号修改为，否则点的标号保持不变。第六步：计算。将*对应点的第一个标号标上*，即变为*，表示已被检查同时设集合，而。第七步：返回第五步，直到所有的点都被检查，而且终点进入到集合S中为止。第八步：在网络中，从终点的第二个标号开始反向追踪，从而找出最短路径;同时从终点的第一个标号可以读出起点到终点最短路的路长。另外，从各个点第一个标号也可以读出从起点到该点的最短路长。2.4.4Dijkstra算法缺陷（1）Dijkstra算法只适用与所有的情形，当网络中有若干条负边权时，Dijkstra算法就不能保证给出正确的结果了。（2）Dijkstra算法的复杂度为顶点数平方的数量级，当网络模型的规模较大时，节点数和边数多达上千或上万时，该算法的计算量就会大大增加，就会花费更多的时间，效率必然低。（3）Dijkstra算法不能一次求出从一个顶点到其它各顶点的所有最短路径。（4）原始Dijkstra算法在储存图形数据和运算时，基于网络的权矩阵，需要根据其节点与距离间的关系，形成关联矩阵、邻接矩阵与距离矩阵，需要定义NN的数组来存储数据，其中N为网络的节点数，当网络的节点数较大时，将占用大量的计算机内存。（5）原始Dijkstra算法在运行时一般将网络节点分为未标记节点、临时标记节点和永久标记节点3种类型。网络中所有节点首先初始化为标记节点，在搜索过程中和最短路径节点相连通的节点为临时标记点，每一处循环都是从临时标记节点中搜索距离原点路径长度最短的节点作为永久标记节点，直至找到目标节点或者所有节点都成为永久标记节点才结束算法[5,6]。根据算法的描述可知对临时标记节点的遍历成为Dijkstra算法的瓶颈，影响了算法的执行效率。（6）Dijkstra算法能够保证百分之百找到最优解，但其搜索速度较慢，搜索效率非常低，时间花费较多，一般只能用于离线的路径规划问题。如节点数为n的图，用Dijkstra算法计算最短路径总共需要迭代n-1次，每次迭代都新加一个节点到临时节点集合中，由于第i次迭代时不在临时节点集合中的节点数为n-i。即第i次迭代需对n-i个节点进行处理，因此其所需的处理数为，对n个节点网络的时间复杂度是O().在实际应用当中，使用Dijkstra算法查找最短路径时耗费大量的时间进行数据的比较[7]。

3配送中心车辆最短路径算法的实现3.1SPFA算法解决最短路径问题3.1.1SPFA算法介绍求单源最短路的SPFA算法的全称是：ShortestPathFasterAlgorithm，是西南交通大学段凡丁于1994年发表的。从名字我们就可以看出，这种算法在效率上一定有过人之处。很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。SPFA（ShortestPathFasterAlgorithm）（队列优化）算法是求单源最短路径的一种算法，在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。3.1.2SPFA算法的理论基础SPFA算法的基本思想是“先进先出”，首先建立一个矩阵，把网络中的待优化节点按顺序存放在矩阵图中，并赋予初始值，先进先出，即每次队首元素u先出列进行优化，对以队首元素u为起始点的所有边的终点进行松弛优化操作，即以队首元素u的最短路径当前值，对终点边v进行松弛优化操作，如果v点的最短路径估计值减小且不在队列中，那么v点就应该进入队列，重复以上松弛操作步骤，直至待优化点队列空为止，便可求出最短路径。SPFA算法不但可以求解最短路径，同时也可以判断网络图是否存在负环，如果某个点弹出队列的次数大于n-1次，则此图必存在负环[8]。如果图存在负环，则无法计算单源最短路径。那么下面介绍一个定理，给出网络图存在负回路的充分必要条件，在给出此定理之前必须先介绍下面三个性质，具体如下：性质一：，其中j=1,2,...,n，k=2,3,；性质二：若存在某个,使得，则有，且对p>k及1，有；性质三：不大于网络图G中弧数不超过k的任何有向（）途径的权，其中j=1,2,,n,k=2,3,。定理3.1网络图G=（V,A,w）不含负回路并且仅当对1jn，有证明:必要性(1)设网络G不含负回路，根据上面的性质中的为网络图G的最短()路的权，故等于图G中最短有向（）途径的权，即由性质三有，因此，由性质一得。（2）充分性()设G含有负回路，则到某些顶点的有向途径的权无下界，从而由性质三可知，存在某些j，使关于k无下界。假若1jn，有，则由性质二知，p>n及1jn，，此与某些关于k无下界矛盾。在介绍SPFA算法具体步骤前，作如下说明：dist[i]：存储源点到顶点的最短路径长度；path[i]：存储最终求得的源点到顶点的最短路径上，顶点的前个一顶点的序号。SPFA算法的基本步骤：(1)初始化，源点的距离dist设为0，其余的距离值均为，path[i]均为；新建一个队列，并将源点入队；(2)取出对头顶点v，标记v出队，并检查顶点v出队的次数，如果大于n，说明出现负环，算法结束。否则遍历从v发出的每条边，并设每条边的终点为u，边<u,v>的权值为w，如果dist[v]+w<dist[u]，则修改dist[u]=dist[v]+w，修改path[u]为v，检查顶点u是否在当前的队列中，如果不在，将其加入队列；如果dist[v]+w<dist[u]不成立，则对顶点u不作任何处理。(3)重复执行步骤（2），直到队列为空。案例1求a点到g点最短路径如图3.1所示。

图3.1a点到g点的线路图Fig.3.1ApointstothelinegraphG

首先建立起始点a到其余各点的最短路径矩阵图首先源点a入队，当队列非空时：队首元素（a）出队，对以a为起始点的所有边的终点依次进行松弛操作（此处有b,c,d三个点），此时路径矩阵图状态为：（队列中元素a)在松弛时三个点的最短路径估值变小了，而这些点队列中都没有出现，这些点需要入队，此时，队列中新入队了三个结点b,c,d。队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e点），此时路径矩阵图状态为：（队列中元素b,c,d）在最短路径矩阵图中，e的最短路径估值也变小了，e在队列中不存在，因此e也要入队，此时队列中的元素为c，d，e。队首元素c点出队，对以c为起始点的所有边的终点依次进行松弛操作（此处有e,f两个点），此时路径矩阵图状态为：(队列中元素c,d,e)在最短路径矩阵图中，e，f的最短路径估值变小了，e在队列中存在，f不存在。因此e不用入队了，f要入队，此时队列中的元素为d，e，f。队首元素d点出队，对以d为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径矩阵图状态为：(队列中元素d,e,f)在最短路径矩阵图中，g的最短路径估值变小了，g点不在队列中，因此g入队。此时队列中元素为e,f,g.队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g点），此时路径矩阵图状态为：(队列中元素e,f,g)在最短路径矩阵图中，g的最短路径估计值没有变小（说明松弛不成功），队列中无新元素加入，此时队列中元素为f，g。队首元素f点出队，对以f点为起始点的所有边的终点依次进行松弛操作（此处有e,g点），此时路径矩阵图状态为：(队列中元素f,g)在最短路径矩阵图中，e，g的最短路径估值又变小，队列中无e点，e入队，队列中存在g这个点，g不用入队，此时队列中元素为g，e。队首元素g点出队，对以g为起始点的所有边的终点依次进行松弛操作（此处只有b点），此时路径矩阵图状态为：(队列中元素g,e)在最短路径矩阵图中，b的最短路径估值有变小，队列中无b点，因此b入队，此时队列中元素为e，b。队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径矩阵图状态为：(队列中元素e,b)在最短路径矩阵图中，g的最短路径估值没变化（松弛不成功），队列中无新元素加入，此时队列中元素为b。队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e这个点），此时路径矩阵图状态为：(队列中元素b)在最短路径矩阵图中，e的最短路径估值没变化（松弛不成功），此时队列为空了。最终a到g的最短路径为14。3.2lingo软件解决最短路径问题随着经济的高速发展，在实际问题中，经常会遇到一些大规模网络问题，如运输管理、管道铺设、交通网优化、物流调配、费用（成本）核算，工程进度等问题，前面所讲到的一些经典算法就会显得有点捉襟见肘，无法保证快速高效的求出最优解。随着科学信息技术的不断提高，开发研究出了一系列优秀计算机软件，lingo就是一款求解大规模网络问题优秀软件。本文论述lingo软件求解网络最短路径问题的实现方法，并用具体的案例进行验证。3.2.1软件概述对于求解大规模最优化模型问题，美国LINDO系统公司开发推出了一款高效的软件产品——Lingo软件。LINGO软件广泛应用与数学规划问题的求解，同时对一些线性和非线性方程组问题提供好的解决方案，它强大无比的求解功能，是优化模型求解的不二选择。Lingo的主要功能：Lingo系统公司的线性、非线性和整数规划求解程序已经被全世界数千万的公司用来做最大化利润和最小化成本的分析。应用的范围包含生产线规划、运输、财务金融、投资分配、资本预算、混合排程、库存管理、资源配置等[9]。相关概念：定义1集合集合是一些相关对象的全体。集合中的每个元素都有一个或多个相关联的特性，被称为属性。定义2LINGO模型利用LINGO编写语言来表达一个实际优化问题，称之为LINGO模型。Lingo模型最基本的组成要素：一般来说，lingo中建立的优化模型可以由五个部分组成，或称为五“段”（SECTION):（1）集合段（SETS):以“SETS”开始，以“ENDSETS”结束。（2）目标与约束段：目标函数、约束条件等，没有段的开始和结束标记，因此实际上就是除其它四个段（都有明确的段标记）外的lingo模型。（3）数据段（DATA)：以“DATA：”开始，“ENDDATA”结束。（4）初始段（INIT):以“INIT”开始，“ENDINIT”结束。（5）计算段（CALC)：以“CALC：”开始,“ENDCALC”结束。3.2.2利用lingo软件解决最短路径问题如图3.2所示，求其最佳运输方案，即求v1v8的最短路径。图3.2点到点的线路图Fig.3.2linediagramofpointtopointLINGO程序全文如附录A，运行结果如表3.1所示:表3.1LINGO程序运行结果Table3.1LINGOprogramresultsFeasiblesolutionfound.Totalsolveriterations:0VariableValueN8.000000L()8.000000L()7.000000L()4.000000L()4.000000L()8.000000L()1.000000L()2.000000L()0.000000D(,)1.000000D(,)4.000000续表D(,)5.000000D(,)3.000000D(,)5.000000D(,)2.000000D(,)1.000000D(,)3.000000D(,)7.000000D(,)6.000000D(,)7.000000D(,)1.000000D(,)2.000000D(,)2.000000X(,)1.000000X(,)1.000000X(,)0.000000X(,)1.000000X(,)0.000000X(,)1.000000X(,)0.000000X(,)1.000000X(,)0.000000X(,)0.000000X(,)1.000000X(,)1.000000X(,)0.000000X(,)1.000000RowSlackorSurplus10.00000020.00000030.00000040.00000050.00000060.00000070.00000080.00000090.000000100.000000110.000000120.000000130.000000140.000000150.000000续表160.000000170.000000180.000000190.000000200.000000210.000000220.000000230.000000由lingo程序运行的结果可知，最短路径为L()=8，路径通过观察上面运行结果中X的值:X(,)，X(,)，X(,)X(,),X(,),X(,),X(,),X(,)的值均为1，则最短路径为，和，因此网络有两条最短路径。

4案例分析及其结果分析4.1案例当今社会互联网络的迅速发展，网上购物已经成为年轻人非常热衷的消费方式，那么作为普通消费者，最关心，最看重的是什么呢？网上调查显示莫过于两方面：一、物品的质量，店铺的信誉度；二、物流配送的速度，店家的服务态度。比如你今天网上买了一个物品，明天或者后天是否能够到达，或者更久，而货品和消费者往往都是跨市、跨省，那么这就涉及到了上面所提到的最短路径的问题。配送路线如何规划设计，能使得所花费用最少、配送速度最快是每个物流配送公司所必须考虑的问题[10]。现有一大型物流配送公司，现有一大批储存货物需要从地配送到地，配送需要途径多处地点，如图4.1所示，就好比古语“条条大路通罗马”那样，请指定出一条最优的送货路线，要求所用时间最短[11]。

图4.1运输路线网络图Figure4.1networkdiagramoftransportroutes4.1.1案例说明在图4.1中，为出发地，为目的地，顶点代表不同的地点，顶点间的连线代表路径，路径边的权值代表路长（单位为：公里，路长均为地区间的近似长度）。对于实际问题，我们需要做一些理想化的假设：（1）单位里程车速度一定；（2）货物装卸时间忽略不计；（3）忽略恶劣天气影响；（4）运输过程中无突发意外情况影响；在以上假设情况下，要求货物以最快的时间发送到目的地，即求解到的最短路径。4.1.2案例分析配送中心车辆需要将货物运输到目的地，要选择合理的路径在最短的时间内完成任务，即运输货物的路程最短。在单位里程车速度一定，在以上理想的假设情况下，根据公式：（其中s表示总里程，v表示单位里程速度，t表示时间）可知，总里程越短，所用时间越短，即总里程最短就可以满足要求。这样我们就把实际问题转化为最短路网络模型，即求解到的最短路径。4.2SPFA算法计算首先建立起始点到其余各点的最短路径矩阵图首先源点入队，当队列非空时：队首元素出队，对以为起始点的所有边的终点依次进行松弛操作（此处有,两个点），此时路径矩阵图状态为：（队列中元素）在松弛时两个点的最短路径估值变小了，而这些点队列中都没有出现，这些点需要入队，此时，队列中新入队了两个结点,。队首元素点出队，对以为起始点的所有边的终点依次进行松弛操作（此处有,,点），此时路径矩阵图状态为：（队列中元素,）在最短路径矩阵图中的最短路径估值没有变小（松弛不成功），，点的最短路径估计值变小了,且,队列中都没有出现，,需要入队，此时队列中元素为,,，队首元素点出队，对以为起始点的所有边的终点依次进行松弛操作（此处有,点），此时路径矩阵图状态为：(队列中元素,,）在最短路径矩阵图中，,的最短路径估值变小了，队列中无点，入队，队列中存在这个点，不用入队，此时队列中元素为,,，队首元素点出队，对以为起始点的所有边的终点依次进行松弛操作（此处有点），此时路径矩阵图状态为：（队列中元素,,)在最短路径矩阵图中,的最短路径估值变小了，队列中无点,入队，此时队列中元素为,,，队首元素点出队,对以为起始点的所有边的终点依次进行松弛操作（此处有,点），此时路径矩阵图状态为：（队列中元素,,)在最短路径矩阵图中,,的最短路径估值变小了，队列中有点,不用入队，队列中无点,入列。此时队列中元素为,,，队首元素点出队，对以为起始点的所有边的终点依次进行松弛操作（此处有,点），此时路径矩阵图状态为：（队列中元素,,)在最短路径矩阵图中，的最短路径估值没有变小（松弛不成功），的最短路径估值变小了，队列中无点，入队，此时队列中元素为,,，队首元素点出队，对以为起始点的所有边的终点依次进行松弛操作（此处有,点），此时路径矩阵图状态为：（队列中元素,,)在最短路径矩阵图中，的最短路径估值没有变小（松弛不成功），的最短路径估值变小了，队列中无点，入队，此时队列中元素为,,，队首元素点出队，对以为起始点的所有边的终点依次进行松弛操作（此处有,点），此时路径矩阵图状态为：（队列中元素,,)在最短路径矩阵图中，,的最短路径估值变小了，队列中没有点，入队，队列中有点，不用入队。此时队列中元素为,,，队首元素点出队，对以为起始点的所有边的终点依次进行松弛操作（此处有点），此时路径矩阵图状态为：（队列中元素,,)在最短路径矩阵图中，的最短路径估值没有变小（松弛不成功），没有新节点加入，此时队列中元素为,，队首元素点出队，对以为起始点的所有边的终点依次进行松弛操作（此处有,点），此时路径矩阵图状态为：（队列中元素,)在最短路径矩阵图中，,的最短路径估值变小了，队列中没有,点，则,入队。此时队列中元素为,,，队首元素点出队，对以为起始点的所有边的终点依次进行松弛操作（此处有点），此时路径矩阵图状态为：（队列中元素,,)在最短路径矩阵图中，的最短路径估值没有变小（松弛不成功），没有新节点加入，此时队列中元素为,，队首元素点出队，对以为起始点的所有边的终点依次进行松弛操作（此处有,点），此时路径矩阵图状态为：（队列中元素,)在最短路径矩阵图中，,,的最短路径估值变小了，队列中没有,点，则,入队。此时队列中元素为,,，队首元素点出队，对以为起始点的所有边的终点依次进行松弛操作（此处有点），此时路径矩阵图状态为：（队列中元素,,)在最短路径矩阵图中，的最短路径估值没有变小（松弛不成功），没有新节点加入，此时队列中元素为,，队首元素点出队，对以为起始点的所有边的终点依次进行松弛操作（此处有点），此时路径矩阵图状态为：（队列中元素,)在最短路径矩阵图中，的最短路径估值没有变小（松弛不成功），没有新节点加入，此时队列中元素为，队首元素点出队，此时队列为空。最终到的最短距离为36，同时从终点v15开始反向追踪，找出最短路径为：4.3Lingo软件运行Lingo程序全文如附录B，软件运行结果如表4.1所示：表4.1LINGO程序运行结果Table4.1LINGOprogramresultsGlobaloptimalsolutionfound.Objectivevalue:36.00000Infeasibilities:0.000000Totalsolveriterations:0VariableValueReducedCostN15.000000.000000W(,)8.0000000.000000W(,)6.0000000.000000W(,)5.0000000.000000W(,)4.0000000.000000W(,)3.0000000.000000W(,)3.0000000.000000W(,)4.0000000.000000W(,)8.0000000.000000W(,)5.0000000.000000W(,)6.0000000.000000W(,)7.0000000.000000W(,)5.0000000.000000W(,)10.000000.000000W(,)6.0000000.000000W(,)9.0000000.000000W(,)6.0000000.000000W(,)10.000000.000000W(,)9.0000000.000000W(,)4.0000000.000000W(,)5.0000000.000000W(,)3.0000000.000000W(,)7.0000000.000000W(,)8.0000000.000000W(,)9.0000000.000000X(,)0.0000000.000000续表X(,)1.0000000.000000X(,)0.0000000.000000X(,)0.0000000.000000X(,)0.0000000.000000X(,)0.0000000.000000X(,)1.0000000.000000X(,)0.0000000.000000X(,)0.0000000.000000X(,)0.0000000.000000X(,)0.0000000.000000X(,)1.0000000.000000X(,)0.0000000.000000X(,)0.0000000.000000X(,)0.0000000.000000X(,)0.0000000.000000X(,)1.0000000.000000X(,)0.0000000.000000X(,)1.0000000.000000X(,)0.0000000.000000X(,)0.0000000.000000X(,)1.0000000.000000X(,)0.0000000.000000X(,)0.0000000.000000RowSlackorSurplusDualPrice10.0000000.000000236.00000-1.00000030.000000-25.0000040.000000-17.0000050.000000-19.0000060.000000-13.0000070.000000-16.0000080.000000-15.0000090.000000-10.00000100.000000-8.000000110.000000-10.00000120.000000-5.000000130.0000000.000000140.0000004.000000150.0000007.000000160.0000005.000000170.000000-11.00000通过程序运行的结果可知，最短路径为36，从表的中间一列可以看得出，X(,)，X(,),X(,)，X(,)，X(,)，X(,)的值均为1，则最短路径为:。

结论配送中心车辆路径的选择即选择最优路径，最短路径是最重要的一环，大力节约企业的运输成本，提高运输服务的质量，进一步提高企业的生产效益，利于企业的长期健康发展。最短路径问题研究是网络优化问题的一个核心基础，主要对网络模型中任意两个节点之间的最优路径进行求解，最短路径问题有着相当悠久的研究历史。尤其是近几年来，随着计算机科学技术的快速发展以及相关软件的开发应用，最短路径问题的研究也上升到了很高的层面，最短路问题的理论研究成果不断运用到相关学科领域中，大力促进了模型分析设计学科的飞速发展。最短路径还广泛应用与社会生产实践中，物流调配，交通网的规划，选址问题，设备更新等问题。总而言之，最短路径问题的研究具有重要的理论价值和实际应用价值。由于本人水平有限、资料掌握不全，时间仓促等方面的限制，本文主要对配送中心车辆路径的选择进行了部分研究，将来对于配送中心车辆路径选择的研究可以从以下方面展开；（1）本文主要是对确定起点和终点的网络进行求解，以后还可以求解任意两点间的最短路径问题。本人限于水平只对小规模网络模型进行了研究，对于大规模网络模型，还需要更深层次的研究。本文主要研究了单个配送中心，单车辆的最短路径，对于多配送中心，多车辆的最短路径问题，需要进一步研究。

致谢衷心感谢我的导师李晶玮老师,感谢李老师在我进行毕业设计期间,给予我无微不至的关怀。感谢他在我论文撰写期间的指导,关心和帮助。可以说我的每一次收获和进步都浸透着李老师的心血,我每一个困难的克服都离不开李老师的鼓励和照顾。李老师对于工作认真负责，细心耐心的指导我，在我遇到困难时，总会给予我无私的帮助，在论文修改期间李老师一遍又一遍的帮我查重修改，伴随着我的每一次成长进步，李老师平时对工作负责，对学术要求严格，给我影响很大，是我以后学习奋斗的目标