旅游线路的优化设计1

一、 问题重述随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算在今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如附表1（见附录I）所示。假设(A)城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。(B)市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C)旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(D)假设景点的开放时间为8:00至18:00。问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。(2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。二、 问题假设1、忽略乘坐出租车时经过收费路段所交的费用；2、在每个城市中停留时，难免会遇到等车、堵车等延时情况，在此问题中我们不做考虑；3、所有旅馆都未客满，并且忽略从旅馆到火车站或景点的时间；4、列车车次和飞机航班没有晚点等情况发生；5、列车和飞机的票足够，没有买不到票的情况发生；6、景点的开放，列车和航班的运营不受天气的影响；7、绘图时，经线和纬线近似平行分布；8、将城市和路径的关系转化为图论问题；9、在时间的认识上，我们把当天的8点至次日的8点作为一天。三、 符号说明有向图矩阵城市路径要经过的城市总数任意两城市之间的距离是否经过两座城市路径上的信息量启发函数信息启发式因子期望启发式因子蚂蚁在时刻由城市转向城市的转移概率第只蚂蚁的禁忌搜索表信息素挥发系数时刻蚂蚁在路径上留下的信息素量到目前为止所找到的全局最短路径长度蚂蚁携带的信息素量本次循环中第只蚂蚁所走的路程长度蚂蚁的总数量蚂蚁的编号所记录的循环次数最大循环次数四、 问题分析4.1问题一的分析针对问题一，要求求出将旅游景点全游览完，所需的最少旅游费用。这和问题,即旅行商问题有些类似，所以本文将问题向问题进行一定的转化，从而进行求解。因为运用传统的动态规划解法，解法的空间复杂性和时间复杂性都十分庞大，不利于求解，所以采用蚁群算法，通过计算机软件进行编程得到路程最短的旅行路线。因题目要求时间不限，用最少的旅游费用游览全部景点，而考虑到不同交通工具的速度和票价都不相同，各个旅馆的住宿费用也不相同，所以我们对其行程进行详细的安排，尽量减少其在交通和住宿上的费用，减少不必要的花费。最后得出一个最少旅游费用的旅游行程表。4.2问题二的分析针对问题二，要求求出将旅游景点全游览完，所需的最少时间。因为考虑到交通工具的不同导致时间上的差异问题，所以仅用问题一的模型不能求解。但是由于任意两座城市之间都能相连接起来，且每座城市只经过一次，所以将任意两座城市之间的路程转变为时间，建立最优化模型，通过计算机软件进行编程，到时间最短的旅游路线。然后，根据题目要求，再对其行程进行详细的安排，尽量避免不必要的时间。最后得出一个最短时间的旅游行程表。4.3问题三的分析针对问题三，题目给出了限制条件，旅游费用不超过2000元。只用2000元游览完全部景点是不可能的，所以我们对其行程进行优化。首先，将问题一的旅游行程根据旅游景点和交通路线划分成21个部分（包括10个景点和11条交通线路），并计算出每一个部分所要花费的旅游费用。然后，对旅游行程进行优化计算，为了简化运算，我们假设交通线路上花费的费用只是简单相加。通过除去旅游景点计算出2000元以下的费用最优解。最后得出一个2000元以下的旅游行程表。4.4问题四的分析针对问题四，题目也给出了限制条件，旅游时间不超过5天。只用5天游览完全部景点是不可能的，所以我们对其行程进行优化。解法与问题三大致相同。首先，对问题二的旅游行程也根据旅游景点和交通路线划分成21部分（包括10个景点和11条交通线路），并计算出每一个部分所要花费的时间。然后，对旅游行程进行优化计算，为了简化运算，我们假设交通线路上花费的时间只是简单相加。通过除去旅游景点计算出5天以内的时间最优解。最后得出一个5天以内的旅游行程表4.5问题五的分析针对问题五，题目给出了两个限制条件，旅游费用不超过2000元，并且旅游时间在5天以内。只用5天和2000元游览完10个景点是不可能的，所以我们对其进行优化。由于飞机价格非常高，所以我们基于第三问，并且结合第四问的数据对其进行优化。首先，对旅游行程也根据旅游景点和交通路线划分成21部分（包括10个景点和11条交通线路），并计算出每一部分所要花费的时间和费用。然后，对旅游行程进行优化计算，为了简化运算，我们假设交通线路上花费的时间和费用只是简单相加。通过除去旅游景点计算出2000元以下和5天以内的时间最优解。最后得出一个最优旅游行程表。五、 模型的建立与求解5.1问题一的求解5.1.1建立图论的数学模型将各个旅游景点之间的关系转化为图论问题，并做以下分析：建立有向图。其中称为图的顶点集，中的每一个元素称为该图的一个顶点，在该题中表示城市；称为图的弧集，中的每个元素称为该图的一条从到的弧，在此题中表示各个城市两两连线的集合。1设城市个数为，表示两个城市与之间的距离，0或1（1表示走过城市到城市的路，0表示没有选择走这条路）。本题可以向问题进行转化，则问题的数学模型为：5.1.2建立蚂蚁算法的数学模型(1)状态转移规则因为蚂蚁不能重复经过一个城市，所以建立禁忌表来记录蚂蚁走过的城市，禁忌表随着时间做动态变化。建立蚂蚁由城市转移到城市的状态转移概率如下： （1）上式中为信息启发式因子，表示路径的相对重要性，是对所积累的信息素影响作用的一个加权值；为期望启发式因子，表示能见度的相对重要性；每只蚂蚁必须依据以城市距离和连接边上信息素的数量为变量的概率函数，决定选择下一个城市的概率。每只蚂蚁必须根据禁忌表和概率函数寻找下一个城市，以保证该蚂蚁从起点出发经过所有城市有且只有一次，并且最终返回到起点。(2)信息素的全局更新规则当只蚂蚁成功的完成一次寻径过程之后，将选出目标函数值最小的路径，用以完成全局信息素的更新，使得较优解保留下来，对后继蚂蚁产生影响，加快收敛到最优解的速度。设，为两个相连接点，则有： （2）其中，变量是在时刻，节点之间路上信息素的增加量是位于0,1上的“激素”挥发因子；为到目前为止所找到全局最短路径长度。(3)信息素的局部更新对于第只蚂蚁，在建立一个解得过程中也同时进行激素迹的更新，如果节点是它所选择路径上的两个相邻节点，规则如下：否则，不更新。其中，是各条路上的信息素的初始值，通常取同一值，表示同一环境。信息素的更新策略有很多种方法，每种更新策略的主要差别体现在的求法上。我们规定蚂蚁在完成一个循环后更新所有路径上的信息素，其方程式为： （3）上式中表示蚂蚁携带信息素的量，其值的大小影响算法的收敛速度；表示第只蚂蚁在本次循环中所走的路程总长度。5.1.3基于蚁群算法的实现步骤2本题基于蚁群算法的实现步骤如下：初始化。时间，循环次数，设置最大循环次数为，；：循环次数；：蚂蚁个数；：蚂蚁选择可以到达的城市，按照状态转移规则移动到下一个城市；：对于城市，由于已经到达，所以添加到禁忌表中；：判断所有城市是否都经过，若未完全经过，表明蚂蚁个数没有达到，则转向执行，否则执行； ：由于信息素改变，要求按照公式（2）（3）更新最短路径信息素，使得较优解保留，加快收敛到最优解的速度；：若表明没有满足终止条件，即转向执行，否则执行；：输出最优结果。5.1.4模型的求解(1)求解城市之间的距离首先，假设经线和纬线近似平行分布，根据附表2（见附录I）可知11座城市的经纬坐标。建立直角坐标系，以纬度最低的城市所在的纬线为轴，以经度最小的城市所在的经线为轴，计算11座城市的坐标。将城市进行编号，计算相应城市间的距离得到附表3（见附录I），得到编程数据（见附录II）。(2)求解最短路径利用上述蚁群算法的步骤，使用附录II的数据，编写程序，得出以下结果：Shortest_Route =6 9 5 4 3 1 2 11 7 10 8图一：模拟图对上述结果进行处理，根据城市编号求出最优解为：徐州常州舟山黄山九江武汉洛阳西安祁县北京青岛徐州由上面结果可以在中国地图上模拟出最短路线，如下：图二：问题一模拟路径图5.1.5设计旅游行程表和求出总费用我们根据蚁群算法得出游览全部景点的最短路径，在得出的最短路径的基础上，我们通过查阅火车票价、车次、运营时间，宾馆价格、名称等大量资料和数据，尽可能的减少其在行程上的花费，设计出如下旅游行程表：表一：问题一行程表（其余答案参见附录III）日期时间行程价格（元）5月1日8:3015:45乘坐L8449次列车（徐州常州）3416:0021:00游览常州市021:007:00住宿于常州蓝色快舟营销人连锁旅店1205月2日7:008:00乘坐公交去中华恐龙园48:0016:00游览中华恐龙园16016:0017:00乘坐公交返回417:0022:30游览常州市022:305:20乘坐K75次列车（常州宁波）735月3日5:308:00乘坐758W公交到白峰码头乘坐船到普陀山168:0014:00游览普陀山20014:0016:00返回宁波站1616:0022:15乘坐K8500次列车（宁波宣城）6322:151:30候车0并且得出最少的总旅游费用为3438元。5.2问题二的求解5.2.1模型的建立基于第一问的模型，我们稍作改进。因为第二问要求安排时间最短的旅游行程表，而费用不限，由于飞机费用过大，所以在第一问我们未做考虑，但由于其时间比火车和汽车都要快的多，所以我们把飞机作为首要考虑对象加入第二问中。第一问的模型中，是把任意两点之间的距离作为参数，从而进行求解，得出最短路径。在第二问中，我们把任意两点之间的所乘坐的交通工具的最短时间作为参数，建立时间最优化模型,结合软件（程序见附录III）求出经过所有旅游景点的花费时间最短的路线。5.2.2模型的解释在模型中，我们引入0-1变量，若通过两城市之间的路径，则赋值为1；若不通过两城市之间的路径，则赋值为0。对于无向图的最短时间路径问题，可以这样理解，从点到点和点到点的边，看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的最短时间路径问题来编程。35.2.3模型的求解利用上述算法的步骤，使用附录II的数据，编写程序，得出以下结果：VariableValueReduced CostX(1,2)1.322.0000X(2,9)1.110.0000X(3,11)1.90.00000X(4,6)1.105.0000X(5,3)1.100.0000X(6,1)1.280.0000X(7,4)1.120.0000X(8,10)1.215.0000X(9,5)1.65.00000X(10,7)1.484.0000X(11,8)1.75.00000即最短时间路径：对上述结果进行处理，根据城市编号求出最优解为：徐州常州西安祁县青岛舟山武汉九江黄山北京洛阳徐州由上面结果可以在中国地图上模拟出最短路线，如下：图三：问题二模拟路径图5.2.4设计旅游行程表和求出总费用我们根据最优化模型得出游览全部景点的最短时间路径，在得出的最短时间路径的基础上，我们通过查阅飞机票价、班次、运营时间，宾馆价格、名称等大量资料和数据，尽可能的减少其在行程上的花费，设计出如下旅游行程表：表二：问题二的行程表（其余答案参见附录III）日期时间行程价格（元）5月1日8:009:30整理行装09:3015:30乘坐K55次列车（徐州常州）7015:3021:00游览常州市021:007:00住宿于常州蓝色快舟营销人连锁旅店1205月2日7:008:00乘坐出租车到中华恐龙园408:0016:00游览中华恐龙园16016:0017:00乘坐出租车返回4017:0021:00游览常州市021:0023:00乘坐MU5638班次飞机（常州西安）111023:0024:00乘坐出租车到秦始皇兵马俑405月3日0:008:00住宿于西安美宝宾馆后宰门店1388:0010:00游览秦始皇兵马俑9010:0011:00乘坐出租车返回4011:0013:00游览西安0并且得出最少的总旅游时间为210小时。5.3问题三的求解基于第一问得出的旅游行程表，我们对其进行优化。由于题目给出了约束条件，旅游经费不超过2000元，所以我们将行程划分为21部分（包括10个景点和11条线路）。然后统计出每一部分所要花费的经费，如下表所示：表三：各地花费经费表（单位：元）徐州常州舟山黄山九江武汉016823226020084洛阳西安祁县北京青岛124944485164徐州常州常州宁波宁波黄山黄山九江九江武汉武汉洛阳347389935792洛阳西安西安祁县祁县北京北京青岛青岛徐州55399415899由上表可以看出，黄山、普陀、九江和常州所花费的经费占10个旅游景点的前4位，这四个景点的总经费大约为915元，所以先不考虑黄山、普陀、九江和常州这四个景点。然后使其从青岛开始出发，尽量避免这四个景点。对其余的景点根据最短路径重新安排行程，避免住宿，减少不必要的花费。表四：问题三行程估计表（其余数据参见附录IV）日期时间行程价格（元）5月1日8:0023:30整理行装023:308:00乘坐K1025次列车（徐州青岛）705月2日8:009:00乘坐311W公交车到崂山风景区79:0017:00游览崂山15017:0018:00乘坐311W公交车返回718:0020:00游览青岛市020:005:30乘坐T26次列车（青岛北京）1165月3日5:307:00休息07:008:00乘坐地铁2号线和公交车到八达岭208:0013:00游览八达岭4513:0014:00乘坐地铁2号线和公交车返回2014:0022:00游览北京市022:0023:30休息023:3013:30乘坐2603次列车（北京祁县）945月4日13:3014:30乘坐公交车到乔家大院214:3018:00游览乔家大院4018:0019:00乘坐公交车返回219:0020:30游览祁县0经过计算，新的旅游行程所花费的经费大约为1517元，与题目给出的2000元还有很大的差距，所以我们重新旅游行程表进行优化，对黄山、普陀、九江和常州这四个旅游景点进行分析，安排行程。发现只有添加九江这个景点旅游费用不会超支，所以设计出如下行程表：表五：问题三行程表（其余答案参见附录III）日期时间行程价格（元）5月1日8:0023:30整理行装023:308:00乘坐K1025次列车（徐州青岛）705月2日8:009:00乘坐311W公交车到崂山风景区79:0017:00游览崂山15017:0018:00乘坐311W公交车返回718:0020:00游览青岛市020:005:30乘坐T26次列车（青岛北京）1165月3日5:307:00休息07:008:00乘坐地铁2号线和公交车到八达岭208:0013:00游览八达岭4513:0014:00乘坐地铁2号线和公交车返回2014:0022:00游览北京市022:0023:30休息023:3013:30乘坐2603次列车（北京祁县）94并且得出旅行费用为1994元。由上面结果可以在中国地图上模拟出最短路线，如下：图四：问题三模拟路径图5.4问题四的求解基于第二问得出的旅游行程表。我们对其进行优化。由于题目给出了约束条件，旅游时间不超过5天，也就是120小时，所以我们将行程划分为21部分（包括10个景点和11条线路）。然后统计出每一部分所要花费的时间，如下表所示：表六：各地花费时间表（单位：小时）徐州常州西安太原青岛舟山1.529.514719.521.5武汉九江黄山北京洛阳2121.517.513.54徐州常州常州西安西安太原太原青岛青岛舟山舟山武汉620.751.251.52武汉九江九江黄山黄山北京北京洛阳洛阳徐州51021.57.5由上表可以看出，常州、舟山、九江和武汉所花费的时间占10个旅游景点的前4位，这4个景点的总时间大约为93.5小时，但是根据路程上所花的时间来看，武汉所花的时间要少于黄山，所以先不考虑常州、黄山、九江、舟山这四个景点。然后，考虑到如果从洛阳开始出发，没有飞机能够直达，早上出发会遇到住宿的问题，从而浪费时间，然而从北京开始出发能够避免此问题，所以从北京出发对其余的景点根据最短路径重新安排行程。表七：问题四行程估计表（其余数据参见附录IV）日期时间行程价格（元）5月1日8:009:30整理行装09:3010:45乘坐KN2904班次飞机（徐州北京）69010:4511:30乘坐出租车到八达岭4011:3014:30游览八达岭4514:3015:15乘坐出租车返回4015:1516:40乘坐MU743班次飞机（北京青岛）61816:4022:00游览青岛市022:007:00住宿于常州蓝色快舟营销人连锁旅店1205月2日7:008:00乘坐出租车到崂山风景区408:0014:00游览崂山15014:0015:00乘坐出租车返回4015:0016:40乘坐SC4607班次飞机（青岛太原）69016:4017:40乘坐出租车到达乔家大院4017:4022:00游览祁县022:008:00住宿于平遥怡兴驿同福客栈98经过计算，新的旅游行程所花费的时间大约为91小时，与题目给出的120小时还有很大的差距，所以我们重新旅游行程表进行优化，对常州、舟山、九江和黄山这四个旅游景点进行分析，安排行程。发现只有添加常州这个景点对时间安排最合理，所以设计出如下行程表：表八：问题四行程表（其余答案参见附录III）日期时间行程价格（元）5月1日8:009:30整理行装09:3010:45乘坐KN2904班次飞机（徐州北京）69010:4511:30乘坐出租车到八达岭4011:3014:30游览八达岭4514:3015:15乘坐出租车返回4015:1516:40乘坐MU743班次飞机（北京青岛）61816:4022:00游览青岛市022:007:00住宿于常州蓝色快舟营销人连锁旅店1205月2日7:008:00乘坐出租车到崂山风景区408:0014:00游览崂山15014:0015:00乘坐出租车返回4015:0016:40乘坐SC4607班次飞机（青岛太原）69016:4017:40乘坐出租车到达乔家大院4017:4022:00游览祁县0并得出旅游时间为110小时。由上面结果可以在中国地图上模拟出最短路线，如下：图五：问题四模拟路径图5.5问题五的求解基于第三问得出的旅游行程表，结合第四问的数据，对其进行优化。由于题目给出了约束条件，旅游经费不超过2000元和旅游时间不超过5天，也就是120小时，所以我们将行程划分为21部分（包括10个景点和11条线路）。根据表三和表六的数据，先不考虑花费经费最大的四个景点和花费时间最长的四个景点，其中有重复，发现还剩下五个景点，即西安、北京、祁县、洛阳和青岛。若根据第四问的行程表从北京开始出发所花费的经费太大，不能合理安排路径，所以根据第三问的行程，从青岛开始出发。然后根据北京和洛阳的在景点的最短停留时间，并且这两座城市之间有合适的班机，所以我们决定将北京往祁县的路线改为由北京飞往洛阳，然后再根据第三问的路径进行优化从洛阳到祁县再返回徐州。最后，再进行优化，设计出如下行程表：表九：问题五行程表（其余答案参见附录III）日期时间行程价格(元)5月1日8:0023:30整理行装023:308:00乘坐K1025次列车（徐州青岛）705月2日8:009:00乘坐311W公交车到崂山风景区79:0017:00游览崂山15017:0018:00乘坐311W公交车返回718:0020:00游览青岛市020:005:30乘坐T26次列车（青岛北京）1165月3日5:307:00休息07:008:00乘坐地铁2号线和公交车到八达岭208:0012:00游览八达岭4512:0013:00乘坐出租车返回3013:0014:30乘坐MU5695班次飞机（北京洛阳）74914:3015:00乘坐出租车到达龙门石窟3015:0018:00游览龙门石窟12018:0022:00游览洛阳市022:001:00休息05月4日1:006:30乘坐K245次列车（洛阳西安）556:307:00休息07:008:00乘坐81W公交车到达秦始皇兵马俑18:0014:00游览秦始皇兵马俑9014:0015:00乘坐公交车返回115:0021:00游览西安市021:006:30乘坐2670次列车（西安祁县）39并得出总旅游费用为1995元，总旅游时间为115小时。由上面结果可以在中国地图上模拟出最短路线，如下：图六：问题五模拟路径图六、 模型评价与改进6.1模型的优点1)在解题过程中，使用软件进行编程，在分析和运算方面有较高的精度，时间大大缩短，使答案更加明了。2)合理恰当的使用了表格和图形，使数据的体现和意思的表达更加清晰。3)答案详细、具体，并且接近实际，具有较强的可操作性。6.2模型的缺点1)没有根据实际路况来解题，与实际存在很大的差异。 2)大多数数据来自于网络，数据缺乏准确性。3)对问题五没有采用更精确的方法进行预测，缺乏合理性。七、 参考文献1费浦生，数学建模及其基础知识详解，武汉：武汉大学出版社，2006.2程世娟，卢伟，陈虬，基于蚁群算法的最短路径搜索方法研究，科学技术与工程，21期：P63，2007。3孙小军，焦建民，一种求解最少时间最小费用路问题的算法，计算机工程与科学，07期：P20，2008。4金诗铭，鲁斌，崔占森，走遍全中国，/view/c6a3fd136c175f0e7cd13735.html，2011年5月1日。5参考网站：/train/7参考网站：/travel/附录附录I附表1：预选的十个省市旅游景点省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时附表2：11座城市的经纬坐标地点经度纬度徐州117.234.26常州119.9531.79青岛120.3336.07北京116.4639.92祁县112.3337.36洛阳112.4434.7黄山118.1430.19武汉114.3130.52西安108.9534.27九江115.9729.71舟山122.329.97附表3：相应城市间的距离徐州常州青岛北京祁县洛阳徐州0401.9388.2634.36620.33507.3常州401.90476.71977.941019.41862.64青岛388.2476.710594.65857.51849.77北京634.36977.94594.650514.36715.7祁县620.331019.41857.51514.360297.11洛阳507.3862.64849.77715.7297.110黄山462.82266.66695.181096.31006.78784.59武汉518.9620.72890.721069.85791.23506.59西安877.611205.611224.431008.15497.51375.22九江523.41486.39846.731136.46935.47670.2舟山707.31305.56701.161257.971324.681156.69黄山武汉西安九江舟山徐州462.82518.9877.61523.41707.31常州266.66620.721205.61486.39305.56青岛695.18890.721224.43846.73701.16北京1096.31069.851008.151136.461257.97祁县1006.78791.23497.51935.471324.68洛阳784.59506.59375.22670.21156.69黄山0407.991078.11235.64430.58武汉407.990709.48198.47838.37西安1078.11709.480905.661484.54九江235.64198.47905.660660.46舟山430.58838.371484.54660.460附录II基本蚁群算法解决问题的程序m=11; %蚂蚁个数Alpha=1; % Alpha 表征信息素重要程度的参数Beta=5; % Beta 表征启发式因子重要程度的参数Rho=0.1; % Rho 信息素蒸发系数NC_max=1000; % NC_max 最大迭代次数Q=100; % Q 信息素增加强度系数C=load(C:Documents and SettingsAdministrator桌面jj.txt); % C n个城市的坐标，n2的矩阵D=load(C:Documents and SettingsAdministrator桌面att34.txt); %D 城市之间的参数（可以是距离、费用、时间等）n=11; %n表示问题的规模（城市个数）Eta=1./D; %Eta为启发因子，这里设为距离的倒数Tau=ones(11,11); %Tau为信息素矩阵Tabu=zeros(11,11); %存储并记录路径的生成NC=1; %迭代计数器R_best=zeros(NC_max,n); %各代最佳路线L_best=inf.*ones(NC_max,1);%各代最佳路线的长度L_ave=zeros(NC_max,1); %各代路线的平均长度while NC=rand);to_visit=J(Select(1);Tabu(i,j)=to_visit;endendif NC=2Tabu(1,:)=R_best(NC-1,:);end%第四步：记录本次迭代最佳路线L=zeros(m,1);for i=1:mR=Tabu(i,:);for j=1:(n-1)L(i)=L(i)+D(R(j),R(j+1);endL(i)=L(i)+D(R(1),R(n);endL_best(NC)=min(L);pos=find(L=L_best(NC);R_best(NC,:)=Tabu(pos(1),:);L_ave(NC)=mean(L);NC=NC+1%第五步：更新信息素Delta_Tau=zeros(n,n);for i=1:mfor j=1:(n-1)Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i);endDelta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);endTau=(1-Rho).*Tau+Delta_Tau;%第六步：禁忌表清零Tabu=zeros(m,n);end%第七步：输出结果Pos=find(L_best=min(L_best);Shortest_Route=R_best(Pos(1),:)Shortest_Length=L_best(Pos(1)subplot(1,2,1)DrawRoute(C,Shortest_Route)subplot(1,2,2)plot(L_best)hold onplot(L_ave)% 画路线图的子函数N=length(R);scatter(C(:,1),C(:,2);hold onplot(C(R(1),1),C(R(N),1),C(R(1),2),C(R(N),2)hold onfor ii=2:Nplot(C(R(ii-1),1),C(R(ii),1),C(R(ii-1),2),C(R(ii),2)hold onend解决问题的程序MODEL: SETS: CITY / 1. 11/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): TIME, ! The TIME matrix; X; ! X( I, J) = 1 if we use link I, J; ENDSETS DATA: !TIME matrix, it need not be symmetric; TIME = 032232070660280602562521528724 3220944851140735583250110840272 3209440751009141395115110101590 708575075105120110105135130 66011401007507019948065731960 280735914105701017504232706961320 6025831395120994175004671300484490 5622501151108042346707021575 521110110105652701300700967170 52884010151357316964842159670828 724272901309601320490751708280; ENDDATA N = SIZE( CITY); MIN = SUM( LINK: TIME * X); FOR( CITY( K): ! It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1; ! It must be departed; SUM( CITY( J)| J #NE# K: X( K, J) = 1; ! Weak form of the subtour breaking constraints; ! These are not very powerful for large problems; FOR( CITY( J)| J #GT# 1 #AND# J #NE# K: U( J) = U( K) + X ( K, J) - ( N - 2) * ( 1 - X( K, J) + ( N - 3) * X( J, K) ); ); ! Make the Xs 0/1; FOR( LINK: BIN( X); ! For the first and last stop we know.; FOR( CITY( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X( K, 1) );附录III问题一答案如下：日期时间行程价格（元）5月1日8:3015:45乘坐L8449次列车（徐州常州）3416:0021:00游览常州市021:007:00住宿于常州蓝色快舟营销人连锁旅店1205月2日7:008:00乘坐公交去中华恐龙园48:0016:00游览中华恐龙园16016:0017:00乘坐公交返回417:0022:30游览常州市022:305:20乘坐K75次列车（常州宁波）735月3日5:308:00乘坐758W公交到白峰码头乘坐船到普陀山168:0014:00游览普陀山20014:0016:00返回宁波站1616:0022:15乘坐K8500次列车（宁波宣城）6322:151:30候车05月4日1:305:00乘坐2521次列车（宣城黄山）265:006:30休息06:307:30乘坐公交去黄山风景区158:0015:00游览黄山23015:0016:00乘坐公交车返回黄山站1516:0018:30游览黄山市018:3023:30乘坐K67次列车（黄山鹰潭）515月5日0:304:00乘坐K253次列车（鹰潭九江）424:007:00休息07:008:00乘坐公交车到庐山风景区108:0018:00游览庐山18018:0019:00乘坐公交车返回九江站1019:0024:00游览九江市05月6日0:001:50休息01:506:30乘坐K924次列车（九江武汉）516:309:00游览武汉市09:009:15乘坐D3221次列车（武汉武昌）69:1