物流论文配送中心车辆最短路径问题的研究

山东交通学院毕业设计（论文）I摘要配送中心车辆路径选择是配送中的关键一环,选择合理的最短路径对加快配送速度、节约运输成本、提高服务质量和提高物流经营管理水平具有重要意义。最短路径问题是研究网络优化问题的一个重要分支和基础。论文的研究旨在运用科学合理、简便高效的方法对车辆最短路径进行选择。论文内容针对DIJKSTRA算法的缺陷，介绍一种新算法，并引入相关计算机的知识，介绍了最短路径在LINGO软件上的实现过程，最后给出具体的模型，分别运用算法和LINGO软件进行求解。关键词配送中心，图论，最短路径，DIJKSTRA算法，SPFA算法，LINGO软件刘孝配配送中心车辆最短路径问题的研究IIABSTRACTDISTRIBUTIONCENTERVEHICLEROUTINGISAKEYLINKINTHEDISTRIBUTIONOF,CHOOSEREASONABLESHORTESTPATHTOSPEEDUPTHEDELIVERYSPEED,SAVETHETRANSPORTATIONCOSTANDIMPROVETHEQUALITYOFSERVICEANDITISOFGREATSIGNIFICANCETOIMPROVETHELEVELOFLOGISTICSMANAGEMENTTHESHORTESTPATHPROBLEMISANIMPORTANTBRANCHANDBASISFORSTUDYINGNETWORKOPTIMIZATIONPROBLEMTHEPURPOSEOFTHISPAPERISTOSELECTTHESHORTESTPATHOFTHEVEHICLEWITHSCIENTIFICANDREASONABLEMETHODTHECONTENTTOOVERCOMETHEDEFECTSOFDIJKSTRAALGORITHM,INTRODUCEANEWALGORITHM,ANDTHEINTRODUCTIONOFCOMPUTERRELATEDKNOWLEDGE,THISPAPERINTRODUCESREALIZATIONPROCESSOFTHESHORTESTPATHINTHELINGOSOFTWARE,FINALLYGIVESTHEMODEL,RESPECTIVELY,USINGTHEALGORITHMANDLINGOSOFTWARETOSOLVEKEYWORDSDISTRIBUTIONCENTER,GRAPHTHEORY,THESHORTESTPATHDIJKSTRAALGORITHM,SPFAALGORITHM,LINGO山东交通学院毕业设计（论文）III目录前言11绪论211研究的背景及意义212论文研究现状313论文研究的内容42配送中心车辆最短路径问题概述521配送中心概述5211配送中心的概念5212配送中心的功能522最短路径问题介绍523最短路径问题的相关概念6231图论相关定义6232最短路径724最短路径问题的常用解决方法DIJKSTRA算法10241介绍10242DIJKSTRA算法思想10243DIJKSTRA算法步骤10244DIJKSTRA算法缺陷113配送中心车辆最短路径算法的实现1331SPFA算法解决最短路径问题13311SPFA算法介绍13312SPFA算法的理论基础1332LINGO软件解决最短路径问题17321软件概述17322利用LINGO软件解决最短路径问题184案例分析及其结果分析2141案例21411案例说明22412案例分析2342SPFA算法计算2343LINGO软件运行26结论29致谢30刘孝配配送中心车辆最短路径问题的研究IV参考文献31附录A32附录B33山东交通学院毕业设计（论文）1前言随着当今经济全球化的发展，现代物流扮演者越来越重要的角色，而配送中心作为物流网络一个重要子节点,显得尤其重要。物流配送作为现代化物流系统结构的一个核心环节。它是指按照顾客的订单要求,通过在配送中心中进行货物的分拣、配货,将配好的货物按时送交收货人的活动。在物流配送业务中,选择合理的车辆配送路径,可以提高货物的配送效率、提高企业服务质量、降低货物配送成本以及增加企业的经济利润。物流配送车辆最短路径是指货物由出发地向目的地的运输过程中,运输车辆所经过的距离最短或者运输费用最少，或者运输时间最少,因此,选择合理的车辆最短路径可以有效地降低配送成本，提高企业服务水平，增加企业的市场竞争力。经典的DIJKSTRA算法和FLOYD算法思路清晰,方法简便,但随着网络节点数的增加,计算过程就会越来越复杂,并具有一定程度的主观性。经典的DIJKSTRA算法和FLOYD算法思路清楚,方法简便,但随着配送点数的增加,计算的复杂性以配送点数的平方增加,并具有一定的主观性。本文详细分析了经典方法的利弊之后,提出了SPFA算法，并引入相关计算机的知识，介绍了最短路径在LINGO软件上的实现过程，最后给出具体的模型，分别运用该算法和LINGO软件进行求解。刘孝配配送中心车辆最短路径问题的研究21绪论11研究的背景及意义随着经济全球化的发展和市场竞争的日益激烈,人们的需求更加多样化和个性化,为了适应市场发展的需要,企业的釆购、生产和销售模式不断转变和拓展,这对物流提出了更高的要求。物流作为连接生产与消费之间的重要环节,在社会大生产中的作用日益突出物流为经济的快速发展提供了重要的保障,物流产业已经成为一个新的经济增长点1。作为物流网络一个重要子节点的物流配送中心,也逐渐引起社会和企业的广泛重视。配送是指在经济合理的区域范围内,根据客户的订货要求包括在货物种类、数量和时间等方面的要求,在配送中心对货物进行拣选、加工、包装、组配、装车等作业,并将配装好的货物按时送达客户点的物流活动。配送是将货物从配送中心送达收货人的过程,它直接与消费者相连,是现代物流中一个重要的的环节,配送是物流的木端环节,实现了资源的最终配置。辆路径优化是配送中重要的部分,在配送过程中采用科学的、合理的方法来安排车辆的配送路线可以有效的提高车辆利用效率,缩短生产周期,降低配送成本,提高服务水平,提高企业的运营效率，提高市场响应速度，从而增强企业的竞争力。配送效率与很多因素有关，最短路径尤为重要。所以最短路径的选择就是核心问题，针对最短路径问题研究起源很久的年代，最短路问题是图论的核心问题之一，也是网络规划的一个基本问题，无向网络和有向网络都有对应的最短路径问题，是研究网络优化问题的一个最基本也最重要的分支，随着社会经济快速发展，信息时代来临，信息显得尤为重要，信息将会促进人类高速发展，人类掌握信息将会拥有人类社会的财富之源。最短路径这一基本问题作为选择网络最优问题的基础，在众多研究和应用领域如运输管理、管道铺设、交通网优化、物流调配、费用（成本）核算，工程进度等问题，都扮演者举足轻重的地位。实际中的许多问题都可以转化为一个特定的网络图模型，进一步转化为求解最短路径这一基本问题，现在，众多国内外学者已经深入研究最短路径问题。所谓最短路，是指从网络中一点寻求到其他点的最短的路。具体什么是最短路，简单地说，最短路就是从网络中某一点到另外一点的所有路中，所有边的权的代数和最小的路。把路中所有边的权的代数和称为路长。这里研究的最短路并不是我们生活中所理解的那种地理意义上的距离，而是能够涉及到其他层面的度量，比如时间、容量以及费用都可以纳入“路径”的范畴。实际中的许多网络最优化问题最终可转化为最短路径问题，或者可以运用最短路的算法作为其子程序。而目前的研究工作主要集中于算法的优化改进以及引用计算机技术。同时，最短路径问题在生产生活的很多方面得到了广泛的应用，比如工程进山东交通学院毕业设计（论文）3度、线路选择、石油运输、费用成本核算、网络铺设等问题。地理科学技术与计算机信息科学技术等许多热门研究都多多少少的涉猎最短路径优化问题。因此，研究最短路径优化问题具有重要的理论价值和实际价值，且应用前景广阔。12论文研究现状目前，求解最短路径优化问题需要用到图论研究中的经典算法理论，最短路径算法是求解网络模型图中任意两个节点之间的最短路径，并且相应的算法理论也在不断地推陈出新，科学完善进步。并随着信息科学技术的快速发展，最短路径优化问题已广泛应用于各社会学科领域，是进行分析与设计具有系统功能模型等不可缺少的理论基础，并与工程生产技术中很多具有实用价值的问题密切相关，近年来随着科技的发展，特别是计算机应用软件的开发，大大促进了其又快又好的发展。最短路径问题凭借着强大的实际应用，已成为近几十年来发展活跃的一门社会学科。对最短路径问题的研究要追溯到二十世纪六十年代,著名的荷兰计算机专家EWDIJKSTA开创性的提出了DIJKSTRA算法针对赋权图，该算法可以求出网络任一顶点到其他各点的最短路。该算法适用于所有权数均为非负（即一切0）的网络。DIJKSTRA算法的复杂度为顶点数平方的数量级即O（2N），由此可知当针对较大规模的网络模型时，顶点数和边数较多，相应的算法的计算量则较大，花费时间更多。因此，DIJKSTRA算法在理论上是正确的，但在实际应用中就会不尽如人意。随着时间的推移，针对各种网络模型，相关研究学者也提出了一些新的算法，如解决含有负权边的网络FORD算法。以及后来提出的更加高效的SPFA算法等。最短路的求解算法很多，主要有DIJKSTA算法、FLOYD算法、BELLMANFLOYD算法以及SPFA算法等等，这些算法是许多更深层算法的基础。目前，使用比较普遍而且得到公认的经典算法是DIJKSTRA算法和FLOYD。无论哪一个算法，他们解决实际问题核心思想就是转化模型；运用图论的知识，将一个无向或有向图都看成一个网络，并把各点间的相关信息看成图的连接矩阵。经上述模型转化，解决最短问题转化为，以矩阵为工具，对图的各顶点穷尽，知道验证目标值为最优解。DIJKSTRA算法是求解网络图最短路径的基本方法,同时也是其他一些算法的理论基础。当前，求解赋权图中任意两顶点之间的最短路问题通常有以下两种方法（1）DIJKSTRA算法。每次以一个结点为起点,重复N次算。（2）FLOYD算法。时间复杂度为O（3N），该算法形式简洁易懂，广泛应用各种模型。最近几年来，互联网应用和科学信息技术的高速发展，人们对社会信息的需求日益膨胀。现实社会中，大量的复杂应用问题每时每刻都以各种各样的形式快速传播衍变，因此，要求人们对最短路径算法进行更深入的研究。计算机通信与网络、智能物流系统和大规模运输网络等的大热，自然而然的推动了这个古老的刘孝配配送中心车辆最短路径问题的研究4研究课题快速发展，目前来看最短路径问题常常都以非常复杂的网络图结构呈现。除此之外，当今的算法主要都是针对两点间的小规模网络，而对于大规模网络图如何解决成为重中之重。所以，最短路径优化问题的研究仍然具有重大的理论价值和实际价值，且发展应用前景广阔。13论文研究的内容本论文首先介绍最短路径优化问题的相关知识，以及图论和配送中心等理论。根据据已知经典算法知识，针对单源小规模无负权边网络最短路径这一问题，引出了DIJKSTRA算法以及相关的算法原理，步骤等。针对DIJKSTRA算法的缺点引出SPFA算法，并介绍该算法基本原理，基本步骤等，运用该算法求解具体的案例，并通过计算机LINGO软件对其运算结果进行分析比较，最后给出科学的验证结果，最后得出SPF算法思想简洁、操作简单易懂，效率高效，是求解大规模网络模型最短路径问题的有效利器。本论文的具体展开内容如下所示第一章绪论。本文主要论述了车辆配送中心最短路径问题的历史背景和意义，并且具体论述了最短路径问题的研究现状、研究目的，以及本论文主干内容和框架结构。第二章最短路径问题及其相关算法。介绍了配送中心相关概念以及功能特点，从而引出最短路径问题。紧接着详细介绍了最短路径问题的一些基本概念、图论的相关定义，并给出了求解小规模网络最短路径问题的经典算法DIJKSTRA算法。详细介绍了DIJKSTRA算法的产生，DIJKSTRA算法的基本原理、DIJKSTRA算法基本步骤、DIJKSTRA算法缺陷等。第三章最短路径问题的SPFA算法。首先针对DIJKSTRA算法的缺陷只能求解给出单源、无负权、小规模网络图模型。在DIJKSTRA算法的基础上进而提出新算法SPFA算法。详细介绍了SPFA算法的产生、SPFA算法的基本原理、DIJKSTRA算法基本步骤、之后给出此算法对运输模型的具体实现过程，并给出具体的最短路径问题案列例的求解结果，最终得出最短路径和路长等。在这一章引入计算机技术LINGO软件。详细介绍了LINGO软件的相关基本概念，LINGO语法，LINGO模型等，并给出具体的最短路径问题的求解过程。第四章案例分析及其结果分析在本章主要是针对具体的最短路径问题案列求解。首先运用SPFA算法进行求解，并得出最后的最短路径和路长。然后针对同一问题运用计算机技术LINGO软件进行求解，并得出最后的最短路径和路长。最后对两种求解方法的最后结果进行分析比较，进而验证其算法的正确性。第五章总结。本章对全文做了一个系统性的针对总结，以及给出本文尚存在的不足，以及以后需要改进的地方。山东交通学院毕业设计（论文）52配送中心车辆最短路径问题概述21配送中心概述211配送中心的概念配送中心是组织配送性销售或供应，以执行实物配送为主要职能的流通型物流结点。日本物流手册定义“配送中心是从供应者手中接受多种大量的货物，进行倒装、分类、保管、流通加工和信息处理等作业，然后，按照众多需要者的订货要求备齐货物，以令人满意的服务水平进行配送的设施2。”配送活动是在物流发展的客观过程中产生并不断发展的，这一活动随着物流活动的深入和物流服务社会化程度的提高，在实践中不断演绎和完善着其组织机构。我们将组织配送性销售或专门执行实物配送活动的流通机构称为配送中心。配送中心具有集货、分货、送货等基本功能，为了提供更完善的配送服务，配送中心有时还具有较强的流通加工能力3。配送中心是物流中心的一种主要形式，是在实践中产生并发展的，因此，国内外学者对配送中心的界定还不完全相同。例如，日本市场用语词典对配送中心的解释是“是一种物流结点，它不以贮藏仓库的这种单一的形式出现，而是发挥配送职能的流通仓库。也称作基地、据点或流通中心4。”212配送中心的功能一般的仓库只重视商品的储存保管，传统的运输只是提供商品运输配送而已，而配送中心是重视商品流通的全方位功能，同时具有商品储存的功能。配送中心的功能全面完整，它把收货验货、储存保管、装卸搬运、拣选、流通加工、配送、结算和信息处理有机地结合起来，通过发挥配送中心的各项功能，大大地压缩整个连锁企业的库存费用，从而降低整个物流系统的成本，提高企业的服务水平。22最短路径问题介绍在实际问题中，经常会遇到一些大规模网络问题，如运输管理、管道铺设、交通网优化、物流调配、费用（成本）核算，工程进度等问题，这就需要解决出行距离最小、花费成本最低、距离最短、最优路径等一系列网络图的寻优问题。对这些类似问题，可以用“最短路径”来描述，有时简称为最短路。最短路径问题一般分为三类第一，单源最短路径问题包括确定起点的最短路径问题与确定终点的最短路径问题；刘孝配配送中心车辆最短路径问题的研究6第二，确定起点和终点的最短路径问题即已知起点和终点，求两顶点之间的最短路径问题；第三，全网络最短路径问题求图中所有顶点间的最短路径问题。用于解决最短路径问题的算法称作“最短路径算法”，有时被减称作“路径算法”。最常用的路径算法有DIJKSTRA算法、A算法、BELLMANFORD、FLOYD算法、SPFA算法等。23最短路径问题的相关概念在日常生活中，经常会遇到各种各样的图或网络，如一个国家或地区的地图、国家铁路运输网、城市交通网、工程图、电信公司铺设的光纤网，自来水管道网等等。如果对某项工程的有关分析、决策等只在实体上进行，将会非常困难，因此需要把现实中的实体抽象成一种既简单又可以量化的图形。那么如何将现实中的实体抽象成可以量化的图或网络、如何对图或网络进行设计以及如何对图或网络进行分析等，这就用到下面要介绍的应用比较广泛的一个数学分支图论。231图论相关定义图自然语言的描述是，图是由表示具体事物的对象（顶点）集合和表示事物之间的关系（边）集合组成，例如针对铁路网，边表示区段，顶点表示区段间的车站；针对城市道路网，边表示道路，顶点表示交叉口。如果用G表示图，用IV表示点，用V表示所有点的集合，用IL表示边，用E表示所有边的集合，那么图的数学语言描述就是G（V,E其中,21NVVVV，,21MEEEE。另外，图G的顶点集合与边集合也可分别用VG和EG表示。根据边有没有方向，将图分为无向图、有向图和混合图。所有边都是无向边的图称为无向图，所有边都是有向边的图称为有向图，既有有向边又有无向边的图一般称为混合图。根据无向图的定义，无向图的数学语言描述为存在图G（V,E，其中V是一个由N个顶点的非空集合，即,21NVVVV，E是一个由M条边的非空集合，即,21MEEEE，若E中任意一条边E是V的无序元素对（JIVV,），其中IJ，即可以有JIVV,（IJVV,，则称图G为无向图，如图21所示。山东交通学院毕业设计（论文）7图21无向图FIG21UNDIRECTEDGRAPH根据有向图的定义，有向图的数学语言描述为存在图G（V,E，其中V是一个N个顶点的非空集合，即,21NVVVV，E是一个由M条边的非空集合，即,21MEEEE,若E中任意一条边E是V的有序元素对（JIVV,），其中IJ，即（JIVV,（IJVV,，则称图G为有向图，如图22所示。图22有向图FIG22DIRECTEDGRAPH如果把无向边用元素对表示，那么边（JIVV,）和边（IJVV,）是同一条边，I和JV称为该无向边的端点，其中无向边与端点（顶点）I和JV相关联，顶点I和JV相邻，如图21中的边（42,VV）和（24,VV）属于同一条边，顶点2V和4V为该无向边的端点。如果把有向边用元素对表示，那么边（JIVV,）和边（IJVV,）就不是同一条边，针对边（JIVV,）来说,顶点I称为该有向边的起点，顶点JV称为该有向边的终点；但针对边（IJVV,）来说，顶点JV为该有向边的起点，顶点I为该有向边的终点，如图22中有向边（42,VV）和（24,VV）就不是同一条边，顶点2V和4V为边（42,VV）的起点和终点，但为边（24,VV）的终点和起点。赋权图把图中的边或点赋上表示一定意义的数量指标，这个数量指标称为权，如果一个图中所有的边都具有权值，那么就称此图为赋权图，或者称为网络。232最短路径刘孝配配送中心车辆最短路径问题的研究8无向图相关术语链无向图G中，两个端点之间的连接路径称为链。如图21中，1V和5V之间的连接路径,53421VVVVV即为链。一条链的起始端点和终止端点不为同一个端点的链称为开链，否则称为闭链，如图21中，链,3421VVVV为开链，链,13421VVVVV为闭链。初等链在无向图G中，如果一条链中没有重复的顶点，则此链称为初等链。如图21中，链,532431VVVVVV不是初等链，因为有重复的顶点3V，而链,3421VVVV是初等链。路针对无向图G的一条链，若链中的每个点都不相同，则称这条链为连接链的起点和终点的路。如图21中链,53421VVVVV也称为路。回路在一个无向图的闭链中，如果除了起始端点和终止端点相同外，没有相同的顶点和相同的边，则此闭链也称为回路。如图21中，闭链,13421VVVVV是回路，而闭链,123421VVVVVV就不是回路，因为有相同的顶点2V和相同的边（21,VV）。有向图相关术语路针对有向图G的一条链，若链中每个点都不相同，则称这条链为连接该链起点和终点的路。如图1中链,2431VVVV称为路。回路在网络图GV,E中，如果路径中的起始端点和终止端点重合，则称这样的路径为回路。无回路网络如果该网络图不含任何一条回路，则称此网络为无回路网络。最短路径在赋权图D中给定两节点，在两节点间的所有可行路径中，边权值最小的路径称为两节点间的最短路径。无向图的邻接矩阵针对有M条边N个顶点的无向图G，G（V,E），其中VNVVV,21，E（MEEE,21），给定一个N行N列矩阵ANNIJA,在矩阵外的左侧对应每一行依次标上N个顶点，在矩阵外的上侧对应每一列依次标上N个顶点，形式如式21所示山东交通学院毕业设计（论文）91VJVMVNNNJNINIJINJJIAAAAAAAAAVVVA111111121其中矩阵A中元素IJA为连接顶点IV和顶点JV的数量。把矩阵A称为无向图G的邻接矩阵，邻接矩阵刻画了无向图G的顶点之间边的连接数量情况。有向图的邻接矩阵有向图邻接矩阵的形式和无向图的邻接矩阵（21）一样，唯一不同的是，有向图的邻接矩阵中，IJA的值是以顶点IV为起点，以顶点JV为终点的边的数量。加权有向图的带权邻接矩阵如果有向图DV,E的每条弧都赋予一个权值，则称D为加权有向图；设D（V,E）是一简单加权有向图，,21NVVVV，则D的邻接矩阵NNIJAA，其中IJA,0,EVVJIWEVVWJIIJJIIJ若，若是它的权；且若（22松弛设边32,VV的权值为32,VVW，如图23所示，如果边32,VV的引入会使得31VDISTK再减小，则要修改31VDISTK，即如果21VDISTK32,VVWK及1NJ，有1KJPJUU；性质三KJU不大于网络图G中弧数不超过K的任何有向（JVV,1）途径的权，其中J1,2,N,K2,3,。定理31网络图G（V