最佳旅行路线设计(值得细读)-图论

最正确旅行线路设计摘要：新疆地域广阔，旅游资源繁多，本文以节约费用或时间为目标，分别为自助游、考察等具体情况安排了旅游线路，并为“五一旅游黄金周”设计线路，缓解景区客流顶峰及提高接待质量。我们采集了全疆共33个景点景区的数据，其中不乏有十分接近的，故我们按地理位置将它们进行聚类，最终得到20大景区。接着，建立在交通费用与路线长度成正比、不同景点的住宿费用相等、车辆行驶于公路铁路的时速恒定等假设条件下，我们先用Floyd算法求出了景区两两间的最短路径，接着用蚁群算法估计了遍历所有景区所花费的时间总和，为下文设计合理的线路做准备。对第一问，通过简单计算我们发现，单位时间内游览景区的花费要小于往返景区途中的花费，亦即：花最少的钱与游尽可能多的地方这两个目标在此题中是统一的。为此，我们提出了一个以确定一条游览尽可能多景区的旅游线路为目标、游览总时间为约束的0-1整数规划模型，利用LINGO软件估计了解的下限，用遗传算法求得了最优解：两人一个月时间花费约6100元游览17个景区。对第二问，根据蚁群算法的结果可知，只要适当安排我们便可以在2个月内完成对新疆所有景区的游览。为此我们从两种思考的角度，建立了不同的模型来求解交通费用的最省问题。首先我们以两次旅游的路程长度之和为适应度函数用遗传算法求出了包含所有景区的两条路径，并使它们的路径长之和最短。接着，我们利用景点分布图固有的特点，从简化图的角度将20个点的连通图化为一个只包含6个顶点的图，并用枚举法将可能的5种结果逐一计算，求得最正确线路。在处理考察任务问题时，由于考察景区所花费的时间远大于在景区间往返的时间，所以我们首先忽略路程上的花费，将如何安排三个考察组抽象成一个线性规划问题，以最小化三个考察小组的最长耗时为目标并用LINGO软件求解，得到一些目标函数值相同但考察景区不同的最优解，在此根底上，我们将路程耗时纳入考虑之列，再一次使用遗传算法，目的是求得更精确的解。对第四问，即设计“五一黄金周”旅游线路问题，我们以错开游客顶峰、景区利用率尽量高、同一线路的景区跨越尽可能小、线路多且丰富等条件作为安排线路的目标来设计算法，在给出14条黄金游线路的同时，又对问题加以进一步完善，即利用剩余资源开辟了一些5-6天的短途游线路，以充分利用旅游资源并满足不同游客的不同要求。在模型与软件的展望局部，我们阐述了规划模型、蚁群模型与遗传算法模型等的特点及其他应用领域，也将文章中运用的四种软件：马克威分析系统、LINGO、Excel以及MATLAB软件的特点和扩展做了逐一的介绍。本文的优点是充分将规划与遗传算法相结合，突出规划模型意义的同时也发挥了遗传算法高效的特点。同时，较好的数据预处理与蚁群算法的环游估计都为解决问题做了铺垫。另外，设计黄金周旅游线路时，我们不仅考虑了丰富多彩10日以上旅游线路，也辅之以一些中短规模的旅游路线，为游客提供了更多的选择余地。值得一提的是，本文还综合运用了四种软件。关键字：聚类、最短路、蚁群算法、遗传算法、线性规划、枚举法、马克威分析系统、LINGO、Excel、MATLAB。一、问题的重述：随着近年来旅游业的不断开展，我国新疆的天池、达坂城、吐鲁番、楼兰古城、伊犁等等的异域风情，越来越吸引着广阔的游客。在本文中，我们要完成以下几个关于旅游路线设计的问题：1．在科学估算旅游费用的根底上，以总本钱尽量小为目标，设计一条在一个月〔计30天〕的时间里，游尽可能多的地方的旅游路线。〔吃饭费用不计〕2．以在各景点间的交通费用尽量小为目标，设计两条互不重叠的旅游路线，路线各为期一个月，且其合集包含新疆所有景点。3．设计三条互不重叠的旅游考察路线，在每个景点考察的时间是旅游观光时间的四倍，用于交通的时间那么不变，要求三条考察路线各自所用时间的最大值尽可能小。4．设计假设干条为期十二天的黄金周旅游路线，以分散游客，提高景点的接待质量，设参加这些旅游路线的游客人数与整条路线的接待能力成比例。5.〔对题目的进一步完善〕对于上面第4个问题，考虑到新疆旅游实际问题的复杂性，除了设计一些为期12天的旅游路线外，还可以适当的设计一些短期的旅游线路，这样既可以方便游客、给他们提供了更多的选择，又可以充分利用各景区的旅游资源，防止其闲置。二、问题的分析在收集新疆各个主要旅游景点之间的路程、各个景点的最正确逗留时间等信息的根底上，我们将问题做以如下的分析和抽象：因为新疆的旅游景点众多，所处的地理位置也不相同，从旅游路线设计的实际出发，显然要考虑到哪些景点相距较近，可以同时游览，因而，我们需要将新疆境内的所有主要的旅游景点按照经纬度及是否可以直接连通予以分组。所以本文中我们首先采用聚类分析的方法，运用马克威软件将各景点归为假设干景区，以便于下一步的分析。另外，由于路程、时间、价格三者因素之间关系错综复杂，我们希望能得到一个统一的标准，所以，我们把路程都化为时间和价格，并寻找后两者的关系，使问题简化。对于第一小题，这一“最值”是某一固定时间内的最小费用，景区数那么不要求遍历而只是越多越好。为此可以建立一个考虑逗留时间和路途时间的规划问题，目标是希望遍历的景点尽量多，而约束那么是限定一个月的时间。而第二小题与第三小题可以说是第一小题中同时考虑逗留时间与路途时间的引申。在第二小题中由于有要求两个暑假游览所有的景点，那么景点上的花费一定，我们只需要考虑使路途时间最少〔即交通费用最小〕，这样也使得总费用最小。而第三小题，由于逗留时间远远大于路途时间，我们简化时可以只考虑逗留时间。当然，为了进一步求解更精确的解，在只考虑逗留时间的简化模型之后，我们还应将路途时间参加。第四小题的处理方法那么有些不同，因为增加了一些新的约束类型，考虑到景区所能够承受的游客流量，同一时刻不能有过多的游客游览同一景点，我们所要做的就是尽量错开游客的旅行线路，使每一时刻，各景点都接待其承受能力之内的游客，并尽可能丰富地设计旅游线路。总之，对于旅游线路的规划问题，我们在一定程度上都可以将其抽象成一个求最短“路”的问题，只不过这里的路常常不单指路程，而还包括时间，费用等等方面。不同的问题，可以通过添加不同的约束条件予以描述。将实际问题抽象成一个规划模型的方法在某种程度上是很相似的，但是，对于抽象出的这些规划问题，具体的求解方法，那么是多种多样的。三、根本假设1、为了尽量节约费用，由于飞机的价格要远高于铁路和公路，而后两者根本相同。所以在新疆境内的交通费用，以铁路票价为主，没有开通铁路的线路，那么以公路票价为主；2、对于公路的收费没有明确标价的路段，以两个旅游点之间的公路里程〔km〕除以平均时速〔60km/h〕进行估算。对于少数公路也欠兴旺的地区，那么以速度折半为30km/h估算；3、假设在新疆的所有景点中，对任何的A、B两个景点，从A到B所需花在路上的时间与从B到A的相同，即忽略例如由于列车停靠站不同所造成的运行时间上的一些差异；4、暑假的一个月为31天，考虑到往返新疆的时间，故花费在新疆境内的旅游时间以30天计；5、在新疆境内各旅游景区的住宿费用均为一个定值：RMB150/标准间〔两人〕/天；6、设旅游途中的休息调整时间合并在每个景点的观光逗留时间之内，不再予以单独的计算；7、不考虑交通费用在白天和夜晚的区别，〔如火车硬座与卧铺价格上的差异等〕均以最低价格即硬座票价计算。8、对于旅行社推出的旅游线路的设计，与自助游不同，我们认为其主要目标不在于节省费用而在于多游览美景和旅途的舒适，因此假设在新疆省内白天的时间都用来游玩，景区间的行程那么采用飞机〔时间短故可忽略〕连接或在晚间乘车抵达。9、假设铁路和公路交通费用的票价，与行驶的里程近似成线性关系，而又因为列车或汽车时速也是一定的，这样，某一段路程需要的交通费用也与其时间呈近似的线性关系，这样，求最小费用，也即求最短路线。注：假设9的依据：我们对局部景点间往返的时间和费用进行采样，并作回归分析如下页图所示：〔R平方为0.9819，F值为595.6604，说明两者呈很强的线性关系。几乎可以认为交通费用与路程成正比。〕〔图1：价格—距离采样关系图〕数据预处理及问题的初步探究1、数据采集及由景点向景区的聚类[新疆境内的33个旅游景点名称及其相应的观光逗留时间，经、纬度等数据，见附录1]我们先用聚类分析方法将上述33个旅游景点予以分组。所谓聚类分析，就是把一个给定的数据对象集合分成假设干个不同的数据对象的集合，这里，我们将它作为接下来的蚁群算法的一个数据预处理步骤。因为聚类是一种无监督分类法，并没有预先指定的类别，因此，采用聚类分析，我们可以更加客观地了解各个景点的分布状况，并对新疆的这些旅游景点进行分组和归类。以上述1至33的景点为分类单元，根据它们的经纬度，运用马克威软件进行聚类[1]，可得到一分组结果如下列图：〔图2：聚类结果图〕除了乌鲁木齐、阿图什、喀什等大城市不受分类限制，将以独立身份计入旅游景区外，其余的旅游景点按照上图中分割线左侧的聚类方案，可以组合成20个景区。例如，序号分别为27、29、30、31的苏丹·沙图克麻扎、喀什、香妃墓、艾提尕清真寺这4处景点，按照上图中的聚类可以归在一处用喀什景区来代表，等等。这样，我们就可以将33个景点归结为20个景区，合并后各景区的观光时间等详细信息可列表如下：景区景区逗留时间1阿勒泰2.52塔城13克拉玛依0.54博乐45石河子16昌吉17乌鲁木齐1.58天山19伊犁1.510天鹅湖0.511吐鲁番1.512哈密213库车大寺114库尔勒115阿克苏116楼兰517阿图什0.7518喀什2.2519尼雅遗址320和田1〔表1：20个景区逗留时间一览〕这20个景区的地理位置分布和相互间的道路连通情况可以如下列图所示，其中各个标明序号的结点上方的墨绿色数字表示在该景区的逗留时间。〔图3：景点分布及逗留时间图〕2、用蚁群算法初步求得的遍历时间尽管上述所示的景区道路图是连通图，但并不是任意两个景区间都存在直接连通的。因为需要计算的是在景区内的逗留时间和路上的消耗时间，所以，我们希望得到任意两个景区间的最短通路，这样，当需要跨越某一景区而到达相对较远的另一景区时，可以有直接的通路，这将使问题更直观和简便。因此，我们运用Floyd算法，首先要做的是将这20个景区之间两两的最短时间计算出来，得到一个20*20的时间矩阵如下所示。根据我们前面的假设3，这是一个对称矩阵，矩阵元素的单位为小时。[矩阵见附录2]根据上述的景区间最短时间矩阵，运用带精英蚂蚁的蚁群算法[2]编制程序，我们可以求得要遍历所有的景区，需要在路上花费的最小时间。以此，再结合各个景区的观光逗留时间，那么可以得到遍历所有景区的总时间，根据它我们可以估算假设要游览新疆的全部各个旅游景点，需要花费的时间是多少，为此题后面的处理做一估计。蚁群算法的运行图示如下：最终可得到如下的结果：通过2.859000秒的计算，我们得到最少环游时间：292.44小时=12.18天。与其相对应的最短环路是：161411128765312410913151718201916而游览所有聚类后的景区总时间为一定值：33天，所以：总时间=最短环游时间+逗留时间=12.18+33=45.18天这个结果的意义在于，它告诉我们要想在一个月即30天内遍历所有的景区是不可能实现的，并给出了一个十分有参考价值的数据。因此对于第一问，我们要选择适宜的线路，从而可以游览尽量多的景区。而由于总时间小于60天，也即我们是可以在2个月内完成对所有景区的考察，第二问也就自然会有可行解。再注意到，如果逗留时间是33天的4倍，即132天，那么考察时间就将会是环游所需总时间的10倍以上。这就启发我们对于第三问，可以先忽略环游时间计算一个近似最优解，再在此根底上逐步地加以完善。模型的建立与求解模型一：通过比拟各种交通费用，我们可以发现，在新疆境内选择飞机出游的花费要远高于铁路和公路的费用，出于节约费用的目的，并且考虑到许多景点都是远离机场的，飞机的优势也并不明显，为此，我们首先摈弃乘坐飞机。此外，选择铁路的性价比要略高于选择公路，但新疆境内的铁路很有限。所以，假设两景点之间同时存在铁路和公路将它们相连通，那么选择铁路，而假设仅有公路那么只能选择公路。另一方面，通过计算公路交通的费用，结合公路里程、客车行驶时间和可以发现，如果某天24小时都花费在往返假设干城市的路途上，那么两个人的花费要超过330元，但是如果某天是停留在某个景点游玩的话，日均游玩费与住宿费之和大约只有280元，所以从这个角度来考虑问题的话，花最少的钱实际上去游尽可能多的景点是一致的。我们的目标就是防止在途中过多的耽误时间，从而使游玩时间减少。建立在总费用=住宿游览费用+路程开支的根本假设之上，我们建立了如下的线性规划模型：对于聚类后得到的20个景区的问题，我们引入一个的矩阵，其中的元素为0-1变量，当时表示我们制定的路线包含从景区直接到景区，否那么不包含景区直接到，我们希望整个游览线路包含尽量多的城市，也即最大化目标函数：。对于约束条件，约束条件1：由于每个景点最多参观一次，所以，矩阵的每行与每列之和均为0或者1；约束条件2：当而为了保证整条链的连通性，即使出现两条以上不相连通的链，我们要求每行之和与每列之和相等。约束条件3：为了满足总的时间小于一个月，还需要增加时间上约束条件。故，完整的线性规划模型为：(其中是第j个景区的逗留时间)我们用Lingo软件对其进行求解[5]，但是很遗憾，由于较多的变量及复杂的约束，程序无法在短时间内完成。好在隐枚举方法给了我们启示，发现可以找到一条至少包含17个城市的链，所以，根据这一启发，我们下面运用擅长处理NP完全问题的遗传算法来重新求解这一问题。算法的思想是：通过模拟自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代代地不断繁衍进化，最后收敛到一群最适应环境的个体，求得问题的最优解。既然线性规划模型已经告诉我们，至少可以找到一条包含17个景区的链，那么我们只需从N=17开始找一条包含N个景区的最小耗时链，假设对于某一N()，最小耗时链的总长大于720分钟，那么一个月内最多可游览的景区即为N-1。下面，我们对遗传算子进行设计：定义个体：我们以一个1行20列的行向量为一个个体。其中，前N列表示一个月内所遍历的景区的链；后20-N列表示剩下的未遍历的景区。假设干个这样的个体组成一个种群。选择运算：根据适应度的上下进行优胜劣汰的选择。在这里，遍历前N个景区道的路上的花费时间以及停留在这N个景区的逗留时间之和越短，适应度越高。对不同适应度分配一个被进化的概率。适应度越高，被选择进化到下一代的概率也越大。交叉运算：交叉的方法有很多种，在这里我们对两两个体以一定概率pm〔0.6~0.95〕决定是否进行交叉运算，假设进行，那么采取CX方法[4]，假设否，那么保存这两个个体。变异运算：变异的方法也有许多种，在这里，我们分别考察每一个个体，并以一个小概率pc〔0.05~0.15〕决定是否进行变异运算，假设进行，那么采取倒位变异，假设否，那么保存该个体。适应度计算：以游览景区个数多少来评价适应度，游览的景区越多那么适应度越高。模型的结果与分析：屡次调整参数，运行遗传算法程序，我们得到一条遍历17个景区的链：78652131091315171820141112而另三个景区4、19、16那么不访问。遍历这条链的总时间花费为642.5700小时，大约27天。〔图4：遗传算法性能追踪图〕我们再尝试N=18的情况，但是，遗传算法的结果告诉我们，无法找到一条遍历18个景区的链，使总的时间开支小于720小时。所以，两个人在暑假一个月内花最少的钱最多可以游17个景区。费用：交通费用：717景点住宿费用：21*150景点游玩费用：1120*2那么总费用：6107/两人模型二：2.1遗传算法的求解根据第一小题的结果，我们发现，如果以与之前相同的出行方式显然不能在一个月之内遍历所有的20个景区，但是，在引言局部，我们也计算出，遍历所有景区与往返景区路途中的总时间是45.18天，这说明分两个月完成游览是完全可以的。由于两个月之内，我们会遍历所有的景区，所以在景区上的开支是恒定的，所以，如何安排两个月所分别游览的景区，使交通费用最省也即是使总费用最省。受第一小题的启发，我们依然想到运用遗传算法进行求解。选择、交叉、变异函数不变，适应度函数定义为两次游览的总交通费用的倒数，这样，用于交通的费用越少，适应度就越高，个体就越能遗传到下一代。由于景区总数只有20个，所以，我们下面采用一种分类遗传的方法，这样可以使结果更精确也可以使计算效率提高。做法是：将20个城市分为两局部，第一个暑假考察N个景区，第二个暑假考察20-N个景区，N从3开始到17〔如果N小于3的话会导致不满足约束条件，即出现一个暑假游览所花费的时间大于30天〕，同时考虑到乌鲁木齐是省会，很多游览天山、昌吉等景区的旅行线路都是以乌鲁木齐为出发点的，所以为更切合实际，在这里我们也要求第一个暑假从乌鲁木齐出发〔当然，这不是必要条件，我们后面采用的方法即不需要满足此条件〕。对每一个给定的N用一次遗传算法。最后将每个N对应的交通上花费的时间作比拟，我们发现，N从7到13所花费的时间较其他更少一些，故，作的柱状图如下：〔图5：景区数量安排与耗时关系图〕模型的结果与分析：从上图的结果，我们可以看到：当两个月各访问10个景点，并且按照我们列出的顺序访问，路上时间最少，而路途耗时与交通费几乎成正比，从而交通费也最省。我们给出一组最优线路：第一个暑假78654910132第二个暑假12111413151718201916遗传算法的效果和求解能力都能到达我们所期望的，但是对于这一问题固有的特性，我们也可以直接从图的角度来建立模型：2.2从图的角度直观求解两次暑假遍历所有的景区，也即是将原来20个景区的连通图分割成两个子图，并找出两条互不重叠的旅游路线。针对问题的特殊性，我们分如下几步来处理问题：第一步，不断地剪去图中所有度为1的顶点，即编号为：2、8、9、11、12、16、19的点〔11是因为剪去12后它成为了度为1的顶点〕。因为我们参观这类景区的时候，进出必然沿同一条线路，花费在这些路上的时间是不可缩减的。所以，在我们的最节约时间方案中一定会包含这些路径，故寻找最短路径的时候可以暂时将其从图上去除。第二步，我们将度为2的顶点去除，但保存原来的路，即编号为：1、4、6、15、17、18、20的点。原因与第一步类似，因为对于这类顶点，一般来说，游览它们的时候，是从顶点的一条边进入而从另一条边离开，所以，通过这类顶点的路径也是确定的，对我们所需要寻找的最短路径不会产生影响，可以暂时将其从图上去除。执行这两步之后，得到如下结果：〔图6：简化后的景点图〕我们发现，余下的顶点的度数都大于等于3。我们把被去除的顶点“附属于”某一个度数大于等于3的顶点，即如果我们到达某个顶点x，我们就要遍历它的“附属”点。要分割原先的图，并找出不重叠的两条路线就要选择如何分割这些度数大于等于3的顶点。模型的结果与分析：由于数据量较少，我们用枚举的方式得出了五种较为合理的分组方式。分组情况一情况二情况三情况四情况五Group11—101—12、141—81—8、11、12、141—6、9、10Group211—2013、15—209—209101315—207,8,11—20情况一：Group123178654109Group212111413151718201916情况二：Group121391045678141112Group213151718201916情况三：Group123187654Group212111413109151718201916情况四：Group121345678141112Group291013151718201916情况五：Group1213564109Group21211147813151718201916由上面五组游览方案，我们分别计算它们的游览时间以及所需的路费，可以得到如下表的结果：单位〔小时〕情况一情况二情况三情况四情况五Group157.37107.0345.1791.8953.41Group2103.364.15126.5176.95130.75总时间160.7171.18171.68168.84184.16价格〔元〕一二三四五Group1292.3573.4220.1511.8270Group2694.3465.9845.7541.6841.3Sum986.61039.31065.81053.41111.3由上表，我们发现，情况一中所消耗的时间最短，所需的费用相应也最少。因此，我们认为，安排两个月的旅游线路最正确的分配方式由情况一的分组给出，具体的线路图可以表示如下：〔图7：最正确线路安排图〕模型三：3.1简化的模型由于考察分三组进行，故我们可以把整个西藏的景区分为三局部，三个考察小组各考察一个局部，设他们考察所花费的时间分别为，完成整个考察工作是指三个小组都完成各自的考察任务，所以，尽早的完成考察也就是使三个小组完成考察时间的最大值最小，即：。引言中，我们已经通过蚁群算法计算出环游全部景区时，所消耗在路上的时间约12天，现在分三组进行，花费在路上的时间更会小于12天。而现在各景区停留考察花费的时间是原先的4倍，即天，两者相差一个数量级。故，我们先考虑一个简化的模型，即忽略路上所花费的时间。现在，问题就转化为一个简单的规划问题：其中表示三组考察的线路，表示20个景区，那么表示第组是否考察第个景区，假设考察，那么，否那么。而第一个约束条件表示每个景点当且仅当被一个小组考察。目标函数中的表示考察每个景区所花费的时间，表示第组考察队伍所花费的考察时间，三组队伍的最大值表示花费的总时间，我们希望这个值尽可能的小。模型的结果与分析：下面我们用LINGO软件对问题进行求解，最优解中，矩阵的值不唯一，但是目标函数的值是唯一的，都是44，由于总共用于所有景区的考察时间为132天，很容易得出三个考察组在各景区所花费的时间都为44天。这与我们从直观上理解——尽量使三个小组的考察时间平均——是一致的。简化的线性规划模型的好处是不言而喻的，但是也存在着一些缺乏，从解的分布来看，三个考察组遍历景点所花费时间都为44天的情况有许多种，尽管用于往返景区途中的时间远小于逗留在景区内的时间，但是为了区分各组解并求得更精确的解，我们需要将路程上的时间消耗列入考虑的范围之内。对于Lingo计算出的假设干组最优解，我们将路程时间纳入考虑，对于其中最优的一组：第一组2318654第二组910131517182019第三组121114716我们计算得，三组停留在景区与往返于景区路上所花费的总时间的最大值为1138.09小时〔47.42天〕但是，由于最优值对应的分布较多，通过Lingo屡次计算不考虑路程的最优解再将路程消耗参加，从而比拟，这样的做法略显烦琐，也不能保证枚举到所有可能的结果。为此，我们再一次运用遗传算法。3.2遗传算法的求解这一问题遗传算法的选择、交叉、变异运算并没有实质的区别，但是适应度函数方面我们做了比拟大的改良：我们根据三个小组遍历的景区计算他们各自在景区逗留和往返景区间的时间消耗和，并将适应度取为三组完成时间的最大值的倒数，这样，根据优胜劣汰的准那么，耗时最长的一组所消耗的时间越短，那么被遗传到下一代的概率越大。以此逐代进化，最终得到最优解：第一二组1358671112第三组1519201416这样，经过1120.21小时〔合46.6754天〕，三个小组将全部完成考察任务，这比之前所使用枚举法的1138.09小时〔合47.42天〕的结果要好一些，进一步说明了遗传算法处理复杂问题的优势。模型四：根据20个景区各自的最正确逗留时间，我们可以算出在黄金周12天时间内每个景区接待顾客流的数量。显然，游客在某一景区逗留的时间越短，景区可以接待游客的批次就越多。由于各景区的接待能力大相径庭，且同一时间每一景区接待的游客数量是有限的。我们希望安排尽量多的游客在不同的时刻游览不同的景区，错开某一景区的人流顶峰，从而提高旅游质量。因此，我们的目标就是尽可能多地设计10天以上的旅游线路，也就是使任意时刻闲置的景区数量尽量地少，这样整个新疆旅游区可以接待更多的游客。值得一提的是，为了使游客花费在路上的时间尽量地节约，我们设计的线路时也考虑使访问的相临两个景区在可能的情况下尽量地接近。然而即使如此安排，我们依然不能保证每一时候所有景区都处于饱和状态，某些景区必然会有一定的时间出现游客数量稀少的情况。考虑到这一情况，为了充分利用新疆的旅游资源，我们在保证长旅游线路的前提下，对于那些无法再构成一条10天以上旅游线路的景区，尽也可能地安排它们组成了一些短程旅游线路，这样，不仅使游客有了更多的选择空间，也可以使更多的游客浏览祖国西部的奇山异景。为此，以半天为一个时间单位，将12天的时间划分为24个单位。并将每一个景区以划分成假设干区段，使每个区段包含的单位数正好等于一批游客的逗留时间。我们设计了如下的算法：表示在第个城市的逗留时间；表示时间轴的变化，；为一的矩阵，表示任一单位时刻，景区是否已经被安排接待某批游客，假设已经有接待任务，那么，否那么。第一步：置；在时刻1，我们随意选择一个空闲的景区a作为起点，，。第二步：从时刻开始，列举下一时刻段没有安排接待任务的景区，从中选择与上一个城市最近的景区为下一个访问对象，直到或者下一时间段没有可供选择的城市。第三步，记录遍历的景区编号和总共需要花费的时间数。置重新执行前两步，直到无初始景区可供选择。模型的结果与分析：由于这一算法在初始时的选择存在随机性，故每次运行的结果并不完全相同，我们运用上述算法每次都可以得到20条不同的线路，并且在任意时候，不同线路的游客不会参观同一景点。我们将一次结果罗列如下，其中，14条线路是10天以上几乎覆盖整个黄金周的旅游，而另6条那么是中短途旅游线路，也可供特殊要求的游客参考：长线：10.5天神秘天山宗教十日游9-冰山水域王陵十日探险1-18-2-8-10-3-1211天玉邑丝路11日游3-10-13-14-20-17-15-9-11-7尼雅双湖文化之旅19-13-15-17-20-14-3-10-911.5天西域风土民俗游8-6-5-3-10-4-13新疆内陆景观游17-15-13-10-3-5-6-7-9-8-14火焰山千佛洞神奇之旅11-7-6-8-5-3-10-13-15-17-20尼雅博湖佛寺探秘之旅15-17-20-19-14-6-5-3-10-13疆内城市风情环游7-3-6-5-10-9-13-15-17-20-8疆内文化古迹环游5-3-10-15-17-20-18-7-6-2博乐天鹅湖周边城市游4-6-8-5-3-10-14-13-15天山玉邑民俗游13-10-9-15-14-20-17-8-6-11-3边疆宝藏探秘之旅10-3-8-2-7-11-12-20-14-512天远古文明之旅16-14-19-5-6-3〔图8：景点线路参考图〕短线：9天环疆山水丝路九日游20-14-8-2-3-7-15-17-108天西疆边境八日游18-10-9-3-17天疆北风情七日游2-5-3-1-13-106天全疆六日环游6-2-17-11-10-35.5天天山天鹅湖六日游12-10-3-8-24.5天哈密和田库尔勒五日游14-20-12以玉邑丝路11日游为例，我们可以安排具体行程如下：7-11-9-15-17-20-14-13-10-3乌市、吐鲁番、伊犁、阿克苏、阿图什、和田、库乐勒、克孜乐千佛洞、天鹅湖、克拉玛依双飞十一日行程安排：第一天：乌鲁木齐市接机、入住酒店，游览城市风光，逛夜市，宿于乌鲁木齐市。第二天：中午乘车前往吐鲁番，当日宿于吐鲁番。第三天：从吐鲁番去火焰山，游览。晚上去伊犁，宿于伊犁。第四天：游览伊犁景点，体验草原民俗风情。第五天：中午飞往阿克苏。第六天：游览阿克苏，上午去阿图什。第七天：早上赴和田，白天游览。当晚乘飞机去库乐勒。宿于库乐勒。第八天：游览库乐勒，当晚乘飞机去库车。宿于库车。第九天：游览库车大寺和克孜乐千佛洞。宿于当地。第十天：乘车去天鹅湖，游览，黄昏乘车去最近的机场，然后乘飞机去克拉玛依。第十一天：游览克拉玛依。飞机返程。其他均可做类似安排，不再详述。六、模型的评价：模型的优点：1、本文以规划模型为根底，以遗传算法作为求解工具，既取了规划模型的优点，即目标函数与约束条件的意义都十分清晰，而辅之的遗传算法又克服了线性规划由于变量过多而导致的计算效率下降等问题，从而使每一个模型根本上都能得到最优解。2、本文使用的模型和方法较为广泛，前三个问题都建立了两个模型或使用了两种方法，这样既丰富了文章的内容，也通过模型之间的相互比拟和互相结合更好地完成了要求的任务。3、对于第四问，我们提出的算法思路不仅求得了多条黄金周旅游线路，同时还给出了一些有价值的短程游路线。参加这一完善结果，可以更充分地利用各景区的旅游资源，而且也同时满足了更多游客，让具有不同旅游需求的游客都可以领略新疆绚丽的风采，可以说取得了一种锦上添花的效果。4、本文综合运用了MATLAB、马克威分析系统、LINGO、EXCEL等多种软件，发挥其各自的特长，在提高编译和求解效率的同时，也使文章图文并茂，更直观更具有可读性。模型的缺乏及进一步探索：1、本文的模型均建立在速度、单位行程的费用等都为恒定的根底假设之上，而实际上，对于不同的道路，时速以及费用都会略有波动，如果在模型中能参加一些随机因素，应该可以更接近现实生活。2、模型处理复杂问题的求解上，根本都采用了遗传算法。但是，由于遗传算法的进化是基于一定的概率，所以单纯的遗传算法有时并不能保证求得最优解，或者虽然能求得最优解却要消耗相当多的时间，而这与我们的初衷是相违背的。如果能将遗传算法与模拟退火算法、局部搜索等相结合，将会取得更好的效果。3、在第四问中我们仅考虑了错开景点旅游顶峰，即仅从理性的角度分析筹划了旅游线路，但没有考虑游客对各景点的偏好程度，即未参加感性的一些元素，而这些对于现实问题还是很有影响的，因此，如果将游客的一些特定需要添加到模型的约束中，将会更符合实际。4、本模型第一步对景点进行了聚类，这样在为后面的分析带来了许多方便的同时，也造成了一旦选择游览某个景区也即游览了此景区的所有景点的约束。而事实上，尤其是在一条线路旅游的最后阶段，有可能出现时间上不允许游览某个景区，但却足够游览一两个景点的情况。而我们的模型会直接将整个景区排除，这是我们线路设计模型的一个略有缺乏之处。七、模型及软件的前景展望：1、蚁群算法模型：本文中我们运用蚁群算法估计游遍新疆境内所有景区在途中所花费的最少时间，从而为合理安排行程做了铺垫。事实上，蚁群优化算法最初用于解决与本文问题相类似的旅行商问题。之后又陆续渗透到诸如图的着色问题、大规模集成电路设计、通讯网络中的路由问题以及平衡问题、车辆调度问题等其他领域中。蚁群优化算法在处理复杂优化问题，尤其是离散优化问题方面显现出较强的优越性。对蚁群而言，在根本原理已经明确的条件下，重要的就是开发出求解问题的算法模型，使求解问题更加切实有效。2、遗传算法模型：基于遗传算法的使用领域很广且算法效率高，本文多处运用遗传算法求解复杂优化问题。这是一种模拟自然选择和遗传的随机搜索算法，它最初被应用于研究自然系统的适应过程和设计具有自适应性能的软件。它也是一种高级最优化技术，可以用来解决函数优化、组合优化、自动控制、图像处理、遗传编程、机器学习、数据挖掘等。遗传算法不单纯是一种算法，也同样是一种思考问题的方式，所以它有很多代扩展的方向，如：遗传算法的数学理论、分布并行遗传算法、分类系统、遗传神经网络、进化算法、人工生命等。3、线性规划模型：规划问题是运筹学中重要的分支，许多复杂问题都可以被抽象为线性、非线性、整数、0-1规划等。本文两处运用线性规划均取得一定的进展，除此之外，它还可以处理包括下料问题、配料问题、选址问题、指派问题、投资问题、装箱问题、最短路问题、最小生成树和最优连线问题等诸多看似一筹莫展的课题。4、马克威分析系统马克威分析系统是一款我国技术人员自行开发的软件，主要功能有：统计分析、数据挖掘、统计图表制作。其操作十分方便，且结果显示清晰，利用马克威分析系统，可以编制分布数列、绘制统计图、计算描述统计指标；实现区间估计、参数检验、非参数检验、方差分析、相关与偏相关分析、回归分析、时间序列分析、聚类分析、判别分析、主成分分析、因子分析等功能。5、LINGO软件LINGO语言以其简洁、易于扩展、“集合”特色等特点，在规划方面独树一帜。它既能求解线性规划问题，也有较强的求解非线性规划问题的能力。LINGO软件不仅运行速度快、计算能力强而且内置建模语言，提供几十个内部函数，从而能减少语句，较直观的方式描述较大规模的优化模型。它的运用范围很广，可以用于解决各种线性、非线性规划、多目标规划等复杂问题甚至实现非线性曲线拟合。6、Excel软件Excel是MicrosoftOffice套件中的电子表格软件，它的应用很广泛。Excel无需编程就可以实现其他软件需要变成才能完成的复杂计算，能进行各种数据的统计、运算、处理和绘制统计图形。Excel的数据功能主要有计算功能和数据分析功能两大块，前者指Excel有强大的计算能力，它提供了300多个内部函数给用户使用，还允许自定义函数。后者指Excel提供了“数据分析”工具包，内含方差分析、回归分析、协方差和相关系数、傅里叶分析、t检验等分析工具。7、MATLAB软件MATLAB是一种高效的工程计算语言，它将计算、可视化、编程等功能集于一个易于使用环境。其典型应用包括数学计算、算法开发、数据采集、系统建模和仿真、数据分析和可视化、科学和工程绘图以及应用软件开发等。MATLAB的一个重要特色就是它有一个套程序扩展系统和一组称之为工具箱的特殊应用子程序——工具箱，每一个工具箱都是为某一类学科专业和应用定制的，主要包括信号处理、控制系统、神经网络、模糊逻辑、小波分析、系统仿真等方面的应用。此外，MATLAB应用程序接口〔API〕支持对C、JAVA、Fortran语言的交互编写，使用户能更加自如地解决实际的问题。本文中的蚁群算法、遗传算法以及安排黄金周线路时都使用了MATLAB编程，其代码简洁、可视化等特点已可见一斑。参考文献：[1] 曾五一等，统计学，北京：北京大学出版社，2006年。[2] 李士勇，蚁群算法及其应用，哈尔滨：哈尔滨工业大学出版社，2004年。[3] 雷英杰等，MATLAB遗传算法工具箱及应用，西安：西安电子科技大学出版社，2005年。[4] 周明等，遗传算法原理及应用，北京：国防工业出版社，1999年。[5] 袁新生等，LINGO和Excel在数学建模中的应用，北京：科学出版社，2007年。[6] 求是科技，MATLAB7.0从入门到精通，北京：人民邮电出版社，2006年。[7] NirwanAnsar，EdwinHou著，李军，边肇祺译，用于最优化的计算智能，北京：清华大学出版社，1999年。[8] 国道距离信息，://crane88/road.asp?myid=312，2007年[9] 公路客运，://china-holiday/online/skb/qhdh.asp?qhsm=新疆，2007年[10] 铁路票价，://china-holiday/online/skb/skb.asp?xs=cc&cc=P8871/8874，2007年[11] 经纬度查询，://hjqing/find/jingwei/index.asp，2007年[12] 旅馆住宿价格查询，://zjxc/lixingshe3/szlxs186，2007年[13] 景点逗留时间：哈纳斯湖,://xjx.cc/kanas/jpxl/guanguang.htm额尔齐斯河,:///asp/line/xianlu.htm阿勒泰,://soochina/article/articleshow.asp?ID=18257塔城,:///Article/ShowArticle.asp?ArticleID=1758克拉玛依,://auyou/auyou/lyxlinfo.asp?auto_id=5088怪石沟,://bozhounews/2006-09/19/content_8079338.htm博尔塔拉,://bozhounews/2006-09/19/content_8079338.htm博乐,://bozhounews/2006-09/19/content_8079338.htm石河子,://soochina/article/articleshow.asp?ID=18253昌吉,://soochina/article/articleshow.asp?ID=18252乌鲁木齐,://xjtstc/news/mj.asp?id=A20072121548535693364天山,://xjtstc/news/mj.asp?id=A2007281050373903767伊犁,://gotoxj/xianl/zj3.htm昭苏边境的乾隆格登碑,://travel.163/04/0830/17/0V25VKL900061DPB.html吐鲁番,://xjtstc/news/mj.asp?id=A20072121548535693364哈密,:///travel/index.htm巴音布鲁克天鹅湖,://uu97/jd_2450.html火焰山,://1/Travel_line/20069/Travel_line_1300.html回王陵,://tvtour/tour/lvj/hami/interest/08.htm克孜尔千佛洞,:///1ashjuku/lv/index.htm库尔勒,://ylnet/travel/yllxs/ylxl3.htm博斯腾湖,://ylnet/travel/yllxs/ylxl3.htm阿克苏,://1/Travel_line/20069/Travel_line_1300.html库车大寺,://xjhy/line_detail.asp?id=1罗布泊,://auyou/auyou/lyxlinfo.asp?auto_id=1102楼兰,:///tanxian.htm苏丹·沙图克麻扎,://26/kzly/_private/kz201.htm阿图什,://26/kzly/_private/kz201.htm喀什,:///xinjiangsankeyou/kashidawakuyou.htm香妃墓,://lvyou114/line/line_show.asp?LineID=1578艾提尕清真寺,://lvyou114/line/line_show.asp?LineID=1578尼雅遗址,://visitxinjiang/xj/Article_Print.asp?ArticleID=3126和田,:///plans/plan.php?id=2949，2007年附录：1、新疆境内的33个旅游景点名称及其相应的观光逗留时间，经、纬度如下表所示：序号景点名称景点观光时间经度纬度1哈纳斯湖187.248.22额尔齐斯河0.586.947.83阿勒泰188.1547.866674塔城182.9666746.755克拉玛依0.584.7666745.66怪石沟18345.27博尔塔拉281458博乐182.144.933339石河子185.9544.2666710昌吉187.244.211乌鲁木齐1.587.6833343.7666712天山188.443.713伊犁181.843.914昭苏边境的乾隆格登碑0.58143.215吐鲁番189.242.916哈密193.442.817巴音布鲁克天鹅湖0.584.143.118火焰山0.590.243.619回王陵192.743.820克孜尔千佛洞0.582.741.821库尔勒0.586.0666741.6833322博斯腾湖0.586.5333341.9523阿克苏180.241.124库车大寺0.582.941.625罗布泊490.441.626楼兰688.841.627苏丹·沙图克麻扎0.2575.939.628阿图什0.7576.1166739.7333329喀什175.939.430香妃墓0.576.239.531艾提尕清真寺0.575.939.232尼雅遗址682.63833和田179.937.12、景点间最短路矩阵：T=[0.0021.006.7315.979.9012.0211.0312.9718.9113.7121.000.0014.2723.5117.4419.5620.6322.5726.4521.256.7314.270.009.243.175.296.368.3012.186.9815.9723.519.240.006.078.199.2611.2012.207.009.9017.443.176.070.002.123.195.1315.3510.1512.0219.565.298.192.120.001.073.0117.4712.2711.0320.636.369.263.191.070.001.9418.5413.3412.9722.578.3011.205.133.011.940.0020.4815.2818.9126.4512.1812.2015.3517.4718.5420.480.005.2013.7121.256.987.0010.1512.2713.3415.285.200.0047.2656.8642.5945.4939.4237.3036.2338.1744.0141.2352.8162.4148.1451.0444.9742.8541.7843.7249.5646.7821.3128.8514.5814.6017.7519.8720.9422.8810.387.6026.0635.6621.3924.2918.2216.1015.0316.9722.8120.0328.9636.5022.2322.2525.4027.5228.5930.5318.0315.2551.3460.9446.6749.5743.5041.3840.3142.2548.0945.3135.9843.5229.2529.2732.4234.5435.6137.5525.0522.2736.5844.1229.8529.8733.0235.1436.2138.1525.6522.8737.4947.0932.8235.7229.6527.5326.4628.4034.2431.4639.1448.7434.4737.3731.3029.1828.1130.0534.3231.5447.2652.8121.3126.0628.9651.3435.9836.5837.4939.1456.8662.4128.8535.6636.5060.9443.5244.1247.0948.7442.5948.1414.5821.3922.2346.6729.2529.8532.8234.4745.4951.0414.6024.2922.2549.5729.2729.8735.7237.3739.4244.9717.7518.2225.4043.5032.4233.0229.6531.3037.3042.8519.8716.1027.5241.3834.5435.1427.5329.1836.2341.7820.9415.0328.5940.3135.6136.2126.4628.1138.1743.7222.8816.9730.5342.2537.5538.1528.4030.0544.0149.5610.3822.8118.0348.0925.0525.6534.2434.3241.2346.787.6020.0315.2545.3122.2722.8731.4631.540.005.5533.6321.2041.2846.4843.5542.9532.6334.285.550.0039.1821.2046.8352.0349.1048.5038.1839.8333.6339.180.0012.437.6537.7114.6715.2723.8623.9421.2026.7512.430.0020.0825.2822.3521.7511.4313.0841.2846.837.6520.080.0045.367.027.6221.0716.2946.4852.0337.7125.2845.360.0045.4944.8935.4336.2243.5549.1014.6722.357.0245.490.000.6014.059.2742.9548.5015.2721.757.6244.890.600.0013.458.6732.6338.1823.8611.4321.0735.4314.0513.450.004.7834.2839.8323.9413.0816.2936.229.278.674.780.00]。3、主要程序：程序1：Floyd算法求最短路：function[zita,GA]=Floyed(C)%%程序说明：%本程序为用Floyed算法求最短路路径%%变量说明：%输入变量：%C；邻接矩阵；%输出变量：%zita：逆向追踪法矩阵；%GA：最短路径矩阵；%%GA=C;%GA为记录最短路径距离之阵；M=10000;n=length(C);line=[1:n]';zita=zeros(n,n);%初始化逆向追踪矩阵；fori=1:nzita(:,i)=line;endzita0=zita;fork=1:nfori=1:nforj=1:n%每行每列比拟，假设新距离小于旧距离，那么替换；ifi~=k&&j~=k&&i~=jifGA(i,k)+GA(k,j)<GA(i,j)&&GA(i,k)+GA(k,j)<M/2GA(i,j)=GA(i,k)+GA(k,j);zita(i,j)=zita0(k,j);endendendendzita0=zita;%更新逆向追踪矩阵；end程序2：精英蚁群算法求解遍历最短路function[TM,LM]=ASPSP(C)%%程序说明：%本程序为用带精英蚂蚁策略求解旅行商问题。%%变量说明：%输入变量：%C：城市坐标；%输出变量：%TM：近似最优路径；%LM：近似最短距离；%%tic;D=C;alpha=1;beta=5;rho=0.5;Q=100;Tao0=1e-6;e=5;Maxtime=200;n=length(D);m=n;Ta=Tao0*ones(n,n)-Tao0*eye(n);TM=[];LM=100000;ant=zeros(m,n+1);ata=zeros(m,n);fori=1:mforj=i+1:nata(i,j)=1/D(i,j);ata(j,i)=ata(i,j);endendfortime=1:Maxtimefork=1:mcity(k,:)=1:n;ends=1;fori=1:mant(i,s)=unidrnd(n);ant(i,n+1)=ant(i,s);city(i,ant(i,s))=0;endwhiles<np=zeros(m,n);fori=1:mA(i)=0;forj=1:nifcity(i,j)~=0A(i)=A(i)+(Ta(ant(i,s),j)^alpha)*(ata(ant(i,s),j)^beta);endendforj=1:nifcity(i,j)~=0p(i,j)=(Ta(ant(i,s),j)^alpha)*(ata(ant(i,s),j)^beta)/A(i);endendpp=unifrnd(0,1);j=1;whilepp>0pp=pp-p(i,j);j=j+1;endj=j-1;ant(i,s+1)=j;fork=1:nifcity(i,k)==j;city(i,k)=0;break;endendends=s+1;endL=compu(ant,D);[Lmin,t]=min(L);ifLmin<LMLM=Lmin;TM=ant(t,:);enddeltaTa=zeros(m,n);fori=1:mforj=1:n-1deltaTa(ant(i,j),ant(i,j+1))=deltaTa(ant(i,j),ant(i,j+1))+Q/L(i);endendforj=1:n-1deltaTa(TM(j),TM(j+1))=deltaTa(TM(j),TM(j+1))+Q/LM;endfori=1:mforj=1:nTa(i,j)=rho*Ta(i,j)+deltaTa(i,j);endendtrace(time)=LM;endfigure(1);plot(trace);toc;functionD=Distance(C)n=length(C);D=zeros(n,n);fori=1:nforj=i+1:nD(i,j)=norm(C(:,i)-C(:,j));D(j,i)=D(i,j);endendfunctionL=compu(ant,D);fori=1:length(D)L(i)=0;forj=1:length(ant)-1L(i)=L(i)+D(ant(i,j),ant(i,j+1));endend程序3：问题一的MATLAB遗传算法程序function[y,road]=GATSP1%程序说明：%本程序为遗传算法求解旅行商问题%%变量说明：%输入：%D：城市位置矩阵n*2。%输出：%y：近似最短路径的总长度；%road：近似最短路径。%ticD=[0.00 6.73 15.97 9.90 12.02 11.03 12.97 18.91 13.71 21.31 26.06 28.96 35.98 36.58 37.49 39.146.73 0.00 9.24 3.17 5.29 6.36 8.30 12.18 6.98 14.58 21.39 22.23 29.25 29.85 32.82 34.4715.97 9.24 0.00 6.07 8.19 9.26 11.20 12.20 7.00 14.60 24.29 22.25 29.27 29.87 35.72 37.379.90 3.17 6.07 0.00 2.12 3.19 5.13 15.35 10.15 17.75 18.22 25.40 32.42 33.02 29.65 31.3012.02 5.29 8.19 2.12 0.00 1.07 3.01 17.47 12.27 19.87 16.10 27.52 34.54 35.14 27.53 29.1811.03 6.36 9.26 3.19 1.07 0.00 1.94 18.54 13.34 20.94 15.03 28.59 35.61 36.21 26.46 28.1112.97 8.30 11.20 5.13 3.01 1.94 0.00 20.48 15.28 22.88 16.97 30.53 37.55 38.15 28.40 30.0518.91 12.18 12.20 15.35 17.47 18.54 20.48 0.00 5.20 10.38 22.81 18.03 25.05 25.65 34.24 34.3213.71 6.98 7.00 10.15 12.27 13.34 15.28 5.20 0.00 7.60 20.03 15.25 22.27 22.87 31.46 31.5421.31 14.58 14.60 17.75 19.87 20.94 22.88 10.38 7.60 0.00 12.43 7.65 14.67 15.27 23.86 23.9426.06 21.39 24.29 18.22 16.10 15.03 16.97 22.81 20.03 12.43 0.00 20.08 22.35 21.75 11.43 13.0828.96 22.23 22.25 25.40 27.52 28.59 30.53 18.03 15.25 7.65 20.08 0.00 7.02 7.62 21.07 16.2935.98 29.25 29.27 32.42 34.54 35.61 37.55 25.05 22.27 14.67 22.35 7.02 0.00 0.60 14.05 9.2736.58 29.85 29.87 33.02 35.14 36.21 38.15 25.65 22.87 15.27 21.75 7.62 0.60 0.00 13.45 8.6737.49 32.82 35.72 29.65 27.53 26.46 28.40 34.24 31.46 23.86 11.43 21.07 14.05 13.45 0.00 4.7839.14 34.47 37.37 31.30 29.18 28.11 30.05 34.32 31.54 23.94 13.08 16.29 9.27 8.67 4.78 0.00];NIND=100;%种群数量；MAXGEN=500;%最大遗传代数；pc=0.8;%交叉概率；pm=0.1;%变异概率；N=length(D(:,1));%求城市数量%随机生成初始种群fori=1:NINDB(i,:)=manu(N);F(i)=Distance(B(i,:),N,D);endSelCh=B;F=F';FitnV=(10000./F);%计算适应度forgen=1:MAXGENfort=1:floor(NIND/30)%寻找每代的一局部最优群种以便遗传给下一代fori=1:NINDifF(i)==min(F)bestSelCh(t,:)=SelCh(i,:);bestFit(t)=F(i);break;endendendSelCh=select('rws',SelCh,FitnV);%选择fori=1:0.1*NIND%生成一局部子代Chrom(i,:)=manu(N);C(i)=Distance(Chrom(i,:),N,D);G(i)=10000/C(i);endSelCh=reins(SelCh,Chrom,1,1,F,G');%插入SelCh=Crossover(SelCh,N,NIND,pc);%交叉SelCh=Muta(SelCh,N,NIND,pm);%变异fori=1:NINDF(i)=Distance(SelCh(i,:),N,D);endfort=1:floor(NIND/30)%遗传的最优个体替换适应度最差的新个体fori=1:NINDifF(i)==max(F)SelCh(i,:)=bestSelCh(t,:);F(i)=bestFit(t);break;endendendFitnV=(10000./F);%计算适应度trace(gen,1)=min(F);%寻找每一代的最优值fori=1:NINDifF(i)==trace(gen,1)key=SelCh(i,:);break;endendtrace(gen,2)=mean(F);%寻找每一代的平均值ifgen==1y=trace(gen,1);road=key;elseify>trace(gen,1)y=trace(gen,1);road=key;%寻找当前最优路径endendendtoc%作图，观察遗传代数与路径长度的关系figure(2);holdon;plot(trace(:,1));plot(trace(:,2),'r');title('性能追踪');xlabel('进化代数');ylabel('目标值');legend('最正确值','平均值');grid;holdoff%交叉函数，使用CX方法functionBB=Crossover(B,N,NIND,pc)tem=B(:,1);B(:,1)=[];fori=1:2:NIND-1ifunifrnd(0,1,1,1)<pcc1=B(i,:);c2=B(i+1,:);k=1;FLAG=0;FLAG(k)=1;STOP=0;fort