交通运输组织学课程设计-启发式算法在物流送货线路设计中的应用 40页

课程设计课程名称:交通运输组织学设计题目:启发式算法在物流送货线路设计中的应用学生姓名:学号:200930010227班级:交通运输0902班院系名称:交通运输工程学院指导老师:2012年12月 《交通运输组织学》课程设计课程名称:交通运输组织学设计题目:启发式算法在物流送货线路设计中的应用学生姓名:任涛学号:200930010227班级:交通运输0902班院系名称:交通运输工程学院指导老师:杨明、张生、李琼星 长沙理工大学课程设计任务书交通运输工程学院交通运输专业2009级2班课程名称交通运输组织学题目:启发式算法在物流送货线路设计中的应用学生姓名任涛学号200930010227同组设计者：无一、已知技术参数和设计要求1、已知技术参数与参考资料①交通运输部客货运组织与管理相关标准与规范②董千里。交通运输组织学[M]。人民交通出版社，2008年③李维斌。公路运输组织学[M]。人民交通出版社，2005年④崔书堂，朱艳茹。交通运输组织学[M]。东南大学出版社，2008年⑤戴彤焱。运输组织学[M]。机械工业出版社，2008年2、设计要求本课程设计是针对学生学习和运用专业知识的综合考核和检查，使学生接受工程类基本训练的重要环节，是交通运输《交通运输组织学》专业课程学习的必修内容之一。本课程设计的特点是，内容所涉及的知识面较一般习题广，有较强的系统性和综合性，在运算、绘图、编写设计文本方面有较高的要求。本课程实际应针对交通运算组织学课程涉及的相关理论与方法，结合具体实践背景，解决实际问题。要求①所涉及方法、模型与理论知识与本课程相关；②有具体的实践背景；③课程实际要求完整、系统，从提出问题、解决问题与结论三个方面开展，思路清晰，条理清楚。二、课程设计应完成的任务1、围绕课程中交通组织方面内容，完成对其方法、模型的阐述；2、结合实际背景，采用以上理论，进行运输组织优化等针对性设计，提出方案；3、对方案结果进行分析。三、工作计划本次课程设计安排时间为二周，2012年12月24日至2013年1月4日，具体工作计划如下：1、2012年12月24日～25日，项目背景资料的收集与整理； 2、2012年12月26日～27日，完成课程设计大纲；3、2012年12月28日～2012年12月31日，完成课程设计背景与基础资料的分析部分书写工作；4、2013年1月1日～2日，完成课程设计核心——模型分析与问题解决部分的书写工作；5、2013年1月3日～2013年1月4日，完成绘图与结论部分的书写以及修改工作。四、课程设计完成提交文档要求按照以下顺序装订成册：1、封面；2、扉页；3、任务书；（4）指导书；5、目录；6、正文；7、附录（表格或图纸）；8、成绩评定表指导老师：同意按照任务书要求开展设计教研室意见：同意按照任务书要求开展设计教研室主任：时间：注：1、此任务书由指导老师填写。如果不够，可以加页；2、此任务书最迟必须在课程设计开始前一周下达给学生；交通运输组织学课程设计 指导书一、课程设计目的与要求1、课程设计目的《交通运输组织学》课程是交通运输本科专业的必修课，一门理论与实践结合紧密的核心课程。本课程设计是在该门课程的课堂教学完成之后，为巩固课程涉及到的交通运输组织学方面的方法、理论而开展的。通过课程设计，使学生能结合实际背景，应该已学理论，解决实际问题，从而培养学生资料查阅能力、绘图能力、理论联系实际的能力、系统解决问题的逻辑思维能力等，为今后从事相关工作打下基础。2、课程设计要求本课程设计要求学生根据课程涉及的相关内容与方法，结合实际背景，系统解决实际问题。从背景分析、提出问题、解决问题、主要结论等几个方面开展。要求课程设计具有系统性、完整性、与课程相关性并具有一定的研究深度。二、课程设计的依据与资料来源课程设计的依据：①交通运输部客货运组织与管理相关标准与规范②董千里。交通运输组织学[M]。人民交通出版社，2008年③李维斌。公路运输组织学[M]。人民交通出版社，2005年④崔书堂，朱艳茹。交通运输组织学[M]。东南大学出版社，2008年⑤戴彤焱。运输组织学[M]。机械工业出版社，2008年资料来源：①指导教师提供相关资料；②实际调研收集资料；③相关书籍；④网络资料收集。三、课程设计学生应完成的内容 内容应从设计背景交代（实际现状分析与问题分析），提出问题，阐述解决问题的理论，并采用理论与模型计算分析，提出优化方案。四、课程设计要求及其它1、时间安排：二周设计时间（2012年12月24日～2013年1月4日），实际操作中，可提前进行相关资料的收集与大纲的完成；2、要求独立完成，一人一题，每人提交1份打印的设计成果（A4）及电子文档；3、格式要求：装订按照要求的顺序依次装订成册，文档具体格式参考格式模板；4、纪律要求：集中在固定教室严格考勤，按照作息，一般不允许请假，如遇特殊情况，需要填写请假条报院领导批准，否则按照每天旷课8节处理。另请假或旷课时数累计达全部设计时间的1/3以上，该课程设计按照零分计。运输与物流工程系2012年12月目录一、问题重述1二、模型假设1 三、文中符号说明2四、问题一的解决方案24.1问题一的分析24.2问题一的模型准备34.2.1邻接矩阵的建立34.2.2Floyd算法计算任意两点间的最短距离34.3问题一的模型建立和求解44.3.1模型建立44.3.2算法实现54.3.3模型求解74.3.4结果分析11五、问题二的解决方案115.1问题二的分析115.2问题二的求解125.2.1第一类货物的送货路径125.2.2第二类货物的送货路径135.2.3第三类货物的送货路径135.2.4第四类货物的送货路径13六、问题三的解决方案146.1问题三的分析146.2模型的建立与求解146.2.1最小生成树的建立146.2.2算法的实现及结果分析16七、总结18参考文献19附录20 一、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在附录一图中O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图附录一，各点连通信息见附录二，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见附录三，50个位置点的坐标见附录四。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。问题一：若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。问题二：假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。问题三：若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。以上各问尽可能给出模型与算法。二、模型假设2.1送货员的送货速度保持恒定，不考虑堵车及其他意外情况；2.2送货员交接完货物后，马上前往下一送货地点，中间没有时间耽搁；2.3相互连通的道路都是双向通道，没有单向的情况；2.4不考虑送货员午休及午饭时间，即送货员按时上班并连续工作。32 三、文中符号说明3.1：邻接矩阵3.2：图中第i个点和第j个点之间的联通情况3.3：最短距离矩阵3.4：第i个点与第j个点之间的最短距离3.5：遗传算法中的种群规模3.6：遗传算法中染色体交叉的概率3.7：遗传算法中基因变异的概率3.8：送货员完成送货任务所走的总路程3.9：完成第i类货物的送货任务所走的路程3.10：送货员完成送货任务所需的总时间3.11：完成第i类货物的送货任务所需的时间3.12：送货员的行进速度3.13：第i类货物具有的货物总数四、问题一的解决方案4.1问题一的分析对于问题一，根据附录三提供的数据，计算得到前30件货物（附录三中的1—30号）的总质量和总体积分别为49.5千克和0.9立方米，两者均未超过送货员的最大承载能力，送货员可以一次性送完所有货物，因此不需要考虑因超过送货员最大承载能力对送货时间造成的影响。附录中已经给定了各点的坐标，货物的信息以及各点之间的联通信息，由于货物交接时间一定，则送货所需的时间主要由送货路程决定，所以最快完成路线即送货路程最短路线。求送货路程最短问题是典型的TSP问题（TravelingSalesmanProblem)32 ），TSP问题的一个显著特征是图中的每个点（除起始点外）必须且只能经过一次，然而，结合题目给定的送货路线，欲完成送货任务，部分点至少需经过两次甚至两次以上。所以，在解决该问题之前，必须将问题作适当的转换，使其成为典型的TSP问题。在建立模型之前，可以根据附录三（各点之间的联通信息）建立[0,1]邻接矩阵，然后运用Floyd算法求出任意两点之间的最短距离，最后用遗传算法和模拟退火算法找到这22个点（包括O点在内）的最短路径及最短距离。4.2问题一的模型准备4.2.1邻接矩阵的建立邻接矩阵是用来判定图中任意两点之间联通信息的0-1矩阵。邻接矩阵表示法是将图以邻接矩阵（adjacencymatrix）的形式存储在计算机中。图的邻接矩阵是如下定义的：是一个的0—1矩阵，其中：也就是说，如果两个点之间有一条弧，则邻接矩阵中对应的值为1，否则为0。本文为了便于描述，邻接矩阵中对应的值为两点之间的距离，如果某两点之间没有路，则认为这两点之间的距离为无穷大。通过计算，得到下列50*50邻接矩阵。（计算结果见表一，程序见附录五）表一送货网点两两之间的联通信息送货网点12345……10Inf1916.28InfInf……2Inf02292.641252.94Inf……31916.28Inf03536.41Inf……4Inf2292.643536.410Inf……5Inf1252.94InfInf0……………………………………04.2.2Floyd算法计算任意两点间的最短距离假定图G中权的最短距离矩阵为，且32 用来存放各边的长度，其中：，；，之间没有路，在程序中用各条边都不可能达到的充分大的数代替；，是之间边的长度，；对于无向图，是对称矩阵。Floyd算法的基本思想是：递推产生一个矩阵序列，其中表示从顶点到顶点的路径上所经过的顶点序号不大于的最短路径长度。计算时用迭代公式：是迭代次数，。当时，即为各顶点之间的最短通路值。由给定数据计算出任意两点之间的最短距离，生成51*51阶矩阵，见表二。（计算程序见附录五）表二网络图中任意两点之间的最短距离单位：米（m）送货网点12345……105295.4925093.6757493.0083620.852……25295.49208455.64411063.328916.344……35093.6758455.64402607.6812195.723……47493.00811063.322607.68103872.156……53620.8528916.3442195.7233872.1560……………………………………04.3问题一的模型建立和求解4.3.1模型建立首先对22个点进行编号，将起始点O编号为1，其他21个点依次编号为，最后对O进行第二次编号，为了便于程序实现，我们把23作为O点第二次编号的序数。于是，建立下列目标函数来求送货最短路径和最短距离。其中，，为任意两点之间的距离。32 4.3.2算法实现4.3.2.1遗传算法遗传算法是一种基于自然选择原理和自然遗传机制的搜索算法，它是模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化，其实质是通过群体搜索技术，根据适者生存的原则逐代进化，最终得到最优解或准最优解。它必须做以下操作：初始群体的产生、求任一个体的适应度、根据适者生存的原则选择优良个体、被选出的优良个体两两配对，通过随机交叉其染色体的基因并随机变异某些染色体的基因后生成下一代群体，按此方法使群体逐代进化，直到满足进化终止条件。表三列出了生物遗传概念在遗传算法中的对应关系。表三生物遗传概念在遗传算法中的对应关系生物遗传概念遗传算法中的作用适者生存算法停止时，最优目标值以最大概率被保留个体解染色体解的编码基因解中每一分量的特征适应性适应度函数值种群根据适应度函数值选取的一组解交配通过交配原则产生一组新解的过程变异编码的某一分量发生变化的过程4.3.2.2遗传算法的实现方法（1）根据具体问题确定可行解域，确定一种编码方式，能用数值串或字符串表示可行解域的每一解。（2）确定适应度函数，适应度函数用来度量解的好坏，且适应度函数应为非负函数。（3）确定进化参数的种群规模，交叉概率，变异概率和进化终止条件。4.3.1.3模拟退火算法32 模拟退火算法得益于材料的统计力学的研究成果。统计力学表面材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。假定要解决的问题是一个寻找最小值的优化问题。将物理学中模拟退火的思想用于优化问题就可以得到模拟退火寻优方法。考虑这样一个组合优化问题：优化函数为，其中，它表示优化问题的一个可行解，表示函数的定义域。表示的一个邻域集合。首先给定一个初始温度和该优化问题的一个初始解，并由生成下一解，是否接受作为一个新解依赖于下面的概率：换句话说，如果生成的解的函数值比前一个解的函数值更小，则接受作为一个新解。否则以概率接受作为一个新解。对于某一个温度和该优化问题的一个解，可以生成，接受作为下一个新解的概率为：在温度下，经过多次转移后，降低温度，得到。在下重复上述过程。因此整个优化过程就是不断寻找新解和缓慢降温的交替过程。最终的解是对该问题寻优的结果。在每个下，所得到的一个新状态完全依赖于前一个状态的，可以和前面的状态无关，因此这是一个马尔可夫过程。使用马尔可夫过程对上述模拟退火的步骤进行分析，结果表明：从任何一个状态生成的的概率，在中是均匀分布的，且新状态被接受的概率满足：32 那么经过有限次转换，在温度下的平衡态的分布由下式给出：当温度将为0时，的分布为：且：。这说明如果降温下降十分缓慢，而在每个温度都有足够多次的状态转移，使之在每一个温度下达到热平衡，则全局最优解将以概率1被找到。因此模拟退火算法可以找到全局最优解。4.3.3模型求解4.3.3.1遗传算法求解过程（1）编码策略采用十进制编码，用随机数列作为染色体，其中，，，；每一个随机序列都和种群中的一个个体相对应。其中编码位置代表送货点，位置的随机数表示送货点在巡回中的顺序。（2）初始种群本文我们先利用经典的近似算法—改良圈算法求得一个较好的初始种群。即对于初始圈，，，交换和之间的顺序，此时的新路径为：记，若，则以新的路线修改就的路线，直到不能修改为止。（3）建立目标函数目标函数为所有目标的路径长度，本文中目标函数还是适应度函数。32 （4）交叉操作本文的交叉操作采用单点交叉。设计如下，对于选定的两个父代个体，，随机地选取第个基因处作为交叉点，则经过交叉运算后得到的子编码为和，的基因有的前个基因和的后个基因构成，的基因有的前个基因和的后个基因构成。交叉操作的方式有很多，在选取交叉基因点时，应尽可能选取好的交叉方式，保证子代能继承父代的优良特征。（5）变异操作变异也是一种实现种群多样性的一种手段，同时也是全局寻优的保证。本文的变异操作具体设计为，按照给定的变异率，对选定变异的个体，随机地取三个整数，使其满足，把，之间的（包括，）的基因段插到后面。（6）选择采用确定性的选择策略，也就是说选择目标函数值最小的个个体进化到下一代，这样可以保证父代的优良特征被保存下来。通过上述操作，运用Matlab程序（见附录六）计算得最佳送货路线为：.结合最短路径矩阵得最终的最短送货路线为：。最短距离为54708m，最佳送货路线见图一（Matlab程序见附录八）。32 图一前30件货物的最佳送货路线4.3.3.2模拟退火算法求解过程（1）确定解空间解空间S可表示成的所用固定起点和终点的循环排列集合，即其中每一个循环排列表示送完21个点的回路，表示在第次侦察点，初始解可以选为。（2）建立目标函数建立下列目标函数来求送货最短路径和最短距离。其中，，为任意两点之间的距离。（3）新解的产生32 2变换法：任选，交换与之间的顺序，此时产生的新路径为：。3变换法：任选序号，和，将与之间的路径插到之后，对应的新路径为（）（4）计算代价函数差对于2变换法，路径差可表示为：（5）接受准则如果，则接受新的路径。否则，以概率接受新的路径，即若大于0到1之间的随机数则接受。（6）降温过程利用选定的降温系数进行降温，即，得到新的温度，这里我们取。（7）结束条件用选定的终止温度，判断退火过程是否结束。若，算法结束，输出当前状态。通过上述操作，运用Matlab程序（见附录七）计算得最佳送货路线为：。结合最短路径矩阵得最终的最短送货路线为：。最短距离为54708m，最佳送货路线见图二（Matlab程序见附录八）。32 图二前30件货物的最佳送货路线图4.3.4结果分析遗传算法和模拟退火算法都是解决组合优化问题的良好方法。通过建立相应的数学模型，我们分别用上述两种方法对问题一进行了解答，两种方法计算出来的送货路线最短距离均为54708m，且送货路线除方向外其他方面完全一致，这说明得到的结果具有较高的可信度。同时，为了避免得到的结果不是最优解或者于最优解的偏差较大，我们进行了多次计算，多次计算得到的结果一模一样，这说明该解的稳定性很高，同时，也说明建立的数学模型和采用的算法具有较高的科学性和适用性。五、问题二的解决方案5.1问题二的分析32 问题二在问题一的基础上增加了时间约束，所以我们只要对模型一加以改进，补充必要的约束条件便可达到解决问题二的目的。附录三中给定的资料显示，送货员从早上8:00出发，分别需要在9:00、9：30、10：15、12:00之前将货物送到各指定点。按照排队论中先到先服务的原则，首先完成送达时间早的货物的送货任务，根据不同送达时间将30件货物分为四类，并将每一类货物的送达地点放到一个集合，这样便得到四个时间点下的不同送达地点组成的集合（见表四），然后分别完成每一类货物的送货任务，并计算出完成每一类送货任务的最佳送货路线和最短时间。由于将30件货物分了类，在保证每一类货物的送货时间均为最短的同时，可能因为寻求局部最优解导致总的送货时间达不到最优，为了避免这一现象的发生，在设计送货路线时，需要综合考虑相邻两类之间送货路线的联系情况。在这里，我们在寻求上一类货物最短路线的同时，尽量使得该送货路线的终点与下一类货物送货路线的起点之间的距离最短，这样不仅保证了每一类货物的送货路线为最优，同时也保证了总的送货时间即为最短送货时间。表四前30件货物的分类情况货物类别第一类第二类第三类第四类送达时间9：009:3010：1512：00送达地点13、18、2431、34、40、4538、42、43、4926、21、14、17、23、32、39、36、27、165.2问题二的求解5.2.1第一类货物的送货路径题目要求此类货物必须在9：00之前送达指定点，该类货物的送达地点组成的集合为，送货员8:00从O点出发，需选择最短路径在9:00之前将货物送达。根据任意两节点之间的最短距离（见表二）及联通信息(见表一和附录二)，很容易得出此类货物的最佳送货路线为O→18→13→19→24。第一类货物最佳送货路线的最短距离：计算得。第一类货物的最短送货时间：32 ，其中表示送货员的行进时间，表示交接货物所需时间，表示第一类货物送货路径的总路程，表示送货员的速度，表示同一送货地点下具有的货物数。最后计算得，从而送货员按此路径能将货物按时送到。5.2.2第二类货物的送货路径此类货物需要在9:30前送达，该类货物的送达地点组成的集合为:，根据表二及附录二中的数据易得完成此类货物的最佳送货路线为：24→31→34→40→45，总路程：总耗时：，故送货员按此路径能将货物按时送到。5.2.3第三类货物的送货路径此类货物需要在10:15前送达，该类货物的送达地点组成的集合为:，根据表二及附录二中的数据易得完成此类货物的最佳送货路线为：45→42→49→42→43→38，总路程：总耗时：，故送货员按此路径能将货物按时送到。5.2.4第四类货物的送货路径此类货物需要在12:00前送达，该类货物的送达地点组成的集合为:，根据表二及附录二提供的数据，运用遗传算法和模拟退火算法求得最优路径为：38→36→27→39→27→31→26→21→17→14→16→23→32，总路程：=22132m。总耗时：32 ，故送货员按此路径能将货物按时送到。通过上述计算可得，总的最佳送货路线为：O→18→13→19→24→31→34→40→45→42→49→42→43→38→36→27→39→27→31→26→21→17→14→16→23→32。总路程，送耗时。六、问题三的解决方案6.1问题三的分析分析问题三可知，与问题一相比，问题三中增加了节点的个数，并增加了重量和体积两个约束条件。故从O点出发后不可以直接送完所有货物并返回，需先划分地区并在每个区域内求最优解。为此，我们首先对100件货物的重量和体积进行了计算得出：kg，，由此可得51个点大致可分为A、B、C三个区域。为了合理的划分这三个区域，我们运用最小生成树作为主要的划分方法，并结合重量与体积最终划分出这三个区域。最后分别运用模拟退火算法和遗传算法寻找各区域的最优路线。6.2模型的建立与求解6.2.1最小生成树的建立为了合理地把图中51个点划分成三个区域,首先运用Kruskal算法建立51个点的最小生成树。其算法的实现过程如下：假设给定了一个加权连通图G，G的边集合为E，顶点个数为n。（1）将所有顶点涂成红色；（2）在白色边中，挑选一条权重最小的边，使其与红色边不形成圈，将该白色边涂红；（3）重复（2）直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合。通过运用32 Kruskal算法（程序见附录九），我们得出51个点的最小生成树（见图三）。从图中可以看出，从O点出发有3条干支，因此大致可以根据这3条干支将51个点分A、B、C三个区域。由于还要考虑到每个区域的重量和体积是否超载，因此必须进行适当的调节。在调节时，尽量满足以下三个准则：①尽量在分组后不要出现单独分叉；②点密度大的区域不要被分割；③分割后每组不可超载。根据上述准则，A、B、C三个区域的划分见表五（重量单位为kg，体积单位为）。由表五可知，各区域均未超过重量和体积的上限，故划分是较为合理的。表五各区域划分统计表区域包含的点总重量总体积A1723161491076183425151211131849．080．9596B2132353843424950474536273948．940．9652C26344037414448463328302022292519243149．980．8752图三51点最小生成树图6.2.2算法的实现及结果分析仿照第一问的方式分别运用模拟退火算法和遗传算法对各区域进行线路优化，得到的结果为：32 （1）模拟退火算法得出最优路线为：（程序见附录十）总路程：S=133509m，时间T=633min（2）遗传算法得出最优路线为：（程序见附录十一）总路程：S=133509m，时间T=633min由上述结果可知，两种算法所得最优路线几乎完全一致，只有A区所走路径方向不一致，由此可得三个区域的划分及最优路线的求解是合理和准备。其三个区域的行进路径见图四（Matlab程序见附录十二）。32 图四100件物品最优送货路线图32 七、总结本文在计算时采用的方法主要是遗传算法和模拟退火算法，这两种算法都是全局寻优的良好算法，但由于要综合考虑算法的空间复杂度和时间复杂度，对于大规模问题，在尽量降低算法所需要的时间后很难求得最优解，通常得到的解均为近似最优解。另外，对于第二问，我们把前30件货物按送达时间分成了四类，这在很大程度上降低了建模和计算的难度，但是往往不能保证所求的结果为最优解。这些都可能造成计算误差，但是为了在求解精度和算法所需时间两方面寻找平衡点，遗传算法和模拟退火算法对于解决此类优化问题显示出了较高的优越性和适用性。在实际生活中，经常会遇到本文提出的问题，如：背包问题、货郎担问题、问题、邮递员问题、哈密尔顿回路问题等等，这些问题都是典型的TSP问题。本文结合图论的知识，运用遗传算法和模拟退火算法对送货线路问题进行了分析和计算，并设计了不同情况下的最优送货路线。文中提到的思想及选取的方法均可以用来解决其他TSP问题，这使得解决本文问题的模型和算法以推广到实际生活中，解决许多普遍的问题，提高了模型的适用性。32 参考文献【1】钱颂迪，运筹学。清华大学出版社，2004【2】刘卫国，MATLAB程序设计教程。中国水利水电出版社，2009【3】岳扬，邮路规划问题与研究。江西南昌32 附录附录一：快递公司送货地点示意图O点为快递公司地点，O点坐标(11000,8250)，单位：（米）附录二：各点联通信息序号位置点1位置点21132183220424538634742851595210611171812711381214914159101610181710718111219121332 20122521121522131823131924131125141826141627141728142129152230152531162332172333183134192435202236212637213638211739223040231741243142254143251944252945273146283347292248302849304150312651313452323553322354334655332856344057353858364559362760374061383662392763403464404565414466413767414668424332 69424970433871444872445073455074454275464876474077484478495079494280504081O1882O2183O26附录三：各货物号信息表货物号送达地点重量(公斤)体积(立方米)不超过时间1132.500.03169：002180.500.03549：003311.180.02409：304261.560.035012：005212.150.030512：006141.720.010012：007171.380.010912：008231.400.042612：009320.700.048112：0010381.330.021910：1511451.100.02879：3012430.950.022810：1513392.560.059512：0014452.280.03019：3015422.850.019010：1516431.700.078210：1517320.250.041212：0018361.790.018412：0019272.450.044512：0020242.930.04209：0021310.800.01089：3022272.250.001812：0023261.570.021012：0024342.800.01039：3025401.140.01559：3026450.680.03829：3027491.350.014410：1528320.520.002012：0029232.910.048712：0030161.200.042912：003111.260.025032 3221.150.05013331.630.04833441.230.00063551.410.03873660.540.00673770.700.01293880.760.03463992.140.008740101.070.012441111.370.051042122.390.042843130.990.004844141.660.049145150.450.020946162.040.009847171.950.032448182.120.055449193.870.026250202.010.032451211.380.041952220.390.000153231.660.050254241.240.053455252.410.001256261.260.005957270.420.022458281.720.058059291.340.037260300.060.040261310.600.027462322.190.050363331.890.049464341.810.032565351.000.005566361.240.017767372.510.036168382.040.011069391.070.044070400.490.032971410.510.009472421.380.045573431.310.012174441.260.000575450.980.041376461.350.024177472.120.023078480.540.054279491.010.056680501.120.028432 81250.790.001182462.120.049283322.770.003484232.290.005485200.210.049086251.290.008887191.120.024988410.900.003889462.380.043490371.420.002091321.010.030092332.510.013393361.170.002094381.820.030895170.330.034596110.300.017297154.430.053698120.240.005699101.380.017510071.980.0493附录四：50个位置点的坐标位置点X坐标(米)Y坐标(米)位置点X坐标(米)Y坐标(米)191855002610860963521445560271038510500372705702856597654373567029258098655262099530156599556100801435319395101007100252280321483510365871602525331250109009138452680347280110651011935305035153051137511785035453612390114151265854185376410115101376305200381391511610141340553253995101205015212559754083451230016153657045414930136501714165738542132651414518882580754314180142151958558165443030150602078083554510915142352112770856046233014500222200883547773514550231476590554888514880247790933049115751516025443595255080101532532 附录五：求解邻接矩阵及最短距离矩阵的MATLAB程序function[D,D1]=JULI(zuobiao,lianjie)%D任意两点的最矩路径%D1表示第一问30件货物所要到达的指定地点之间的任意两点之间的最短距离[a,b]=size(zuobiao)%计算任意相邻的两点间的距离fori=1:aforj=1:ajuli(i,j)=sqrt((zuobiao(i,1)-zuobiao(j,1))^2+(zuobiao(i,2)-zuobiao(j,2))^2);endend%计算在lianjie情况下,所应该知道的可到达的距离[c,d]=size(lianjie);e=zeros(a);fori=1:ce(lianjie(i,1),lianjie(i,2))=1;e(lianjie(i,2),lianjie(i,1))=1;end[f,g]=find(e~=1);h=length(f);fori=1:hj=i;juli(f(i),g(j))=inf;end[p,o]=size(juli);fori=1:pjuli(i,i)=0;end%运有floyd算法计算任意两点间的最短离a=juli;n=size(a,1);D=a;path=zeros(n,n);fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;endendendfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)rand(1)S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:23)];Sum=Sum+df;endT=T*at;ifT0flag=0;form=1:L-3forn=m+2:L-1ifd(c1(m),c1(n))+d(c1(m+1),c1(n+1))rand(1)S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:20)];Sum=Sum+df;endT=T*at;ifT0flag=0;form=1:L-332 forn=m+2:L-1ifd(c1(m),c1(n))+d(c1(m+1),c1(n+1))