毕业论文最短路优化问题

最佳答案检举 模型一：利用“图”的知识，将送货点抽象为“图”中是顶点，由于街道和坐标轴平行，即任意两顶点之间都有路。在此模型中，将两点之间的路线权值赋为这两点横纵坐标之和。如A（x1，y1），B（x2，y2）两点，则权值为Q=|x2-x1|+|y2-y1|。并利用计算机程序对以上结果进行了校核。经典的Dijkstra算法和 Floyd算法思路清楚、 方法简便,但随着配送点数的增加,计算的复杂性以配送点数的平方增加,并具有一定的主观性. 所以本研究在利用动态规划法的基础上引入扑食搜索法的原理,提高辆车的装载率,从而减少车辆的需求,达到降低成本的目的.模型二：根据题意（B题），建立动态规划的数学模型。然后用动态规划的知识求得最优化结果。根据所建立的两个数学模型，对满足设计要求的送货策略和费用最省策略进行了模拟，在有标尺的坐标系中得到了能够反映运送最佳路线的模拟图。最后，对设计规范的合理性进行了充分和必要的论证。快递公司送货策略1 问题的提出在快递公司送货策略中，确定业务员人数和各自的行走路线是本题的关键。这个问题可以描述为:一中心仓库(或配送调度中心) 拥有最大负重为25kg的业务员m人, 负责对30个客户进行货物分送工作, 客户i 的货物需求为以知 , 求满足需求的路程最短的人员行驶路径,且使用尽量少的人数,并满足以下条件:1) 每条配送路径上各个客户的需求量之和不超过个人最大负重。2) 每个客户的需求必须满足, 且只能由一个人送货.3）每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h。4）为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为千克。处于实际情况的考虑, 本研究中对人的最大行程不加限制.本论文试图从最优化的角度，建立起满足设计要求的送货的数学模型，借助于计算机的高速运算与逻辑判断能力，求出满足题意（B题）要求的结果。2 问题的分析2. 1根据题意（B题）的要求，每个人的工作时间不超过6小时，且必须从早上9点钟开始派送，到当天17点之前（即在8小时之内）派送完毕。表一列出了题中任意两配送点间的距离。表一：任意两点间的距离矩阵因为距离是对称的，即从送货点i到送货点j的距离等于从j到i的距离。记作：di,j.表二给出了产品的需求，为了完成配送任务，每个人在工作时间范围内，可以承担两条甚至更多的配送线路。表中给出了送货点编号，快件量T，以及送货点的直角坐标。表二对于上述的路线确定和费用优化问题，应用如下启发从公司总部配出一个人，到任意未配送的送货点，然后将这个人配到最近的未服务的送货点范围之内的邻居，并使送货时间小于6小时，各送货点总重量不超过25kg。继续上述指派，直到各点总重量超过25kg，或者送货时间大于6小时。最后业务员返回总部，记录得到的可行行程（即路线）。对另一个业务员重复上述安排，直到没有未服务的送货点。对得到的可行的行程安排解中的每一条路径，求解一个旅行商问题，决定访问指派给每一条行程的业务员的顺序，最小化运输总距离。得到可行解的行程安排解后退出。上面的方法通过以下两种方法实现：（1） 每一个行程的第一个送货点是距离总部最近的未服务的送货点。用这种方法，即可得到一组运行路线，总的运行公里数，以及总费用。（2） 每一个行程的第一个送货点是距离总部最远的未服务的送货点。然后以该点为基准，选择距它最近的点，加上约束条件，也可得到一组数据。 然后比较两组结果，通过函数拟合即可得到最优化结果。3 模型假设 （1）假设每个人的送货路线一旦确定，再不更改。 （2）送货期间，每个人相互之间互不影响。 （3）如果到某一个点距离最近的点不至一个，就按下面的方法进行确定：考虑该点需求的快件量，将其从大到小依次排列，快件量需求大者优先，但路线中各点总重量加上该点的快件量超过25kg的上限时，该点舍去。如距离4最近的点有2，5，6，7四个点，其中，0-1-3-4路线易确定，且各点重量之和为 ，因此对于2，7两点，直接舍去，选5最合适。4 符号说明 A：所有配送点的集合，A=，其中0代表配送中心m: 业务员人数 C：任意一点到原点（总部）的距离 C总：表示一条路线所运行的总公里数 i,j: 表示送货点，如i点，j点 K：表示K条路线 qi: 点i的需求量，q0=0，表示总部的需求量 B总K: K条路线的总运行费用 X：校核时的适应度 Xij: 业务员路线安排5 模型的建立及求解 TSP模型的数学描述为：其顶点集合为A顶点间的距离为C= m nmin ∑ ∑ CijXij i=1j=1满足 n∑ Xij=1,ⅰi=1,2,⋯nj=1 m∑ Xij=1,j=1,2,⋯nj=1Xij∈, i=1,2⋯n,j=1,2⋯n，而根据题意，任意两点之间都有通路，即不存在Xij=0的情况。 根据上述所列的启发式方法生成一个行程安排解。每一个行程的第一个送货点是距离总部最近的未服务的送货点。 第一条行程中访问了节点0-1-3-4-5-0，是因为1距离原点最近，因此由1出发，3是距离1点最近的点，而且两处快件量之和为14kg，小于每个人最大负重量，可以继续指配。接着，4是距离3最近的点，而且三处快件量之和为 ，仍小于25kg,还可以继续指配。在剩下未服务送货点中，5距离4最近（其实距离4最近的点有2，5，6，7四个点，然后考虑该点需求的快件量，将其从大到小依次排列，快件量需求大者优先，但超过25kg上限的点舍去。这里2，7被舍去，故选择了5）总快件量之和为24kg。再继续扩充，发现就会超出“25kg”这个上限，因此选择返回，所以0-1-3-4-5就为第一条路线所含有的送货点。 现在0-1-3-4-5这四个送货点之间的最优访问路径安排就是一个典型的单回路问题。可以通过单回路运输模型-TSP模型求解。一般而言，比较简单的启发式算法求解TSP模型求解有最邻近法和最近插入法两种。由RosenkrantzStearns等人在1977年提出的最近插入法，能够比最近邻点法，取得更满意的解。由于0-1-3-0 已经先构成了一个子回路，现在要将节点4 插入，但是客户4有三个位置可以插入，现在分析将客户4插入到哪里比较合适:1.插入到（0，1）间，C总= 7+4+5+1+4+9=30。2.插入到（1，3）间，C总=5+6+4+9=24。3.插入到（3，0）间，C总=5+4+4+11=24。比较上述三种情况的增量，插入到（3，0）间和（1，3）间增量最小，考虑到下一节点插入时路程最小问题，所以应当将4插入到送货点3和总部0之间。接下来，用同样的方法，将5插到4和0之间，能使该条路线总路程最小，该路线总路程为32km，历时。结果子回路为T= .因为街道平行于坐标轴方向，所以它就是最优化路线。第二条行程这中，由于所剩下节点中，2距离0点最近，因此由2出发，就可以找到最近点13，接着是7，然后6.这样，第二条优化路线0-2-13-7-6-0就确定了。用这种方法，依次可确定以下剩余六条路线。具体参看如下图表三（一，二，三，……为路线编号；总重量为该路线所有节点快件量之和）：由启发式方法得到的可行的行程安排解一： 表三直观的具体路线图如下：图一然后，根据所经历的时间进行划分，确定运送人数。在工作时间小于6小时的前提下，可作如下分类：这样，将确定的五种组合情况分别分配给五个业务员去送即可。这个解是第一个中间最好解。在选择可行解1每条行程中的第一个送货点时，选择了距离总部最近的未服务的点。接下去通过选择距离仓库最远的未服务的点为每条行程的第一个客户生成了可行解2。为了方便遗传算法的分析，编号将连续进行。如果继续增加的新的标签的行程和前面可行解1 中的重复，就是用原先的标签号。由启发式方法得到的可行的行程安排解二：表四直观的具体路线图如下：图二注意：通过上述方法，最后剩两个点1，9还没有被列入路线。于是问题就出来了，如何将这两个点插入进这八条路线？除第十条路线之外，其余各条均能将9号点纳入，而1号点没有办法纳进去，只能作为第十七条路线出现。那么，9号点应纳入哪一条呢？显然，纳入第十六条比较合适，原因是他对总路程的大小没影响，顺便可以带上。由此可以看到，可行解2没有替代中间最优解，以总路程518km,历时高于492km和。通过对上面的两个可行解进行交叉操作。其中每个解的行程已经按照他们送每千克快件量在每一千米的路程范围内的送货成本的大小降序重新排列，这个参数是对每一行程质量的比较好的测度。本文以此作为适应值（X）。在对两个解中的行程进行交叉分析时，根据适应值计算的接受每条行程的概率附加到每条行程上。P(X)=Ke- λx ，然后通过设定参数对结果进行拟合。具体而言。如果一条行程的选择概率P(select)值至少和exel相应行的随机概率一样大，那么他就被选择出来可能在交叉分析中被包括进去。在本题中，根据上述要求，求出了两种可行解，但是由于本题的特殊性（即街道和坐标轴平行），两条路径中没有相同的运行路线，也就是说最终的拟合结果就是解一的结果。因此，可行解一就是本题中的最优解。至此，B题中的第一问已经解决了。即需要5个业务员，每个业务员的运行线路如下：第一个人：0-1-3-4-5-0和0-18-26-28-0；第二个人：0-2-13-7-6-0和0-19-25-24-0；第三个人：0-10-12-8-9-0和0-16-17-20-14-0；第四个人：0-22-32-23-15-11-0；第五个人：0-27-29-30-0.总的运行公里数为：C总K=32+42+42+72+68+56+88+92=492km。5．2 下面我们求解B题中的第二个问题：根据上面设计的最优化路线，容易算出每条路线运行费用及运行第二时间（这里的第二时间指的是在问题2中的新速度的前提下算出的）。具体参看下表五和表六：表五表六从表五和表六的比较来看，解法二以总费用元和总时间高于解一的元和。因此我们选择了解一的优化结果。从上表（表五）很容易看出：B总K=元。然后根据第二时间的大小，我对运行路线和人员个数做以下调整，具体参看表五。这样，就需六个人就才能完成任务。考虑到人员工作时间不能一边倒（即部分线路组合工作时间太长，部分太短）的情况，每个人的组合路线如下：第一个人：0-1-3-4-5-0和0-19-25-24-0；第二个人：0-2-13-7-6-0和0-10-12-8-9-0；第三个人：0-16-17-20-14-0；第四个人：0-22-32-23-15-11-0；第五个人：0-18-26-28-0；第六个人：0-27-29-30-0。

对于某个具体的问题，提出合适的特定的最优化计算方法。或者对于某一类最优化计算方法，提出改进或进一步挖掘理论。举个例子，随着科学技术的不断发展，最优化问题的规模越来越大，使得传统方法无法有效计算，因此近年来子空间方法成为热点。袁亚湘院士近年来关注于子空间信赖域方法的算法与理论研究，发表了一系列相关论文和技术报告，您可以参考一下。

// : 定义控制台应用程序的入口点。//#include ""#define N 12#include using namespace std;const static int soure[N][N] ={ /*这填邻接矩阵*/};int min(int arr[N],bool bj[]){ int tmp = 999; int temp = 0; for(int i=0; i>i>>j; cout<<"最短路径长度为："<