送货员最短路径.doc

送货线路问题摘要：现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达。在信息技术高速发展的今天，设计高效实用的物流配送算法为物流配送系统实现合理路径运输,从而节约运输时间、减少运输费用, 提高现代物流系统效率和降低成本非常必要。本课题借鉴已有的数学模型，建立从库房到所有目标最优路径问题模型，并在此基础上借助运筹学路网中的最短路径算法。课题最后选择一种较为理想的算法利用C+语言编写了程序，利用C+知识编写程序，计算出两点之间的距离，用它作为连通路线上的权值，建立无向图，利用Dijkstra从起始点O到其他各点的最短路径，再在MATABLE里面根据算出来的最短路径编写程序计算出最快完成路线方式。关键字：线性规划模型、最短路径、Dijkstra算法送货员线路设计问题一、问题重述在网购越来越普及的情况下，送货线路设计问题成为一个很有研究价值的课题。送货员在库房选择怎样的路径才能在客户要求的时间内将货物送到，并且保证所选路径为最优路径，即最短时间。二、模型假设与符号说明2.1 模型假设1假设连通的道路为直线，送货员只能沿连通道路行走，不能走其他路线。2.假设每件货物交接的时间相同均为3分钟。3.送货员在一个地方也可以有多件货物交接，此时货物交接的时间也是3分钟。4.不考虑道路是否平坦交通状况等，送货员的平均速度为24公里/小时2.2 符号说明G=(V,E,L)无向图（路线网路）Vm个节点构成的点集（送货地点）En条边构成的边集（目的地之间的线路）L路权集（目的地之间的距离）vi(i=1,2,3,N)目的地的代码T标号临时标号P标号固定标号P,Qv1、终点vN开始的扩展点(固定标号)集合vm,vnP,Q的当前扩展点;d(vm)起点到vm的最短路径e(vn)起点到vn的最短路径三、问题分析3.1问题(1)的分析：利用C+知识编写程序，计算出两点之间的距离，用它作为连通路线上的权值，建立无向图，利用Dijkstra从起始点O到其他各点的最短路径，再在MATABLE里面根据算出来的最短路径编写程序计算出最快完成路线方式。3.2问题(2)的分析3.3问题(3)的分析四、模型建立与求解4.1模型准备1234567891011121314151617181920212223242526272829303132333735363438394041424445464750484943计算出两点之间的距离后，建立无向图，边上的权值为两点之间的距离。两点之间的距离见附录，所求距离的程序见附录。4.2问题（1）的模型建立与求解最短路径的算法研究，讨论最短路径算法及根据实际问题对经典算法进行优化，以提高运行效率。线性规划的一类重要的应用是网络最优化的问题。我们用符号G（V，E）来表示，V为节点集，E为弧集。最短路问题是对一个赋权的有向图D（在本文中就是路程的长度）中的指定的两个点vs到vt的最短路。这条路上所有弧的权数的总和被称之为vs到vt的距离。则无向图G=( V , E , L ) 。其中, V m 个节点构成的点集; E n 条边构成的边集; L 路权集, 同时满足: (1) G 为一个简单图,不含环和多重边; (2) 路权具有可加性。若有路径vi - vk - vj ,则有l ( vi , vj) = l ( vi , vk) + l ( vk , vj)求A , B 间的最短路径P满足：min L =最短路径算法：运用Matlab软件设计程序，具体程序及运行结果见附录。4.3问题（1）和（2）中模型的检验五、模型评价5.1模型优缺点5.1.1模型优点 (1) 在问题(1)和(2)中建立的模型是线性模型，用线性方程求解，简单快速。(2) 在问题(3)中，用直线交比模型对问题(1)、(2)中的模型进行检验，求解的结果，在世界坐标和图像坐标下，相互对应的交比误差在数量级，在误差允许的条件下，可以认为对应的交比是相等的。由此说明，模型符合交比不变性质，则可以很好的判定模型的精度。用噪音分析的方法检验问题(1)、(2)中的模型，从结果可以看出随着噪声像素的增加，欧式距离期望在增大，但是距离噪声比不断降低,可以很好的判定模型的稳定性。5.1.2模型缺点(1) 通过问题(1)中的算法求解出来的物图和像图中一些相对应的点坐标，可能存在一定的误差，代入相机标定模型中就有可能求得的参数误差较大，从而导致最终求得的物图中圆的圆心在像图中的坐标存在一定误差，需要进一步讨论，减小这种误差。 (2) 在建立模型时，我们假设相机成像过程是线性的，即不考虑镜头的畸变，从而得到的是相机的线性模型，即经典的小孔模型，由于不考虑镜头畸变，准确性是欠佳的；实际的相机系统通常都是由透镜或者透镜组构成，以得到更大的透光量，缩短曝光时间，并能得到较清晰的图像。而小孔成像由于透光量少，需要更长曝光时间，并且很难得到清晰图像。5.2 模型改进在模型建立中考虑镜头畸变。镜头的畸变，尤其是径向畸变往往是不可避免的。因此我们只考虑径向畸变，而忽略切向畸变。图9是带有径向畸变的相机模型。 参考文献1 郑瑾. 基于双目视觉的目标定位与运动分析研究. 燕山大学硕士研究论文. 2006.2 Richard Hartley, Andrew Zisserman著，韦穗等译. 计算机视觉中的多试图几何. 合肥：安徽大学出版社，2002. 3 张剑清, 潘励, 王树根等. 摄影测量学. 武汉：武汉大学出版社，2003。4 段德山. 基于HALCON的双目立体视觉系统实现. 中国图象网. /lunwen/120060919901915104296457.html. 200 交比解释 /view/1231510.htm .200摄像机标定. 【精敏视觉实验室】博客网站. /blog/user1/98/index.html.2008.9.21附录： 每两个连通点之间的距离序号位置点1位置点2两点间距离1131916.2792182863.78232207823.3154381958.0925343536.4146422292.647521252.93785155004.549611307.377107185917.94111711968.248128121756.765139101945.508149142681.3481510185909.545161072059.3691711121417.6831812131456.7941912154805.7992012255756.572113183113.4632213193455.6982313111669.5582414213296.7332514172195.7232614162607.6812714185342.1812815254235.3982915222860.9833016232097.6423117231774.5143218312103.6933319242258.6393420221498.9333521171832.9113621362880.1783721262191.743822301287.4883924311780.1474025191966.2154125291885.9024225414151.5944326311537.0264427311067.7554528331325.6894629221097.8624730281017.894830414997.6244931342324.7475032231311.8695132351114.0025233463758.515334401630.7825435381409.7255536272203.9175636453182.4565737402090.0545838361537.4175939271779.9236040453217.0066141462735.4166241442366.036341372601.922644243917.6746542491971.3766643382618.4446744504987.0466845422351.7236945503109.8437046481494.137147402331.2237248442152.5397349503568.8167450403043.49375 O182182.02976 O211796.94277 O261392.058源程序为：#include