西安市经开区公共自行车服务系统优化方案设计-数模论文.doc

该【西安市经开区公共自行车服务系统优化方案设计-数模论文 】是由【夜紫儿】上传分享，文档一共【21】页，该文档可以免费在线阅读，需要了解更多关于【西安市经开区公共自行车服务系统优化方案设计-数模论文 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。西安市经开区公共自行车服务系统优化方案设计-数模论文摘要对于第一问,依据租赁点的需求和约束条件分配自行车;根据经纬度和Floyd算法求出各租赁点之间的距离,引入0—1变量表示租赁点间是否发生调度,采用最小生成树算法,经过租赁点的时间及装卸自行车的时间为权重,通过Matlab编程用避圈法求解最小生成树,求得的路径就是最佳行车路线,每辆车调度一次平均用时135分钟,完成一天的调度总时间为806分钟。对于第二问,约束为投入经费总数和租赁点自行车需求,目标是设置的租赁点能够覆盖更大的面积,而且整个调度花费时间较少,用excel将备选租赁点需求量由大到小排序,选取自行车需求较多且三个时间段需求相差小的网点,应用动态规划算法,设新增租赁点数为代入经费约束即可得到k值不大于28,通过调整新增租赁点采用启发式搜索求新增网点和k,车辆的合适分配方案,编程得出新增网点为26个,自行车总数697辆。对于第三问,通过增加调度车来减少调度时间,采用租赁点分区的思想,每辆调度车只在一个分区最小生成树启发式搜索0-1变量Matlab编程1西安市经开区公共自行车服务系统优化方案设计目录一、问题的背景与重述................................................................................................................................................................................................................................................................................................................3二、问题分析..............................................................................................................................................................................................................................................................................................................................................................................................................................4三、问题的基本假设.................................................................................................5四、符号规定...............................................................................................................5五、模型的建立与求解...............................................................................................6问题一的模型:....................................................................................................6问题二的模型........................................................................................................8问题三的模型:..................................................................................................11六、模型的分析和检验:...............................................................................................................................................................................................................................................................................................................................................................................................15七、模型的推广.........................................................................................................16八、参考文献.............................................................................................................16九、附录:.................................................................................................................162一、,我国各级城市的机动车数持续增长引发了道路拥堵、空气污染等问题,而租借公共自行车服务系统能够从一定程度上缓解这一现象。然而,居民居住地和交通站点通常都有一段距离,这段不远的距离以及现实存在的公共交通拥挤现象则使居民乘坐公共交通的意愿降低,公共自行车服务系统已被证明能够从一定程度上解决这一问题。将租赁点设置在合适的位置,可以覆盖更多的面积提高效率,避免资源浪费,根据租赁点自行车的需求量和使用频率,合理的分配自行车,并通过调度专用车在使用高峰期阶段进行合理调度,尽量使调度过程花费短的时间,且不能影响自行车的租用,最大程度地满足居民对车辆的需求,提高车辆利用率。,自行车总量达到850辆。现已知前期的30个租赁点位置,每个租赁点能够放置的车辆数目不能超过40辆,且通常车辆总数至少应超出需求量的10%。将实时观测到的数据归结到3个车辆使用需求最多的时间段(可认为每天的需求量不变)居民可在任意一个租赁点还车,在某个租赁点还车的概率与租车点和还车点的距离成反比,且假设居民的骑行距离不超过2km;假设车辆调度只在车辆需要最多的时间段进行,目前西安经开区用于运送公共自行车的调度车有2辆,每辆每次可运50辆自行车,调度车平均时速30km/h,每辆自行车装(或卸)平均耗时1min;假设建设一个租赁服务网点需要50000元,在使用周期内,购买、养护一辆自行车需要1000元。(1)根据目前经开区网点自行车需求情况等信息,若要求调度平均耗时尽量少,针对已有的30个租赁点来决定最优车辆分配方案、调度方案,并给出完成调度所耗费的时间。3(2)假设经开区公共自行车服务系统三期建设准备投入建设经费200万元,据此建立数学模型,确定新增租赁点数目、位置以及合适的放置车辆数目。(3)针对问题(2),进一步研究,如果要求在150min内完成调度,是否需要增加调度车辆(购置调度车辆费用由其它项目经费解决,不包含在三期建设提供的200万元经费中间),并写出该情形下的自行车调度方案。二、,根据结论要保证调度平均耗时最少,则在每个时间段内调度车行驶时间和装卸自行车总时间要最少,先求解出租赁点之间的实际车行距离和居民还车的概率,也相继可以确定居民还车数目,根据每个租赁点的需求数,通过建立相应的数学模型,进而可得调度车在每一个租赁点的调度时间。因此可以根据已知的道路连通图,首先通过Floyd算法算出任意两个租赁点间的距离,其次以时间为权重建立最小生成树模型,找出能使调度车耗时最少的行驶路线和调度车的分配方案。,目标都是使得整个调度花费时间最短。新增网点和自行车必须满足经费约束,为使设置方案最合理应将网点设在需求量较多的地方,将需求量排序后筛选出备选网点,按照网点需求将所有自行车分配,使得既满足需求又能让调度时间最短。同问题一一样首先用Matlab编程求出所有网点间距离,利用启发式搜索的算法,依次改变备选的新增网点,直到找出花费最短时间的路径。,调度是在问题二分配的结果上进行,因此采用最小生成树算法寻找最快调度方案,可以将网点进行分区(相距4近的网点为一个分区)来提高调度效率降低时间复杂度,假设需要增加p辆调度车,每辆调度车只在一个分区行驶且相互独立,应用问题二的模型计算各自的调度时间,改变p值直到最大值不大于150分钟,即为新增调度车。三、;;,能够满足需要;、费用和数量因素;5调度车在网点间的行驶距离可以按照经纬度计算。四、符号规定装卸车在第i个租赁点装卸的自行车数;ai:bi:第i个租赁点在调度后的自行车数;ci:第i个租赁点在租完还完后的自行车数;xi:租赁点i需要的自行车数;新增的租赁点点数;k:增加的自行车数;m:增加的调度车数;p:sij:租赁点i与租赁点j之间的距离;1,租赁点i与租赁点j有自行车的调度xij0,否则5(i,jR)五、模型的建立与求解根据以上的分析,可将原问题转化为:自行车分配和调度车路线的优化问题。问题一的模型:在问题一中,我们考虑编号1—30的租赁点,首先,由假设可根据7:00—8:00之间各个租赁点的自行车需求量,将850辆自行车按照需求比例分给各网点,通过对分配结果的分析,并结合题中的约束条件,对分配情况进行调整,然后重复分配—分析—调整,从而得到第一个时间段的最优的分配方案,即各个租赁点的b,结果如下:我们用0-1变量xij来表示租赁点i与租赁点j是否有自行车的调度,即1,租赁点i与租赁点j之间有自行车的调度xij0,否则(i,jR)目标函数为寻找一条从起始点开始到各个节点生成的最优树,要求各条线路的权值(权值即为两个租赁点间所用的时间和装卸自行车用的时间)和最小,附录中列出了30个点之间的距离,我们可以把它看成一个赋有权值的图G,先要求出图G的最小生成树,使树上各边的总权和达到最小。然后基于最小生成树生成一个可行的最短行车路径。即:mini1302sx,aijijij1i13030630cibi,xi,,,a40iii模型的求解具体过程如下:步骤1:利用题目中给出的各租赁点的经纬度数据,Matlab编程得到任意两个租赁点之间的距离,然后根据还车的概率与租车点和还车点的距离成反比,即可以得到各个租赁点还入的自行车数。步骤2:求解最小生成树的方法有破圈法、避圈法、Dijkstra算法等。这里我们用避圈法求解,避圈法是指将图G中的边按照权数大小逐条考察,按不构成圈的原则加入到T(树)中,直到q(T)p(G),1为止,即T的边数=G的顶点数-1为止。避圈法的算法[1]是:(e1)w(e2)w(em).,令T0(V,),i1,,ei含圈,则转3,(令ii,1,若im则转2;否则停止,G不存在最小生成树。,1Tj,ei,jj,1。,1,结束,Tj是最小生成树;,matlab编程得到的结果如下:7(图中打钩的表示两个网点之间有自行车的调度)步骤3:由于0-1整数规划法中决策变量为整数,我们利用lingo优化软件分析求解此规划问题,根据问题一模型的建立中目标函数及约束条件编写lingo程序如下:sets:sk/1..30/:s,x;si/1..30/:a;sik(si,sk):c,l;endsetsmin=***@sum(sk:2s*x)+***@sum(sik:a);***@for(si(i):***@sum(sk(i):l(j,i))=1);***@for(sik(i,j):l(i,j)<=w(i));***@for(sk:***@bin(s));***@for(sik:***@bin(x));data:s,c,x=***@ole(?C:\?,?s?,?_c?,?x?);***@ole(?C:\?,?s?,?_c?,?x?)=s,c,x;enddataend将matlab编程得到的结果结合实际情况,采用最小生成树的算法,调度方案车一:271028930782364173214车二:1112131151629**********平均调度一次花费时间为:车一时间:137分钟车二时间:134分钟问题二的模型目标:新增租赁点能够覆盖更大的面积满足需求量大的网点且整个调度过程8花费时间最短,即minT,maxb约束:新增的租赁点和自行车所花费用小于投入建设经费200万元。所以得到如下模型:mini130,k30,kj12sx,aijijii130,ki130,kmaxbi30cibi,xi,,,ai405k,,所以我们在问题一的基础上加以改进,采用启发式搜索算法。此算法的步骤如下。步骤一:将备选的网点的自行车需求数量按照从高到低的进行有序排列,形成70×3的矩阵,每行表示该网点在各时间段需要的自行车。步骤二:按照需求量的大小进行选择新增的网点,新增自行车即为所选网点的自行车总和,代入投入经费的约束条件,选取符合条件的假设新增网点,用问题一所的模型分配自行车。步骤三:应用问题一的模型,根据经纬度把新增的网点与原网点间距离用folyd算法和Matlab编程计算出来。步骤四:用最小生成树法寻找调度花费时间最短的路径,改变假设的新增网点,重复上述步骤,直到找出花费时间最短的最优的路径。备选租赁网点自行车需求量排序:9根据附件2中的数据可知,经开区每个酒店附近日均人流量1500人,公共场所日均人流量一万人,十字路口3000人,地铁出口2万人,社区2000人,在结合题目附录所给的各个租赁点需求量,结合前期建设的30个租赁点,保证每15人一辆自行车,在考虑到调度最优,结合问题一最小生成树算法所得到的10最优路径,运用MATLAB进一步分析可得到每个租赁点具体分配车方案:所以,综上所述,共新建自行车租赁点26个,新增自行车697辆,。每辆车平均一次调度花费的时间为:208分钟。问题三的模型:目标:在新增网点后使整个调度在150分钟完成;约束:每辆调度车每次运送的自行车不大于50辆;11所以得到模型:max(i156/p56/pj12sx,a)150ijijii1