柏乡超市配送路径优化问题研究

《运输与配送》结课论文题目柏乡超市配送路径优化问题研究柏乡超市配送路径优化问题研究摘要：随着我国物流快速迅速，一些物流企业之间竞争日益激烈，合理的控制物流配送成本已经成为物流企业生存的根本。其中的最短路问题是图论问题的一个经典问题，寻找最短路就是在指定网络两点间寻找一条距离最短的路，最短路径算法的选择与实现是通道路线设计的基础，最短路径算法是计算机科学与地理信息科学等领域的研究热点，许多网络相关问题均可纳入最短路径问题的传承中，经典的图论与不断发展完善的计算机数据结构及算法的有效结合，使得新的最短路径算法不断涌现。通过对柏乡镇方鲁村的小配送站与8个小超市之间的运输距离的收集整理，使用管理运筹学软件分析处理，得出从小配送站到各超市配送的最优路径，从而提高配送站物流配送效率，降低物流配送成本，提高市场竞争力，实现精细化管理，使配送更合理、更高效。 关键词：柏乡配送站；超市；路径优化；管理运筹学软件；数据分析绪论1.1研究背景随着物流产业不断发展、规模的不断扩大，物流配送的作用日益显著，配速是是一种综合特殊的物流形式，它实际上包含了全部的物流功能要素，是一种小规模的物流活动的表达，也可以说是一种小的物流系统。配送系统在物流产业发展中发挥着重要的作用，树立正确的物流配送意识，合理正确了解配送系统的结构和运行方式是配送站取得成功的保障，高效的配送效率和经济合理的物流配送成本是配送站提升市场竞争力的必然要求，对于小配送站而言，优化配送路径可以提高物流配送效率，降低物流配送成本，从而完善配备服务，提高市场竞争力[1]。在柏乡镇方鲁村有一个小配送站，配送站向柏乡镇多个小超市配送物资，因为小超市一般仅有周边人去购物，所以它的总需求量不大，故小配送站以每月两次的频率，用一辆大送货车完成周边9个超市物资的配送。现小配送站实行精细化管理，规划其最佳运输路线，节约成本，提高效益。1.2研究的目的和意义在整个物流系统中，配送是与消费者有关，有着密切关联的一个环节，而物流配送中的路径优化则在物流系统优化环节中起关键作用，好的配送方案不仅能节约物流成本，提高商品流动的速度，而且还由于它能有效连接生产与消费，从而既有利于物流服务与商品附加价值的实现，又能有效促进生产商品按需生产，真正使物流管理建立在持续经营的基础上。随着方鲁村的小配送站的不断发展，如何实现精细化管理，制定一个好的配送方案已经是配送站目前必须需要关注的事情。小配送站需要实现物流配送中的路径优化，提高物流配送效率，降低物流配送成本，完善配备服务，提高市场竞争力。2国内外路径优化研究现状2.1国内路径优化研究现状随着物流行业的蓬勃发展，物流企业正在逐渐走入高质量发展中，但我国物流行业和外国物流行业对比起步较晚，现在程度较低，20世纪70年代之前，我国各项经济研究中从未出现过物流一词，然而物流的各个环节早就运用在了国民经济的各个领域中，自20世纪80年代，物流出现在大众视野，并逐渐得到了专家学者们的关注，20世纪90年代的流通，从实际意义上证实了配送是一种十分重要的物流方式，我国许多城市建立了物流配送中心，从而给物流配送提供了很广阔的发展空间，越来越多的学者提出物流配送体系的构建模型及具体构建方法，从而使物流配送路径最优化。近年近年来我国物流配送发展迅速，但永远达不到现代物流发展的要求，我国各大小配送站的物流配送还存在诸多问题，许多地方都有自己的小型配送中心，然而这些配送中心大多效率不高。导致配送不高的原因，一般是资金和技术缺乏和落后，配送功能不齐全，技术不先进，导致配送中心配送直接脱节，另一方面，大多数配送中心只专注于“送”而忽略了“配”[2]。2.2国外路径优化研究现状路径优化问题属于车辆路线问题（VRP）类别，是Dantzig和Ranser在1999年第一次对VRP进行研究，提出了加油站路线优化的数学模型和算法，1964年Clarke和Wright提出了一种包含Ramser方式在内的Dancer，更有效的提高了启发式算法的保存算法，经过两篇开创性论文，VRP很快引起了应用数学、运筹学、图论、组合数学、计算机的应用及物流学派学科专家的重视。目前用来解决国外问题的方式主要分可分为优化算法和启发式算法，因为优化算法的应用领域有限，所以专家致力于构建高品质的启发式算法。3最短路算法定量算法分析3.1Floyd算法Floyd算法只有五行代码，代码简单，三个for循环就可以解决问题，所以它的时间复杂度为O(n*n*n)，可以求多源最短路问题。Floyd算法可以处理带有负权边，但不能处理带有“负权回路”的图。3.2Dijkstra算法（单源最短路）Dijkstra算法是单源最短路，以一个顶点出发到所有点的最短路。每次找到离源点最近的顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。即为依次找到离源点最近的顶点跟每个点到源点的距离，然后每个点到源点的距离与离源点最近的顶点加上两顶点的距离分别比较。就是dis[v]=dis[u]+e[u][v]。3.3Bellman-Ford（解决负权边）Bellman-Ford算法最多有n-1个阶段。在每一个阶段，我们对每一条边都要执行松弛操作。其实每实施一次松弛操作，就会有一些顶点已经求得其最短路，即这些顶点的最短路的“估计值”变为“确定值”。此后这些顶点的最短路的值就会一直保持不变，不再受松弛操作的影响[3]。3.4SPFA算法SPFA其实就是使用队列优化的Bellman-Ford算法。SPFA算法在形式上和广度优先搜索非常类似，不同的是在广度优先搜索的时候一个顶点出队后通常就不会再重新进入队列。而这里一个顶点很可能再出队列之后再次被放入队列，也就是当一个顶点的最短路程估计值变小之后，需要对其所有边进行松弛，但是如果这个顶点的最短路程估计值再次变小，仍需要对其所有边再次进行松弛，这样才能保证相邻顶点的最短路程估计值同时更新。初始时将源点加入队列，每次队首（head）取出一个顶点，并对与其相邻的所有顶点进行松弛尝试，若某个点松弛成功，且这个相邻的顶点不在队列中，则将他加入到队列中，对当前顶点处理完毕后立即出队，并对下一个新队首进行如上操作，直到队列为空时算法结束。这里用一个book数组来记录每个顶点是否在队列中[4]。3.5管理运筹学软件管理运筹学软件提供了线性规划，图与网络，其他模型三大类功能，拥有线性规划、运输问题、整数规划、目标规划，对策论等运筹方案，可以很好满足用户的各种运筹管理需求，得到路径的优化方案。4数据的收集与整理4.1运输距离数据的采集4.1.1确定地图位置研究的主题是柏乡镇方鲁村小配送中心向柏乡镇8个小超市即福顺超市、丰隆超市、冠迟超市、爱家超市、美阳购物、英杰购物中心、聚宝隆超市、博宇超市配送的路径优化问题。在高德地图上标出各地的具体位置，如图所示。4.1.2确定各地运输距离如下图所示，用高德地图地位，分别得出不同地点之间的距离。配送站到各地的距离：新福顺超市2.4千米，丰隆超市2.2千米，冠迟超市3.4千米，爱家超市3.3千米，美阳购物2.9千米，英杰购物中心2.4千米，聚宝隆超市3.6千米，博宇超市1.1千米。新福顺超市到各地距离：丰隆超市0.428千米，冠迟超市2.2千米，爱家超市0.802千米，美阳购物0.22千米，英杰购物中心0.517千米，聚宝隆超市1.5千米，博宇超市5.9千米。丰隆超市到各地距离：冠迟超市3.3千米，爱家超市3.1千米，美阳购物2.6千米，英杰购物中心1.4千米，聚宝隆超市3.0千米，博宇超市5.2千米。冠迟超市到各地距离：爱家超市2.6千米，美阳购物2.1千米，英杰购物中心1.5千米，聚宝隆超市2.7千米，博宇超市6.7千米。爱家超市到各地距离：美阳购物5.9千米，英杰购物中心5.3千米，聚宝隆超市4.3千米，博宇超市6.6千米。美阳购物到各地距离：英杰购物中心1.6千米，聚宝隆超市2.8千米，博宇超市6.9千米。英杰购物中心到各地距离：聚宝隆超市3.3千米，博宇超市6.6千米。聚宝隆超市到各地距离：博宇超市6.3千米。4.2运输距离数据整理 将所得数据进行整理，填入表格中。配送站新福顺超市丰隆超市冠迟超市爱家超市美阳购物英杰购物中心聚宝隆超市博宇超市配送站2.42.23.43.32.92.43.61.1新福顺超市0.4282.20.8020.220.5171.55.9丰隆超市3.33.12.61.43.05.2冠迟超市2.62.11.52.76.7爱家超市5.95.34.36.6美阳购物1.62.86.9英杰购物中心3.36.6聚宝隆超市6.3博宇超市5管理运筹学软件求解5.1管理运筹学软件介绍管理运筹学软件3.0是一款功能强大的运筹管理工具，为用户提供了线性规划，图与网络，其他模型三大类功能，拥有线性规划、运输问题、整数规划、目标规划，对策论等运筹方案，可以很好满足用户的各种运筹管理需求，非常适用于科学、运筹学、生产运作管理等场合，让运筹管理更加轻松高效。并且软件中的每种运筹方案都提供了详细的数据录入方式，例如在线性规划模式下就可以自定义变量个数、约束条件个数、目标函数，设置完毕就可以生成表格录入详细的数据，从而在软件快速分析各项数据，结合模型就可以直观的查看分析结果，让用户可以轻松管理统筹项目。另外，管理运筹学软件还支持多重求解，将一组数据提供不同的函数变量计算出可能出现的多组数据。5.2管理运筹学软件建模求解打开管理运筹学软件，点击“图与网络模块”中的“最短路问题”，根据所调查的数据，输入信息。软件输出一系列结果，如下表所示。整理信息可得最短路径为1→3→6→4→5→2→7→8→9→1，总路程为2.2+2.6+2.1+2.6+0.802+0.517+3.3+6.3+1.1=21.519。6总结将最短路理论应用到实际生活中，尤其是在配送路线中的应用具有非常重要的意义，可以提高物流配送效率，降低物流配送成本，完善配备服务，提高市场竞争力。这显出学习和应用最短路问题原理的重要性。另外最短路问题在城市道路建设、物资供应站选址等问题上也有很重要的作用。使用管理运筹学软件可以大量分析数据，得出最短路线，极