公共自行车调度问题-数学建模论文.doc

. -目录一、问题引入3二、问题分析32.1第一问分析42.2第二问分析42.3第三问分析4三、模型假设和符号说明53.1模型假设53.2符号系统6四、模型建立64.1模型分类64.2 租赁点分配方案建模74.3 调度车调度方案建模8一辆调度车调度方案8多辆调度车调度方案94.4租赁点数目和位置确实定114.5 调度时间的模型12五、模型的求解135.0经纬度转换为横纵坐标135.1 求解最短路径135.2 模型一次运行后的单车重分配求解145.3 求解分配方案的预估校正算法165.4 求解调度方案的启发式算法16算法简介16算法容17约束条件18算法流程图195.5租赁点位置205.6计算结果20第一问结果20第二问结果21第三问结果23六、模型检验26七、模型优缺点以及改良267.1分配方案的优点277.2调度方案的缺优点277.3新增节点模型的优缺点277.4模型和算法的改良28算法的改良28模型的改良28八、参考文献30附录30一、问题引入近年来，随着经济的开展，我国各级城市的机动车保有量都进入了持续高速增长时期，但由此所引发的道路拥堵、空气污染也引起了政府以及百姓的极大关注。众所周知，建立快速、便捷的城市公共交通体系是解决这一问题的有效手段之一。然而，居民居住地和交通站点通常都有一段距离，这段不远的距离以及现实存在的公共交通拥挤现象那么使居民乘坐公共交通的意愿降低，而将公共自行车租赁效劳系统纳入城市公共交通体系，能够从一定程度上缓解这一现象。市经济开发区公共自行车效劳系统于2011年4月开场建立，到目前为止，已建成租赁点30个，自行车总量到达850辆。目前正在筹备第三期建立，请你针对如下问题建模：1根据目前经开区网点自行车需求情况等信息，要求调度平均耗时尽量少，针对已有的30个租赁点设计最优车辆分配方案、调度方案，给出完成调度所消耗的时间。2假设经开区公共自行车效劳系统三期建立准备投入建立经费200万元，据此建立数学模型，确定新增租赁点数目、位置以及适宜的放置车辆数目。3针对问题2，进一步研究，如果要求在150min完成调度，确定是否需要增加调度车辆购置调度车辆费用由其它工程经费解决，不包含在三期建立提供的200万元经费中间，并给出该情形下的自行车调度方案。二、问题分析首先，题目给出的初始条件为经度和纬度，我们利用地球的坐标系统将其转换为平面坐标，后续的计算都在平面坐标的根底上进展。2.1第一问分析第1问对对应前两期工程，30个租赁点，因此在的点上根据需求量确定自行车的分配方案和调度方案。这个问题是在节点具体的位置的条件下求解两个问题：每个节点的自行车分配问题和调度问题。这两个问题可以分开来求解。第(1)问要求调度时间尽量少，我们从计算两点的最短路径入手，将最短路径计算出后考虑将早中晚三个时间段的顶峰期取平均值后再最初计算。我们建立反比例函数关系式：p=Kd，再根据归一化条件求得2km的概率系数K。随后，算出每个点以需求量的数目的前提下会向2km的各个租赁点送出多少辆单车，并以负反应的方式经屡次计算得出一个稳定解，即大局部租赁点的单车数量满足110%的要求，少局部租赁点单车数目远远超出需求量，还有少局部单车数目几乎为零奇点。最后，将计算所得的几个奇点分块，从单车数量超出40或大量超出需求量的地点运送单车至奇点并计算运送时间。2.2第二问分析第2问对应第三期工程，根据投入的建立费用等确定新增的租赁点的数目和每个租赁点的分配方案。这些新增的租赁点是在规定的70个点中选取的，而且每个待选点的需求量是给定的，因此在需求量和工程费用的限制下，现效劳系统最优的选点方案和分配方案。建立新的一定数目的租赁点，我们首先将另外70个点的数据列出，考虑到是否选择一个点与这个点的平均需求量和最大需求量均有关，所以将早中晚三个时间段的需求量的平均值和三个时间段需求量的最大值列出，然后将这两个数据以一定比例加权平均，最后得出的数字排序，由上到下计算出每个点的需求金额，截止到2000000元时。租赁点即为截止前的点，相对应的数目即为每个点对应的数目。2.3第三问分析第3问建立在第2问的根底上，同第1问，类似，在解第3问前，租赁点的具体位置和需求量了，并且，这些租赁点的分配方案也已将求得，很容易求得每一个租赁点需要调度的具体数值，在这些条件下，要求在给定时间完成调度，给出调度方案。如调度车辆不够，那么给出增加的车辆数目和调度方案。问题类似于第1问的给出分配方案后求调度的问题。根据以上分析，我们要解决的问题主要有以下几个局部：1、求出任意两个租赁点之间的最短路径。2、求出给定租赁点的分配方案。3、求出给定租赁点的系统的自行车调度方案。4、在给定约束下求租赁点的数目和位置。解决以上三个问题，此题所要求的问题就可以解决了。三、模型假设和符号说明3.1模型假设1、每个租赁点调度需求量为负，有多余的自行车可以提供应调度车那么为正数；2、假设两个停车场就在某两个租赁点上，那么选取的两个租赁点必须是有自行车盈余的点，并且调度车出发后，车上装载的自行车的数量就是租赁点的调度量。由于每个租赁点的自行车最大分配量小于调度车的最大装载量，所以总是能够将盈余量全部装在调度车上；3、每辆调度车从固定的某租赁点出发，最后又回到原来的点，以方便下次调度但是回到原点的时间可以不计。因为只有在调度完成后才会回到原点，此时不需要调度，不再受时间限制；4、同一辆调度车只能经过同一个租赁点一次除了作为车站的租赁点；5、每次到达下一个租赁点时，调度车上的自行车数量满足该租赁点需求，即对于需求点来说，只需用调度一次就完成调度；对于盈余点来说，调度车到达这些点要尽量多装。如果未到达调度车的限量就将该租赁点所有的盈余自行车装载，如果多出，那么装满。3.2符号系统G-租赁点的集合-调度总时间不包括完成调度后调度车返回原点的时间。-调度车编号-租赁点间的最短距离-第k辆车调度完i后是否再调度j-是否使用调度车k-租赁点j的需要调度的量-i和j间的距离是否大于M千米-t时间段租赁点j的需求量-j点的需求量占总需求量的比例-从i点出发到达j租赁点的自行车数量-i点的单车数量a-建立一个租赁点耗资b-维护每辆自行车耗资p-每一个租赁点的耗资数P-新增租赁点的耗资总数四、模型建立4.1模型分类在租赁点的分配方案确定后，只剩下调配问题，属于VRP问题，该问题是著名的问题TSP旅行商问题的一个特例，因而也是NP-hard问题。典型的VRP模型定义如下：假设客户网络中的客户数量、客户所在的位置、客户需求和配送车辆的最大负荷，要求在满足约束的前提下为给定的中心仓库设计车辆路径，使运输本钱最小。传统电子商务配送模型是分区域配送模式的单一配送中心Distribution centre ,DC-多需求点demands , DS的路径优化模型，而且不考虑沿途补货的情况。而针对区域广泛、客户众多且分散、业务量大且频繁的电子商务物流配送业务，需要考虑多个配送区域联合、沿途屡次补货的配送策略，从而得到电子商务配送的跨区域VRP模型。这个思路和我们所要考虑的利用公交车收集和分配公共自行车很类似，问题中有多余自行车的租赁点即可看作电子商务问题中的配送中心DC，而缺少自行车的租赁点也可看作是需求点DS。我们的问题和电子商务问题的一个不同点是，在调度时，如果调度点由盈余的自行车且数量加上调度车上已有的自行车时其总量会可能会超过调度车的最大装载量，因此有可能导致这些点的二次调度，这和电子商务配送模型中一次性完成调度有所区别，但是可以经过是党的改正后得到正确的模型。4.2租赁点分配方案建模影响租赁点自行车分配的因素有：各租赁点的需求量、从租赁点离开的自行车、从其他租赁点起来的自行车等。假设仅考虑需求量对租赁点分配自行车数目的影响，有如下模型：1式确定按照最终的需求量，以按比例分配的方式确定租赁点的分配量。2式给出需求量占总需求量的比例。以仅考虑需求量的方式确定的分配方式显然不是最正确方案。分配方案还和租赁点之间的距离有关。由题意可知，从在某个租赁点还车的概率与租车点和还车点的距离成反比，且假设居民的骑行距离不超过M km，由此可得出下式：式4-2-3首先按照4-2-1式的方式产生一组分配方案，然后让其按照自行车间行驶的规那么再次分配，产生新的一组分配方案，然后用4-2-4式校正，最终得到优化了的分配方案。4.3 调度车调度方案建模4.3.1一辆调度车调度方案在我们的求解问题中，第一问中调度车辆问2辆，为了问题是建模化简，我们先考虑调度车为一辆的情况，然后推广到多量的情况，这样就可以给对第一问和第三问的调度问题建立实际的解题模型。设拥有最大负荷为Q的调度车从指定的节点出发，对集合为G的节点进展调度。完成任务后返回原点。调度需求量和租赁点间的距离已经求得。整个调度方案可以由以下一组方程和约束条件确定：4-3-1式为目标函数，求出最短距离；4-3-2确定了出发点，即必须从出发点出发，然后再回到出发点；4-3-3-4-3-4确定了调度车对特定节点只能调度1次，不能重复经过一个节点；4-3-5式保证调度车调度时调度车上的数量能够满足任意节点的调度需求量，同时装载量不能超过调度车的最大载重；4-3-6式确定了某一节点的总需求量就是从该租赁点离开去往其他租赁点的自行车的数量之和；4-3-7式确定了每一节点的调度量；4-3-8式给出总需求量、分配量、调度量从该节点出发的自行车数目和到达该节点的自行车的数量之间的关系。4.3.2多辆调度车调度方案设拥有最大负荷为Q的k调度车从指定的节点出发，对集合为G的节点进展调度。完成任务后返回原点。调度需求量和租赁点间的距离已经求得。整个调度方案可以由以下一组方程和约束条件确定：3-4-9式为目标函数，求出最短距离；3-4-10式确定调度车的数目；3-4-11确定了出发点；3-4-12-3-4-13确定了每辆调度车对特定节点只能调度1次，不能重复经过一个节点；3-4-14式保证每次调度时调度车上的数量能够满足任意节点的调度需求量，同时装载量不能超过调度车的最大载重；3-4-15式确定了某一节点的总需求量就是从该租赁点离开去往其他租赁点的自行车的数量之和；3-4-16式确定了每一节点的调度量；3-4-17式给出总需求量、分配量、调度量从该节点出发的自行车数目和到达该节点的自行车的数量之间的关系。3-4-18式保证不同的调度车不能再同一时刻到达同一个租赁点。根据以上一组方程和约束条件，就可以将调度问题相对完整的描述出来。这是一个优化问题，在求解过程中由众多的算法可以采用，但是考虑到算法的复杂性可标称的简洁性，我们采用的算法是启发式算法，这将在模型求解中详细讨论。4.4租赁点数目和位置确实定题目中新增的租赁点是在的假设干点中选取的，因此，分析清楚选取租赁点的约束条件，就可以从最优解的角度得到新增的节点。建立租赁点时首先考虑的是各个点的需求量，由于在不同时段的需求量不同，所以应当考虑平均需求、不同时段需求。所以首先我们应当确定加权平均比例，一保证确定的租赁点在全天到达最优。在这里引入一个加权平均比，取决于我们实际问题的要求和调度问题的特点。首先将数据加权平均，有：再将每一个租赁点的耗资数额按照公式4-4-1求出最后将耗资数额加和，即求得满足式5-2-2的最大k值。考虑了需求量对新租赁点的影响之后，我们还需要考虑骑行规律对租赁点选取的影响。所谓运输规律就是：居民可以在任意一个租赁点还车，在某个租赁点还车的概率与租车点和还车点的距离成反比，且假设居民的骑行距离不超过M。于是仅考虑运输规律，我们引入一个方便因数，定义如下：Con用来衡量新设置的租赁点的合理程度，它与租赁点的分配量、常数、的乘积之和有关，其中，常数的定义如下：的定义如下：表示i租赁点能够到达其他节点的数目之和，越大说明该节点的辐射能力越强，也越合理。在路程不超过M的围，租赁点i能够到达的节点越多，那么常数越大。还要保证新增的节点数k尽可能地少。在新增租赁点的过程中不考虑随后的调度方案，因此在总建立经费的限制下，可以按照优化的方法求出方便因数的最小值。4.5 调度时间的模型 在三期建立中，为了实现经开区更大的网点覆盖面积，进一步增设站点，新增了一批租赁站点并购进自行车。然而，更多的站点可能会导致局部租赁点的自行车短缺或堆积现象，从而降低了资源利用效率。为了探讨这个问题，我们必须对现有调度方案进展检验和矫正，更好的实现资源利用最大化。故对调度时间进展了计算，发现用两辆调度车进展自行车调度很难满足调度需求,调配时间超过限制时间，必须购置更多的调度车辆，虽然会增加一定本钱，但对整体的统筹有很大的意义。 将原有的站点与新增站点进展混合，重新根据密集度，自行车需求量等因素进展分组，根据分组情况配备调度车辆。假设所分组数增多，那么增加调度车辆的数目可以更快捷地实现调度需求。然后对每一组的调度方案进展独立分析，即求解那么总调度时间：k代表组数具体建模思想与第一问的求解相似。五、 模型的求解5.0经纬度转换为横纵坐标5.1 求解最短路径思想描述：我们将最短路径的计算作为一个函数。而经过讨论我们决定计算采用Floyd-Warshall计算方法以下简称Floyd算法。Floyd算法是以动态规划为手段，以解决任意两点间的最短路径为目的的一种算法,该算法的时间复杂度为，空间复杂度为。它可以正确处理有向图或负权的最短路径问题，故该方法适用于我们的问题(在实际算法中，为了节约空间，我们直接在原来空间上进展了迭代，这样空间可降至二维)。Floyd算法的描述如下：设为从i到j的只以集合中的节点为中间节点的最短路径的长度。假设最短路径经过点k，那么；假设最短路径不经过点k，那么。因此，。if () 综上,最短路径矩阵为：单位：km图5-1-15.2 模型一次运行后的单车重分配求解依据题意不难得知，在租赁点还车的概率与租车点和还车点的距离成反比，且居民的骑行距离不超过2km。据骑行距离此可得出筛选算法：k=1; if if elsek=k+1;根据反比例关系不难得出每个租赁点向2km的各个租赁点发送的单车数量为：根据归一化条件：综上可得出求得2km的概率系数K的算法：s=0;if ;；K=K s;根据各个租赁点发送出的单车概率可求得运行一次后的各个租赁点单车数目：据此可得出求解运行一次后的各个租赁点单车数目的算法：t=0;if ；;模型运行一次后的结果如下图：图5-2-15.3 求解分配方案的预估校正算法每个租赁点的单车数量可以以预估计算的方式经屡次计算得出一个稳定解。即大局部租赁点的单车数量满足110%的要求，少局部租赁点单车数目远远超出需求量，还有少局部单车数目几乎为零奇点。最后，将计算所得的几个奇点分块，从自行车数量超出40或大量超出需求量的地点运送单车至奇点用启发算式法计算运送路线及运送时间。5.4 求解调度方案的启发式算法5.4.1算法简介启发式算法是依据有限的知识在短时间找到问题解决方案的一种技术。在可承受的花费指计算时间和空间下给出待解决组合优化问题每一个实例的一个可行解。在搜寻问题中，每个节点都有b个选择以及到达目标的深度d，一个毫无技巧的算法通常都要搜寻bd个节点才能找到答案。启发式算法借由使用某种切割机制降低了分叉率(branching factor)以改良搜寻效率，由b降到较低的b'。分叉率可以用来定义启发式算法的偏序关系，例如：假设在一个n节点的搜寻树上，h1(n)的分叉率较h2(n)低，那么 h1(n) < h2(n)。启发式为每个要解决特定问题的搜寻树的每个节点提供了较低的分叉率，因此它们拥有较佳效率的计算能力。我们主要应用启发式算法的这个优点来解决此题的调度问题。算法的流程图如下：图5-4-35.4.2算法容以指定租赁店点为初始站点，对该租赁点的下一租赁点，搜索路径，搜索规那么如下：1查找与初始点距离最近的N个租赁点N值按照题目适当确定，并且按照距离由小到大的规律排序；2依次遍历排好序这N个租赁点，如果这个租赁点为需求点且需求量大于车上的剩余自行车无法满足一次性完成调配，那么删除该节点，并重新得到新的N个租赁点。3计算每一层的自行车调度数量取绝对值和走过的距离，并求出两者的比值。4以搜索到的满足条件的N个租赁点分别为初始点，重复第1-3步。搜索深度为N。5求出每一次搜索路径自行车调度数量和走过距离的比值后，求和，选取比值之和最大的那条路径，那么这条路径中初始节点对应的下一节点为调度方案的下一个调度点。6以下一个点为起始点，重复第1-5步，直到所有的车辆都被搬运完毕。算法如下图：起点。搜索至第N层后返回图5-3-15.4.3约束条件1、综合考虑租赁点的数目，搜索深度根据不同分组的站点数目N取35。2、如果租赁点是调度需求点，那么调度车上的自行车数目必须满足需求，一次性完成该租赁点的需求；如果该点是盈余点，那么在不超过调度车最大负载的情况下，调度车要尽可能地多装；3、 调度的出发点选为某一个租赁点，从这一点出发完成调度后，需要返回原来的租赁点，但是返回租赁点的耗时不必计入总耗时；4、 两辆调运车不能同时到达一个租赁点。5.4.4算法流程图该算法的程序流程图如下：图5-4-1启发式算法能够解决在租赁点确定后的调度问题，在第一问、第三问中应用。5.5租赁点位置5.6计算结果第一问结果启发式计算结果为：早上A：26->27->7->8->9->28->10->24->22->6早上B：5->20->18->11->12->13->14->3->4中午A：9->10->24->22->4->17中午B：26->7->30->8->21->20->18->12->11晚上A；25->26->27->7->30->9->28->10->24->23->3晚上B：19->5->20->21->18->11->12->14->2图5-5-1图5-5-2图5-5-3消耗时间为：早上：t =7.9834e+003 s=133.1min中午：t =5.4157e+003 s=90.3min晚上：t =7.7568e+003 s=129.3min平均：t=117.6min第二问结果如表5-6-1所示：网点编号7:008:30车辆需求数11:0012:30车辆需求数17:3019:00车辆需求数均值最大值加权均值耗资5640404040 40 40.0 90000 5038373236 38 36.0 86000 7223393432 39 34.0 84000 6033323734 33 34.0 84000 7733362832 36 34.0 84000 7320373631 37 33.0 83000 9023323731 37 33.0 83000 8825333531 35 32.0 82000 4723363230 36 32.0 82000 8713383629 38 32.0 82000 6939212328 39 32.0 82000 468373928 37 31.0 81000 627373827 38 31.0 81000 4933183529 35 31.0 81000 314027825 40 30.0 80000 6324283328 33 30.0 80000 8421293328 33 30.0 80000 8018362225 36 29.0 79000 3615372225 37 29.0 79000 9132222025 32 27.0 77000 7619272925 29 26.0 76000 338273323 33 26.0 76000 4518262322 26 24.0 74000 4132121219 32 23.0 73000 1939000 表5-6-1综上所述，我们得出的答案：新增租赁点数目为23个，租赁点编号和相对应的放置车辆数目如表<5-2-2>所示：租赁点编号313336454647495056606263放置车辆数目342932263636344144393533租赁点编号6972737677808487889091放置车辆数目3538373037323336363730表5-6-2网点位置如下图5-6-1：图5-6-1第三问结果假设只有两辆车，那么结果为：早上A：25->41->52->40->39->30->8->6->22->38早上B：29->19->5->20->4->17->3->31->51->12->49->47->43中午A：23->36->9->30->39->28->10->37->38->34->22->4->33->32中午B：16->15->1->31->13->14->51->12->48->50->11->49->47->46->45->52晚上A：8->21->16->15->50->51->2->32->33->34->38->10晚上B：25->26->42->7->30->28->39->40->52->53->41->45->46->47->49早上：t=9.6054e+003 s=160.1min中午：t=1.2808e+004 s=213.5min晚上：t=1.3061e+004 s=217.7min平均：t=197.1min>150min综上，仅有两辆运输车是不够的，所以我们就三辆运输车的情形进展了分块计算。计算结果如下：上午A：35->38->28->39上午B：21->20->5->19->31->3->4->22->6->8->40上午C：42->52->41->43->44->12->51->50->49->47中午A；37->24->34->38->36->10->28->39中午B：8->23->22->6->4->33->32->31->51->50->48中午C：26->25->52->45->46->47->49晚上A：24->35->9->28->40->39->10->38->34晚上B：16->15->50->2->32->33->23->21晚上C：18->43->25->41->53->52->45->46->47->49早上：t=6.3253e+003 s=105.4min<150min中午：t=8.5675e+003 s=142.8min<150min中午：t=8.7849e+003 s=146.4min<150min平均：t=131.5min<150min六、模型检验1. 问题一中求解最短路径采用Floyd-Warshall算法，以动态规划为手段，解决任意两点间的最短路径，并通过Matlab求解；2. 问题一求解最短调度时间采用启发式算法，通过C+程序设计穷举算法，并搜索最正确调度方案，由于上述结果是通过穷举得到的，必然全局最优；3. 问题二引入方便因数，全面综合各方面因素，所以得到的站点分配为最优解。4. 问题三的方法与问题一和问题二相似，故所求调度方案为最正确调度方案。七、模型优缺点以及改良在确定自行车的分配方案和调度方案时，这个问题是在节点具体的位置的条件下求解两个问题。我们对两个问题分开求解，即先确定最分配方案，再根据最优分配方案确定对应的最优调度方案。然而根据数学模型和实际情况得这两者并不是相互独立的，即问题最优解并非简单地两者最优解的结合。因此，我们的最优结果可能和实际情况存在偏差。为了方便问题的求解，我们做出了一些假设，比方假设每辆调度车从固定的某租赁点出发，最后又回到原来的点，而实际情况中会更局具体情况选择车辆停靠点。这些假设方便了求解，但实际上简化了问题的复杂度。7.1分配方案的优点租赁点自行车分配中，我们采用了一种创新的分配方案，在分配中不仅考虑了需求量对分配的影响，而且还按照动态的目光，先给出合理的分配初值，然后让其按照自行车的骑行规律即在某个租赁点还车的概率与租车点和还车点的距离成反比自动分配假设干次，每一次得出一个新的分配方案后和原来的方案比拟，然后做出调整，最终得出最优的分配方案。这个分配方案的优点是突出的，主要表达在以下几点：1、 首先考虑了需求量对分配方案的影响，使之从一开场就是合理的，兼顾重要因素。2、 由于即在某个租赁点还车的概率是一个常数，所以常数因子对分配方案的影响可以通过一次优化最终补偿，最终的结果是形成的调度方案是满足骑行规律的最优解。3、 这个模型还有一个优点是，在校正后，能够使得需要调度的自行车数目到达最小，从而在计算调度量时，为最优解提供保证。7.2调度方案的缺优点调度方案的优点是在租赁点不大的情况下，按照启发式算法一次性可以把相对来说最优的调度方案解出来，建模简单，求解也相比照拟容易。调度方案的缺点重要表达在算法的局限性上。而启发式算法那么试图一次提供全部目标。例如通常能发现很不错的解，但是也没方法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没方法知道它是否每次都可以这样的速度求解。总的来说，启发式算法有一定的不稳定性。可以用性能更好的遗传算法或者退火算法解决。7.3新增节点模型的优缺点在求解新增节点时，我们巧妙地引入了一个“方便因数，用来衡量新增的租赁点的合理程度，用求解最优解的思路来求解新增的租赁点和分配的自行车数目，模型简单明了，容易用现成的算法实现。但是方便因数并没有将影响新增租赁点的所有的因素都考虑进去，仅仅考虑了分配值、节点数、和邻近该租赁点的其他租赁点的数目。其他因素如是否能到达调配量最小等因素没有考虑，其次定义的一些量如、不尽合理，原因是只考虑了新增加的单个节点所收到的影响，不没有考虑新增的节点间的相互影响，因此所得的结果有可能和最优解有一定的差距。7.4模型和算法的改良7.4.1算法的改良由于启发式算法的局限性，可以采用收敛速度更快的遗传算法Genetic Algorithm，简称GA和退火算法Stimulated Annealing，简称SA。与启发式算法相比拟其优点有：计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题。在此题中，由于数据量相对较小，启发式算法还能够满足要求，为了使结果更加稳定，可以考虑退火算法和遗传算法。7.4.2模型的改良我们可以把调度问题看成一个赋有权值的图G，先要求出图G的最小生成树，使树上各边的总权和到达最小。然后基于最早生成树生成一个可行的最短行车路径。对上述30个租赁点重新编号，依次为1-30，用集合R表示。我们用0-1变量来表示公交车是否从租赁点i到租赁点j,即目标函数为寻找一条从起始点开场到各个节点生成的最优树，要求各条线路的权值和最小，即约束方程为：求解最小生成树的方法有破圈法、避圈法、Dijkstra算法等。这里我们用避圈法求解，避圈法是指将图G中的边按照权数大小逐条考察，按不构成圈的原那么参加到T树中，直到为止，即T的边数=G的顶点数-1为止。避圈法的算法是：1. 把G的边按权的大小整理成令.2.假设含圈，那么转3，否那么转4.3令，假设那么转2；否那么停顿，G不存在最小生成树。4.令，。5.假设，完毕，是最小生成树；否那么转3.根据避圈法的算法，编写Matlab程序求得结果，得到最小生成树，结果列表如下：表7-4-1 求最小生成树结果注：图中打处表示两个租赁点连通。采用最小数算法算出的搜索路径比拟原模型结果比拟稳定，这是一个突出优点。八、参考文献1 Clarke G and Wright J. Scheduling vehicles from a central depot to number of delivery pointsJ. Operations research, 1964, 12(4): 12-182登涛, 方文道, 章坚民, 等. 公共自行车交通系统调度算法J. 计算机系统应用, 2011, 20(9): 112-116.3宏志, 龚加安. 带时间窗车辆路径问题的改良节约算法J. 纯粹数学与应用数学, 2011, 27(5): 688-693.4柳祖鹏, 丁卫东, 程逸旻. 公共自行车系统站间调度优化研究J. 城市公共交通, 2011 (1): 39-42.5肖华勇.实用数学建模与软件应用.：西北工业大学 2008.11附录距离计算：distance=zeros(53);for i=1:1:53 k=1; for j=1:1:53 if i=j distance(i,k)=abs(x1(i,1)-x1(j,1)+abs(x1(i,2)-x1(j,2); end k=k+1; endend概率系数计算：K=；for i=1:1:53 s=0; for j=1:1:53 if z(i,j)=0 s=s+1/z(i,j);%输出概率的K end end s=1/s; K=K s;end分块距离矩阵计算：distanceMb=zeros(20);for i=1:1:20 k=1; for j=1:1:20 if i=j distanceMb(i,k)=abs(x1(Mb(i),1)-x1(Mb(j),1)+abs(x1(Mb(i),2)-x1(Mb(j),2); end k=k+1; endend启发式算法代码：#include<iostream>#include<cmath>#include<fstream>#include<stdlib.h>#define ZD 20/定义站点数 ZD = Zhan Dian#define DE 3/搜索深度using namespace std;int numZD;/各个站点相应的多余、缺少的车辆的数目int route10*ZD; /车行走的路径bool IsEnd(int num)/判断是否所有的车都已经调度完毕int i;for(i=0; i<ZD; i+)if(numi!=0) return false;else return true;int Pathfinding(int first,int vol,int depth)/寻路 找到下一个路径最优的站点double distanceZDZD; /各个站点之间的距离if(depth <=0)return -1;int temp_distanceZD;int i,j,k;for(i=0;i<ZD;i+)temp_distancei = i;/存储站点for(i=0;i<ZD;i+)for(j=i;j<ZD;j+)if(distancefirsttemp_distancei>distancefirsttemp_distancej)k = temp_distancei;temp_distancei = temp_distancej;temp_distancej = k;/排序 保存的是距离从小到大的站点int bound = DE;/设置边界int temp_siteDE;int next_siteDE;j=0;for(i=0;i<ZD;i+)if(vol + numtemp_distancei >= 0 && numtemp_distancei!=0 && temp_distancei!=first)if(vol>=50 && numtemp_distancei >0)