乘公交看奥运.doc

乘公交，看奥运摘要本文解决的是公交线路选择问题，根据查询者的各种不同需求，设计出一套线路选择的模型与算法。乘客一般希望自己乘坐的公交线路经济、方便、快捷，因此我们分别以总费用最小、总耗费时间最少以及总换车次数最少为目标，建立最优化模型。针对问题一：由于交通网络的复杂性，公交线路的选择问题不同于一般的图论问题，根据城市公共交通的自身特点，利用改进的扩散路由算法，可以实现在城市中任意两站之间的线路查询。乘客一般希望乘坐的公交路线能够经济、快捷、方便，因此可以分别以总费用最小、总耗费时间最少以及总换车次数最少为目标建立最优化模型，根据改进的扩散路由算法选择出分别以总费用最小、总耗费时间最少以及总换车次数最少为目标的最佳路线。如下表：出发站终点站S3359S1828S1557S0481S0971S0485S0008S0073S0148S0485S0087S3676最短耗时（min）1011061288310665最少转乘次数（次）121122最少费用（元）333232针对问题二：在问题一的基础上加入了地铁线路，算法与问题一一样，利用改进的扩散路由算法分别以总费用最小、总耗费时间最少以及总换车次数最少为目标建立最优化模型，根据改进的扩散路由算法选择出分别以总费用最小、总耗费时间最少以及总换车次数最少为目标的最佳路线。如下表：出发站终点站S3359S1828S1557S0481S0971S0485S0008S0073S0148S0485S0087S3676最短耗时（min）731061017092.538最少转乘次数（次）121120最少费用（元）333251针对问题三：在该问中，我们可以通过步行，从一个车站走到另一个车站，从而找到更省时间或更方便的乘车线路。而在我们知道了任意两站之间的步行时间后，从理论上讲所有车站之间可以通过步行来换乘车线路。但从实际出发，人的步行距离和时间是有可接受限度的，即不能走很长的距离和时间，因此我们要对步行时间加以限制。在设定最大步行时间限制的情况下， 分别以总费用最小、总耗费时间最少以及总换车次数最少为目标建立最优化模型。最后，我们利用GUI Design Studio软件设计出北京公交自主查询系统的GUI图形界面，并对仅考虑公汽线路的情况（问题一）和考虑公汽与地铁线路的情况（问题二）分别进行仿真，得到满足查询者各种不同需求的最佳线路。该公交自主查询系统实用性强，可以满足查询者的各种不同需求。关键字：改进的扩散路由算法、GUI图形界面、最优化模型、换车次数1.问题重述问题背景我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。公交线路及相关信息：【附录1】基本参数设定相邻公汽站平均行驶时间(包括停站时间)： 3分钟相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。【附录2】公交线路及相关信息 （见数据文件B2007data.rar） 本文需解决的问题有：问题一：仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S3676问题二：同时考虑公汽与地铁线路，解决以上问题。问题三：假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2.模型假设与符号说明2.1模型假设假设一：公汽线路间的换乘只能是在同一公汽站或是在对应的地铁站；假设二：查询者转乘公交的次数不超过两次；假设三：不考虑公汽线路出现拥堵的情况；假设四：从起点步行至通过地铁站相连的车站和从某站（通过地铁站与终点相连）步行至终点所花费的时间不计入总乘车时间。2.2符号说明表示第i条公汽线路编号表示第i条地铁线路编号（i=1,2）表示从起点站到终点站耗费的总时间表示相邻公汽站平均行驶时间表示相邻地铁站平均行驶时间表示公汽换乘公汽换乘次数表示地铁换乘地铁换乘次数表示地铁换乘公汽换乘次数表示公汽换乘地铁换乘次数表示总换车次数表示总费用表示选择的交通方式（其中=1表示单一票价的公汽；=2表示分段计价的公汽；=3 表示地铁）表示乘坐第i辆公汽需要经过的站点个数表示乘坐第i列地铁需要经过的站点个数表示乘坐第i辆车的费用表示步行的最大时间限制表示步行经过的公汽站点的个数表示步行经过的地铁站点的个数3.问题分析本文研究的是公交线路的选择问题。某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统，以满足查询者的各种不同需求。为了设计这样一个系统，其核心是线路选择的模型与算法。需求分析：要开发此公交线路选择的自主查询计算机系统至少需要满足以下要求：第一，模型的算法要利于程序的实现和在现实中的推广应用。即用户输入起始站和终到站两个参数后要在尽量短的时间内得到最佳的公交线路走法。第二，要满足查询者的各种不同需求。所谓“不同需求”一是乘公交的时间要尽量少，二是车费要尽量少，三是转车次数要尽量少；因此我们认为，算法简单易行是本文建立模型的最重要标准。算法分析：如果将整个城市看成一个连通图，图中的顶点代表公交站点，边代表公交线路，边的权值为相应点间隔的车站数，问题则等价于求赋权图中两点间的最短路径。求任意两顶点之间的最短路径算法很多，最经典的是Dijkstra算法，在地理信息系统中得到广泛应用。但是，Dijkstra算法难以应付公交线路网络中的复杂性。根据城市公共交通的自身特点，考虑到便携设备本身存在的缺陷，如CPU运算速度低，内存容量小等，不宜采用Dijkstra算法，而改进利用扩散路由算法，实现在城市中任意两站之间的线路查询。针对问题一：首先，数据处理。由于公汽线路的类型是有差别的，按票价信息分为：单一票制和分段计价；按线路的循环模式分为：单线（分为上下行不一致的型和上下行一致的型两种）、环线（设为型）和按原路返回（设为IV）。其中可将按原路返回的线路（IV）归为上下行一致的II型（原序作为上行，倒序作为下行），这样就将线路分为两类：单线和环线。将公汽线路编号11040存入三维细胞元组中，并作出所有公汽站点的关联矩阵。其次，选择算法。公交线路的选择问题不同一般的图论问题，根据城市公共交通的自身特点，改进利用扩散路由算法，可以实现在城市中任意两站之间的线路查询。最后，模型确定。乘客一般希望乘坐的公交路线能够经济、快捷、方便，因此可以分别以总费用最小、总耗费时间最少以及总换车次数最少为目标建立最优化模型，根据改进的扩散路由算法选择出分别以总费用最小、总耗费时间最少以及总换车次数最少为目标的最佳路线。针对问题二：在问题一的基础上加入了地铁线路，并且与地铁站相邻的公汽站点可以通过地铁站步行达到。算法与问题一相似：首先，考虑是否有直达的情况，如果可以直达则考虑起点站与终点站是否与统一地铁线路相邻，相邻则坐地铁直达，不相邻则坐公汽直达；其次，考虑换一次车的情况，有四种可能：公汽换公汽、公汽换地铁、地铁换地铁、地铁换公汽。如果起点站与终点站都不与地铁相邻则为第一种可能，如果起点站不与地铁相邻而终点站与地铁相邻则为第二种可能，如果起点站与终点站都与地铁相邻则为第三种可能，如果起点站与地铁相邻而终点站与地铁不相邻则为第四种可能；最后，考虑换两次车的情况，有六中可能：公汽换公汽再换公汽、公汽换地铁再换公汽、公汽换地铁再换地铁、地铁换公汽再换公汽、地铁换公汽再换地铁、地铁换地铁再换地铁。根据上面讨论将各种可能加入到算法中实现。针对问题三：在该问中，我们可以通过步行，从一个车站走到另一个车站，从而找到更省时间或更方便的乘车线路。而在我们知道了任意两站之间的步行时间后，从理论上讲所有车站之间可以通过步行来换乘车线路。但从实际出发，人的步行距离和时间是有可接受限度的，即不能走很长的距离和时间，因此我们要对步行时间加以限制。在设定最大步行时间限制的情况下， 分别以总费用最小、总耗费时间最少以及总换车次数最少为目标建立最优化模型。4.数据处理4.1数据存储数据的处理是和我们的模型与算法密切相关的，即有什么样的模型算法就对应着特定形式的数据处理。根据上面对问题的分析，在解决该问题的过程中，我们要找的最佳路线，是通过搜索出所有可能线路对应的目标值、然后比较目标值得到的。而搜索的对象就是跟优化目标密切相关的关联矩阵。我们通过以下的方法进行数据处理：把“1.1 公汽线路信息.txt”、“2.1 地铁T1线换乘公汽信息.txt”和“2.2 地铁T2线换乘公汽信息.txt”三个文本文件导入到Matlab中，成为细胞元矩阵；公汽线路编号票价信息上行线信息下行线信息L001分段计价S0619-S1914-S0710L002分段计价S3748-S2160-S0004S0004-S1968S2160-S3748L519分段计价S0036-S0203S3414S3414-S1462-S0203-S0036L520单一票制1元S0600-S2861-S1848S1848-S2645-S2027-S06004.2数据处理公汽线路的类型是有差别的：一按票价信息分为：单一票制和分段计价，两种线路有不同的收费方法。二按线路的循环模式分为：单线（分为上下行不一致的型和上下行一致的型两种）、环线（设为型）和按原路返回（设为IV）。其中可将按原路返回的线路（IV）归为上下行一致的II型（原序作为上行，倒序作为下行），这样就将线路分为两类：单线和环线。针对问题一：我们将公汽线路11040进行编号，把公汽线路信息表做成如下的结构数组“公汽线路信息数组”data_1：公汽线路编号票价信息线路信息001分段计价S0619-S1914-S0128-S0710002分段计价S0710-S0128S1914-S0619003分段计价S3748-S2160-S1968-S0004004分段计价S0004-S1968S2160-S37481037分段计价S0036-S0203-S1462-S34141038分段计价S3414-S1462-S0203-S00361039单一票制1元S0600-S2861-S2645-S18481040单一票制1元S1848-S2645-S2027-S0600公汽线路编号对应的公汽线路为：针对问题二：将地铁线路T1分为上下行（原序作为上行，倒序作为下行），这样地铁线路T1为单线，地铁线路T2为环线。将地铁线路T1、T2编号10411044存入公汽线路的三维数组中，并作出所有公汽站点和地铁站点的关联矩阵。把公汽地铁线路信息表做成如下的结构数组“公汽地铁线路信息数组”data_2：公汽线路编号票价信息线路信息001分段计价S0619-S1914-S0128-S0710002分段计价S0710-S0128S1914-S0619003分段计价S3748-S2160-S1968-S0004004分段计价S0004-S1968S2160-S37481037分段计价S0036-S0203-S1462-S34141038分段计价S3414-S1462-S0203-S00361039单一票制1元S0600-S2861-S2645-S18481040单一票制1元S1848-S2645-S2027-S06001041单一票制3元D01-D02-D03-D22-D231042单一票制3元D23-D22-D21-D02-D011043单一票制3元D24-D25-D26-D39-D241044/END公汽-地铁线路编号对应的公汽-地铁线路为：5.问题一的解答针对问题一：尽考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。5.1算法的设计扩散路由算法设计【1】设城市的所有公交线路，记为其中表示第i号公交线路的线路名，记为，其中表示i路公交车线路上的第j站名称。因此，假设公交存在如下线路(暂只考虑单程)：则其中每行代表一路公交，任一站的全部后续站为它所能直接到达的站，如图1所示，在连通图中表现为邻结点。路由扩散算法具体的实现是将每一个分组将被发送到除了它进来的那条线路以外的每一条输出线路上。公交网络中可直达的站类似网络中的邻接点，在R中表现为同一行的后继元素。图一 从A点开始依次可到达的站点查询从起点X开始，扩散到除了它过来的那个站点以外的每一个站点上，然后判断这些站点中是否包括终点Y，否则再从每个扩散到达的站点继续扩散，逐步扩展以X为基点的网络，一直找到Y为止。扩散深度越大，运算也越复杂，因此深度一般不超过4，即换乘3次。而现实中如果一个城市的公交足够发达，线路设置较合理的话，极少有换乘超过3次的情况。很显然，扩散法将会产生大量的重复分组，实际上，需要采取一种办法来抑制扩散过程，否则将有大量无效重复的运算。选择性扩散是很重要的，在换乘时，问题很突出的表现出来。假设线路Routel，Route2和Route3如上，且其它任何线路均不经过C地。考察从B地出发去往F地，易知，需要换乘一次。由于FlB=C，D，G，H)(其中FlB的l表示扩散深度，对应乘车的次数，B为扩散点)。因此C，D，G，H均可能成为换乘地点，但经过C的公交线路集Rc=Routel，而经过B的线路集=Route1，Route3，即换乘无意义。因此扩散只进入D，G和H，到C后应给予抑制，防止进入下一层的扩散。最后，线路集合中经过结点数最少、总权值最小的路径，即X到Y的最佳路径。算法实现：Step1:确定起始站X()与终点站Y（），并将其输入系统中;Step2:由X在Li中开始扩散，逐个查找其对应元素所在行的后续元素：当，i=j则为Li线路上的直达站，集合记为F1X=x1(Dx1), x2(Dx2), x3(Dx3).(其中F1X的1为扩散深度，X为扩散点，Dx1为X到x1间隔站数，xm多次存在，只保留Dxm值的最小者)。Step3:Y是否属于集合F1X中？如果是，则说明X到Y可以直达，不需换乘，直接转到Step6步执行；否则，执行Step4。Step4：选择集合F1X换乘有意义的站，逐个作为顶点在扩散，访问它们除X以外每个元素。Step5:Y是否属于集合F2X中？如果是，说明X到Y乘两次（换一次车）可以到达，直接转到Step6步执行；否则，进行进一步扩散到深度为3的顶点（换二次车）。Step6：将满足条件的线路（可能不止一种）优化并输出结果，结束运算。算法的具体流程图如下（图5.1）：图5.1 算法流程图5.2模型一的建立为了满足不同查询者的各种不同需求，我们分别以总费用最小、总耗费时间最少以及总换车次数最少为目标建立最优化模型。（1） 以总费用最少为最优路线的模型： 目标函数为： （2） 以总耗费时间最少为最优路线的模型：总时间等于公汽行驶时间与公汽换乘时间之和目标函数为：（3） 以总换车次数最少为最优路线的模型：目标函数为：5.2模型一的求解根据以上算法和前面建立的模型一（不考虑地铁站换乘），用matlab进行编程（程序见附录一）就可以得出不同目标下的最优路线。（1）以耗时最少为目标的最优路线起始站S3359到终到站S1828耗时最少为101min；起始站S1557到终到站S0481耗时最少为106min；起始站S0971到终到站S0485耗时最少为128min；起始站S0008到终到站S0073耗时最少为83min；（注：其耗时最少的路线有13条）起始站S0148到终到站S0485耗时最少为106min；（注：其耗时最少的路线有3条）起始站S0087到终到站S3676耗时最少为65min；其耗时最少的最优路线如表5.1所示。起始站到终点站最佳线路车费/元时间/min换车次数3101131062312812831310622651（2）以费用最少为目标的最优路线起始站S3359到终到站S1828费用最少为3元；起始站S1557到终到站S0481费用最少为3元；起始站S0971到终到站S0485费用最少为3元；起始站S0008到终到站S0073费用最少为2元；起始站S0148到终到站S0485费用最少为3元；起始站S0087到终到站S3676费用最少为2元；其费用最少的最优路线如表5.2所示。起始站到终点站最佳线路车费/元时间/min换车次数3101131062312812831310622652（3）以换车次数最少为目标的最优路线起始站S3359到终到站S1828换车次数最少为1次；起始站S1557到终到站S0481换车次数最少为2次；起始站S0971到终到站S0485换车次数最少为1次；起始站S0008到终到站S0073换车次数最少为1次；起始站S0148到终到站S0485换车次数最少为2次；起始站S0087到终到站S3676换车次数最少为2次；其换车次数最少的最优路线如表5.3所示。起始站到终点站最佳线路车费/元时间/min换车次数31011311223128138313106226525.3模型的评价再次考虑换乘次数与时间、车费等因素对最佳线路的影响：对于所给六组数据，分别以时间和车费为优化目标的最佳线路完全相同。这说明省时和省钱原则在公汽线路选择上的一致性。换乘一次的方案（如果存在的话）相比较换乘两次的方案，所用时间普遍较多、而所用费用却稍微偏低。这说明对于一个线路和站点很多、较发达的公交系统来说，换乘次数增加只是感觉上比较麻烦，而实际上由于及时调整了线路，整体上可以节约大量的时间，当然相对应的，由于多乘了若干次车，车费就会增加。但总体来说时间上的差异是主要的。6.问题二的解答问题二：同时考虑公汽与地铁线路，解决以上问题。6.1模型二的建立为了满足不同查询者的各种不同需求，我们分别以总费用最小、总耗费时间最少以及总换车次数最少为目标建立最优化模型。（1）以总费用最少为最优路线的模型： 目标函数为： （2） 以总耗费时间最少为最优路线的模型：总时间等于公汽和地铁的行驶时间与公汽换乘时间和地铁换乘时间之和目标函数为： （3） 以总换车次数最少为最优路线的模型：目标函数为：6.2模型二的求解根据以上算法和前面建立的模型一（不考虑地铁站换乘），用matlab进行编程（程序见附录一）就可以得出不同目标下的最优路线。（1）以耗时最少为目标的最优路线起始站S3359到终到站S1828耗时最少为73min；起始站S1557到终到站S0481耗时最少为106min；起始站S0971到终到站S0485耗时最少为101min；起始站S0008到终到站S0073耗时最少为70min；起始站S0148到终到站S0485耗时最少为92.5min；起始站S0087到终到站S3676耗时最少为38min；其耗时最少的最优路线如表5.1所示。起始站到终点站最佳线路车费/元时间/min换车次数373231062510123702592.523380（2）以费用最少为目标的最优路线起始站S3359到终到站S1828费用最少为3元；起始站S1557到终到站S0481费用最少为3元；起始站S0971到终到站S0485费用最少为3元；起始站S0008到终到站S0073费用最少为2元；起始站S0148到终到站S0485费用最少为5元；起始站S0087到终到站S3676费用最少为1元；其费用最少的最优路线如表5.2所示。起始站到终点站最佳线路车费/元时间/min换车次数3101131062312812831592.521460（3）以换车次数最少为目标的最优路线起始站S3359到终到站S1828换车次数最少为1次；起始站S1557到终到站S0481换车次数最少为2次；起始站S0971到终到站S0485换车次数最少为1次；起始站S0008到终到站S0073换车次数最少为1次；起始站S0148到终到站S0485换车次数最少为2次；起始站S0087到终到站S3676换车次数最少为0次；其换车次数最少的最优路线如表5.3所示。起始站到终点站最佳线路车费/元时间/min换车次数3101131062312812831592.5233806.3模型二的评价7.问题三的解答问题三：假设知道所有站点之间的步行时间，建立一个任意两站点之间线路选择问题的数学模型。7.1模型三的建立在该问中，我们可以通过步行，从一个车站走到另一个车站，从而找到更省时间或更方便的乘车线路。在问题一和问题二中，只能由本车站通过地铁站换乘。而在我们知道了任意两站之间的步行时间后，从理论上讲所有车站之间可以通过步行来换乘车线路。但从实际出发，人的步行距离和时间是有可接受限度的，即不能走很长的距离和时间。因此我们要对步行时间加以限制，假设步行的最大时间限制为假设所有相邻公汽站点的距离相等，乘客在相邻公汽站点之间的步行时间为，则步行的站点个数最多为假设所有相邻地铁站点的距离相等，乘客在相邻地铁站点之间的步行时间为，则步行的站点个数最多为是否选择步行方式的函数： （1）以总费用最少为最优路线的模型： 目标函数为： （2） 以总耗费时间最少为最优路线的模型：总时间等于公汽行驶时间、地铁行驶时间、公汽-地铁换乘时间与步行时间之和目标函数为：（3） 以总换车次数最少为最优路线的模型：目标函数为：8. 公交自主查询计算机系统仿真对于北京公交自主查询计算机系统我们利用GUI Design Studio软件设计出北京公交自主查询系统的GUI图形界面（图8.1），并对仅考虑公汽线路的情况（问题一）和考虑公汽与地铁线路的情况（问题二）分别进行仿真。图8.1北京公交自主查询系统的GUI图形界面由于乘客的年龄段不同、喜好不同，选择的公交乘坐方式也不尽相同。年轻人充满激情，喜好用时少、快捷的乘坐方式；中年人如上班族时间紧、工作繁忙，喜好用时少、换车次数少快捷方便的乘坐方式；老年人腿脚不方便，比较经济节约，喜好费用少、换车次数少的经济快捷的乘车方式。北京公交自主查询系统的使用方法：首先，查询者输入自己所在的起始站以及想要到达的终点站，并且选择是否包含地铁站（如果不包含地铁站则是问题一的模型，如果包含地铁站则是问题二的模型）；其次，查询者根据个人的喜好不同，选择乘坐方式，有快捷、经济、方便可供选择（单选，这里不考虑多选的情况，因为最后输出中计算机会根据另外两个指标在多种线路中选择最优路线）；最后，系统将为查询者提供一条最佳线路，并输出这条线路的所需时间、换车次数以及所欲费用。该公交自主查询系统可以得到满足查询者各种不同需求的最佳线路，实用性强。9.模型的优点与缺点模型的优点：（1） 模型一和模型二在假设换车次数不超过两次的情况下，得到直通、换车一次和换车两次从起点站到终点站的所有路线，通过三个目标函数分别确定其最优路线；（2） 模型充分考虑了不同查询者的各种不同需求，具有实用性和可推广性；（3） 模型的算法并不复杂，公交自主查询计算机系统可以在很短的时间内得到满足查询者需求的最佳线路。模型的缺点：（1） 模型只考虑了换车不超过两次的情况，但很有可能换车三次可以达到更优的解；（2） 模型不能得到综合快捷、经济、方便的最优路线，只能得出在一种或两种指标下的最优路线。（3） 模型没有考虑线路上拥堵的情况，而实际生活中拥堵程度会影响乘客的选择。10.模型的改进与推广本文的背景是北京奥运会，届时有大量的观众到现场观看比赛，大部分观众为国内外旅客，他们想要乘坐的交通线路可能并不是以快捷、经济、方便为主，而是更多的偏向于乘坐的路线能够经过更多的景点，可以在乘车之余浏览北京的著名景区。针对这种情况，我们可以在每条公汽线路上赋上权值，表示经过的景点数，将北京公交网表示成有向赋权图，用一种映射关系将车站附近的景点相联系，在游客查询他所到目的地的乘车路线时，将路线所经过的站点与景点一起显示在公交自主查询计算机系统的界面，供游客根据个人偏好选择最理想的路线。11.参考文献【1】龚 翱，朱宁波，史长琼，袁辉勇 基于便携设备的城市公交线路查询算法的研究 2008年12月【2】gui design studio教程/view/6d85a62f0066f5335a812158.html12.附录附录一 问题一的总程序注：将1.1公汽线路信息txt文件导入到matlab中（在Import Wizard中将Text header lines中的3改为3000），文件名改为data，导出到桌面，然后运行下面的程序。function vv(start,aim)%d=importdata(d:我的文档桌面matlab.mat);fee d=data();if numel(find(d=start)=0 fprintf(The path cannot be found!); else row col=find(d=start); for i=1:numel(row) rows cols(i,1:2)=find(d(row(i),:)=start); end F=creatF(start,row,cols,d);endif ismember(aim,F(:,2) num=find(F(:,2)=aim); line=round(F(num,3)-0.5); long=F(num,1)-1; time=3*F(num,1); value=val(0,F(num,:),fee); updown=ud(F(num,3); n=start,updown,line,aim,long,time,value; print(n);else size_F=size(F); cha=1; Fc=; n=; for i=1:size_F(1) row1 col1=find(d=F(i,2); rows cols=find(d=start); row1=setdiff(row1,rows); if numel(row1)0 for j=1:numel(row1) col1(j,1:2)=find(d(row1(j),:)=F(i,2); end F1=creatF(F(i,2),row1,col1,d); Fc=Fc F1; if ismember(aim,F1(:,2) num1=find(F1(:,2)=aim); line1=round(F(i,3)-0.5); mid1=F(i,2); long1=F(i,1)-1; line2=round(F1(num1,3)-0.5); long2=F1(num1,1)-1; time=3*(F(i,1)+F1(num1,1)+5; value=val(0,F(i,:),fee); value=val(value,F1(num1,:),fee); updown1=ud(F(i,3); updown2=ud(F1(num1,3); n(cha,:)=start,updown1,line1,mid1,long1,updown2,line2,aim,long2,time,value; cha=cha+1; end end end if cha=1 fprintf(The path with once chang cannot be found!n); sizec=size(Fc); kind=1; for j=1:sizec(2) siz=size(Fcj); Fj=Fcj; for k=1:siz(1) row2 col2=find(d=Fj(k,2); rows cols=find(d=Fj(1,2); row col=find(d=start); row2=setdiff(row2,rows); row2=setdiff(row2,row); if numel(row2)0 for l=1:numel(row2) col2(l,1:2)=find(d(row2(l),:)=Fj(k,2); end F2=creatF(Fj(k,2),row2,col2,d); if ismember(aim,F2(:,2) num2=find(F2(:,2)=aim); num1=find(Fj(:,2)=F2(1,2); num=find(F(:,2)=Fj(1,2); line1=round(F(num,3)-0.5); line2=round(Fj(num1,3)-0.5); line3=round(F2(num2,3)-0.5); mid1=F(num,2); mid2=Fj(num1,2); long1=F(num,1)-1; long2=Fj(num1,1)-1; long3=F2(num2,1)-1; time=3*(long1+long2+long3+3)+10; value=val(0,F(num,:),fee); value=val(value,Fj(num1,:),fee); value=val(value,F2(num2,:),fee); updown1=ud(F(num,3); updown2=ud(Fj(num1,3); updown3=ud(F2(num2,3); n(kind,:)=start,updown1,line1,mid1,long1,updown2,line2,mid2,long2,updown3,line3,aim,long3,time,value; kind=kind+1; end end end end if kind=1