10300c佳旅游路线设计与对比

题目 最佳旅游路线设计与对题目 最佳旅游路线设计与对划模型，在给定游览景点个数的情况下以人均总费用最小为目标。再引入0—11080（不考虑旅游人数对游览费用的响。Excel排序，SPSS预测，这样给0—1变量进行了使用和约束，简化TSP问题最佳路线线性规划11-1TSPTSPTSPTSP商旅模型进行修改，通过编程将所TSP旅行商问题旅行商问题（TravelingSalemanProblemTSP）是VRPGaery[1]TSPNPVRPNP难题。旅行商问题（TSP）TSP问题，是Dantzig（1959）等人提出。TSP问题在物流中的描述是对应一个物流配送公司，n个客户的订货沿最短路线全部送到。如何确定最短路线。TSP问题最简单n个点的所有排列的集合，大小为（n-1。可以形象地把解空图 TSP问题模型TSP旅行商问题常见算法：枚举法，蚁群算法，模拟退火柴法，TSP问题是NP计算复杂性。因此，任何能使该nEdmonds，Cook和KarpNP完全问题（NP-CompletNPC）NP难题（NP-HardNPH）不Hamilton1、途程建构法（TourConstruction-2节省法（Clark节省法（ClarkandWrightSaving）：插入法（Insertionprocedures）：如插入法、最省插入法、随意插入法、2、途程改善法（TourImprovement1）K-Opt(2/3Opt)：KK为止，K23。x1Si。通常，所求解的问题需要求取一个使某一规范函数mnP，从而找出该问题Pi(x1,…Xi)（即限界函数）n-元组的部分向量(x1,…,Xi)，看其是否可能（m）要少得多。用回溯法求解的旅行商问题，即在枚举法的基础上多了一个FIFOE-结点全部儿FIFO（FirstInFirstOut），它的活结点表采用一张先进先-3228:0018:003问题三的分析-42.445 2.445 5ij——第iji，jti——每个家庭在第ici——每个家庭在itij——从第ijcij——从第ijZ-56 主成分分析(PrincipalComponentsAnalysis，PCA)6 主成分分析(PrincipalComponentsAnalysis，PCA)（指标-66.2m从而得到目标函数：（1）因为cij6.2m从而得到目标函数：（1）因为cij表示从第ij个景点所需的交通费用，而rij庭是否从第ij个景点的0—111riji1（2）因为ci表示家庭成员们在i个景点的总消费，rij是否到达过第i个和第j个景点，而整个旅游路线又是一个环形，因此rcc11 i1rcc11 m i1 rcc11c+111＝ ij i1j1i1-76.3括在路途中的时间和在旅游景点逗留的时间。因为tij表示从第i个景点到第j11rijtij；6.3括在路途中的时间和在旅游景点逗留的时间。因为tij表示从第i个景点到第j11rijtij；ti表示成员们在第ii1rtt11ij i1j1景点的逗留时间，故家庭们在旅游景点的总逗留时间为rtt1111ij i1j1rt i111即表示代表们旅游的景点数，这里我们假定要旅游的景点数为i1=2，3，……，1111i1④0——1对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束：-8rij（i，j当irij（i，j当i1时，因为重庆市出发点，所以rijj1时，因为家庭成员最终要回到重庆，所以rij1（i，jj2时，根据题意不可能出现rijrji1同样，当irij（i，jGVA。其中V{V1,V2,......,VnG的顶点集，V中的每一个元素Vi(i12n..)为该图的一个顶点，在该题中表示nA{a1a2,an}为图G的弧集，A中的每个元素akVi,Vj称为该图的一条从Vi到Vj过城市ij的路，0。本题可以向TSP问题进行转化，则TSP问题的数学模型为：mindijiTSP-9(t) jp(t) (t)(t) jp(t) (t)jNL i,Ei,j（3）NLi, rT(L) Ei,jrT(L)T1515小时。 rcc1111c+1＝ ij i1j1i16.4.2模型求解与结果分析-10T(L)≤30L0称为劣解，如果存在可行解L1，且不等于L0，满足P(L0)<P(L1)，C(L0)>C(L1)L0L1小，花费却比L1大。非劣解（有效解4.目标空间：所有非劣解对应的目标函数集C(L)）T(L)≤30L0称为劣解，如果存在可行解L1，且不等于L0，满足P(L0)<P(L1)，C(L0)>C(L1)L0L1小，花费却比L1大。非劣解（有效解4.目标空间：所有非劣解对应的目标函数集C(L)）2、3、4步均是简单的比较和判定，完全可以找到多项式时间级的算法。1N≤30O()ndij——第ij我们可以得到dij的具体值，根据公式tijdijv可得到相应的tij式cijdijm可以得到相应的cij（ij=1，2，……，11（dij、tij和cij体数值见附录同样，通过对四川的一些旅行社进行咨询，我们得出家庭成员们们在第i个景点的最佳逗留时间和他们在第i个景点总消费：-11Matlab图 Matlab模拟6.511riji111rijMatlab图 Matlab模拟6.511riji111riji1Min-12（元6.611rijMini1rtt6.611rijMini1rtt1111ij i1j1rt i111（i，ji1 rij6.6.1Lingo6.70.51005的矩阵Aks1005（见附录。i——第i-13（单位：元重庆→成都→峨眉→绵阳→九寨沟→达州→都江由假设可知成都是成员肯定要游览的一个景点，因此10 =0.185 =0.217由假设可知成都是成员肯定要游览的一个景点，因此10 =0.185 =0.217 100100k1k1 =0.196 =0.206 100100k1k1 0.196 100k1LINGO7.7天（其9.4天。-14（3）rcc11rc+19011 i i1j1i1rcc（3）rcc11rc+19011 i i1j1i1rcc11111ij i1j1r m=（4）kSS{VG-SViSS{V使得到的权最小，SS{V中找到VitVit到Vit12.若GSG2°VV3.SHamiltoni 0 ，T=0 SS{V N*i0，T=T+中找到i1i1i0WWSS{V权（i1,i0）最小i1,i0+i1中找到Vit，使得N*S，在N*2.的边权最小，SS{VW1Tit,it1+3°，2°VV3.SHamiltoni 0 -15T假设Cv1v2vpv1是图GT假设Cv1v2vpv1是图GHamiltoni,j适合0i并且(vivj(vi1vj1)(vivi1(vjvj1HamiltonCi,jv1v2vivjvj1vi1vj1vpv1(原图删除两条边vivi1vjvj1用两条新边vivj和vi1vj1证明：WCi，jWC(vivi1(vjvj1(vivj(vi1vj10，故知jp4，设Cv1v2vp是顶点集v1v21°置k2°kk3°若kp3ji4°jjjn16°7°若(vivj(vi1vj1)(vivi1(vjvj18°Hamilton路修改为v1v2vivjvj1vi1vj1vp1°6.81.根据假设，整个旅游路线是环形，即最终成员要回到重庆，因此11即表示成员旅游的景点数，这里我们假定要旅游的景点数为i1=2，3，……，11-1611i12.0——1对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束：（i，j当i1时，因为重庆是出发点，所以rijj11i12.0——1对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束：（i，j当i1时，因为重庆是出发点，所以rijj1时，因为代表们最终要回到重庆，所以rij1rij（i，j同样，当ij2时，根据题意不可能出现rijrji1rij（i，j6.9rcc11rc+19011i i1j1i i1j1=100rtt1111ij i1j1rt i111i1 （i，j-176.9.1i——第ii——第i6.9.2mm6.9.1i——第ii——第i6.9.2mmmm2m2（上述四个量是假设两个组分别旅游的费用-18'' '' '' '' '' '''''' '''' '''' '''' '''' m3 m=m'+m''+m'+''－ rcc11111= ij im3 m=m'+m''+m'+''－ rcc11111= ij i1j1c i111mr'50 i111 m50 ''i11‰，r'cc11 m 50i1r''c1150m i1-196.1015天（120小时而这些时间包括在路途中的时间和在旅游景点逗留的时间。因为tij第i个景点到第j1111分别为r' ''t表示家庭成员们在第ii1i1r'tt6.1015天（120小时而这些时间包括在路途中的时间和在旅游景点逗留的时间。因为tij第i个景点到第j1111分别为r' ''t表示家庭成员们在第ii1i1r'tt11ij i1j1时间，故两组代表们在旅游景点的总逗留时间分别为r''t11 i1r'tt1111ij i1j1r't i1r''tt1111ij i1j1'' i111riji1=2，3，……，111111r i1i1③0——1对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束：rr r （i，j当i1时，因为成都是出发点，所以r1并且r -20当j1时，因为代表们最终要回到成都，所以r1并且r 1jrr r （i，jrrrr 当j1时，因为代表们最终要回到成都，所以r1并且r 1jrr r （i，jrrrr j同样，当i，j2时，根据题意不可能出现 1和 1，即 r' ''r（i，j 6.10.1 m=m'+m''+m'+''－ 11mr'50 i111 m50 ''i1r'c11500.95m i1r''cc11 m 50i1m1000.051c11c j1-21r'tt1111ij i1j1r't i1r''tt1111ij ir'tt1111ij i1j1r't i1r''tt1111ij i1j1'' i11111r i1i1rr r （i，jr rr jr' ''r（i，j c(n)min——家庭成员旅游nc(n)max——家庭成员旅游nl(n)min——家庭成员旅游nl(n)max——家庭成员旅游nV(V0,E0,W0) ViG0ij边ijijijG0(V0,E0,W0)L1L2L1L2V0。-22G0(V0,E0,W0)G0G0*(12（考虑费用权而非时间权，但道理如前G0(V0,E0,W0)G0*(V0,E0*,W0*)的权和G0(V0,E0,W0)G0G0*(12（考虑费用权而非时间权，但道理如前G0(V0,E0,W0)G0*(V0,E0*,W0*)的权和G0*(V0,E0*,W0*)V1,V2E,W)，令VV0EE0*E1,i,E2,i,i也就是原图中任意一个顶点均与V,V W0i3;ji, i,MWi,ji,j3W 6.10.236-23图 干线设计结构图 干线设计结构 Q1C2(C,L如上所述，12为权重且121)6.11 Q1C2出问题的准确解。通过进一步分析目标函数，发现路径最短问题可以直接转化1元/（公里*人）计算，因此只要把路程乘以空调旅游S车单位距离的车费就可得到路费。综上所述，我们可以把去某个景点的要花的路费和景点的门票价加起来作为该景点的旅游花费。然后用蒙特卡罗改进的模拟退火算法对问题进行求解。-24新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解始值无关，算法求得的解与初始解状态(是算法迭代的S起点)无关；模拟退火l收敛于全局最优解的全nn⋯,2,1。每一个景点都有可能会游览其他景