欢迎来到沃文网! | 帮助中心 分享知识,传播智慧!
沃文网
换一换
首页 沃文网 > 资源分类 > DOC文档下载
 

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

  • 资源ID:1278       资源大小:2.13MB        全文页数:36页
  • 资源格式: DOC        下载权限:游客/注册会员/VIP会员    下载费用:20积分 【人民币20元】
快捷注册下载 游客一键下载
会员登录下载
三方登录下载: QQ登录   微博登录  
下载资源需要20积分 【人民币20元】
邮箱/手机:
温馨提示:
支付成功后,系统会自动生成账号(用户名和密码都是您填写的邮箱或者手机号),方便下次登录下载和查询订单;
支付方式: 微信支付    支付宝   
验证码:   换一换

加入VIP,免费下载资源
 
友情提示
2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,既可以正常下载了。
3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

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

-1-目录一、问题引入.....................................................................................................................................-3-二、问题分析.....................................................................................................................................-3-2.1第一问分析...................................................................................................................-4-2.2第二问分析...................................................................................................................-4-2.3第三问分析...................................................................................................................-4-三、模型假设和符号说明.................................................................................................................-5-3.1模型假设.......................................................................................................................-5-3.2符号系统.......................................................................................................................-6-四、模型建立.....................................................................................................................................-6-4.1模型分类.......................................................................................................................-6-4.2租赁点分配方案建模..................................................................................................-7-4.3调度车调度方案建模..................................................................................................-8-4.3.1一辆调度车调度方案.......................................................................................-8-4.3.2多辆调度车调度方案.......................................................................................-9-4.4租赁点数目和位置的确定.........................................................................................-11-4.5调度时间的模型........................................................................................................-12-五、模型的求解.............................................................................................................................-13-5.0经纬度转换为横纵坐标.............................................................................................-13-5.1求解最短路径............................................................................................................-13-5.2模型一次运行后的单车重分配求解........................................................................-14-5.3求解分配方案的预估校正算法............................................................................-16-5.4求解调度方案的启发式算法....................................................................................-16-5.4.1算法简介.........................................................................................................-16-5.4.2算法内容.........................................................................................................-17-5.4.3约束条件.........................................................................................................-18-5.4.4算法流程图.....................................................................................................-19-5.5租赁点位置.................................................................................................................-20-5.6计算结果.....................................................................................................................-20-5.6.1第一问结果.....................................................................................................-20-5.6.2第二问结果.....................................................................................................-21-5.6.3第三问结果.....................................................................................................-23-六、模型检验...................................................................................................................................-26-七、模型优缺点以及改进...............................................................................................................-26-7.1分配方案的优点.........................................................................................................-27-7.2调度方案的缺优点.....................................................................................................-27-7.3新增节点模型的优缺点.............................................................................................-27-7.4模型和算法的改进.....................................................................................................-28--2-7.4.1算法的改进.....................................................................................................-28-7.4.2模型的改进.....................................................................................................-28-八、参考文献...................................................................................................................................-30-附录...................................................................................................................................................-30--3-一、问题引入近年来,随着经济的发展,我国各级城市的机动车保有量都进入了持续高速增长时期,但由此所引发的道路拥堵、空气污染也引起了政府以及百姓的极大关注。众所周知,建立快速、便捷的城市公共交通体系是解决这一问题的有效手段之一。然而,居民居住地和交通站点通常都有一段距离,这段不远的距离以及现实存在的公共交通拥挤现象则使居民乘坐公共交通的意愿降低,而将公共自行车租赁服务系统纳入城市公共交通体系,能够从一定程度上缓解这一现象。西安市经济开发区公共自行车服务系统于2011年4月开始建设,到目前为止,已建成租赁点30个,自行车总量达到850辆。目前正在筹备第三期建设,请你针对如下问题建模(1)根据目前经开区网点自行车需求情况等信息,要求调度平均耗时尽量少,针对已有的30个租赁点设计最优车辆分配方案、调度方案,给出完成调度所耗费的时间。(2)假设经开区公共自行车服务系统三期建设准备投入建设经费200万元,据此建立数学模型,确定新增租赁点数目、位置以及合适的放置车辆数目。(3)针对问题(2),进一步研究,如果要求在150min内完成调度,确定是否需要增加调度车辆(购置调度车辆费用由其它项目经费解决,不包含在三期建设提供的200万元经费中间),并给出该情形下的自行车调度方案。二、问题分析首先,题目给出的初始条件为经度和纬度,我们利用地球的坐标系统将其转换为平面坐标,后续的计算都在平面坐标的基础上进行。-4-2.1第一问分析第(1)问对对应前两期工程,30个租赁点已知,因此在已知的点上根据需求量确定自行车的分配方案和调度方案。这个问题是在已知节点具体的位置的条件下求解两个问题每个节点的自行车分配问题和调度问题。这两个问题可以分开来求解。第1问要求调度时间尽量少,我们从计算两点的最短路径入手,将最短路径计算出后考虑将早中晚三个时间段内的高峰期取平均值后再最初计算。我们建立反比例函数关系式pKd,再根据归一化条件求得2km内的概率系数K。随后,算出每个点以需求量的数目的前提下会向2km内的各个租赁点送出多少辆单车,并以负反馈的方式经多次计算得出一个稳定解,即大部分租赁点的单车数量满足110的要求,少部分租赁点单车数目远远超出需求量,还有少部分单车数目几乎为零(奇点)。最后,将计算所得的几个奇点分块,从单车数量超出40或大量超出需求量的地点运送单车至奇点并计算运送时间。2.2第二问分析第(2)问对应第三期工程,根据投入的建设费用等确定新增的租赁点的数目和每个租赁点的分配方案。这些新增的租赁点是在规定的70个点中选取的,而且每个待选点的需求量是给定的,因此在需求量和工程费用的限制下,求实现服务系统最优的选点方案和分配方案。建立新的一定数目的租赁点,我们首先将另外70个点的数据列出,考虑到是否选择一个点与这个点的平均需求量和最大需求量均有关,所以将早中晚三个时间段的需求量的平均值和三个时间段需求量的最大值列出,然后将这两个数据以一定比例加权平均,最后得出的数字排序,由上到下计算出每个点的需求金额,截止到2000000元时。租赁点即为截止前的点,相对应的数目即为每个点对应的数目。2.3第三问分析第(3)问建立在第(2)问的基础上,同第(1)问,类似,在解第(3)问-5-前,租赁点的具体位置和需求量已知了,并且,这些租赁点的分配方案也已将求得,很容易求得每一个租赁点需要调度的具体数值,在这些已知条件下,要求在给定时间内完成调度,给出调度方案。如调度车辆不够,则给出增加的车辆数目和调度方案。问题类似于第(1)问的给出分配方案后求调度的问题。根据以上分析,我们要解决的问题主要有以下几个部分1、求出任意两个租赁点之间的最短路径。2、求出给定租赁点的分配方案。3、求出给定租赁点的系统的自行车调度方案。4、在给定约束下求租赁点的数目和位置。解决以上三个问题,本题所要求的问题就可以解决了。三、模型假设和符号说明3.1模型假设1、每个租赁点调度需求量为负,有多余的自行车可以提供给调度车则为正数;2、假设两个停车场就在某两个租赁点上,则选取的两个租赁点必须是有自行车盈余的点,并且调度车出发后,车上装载的自行车的数量就是租赁点的调度量。由于每个租赁点的自行车最大分配量小于调度车的最大装载量,所以总是能够将盈余量全部装在调度车上;3、每辆调度车从固定的某租赁点出发,最后又回到原来的点,以方便下次调度但是回到原点的时间可以不计。因为只有在调度完成后才会回到原点,此时不需要调度,不再受时间限制;4、同一辆调度车只能经过同一个租赁点一次(除了作为车站的租赁点);5、每次到达下一个租赁点时,调度车上的自行车数量满足该租赁点需求,即对于需求点来说,只需用调度一次就完成调度;对于盈余点来说,调度车到达这些点要尽量多装。如果未达到调度车的限量就将该租赁点所有的盈余自行车装载,-6-如果多出,则装满。3.2符号系统G------租赁点的集合T------调度总时间(不包括完成调度后调度车返回原点的时间)。k------调度车编号ijd------租赁点间的最短距离kijx------第k辆车调度完i后是否再调度jku------是否使用调度车kjl------租赁点j的需要调度的量ijB------i和j间的距离是否大于M千米tjZ------t时间段内租赁点j的需求量j------j点的需求量占总需求量的比例ijF------从i点出发到达j租赁点的自行车数量iF------i点的单车数量a------建立一个租赁点耗资b------维护每辆自行车耗资p------每一个租赁点的耗资数P------新增租赁点的耗资总数四、模型建立4.1模型分类在租赁点的分配方案确定后,只剩下调配问题,属于VRP问题,该问题是著-7-名的问题TSP(旅行商问题)的一个特例,因而也是NP-hard问题。典型的VRP模型定义如下假设已知客户网络中的客户数量、客户所在的位置、客户需求和配送车辆的最大负荷,要求在满足约束的前提下为给定的中心仓库设计车辆路径,使运输成本最小。传统电子商务配送模型是分区域配送模式的单一配送中心(Distributioncentre,DC)-多需求点(demands,DS)的路径优化模型,而且不考虑沿途补货的情况。而针对区域广泛、客户众多且分散、业务量大且频繁的电子商务物流配送业务,需要考虑多个配送区域联合、沿途多次补货的配送策略,从而得到电子商务配送的跨区域VRP模型。这个思路和我们所要考虑的利用公交车收集和分配公共自行车很类似,问题中有多余自行车的租赁点即可看作电子商务问题中的配送中心DC,而缺少自行车的租赁点也可看作是需求点DS。我们的问题和电子商务问题的一个不同点是,在调度时,如果调度点由盈余的自行车且数量加上调度车上已有的自行车时其总量会可能会超过调度车的最大装载量,因此有可能导致这些点的二次调度,这和电子商务配送模型中一次性完成调度有所区别,但是可以经过是党的改正后得到正确的模型。4.2租赁点分配方案建模影响租赁点自行车分配的因素有各租赁点的需求量、从租赁点离开的自行车、从其他租赁点起来的自行车等。若仅考虑需求量对租赁点分配自行车数目的影响,有如下模型124jtjjZy2-2-41njtjtjjZZ(1)式确定按照最终的需求量,以按比例分配的方式确定租赁点的分配量。(2)式给出需求量占总需求量的比例。以仅考虑需求量的方式确定的分配方式显然不是最佳方案。分配方案还和租赁点之间的距离有关。由题意可知,从在某个租赁点还车的概率与租车点和还车点的-8-距离成反比,且假设居民的骑行距离不超过Mkm,由此可得出下式3-2-4,1,11ijnjiiijjinijjjikjkjBxBxyy4-2-41Ryykjj式(4-2-3)首先按照(4-2-1)式的方式产生一组分配方案,然后让其按照自行车间行驶的规则再次分配,产生新的一组分配方案,然后用(4-2-4)式校正,最终得到优化了的分配方案。4.3调度车调度方案建模4.3.1一辆调度车调度方案在我们的求解问题中,第一问中调度车辆问2辆,为了问题是建模化简,我们先考虑调度车为一辆的情况,然后推广到多量的情况,这样就可以给对第一问和第三问的调度问题建立实际的解题模型。设拥有最大负荷为Q的调度车从指定的节点出发,对集合为G的节点进行调度。完成任务后返回原点。调度需求量和租赁点间的距离已经求得。整个调度方案可以由下列一组方程和约束条件确定1-3-4||min1,1ijniijjjijxlvdT2-3-4111njjinjijxx3-3-411niijx4-3-411njijx5-3-40Qrlijj6-3-41ijnjijiBFZ-9-7-3-411ijnjijnjjiijjBxxyZl8-3-411ijnjijnjjiijjBxxylZ(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的节点进行调度。完成任务后返回原点。调度需求量和租赁点间的距离已经求得。整个调度方案可以由下列一组方程和约束条件确定9-3-4||min1,11kijniijjjijkkxlvdT10-3-41kukii11-3-4111njkjinjkijxx12-3-411,1kknijikijx-10-13-3-411,1kknijjkijx14-3-40Qrlkijj15-3-41ijnjijiBFZ16-3-411ijnjkijnjkjiijjBxxyZl71-3-411ijnjkijnjkjiijjBxxylZ18-3-42010zjitkjitxx(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)式保证不同的调度车不能再同一时刻到达同一个租赁点。根据以上一组方程和约束条件,就可以将调度问题相对完整的描述出来。这是一个优化问题,在求解过程中由众多的算法可以采用,但是考虑到算法的复杂性可标称的简洁性,我们采用的算法是启发式算法,这将在模型求解中详细讨论。-11-4.4租赁点数目和位置的确定题目中新增的租赁点是在已知的若干点中选取的,因此,分析清楚选取租赁点的约束条件,就可以从最优解的角度得到新增的节点。建立租赁点时首先考虑的是各个点的需求量(已知),由于在不同时段的需求量不同,所以应当考虑平均需求、不同时段需求。所以首先我们应当确定加权平均比例,一保证确定的租赁点在全天达到最优。在这里引入一个加权平均比,取决于我们实际问题的要求和调度问题的特点。首先将数据加权平均,有再将每一个租赁点的耗资数额按照公式(4-4-1)求出)(加权需求量1-4-4bXaY最后将耗资数额加和,即求得满足式(5-2-2)的最大k值。)(2-4-4k1iibXap考虑了需求量对新租赁点的影响之后,我们还需要考虑骑行规律对租赁点选取的影响。所谓运输规律就是居民可以在任意一个租赁点还车,在某个租赁点还车的概率与租车点和还车点的距离成反比,且假设居民的骑行距离不超过M。于是仅考虑运输规律,我们引入一个方便因数,定义如下)(3-4-41SPyConiniiCon用来衡量新设置的租赁点的合理程度,它与租赁点的分配量、常数iP、iS的乘积之和有关,其中,常数iP的定义如下)(4-4-41njijiBPiS的定义如下)(5-4-41ijnjijidBSiS表示i租赁点能够到达其他节点的数目之和,iS越大表明该节点的辐射能力越-12-强,也越合理。在路程不超过M的范围内,租赁点i能够到达的节点越多,则常数iP越大。还要保证新增的节点数k尽可能地少。在新增租赁点的过程中不考虑随后的调度方案,因此在总建设经费的限制下,可以按照优化的方法求出方便因数的最小值。4.5调度时间的模型在三期建设中,为了实现经开区更大的网点覆盖面积,进一步增设站点,新增了一批租赁站点并购进自行车。然而,更多的站点可能会导致部分租赁点的自行车短缺或堆积现象,从而降低了资源利用效率。为了探讨这个问题,我们必须对现有调度方案进行检验和矫正,更好的实现资源利用最大化。故对调度时间进行了计算,发现用两辆调度车进行自行车调度很难满足调度需求,调配时间超过限制时间,必须购置更多的调度车辆,虽然会增加一定成本,但对整体的统筹有很大的意义。将原有的站点与新增站点进行混合,重新根据密集度,自行车需求量等因素进行分组,根据分组情况配备调度车辆。若所分组数增多,则增加调度车辆的数目可以更快捷地实现调度需求。然后对每一组的调度方案进行独立分析,即求解kijniijjjijkkxlvdt1,11||min则总调度时间kkktT1min(k代表组数)具体建模思想与第一问的求解相似。-13-五、模型的求解5.0经纬度转换为横纵坐标5.1求解最短路径思想描述我们将最短路径的计算作为一个函数。而经过讨论我们决定计算采用Floyd-Warshall计算方法(以下简称Floyd算法)。Floyd算法是以动态规划为手段,以解决任意两点间的最短路径为目的的一种算法,该算法的时间复杂度为3NO,空间复杂度为2NO。它可以正确处理有向图或负权的最短路径问题,故该方法适用于我们的问题在实际算法中,为了节约空间,我们直接在原来空间上进行了迭代,这样空间可降至二维。Floyd算法的描述如下设kjiD,,为从i到j的只以...1k集合中的节点为中间节点的最短路径的长度。若最短路径经过点k,则1,,1,,,,kjkkkikjiDDD;若最短路径不经过点k,则1,,,,kjikjiDD。因此,,min1,,1,,1,,,,kjikjkkkikjiDDDD。30;11kkkkk30;11iiiii30;11jjjjjifjijkkiDDD,,,jkkijiDDD,,,综上,最短路径矩阵为(单位km)-14-图5-1-15.2模型一次运行后的单车重分配求解依据题意不难得知,在租赁点还车的概率与租车点和还车点的距离成反比,且居民的骑行距离不超过2km。○1据骑行距离此可得出筛选算法30;11iiiiik1;30;11jjjjjifjiif2000,jid;0,jidelse;0,jidkk1;○2根据反比例关系不难得出每个租赁点向2km内的各个租赁点发送的单车数量为jijijidKF,,,-15-根据归一化条件11,,,njjijijidKF综上可得出求得2km内的概率系数K的算法30;11iiiiis0;30;11jjjjjif0,jidjidss,1;ss1;K[Ks];○3根据各个租赁点发送出的单车概率可求得运行一次后的各个租赁点单车数目nijijFF1,据此可得出求解运行一次后的各个租赁点单车数目的算法30;11jjjjjt0;30;11iiiiiif0,jidjiiidKFtt,;tFj;模型运行一次后的结果如图所示-16-图5-2-15.3求解分配方案的预估校正算法每个租赁点的单车数量可以以预估计算的方式经多次计算得出一个稳定解。即大部分租赁点的单车数量满足110的要求,少部分租赁点单车数目远远超出需求量,还有少部分单车数目几乎为零(奇点)。最后,将计算所得的几个奇点分块,从自行车数量超出40或大量超出需求量的地点运送单车至奇点(用启发算式法计算运送路线及运送时间)。5.4求解调度方案的启发式算法5.4.1算法简介启发式算法是依据有限的知识在短时间内找到问题解决方案的一种技术。在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解。在搜寻问题中,每个节点都有b个选择以及到达目标的深度d,一个毫无技巧的算法通常都要搜寻bd个节点才能找到答案。启发式算法借由使用某种切割机制降低了分叉率branchingfactor以改进搜寻效率,由b降到较低的b。分叉率可以用来定义启发式算法的偏序关系,例如若在一个n节点的搜寻树上,h1n-17-的分叉率较h2n低,则h1n27-7-8-9-28-10-24-22-6早上B5-20-18-11-12-13-14-3-4中午A9-10-24-22-4-17中午B26-7-30-8-21-20-18-12-11晚上A;25-26-27-7-30-9-28-10-24-23-3晚上B19-5-20-21-18-11-12-14-2图5-5-1-21-图5-5-2图5-5-3消耗时间为早上t7.9834e003s133.1min中午t5.4157e003s90.3min晚上t7.7568e003s129.3min平均t117.6min5.6.2第二问结果如表5-6-1所示网点编号700830车辆需求数11001230车辆需求数17301900车辆需求数均值最大值加权均值耗资56404040404040.090000-22-50383732363836.08600072233934323934.08400060333237343334.08400077333628323634.08400073203736313733.08300090233237313733.08300088253335313532.08200047233632303632.08200087133836293832.08200069392123283932.0820004683739283731.0810006273738273831.08100049331835293531.0810003140278254030.08000063242833283330.08000084212933283330.08000080183622253629.07900036153722253729.07900091322220253227.07700076192729252926.0760003382733233326.07600045182623222624.07400041321212193223.0730001939000表5-6-1综上所述,我们得出的答案新增租赁点数目为23个,租赁点编号和相对应的放置车辆数目如表所示表5-6-2网点位置如图5-6-1所示租赁点编号313336454647495056606263放置车辆数目342932263636344144393533租赁点编号6972737677808487889091放置车辆数目3538373037323336363730-23-图5-6-15.6.3第三问结果若只有两辆车,那么结果为-24-早上A25-41-52-40-39-30-8-6-22-38早上B29-19-5-20-4-17-3-31-51-12-49-47-43中午A23-36-9-30-39-28-10-37-38-34-22-4-33-32中午B16-15-1-31-13-14-51-12-48-50-11-49-47-46-45-52晚上A8-21-16-15-50-51-2-32-33-34-38-10晚上B25-26-42-7-30-28-39-40-52-53-41-45-46-47-49早上t9.6054e003s160.1min中午t1.2808e004s213.5min晚上t1.3061e004s217.7min平均t197.1min150min综上,仅有两辆运输车是不够的,所以我们就三辆运输车的情形进行了分块计算。计算结果如下-25-上午A35-38-28-39上午B21-20-5-19-31-3-4-22-6-8-40上午C42-52-41-43-44-12-51-50-49-47中午A;37-24-34-38-36-10-28-39中午B8-23-22-6-4-33-32-31-51-50-48中午C26-25-52-45-46-47-49晚上A24-35-9-28-40-39-10-38-34-26-晚上B16-15-50-2-32-33-23-21晚上C18-43-25-41-53-52-45-46-47-49早上t6.3253e003s105.4minincludeincludeincludedefineZD20//定义站点数ZDZhanDiandefineDE3//搜索深度usingnamespacestd;intnum[ZD];//各个站点相应的多余、缺少的车辆的数目-32-introute[10*ZD];//车行走的路径boolIsEndintnum[]{//判断是否所有的车都已经调度完毕inti;fori0;idistance[first][temp_distance[j]]{ktemp_distance[i];temp_distance[i]temp_distance[j];temp_distance[j]k;}}//排序保留的是距离从小到大的站点号码intboundDE;//设置边界inttemp_site[DE];intnext_site[DE];j0;fori0;i0num[temp_distance[i]]0-33-temp_distance[i]first{ifvol50num[temp_distance[i]]0continue;temp_site[j]temp_distance[

注意事项

本文(公共自行车调度问题数学建模论文.doc)为本站会员(星星008)主动上传,沃文网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知沃文网(发送邮件至2622162128@qq.com或直接QQ联系客服),我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给沃文网发消息,QQ:2622162128 - 联系我们

版权声明:以上文章中所选用的图片及文字来源于网络以及用户投稿,由于未联系到知识产权人或未发现有关知识产权的登记,如有知识产权人并不愿意我们使用,如有侵权请立即联系:2622162128@qq.com ,我们立即下架或删除。

Copyright© 2017-2019 www.wodocx.com ,All Rights Reserved |陕ICP备19002583号  

陕公网安备 61072602000132号     违法和不良信息举报:0916-4228922