logo资料库

基于TSP模型的杭州公共自行车调度优化.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.68M 资料格式：pdf 举报 版权申诉
第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
资料共16页，剩余部分请下载后查看
    基于TSP模型的杭州公共自行车调度优化【指导老师】梁军【姓名学号】王帅威31101012980【开始时间】2013年10月1号【结束时间】2013年10月30号【摘要】本文基于TSP商旅问题尝试解决杭州公共自行车在运营过程中存在的借车难和还车难的问题。根据自行车调度的实际情况，采集一些样本数据分析得出平均结果，考虑公共自行车调度过程当中相关的约束条件，建立适当的数学模型。由于经典的商旅TSP模型没有精确地模型求解，最后尝试用启发式搜索方法中的蚁群算法，求得模型的最优解（或近似解）。文章以30个杭州公共自行车站模型为例，用改进蚁群算法求解调度回路。【关键词】TSP；启发式搜索；蚁群算法；公共自行车调度一【引言】1.1问题背景随着绿色出行理念的普及，公共自行车作为一种节能、环保、健康的出行方式，越来越受到人们的青睐．国内以杭州、上海、武汉、南京等为代表的多个城
    市在大力发展公共自行车的同时，也出现了种种问题，其中最突出的是借车时车已借完还车时车位已满．针对这一问题，除了对公共自行车租赁点的布局、规模进行合理规划外L1]，还需要在营运中建立准确、高效的调度系统．杭州市公共自行车目前共有1080个租车点，在为广大市民和游客带来出行方便的同时，随着租赁网点以及投入使用的自行车数量的不断增加，也对自行车的管理调度提出了更高的要求。以下图片是关于杭州公共自行车的相关网页和相关手机应用中采集的一个正常工作日下的晚高峰时候的杭州城战、浙大玉泉校区正门附近以及古荡附近区域的自行车租借情况。图1.古荡晚高峰自行车租借情况图2.杭州城战晚高峰租借情况
    图3.浙大玉泉校区附近自行车租借情况从图1和图2的对比可以看出，晚高峰时候某些站点（如古荡）存在有车难还的情况，而某些站点（如城战）存在无车难借的问题，同时又有某些站点（如浙大玉泉校区）存在附近租借车不平衡问题。因此，这为我们对自行车调度问题进行优化提供了必要性依据。综上分析，杭州公共自行车的问题主要是在特殊时间段“借车难、还车难”的问题，缺乏合理的调度成为继选址不合理等已经确定的因素以外的又一重要部分。公共自行车站点的及时调度和再分配可以有效的提高系统中自行车的周转和租用率，提高公共自行车系统的利用率和用户满意度。“调度自行车”问题类似于在不同站点之间寻找一条最优的路径的经典的旅行商问题，求解问题的难度随站点数量的增大而增大。1.2问题的重述杭州在全国首推公共自行车服务系统，以缓解行路停车难，解决“最后一公
    里”交通问题。公共自行车借车、还车环节需在服务点完成。每个服务点设有若干车架，每一车架只能锁住一辆自行车。当车架上有车时，刷卡开锁就可借出自行车；当车架上无车时，可刷卡将车锁在该车架上实现还车；当服务点所有车架都有车（简称满架）时，只能借车而不能还车；当服务点所有车架都无车（简称空架）时，不能借车而只能还车。服务点的理想状态是既不满架也不空架，出行人可根据自己需求就近随时借车还车。服务点为不理想状态时，就会出现借不了车或是还不了车的情况。此时工作人员可通过上架或下架操作使该服务点恢复理想状态。若服务点满架，则下架部分自行车置于附近；若服务点空架，则将部分置于附近的自行车上架。现在需要利用数学建模的思想解决以下问题：假设在固定范围区域内自行车的租借站点地址已知，现在需要通过一辆大型自行车调度车从起始点出发调度一次，使得调度经过所有的站点且路径最短，应该选择什么样的路径和工作顺序。二【正文】2.1模型的数学描述公共自行车调度问题是一个特殊的TSP问题，调度车必须从一个固定的起点出发。并且在每个经过的站点数收集多余的自行车或者投放一定数量的自行车，最终回到起点，完成一次自行车调度。根据调度模型的特殊性，建立模型的数学描述：给定图G=（V，A）式中，V为给定自行车站点的集合；A为各个站点直接相连的边。设D=dij是站点i和j之间的距离矩阵；设B=bi为各个自行车所要调度的自行车数目，当bi>0时，表示该自行车站点有多余的bi辆自行车，当bi<0时，表示该自行车站点需要补给bi辆自行车，当bi=0时，说明该自行车点不需要调度。各个站点的bi是根据统计采样数据由当前实际自行车数和采样平均数据相减计算获得。同时我们可以假设所有的bi的和为0，如果有特殊的投放自行车，可以将多余的自行车数映射到某个站点，以保证所有bi之和为0。约束条件分析：首先调度车上自行车的数量必须大于等于下一个站点的补给自行车的需求，否则调度车上的自行车将不够投放；其次，必须保证下一个站点多余的自行车能够在调度车上有足够的冗余空间来放置，否则不能处理多余的自
    行车。综上所述，可以记bai为为调度过程中调度车上的自行车数量，其中bai必须满足0ibaBIKEMAX，再由上述两个约束条件得到01iiibbabaBIKEMAXbbabaiii1其中)0(,0)0(,1tttbbbba调配中心是否需要加入一定数量的车由后续站点的需求决定【目标函数】niiiddL11min从而上述自行车调度问题可以转化为如何走一个最短路径的hamilton回路来实现需求自行车的调度问题，这是一个特殊的TSP问题。2.2模型的基本假设（1）每个公共自行车站点周围有足够的自行车供调整。（2）每个站点的某个时刻的自行车借还需求已知。（3）自行车的任何一个站点经行一次调整之后能够保证一定的理想状态。（4）假设调度车必须走过每个站点查看现场情况，即一个完整Hamilton回路。2.3模型的求解旅行商问题是1个典型的组合优化问题，并且是1个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式。蚁群算法可以很好地应用到旅行商问题的优化求解中，经过修改后可应用到自行车系统站间调度优化的问题中，在Matlab中应用蚁群算法优化调度回路的过程如下：1)初始化程序参数。输入站点位置、距离dij自行车数bi等基础数据；初始
    化蚁群算法参数：蚂蚁数量、迭代次数、计算参数等。2)迭代计算。(1)在随机站点生成若干个蚂蚁。(2)每个蚂蚁独立寻找自己的回路。每个调度回路中：a．整理出下一站点列表，先清理出已经过的站点，得到未经过的站点列表；再在其中清除掉不能满足调度车容量约束或下一站点补给约束的站点，得到满足约束的下一站点列表。b．计算下一站点列表中的转移概率，根据生成的随机数选择其中的一个作为下一站点。重复以上2步，直到该蚂蚁走完所有站点，完成自己的调度回路。每个蚂蚁重复以上步骤，直到所有蚂蚁完成各自的调度回路。(3)计算每个蚂蚁的调度回路总距离，记录此次迭代中的最优回路。(4)计算此次迭代后的信息素变化。计算挥发的信息素、增加的信息素，更新此次迭代的信息素。(5)重复迭代，直到迭代次数达到最大次数。3)输出结果。从每次迭代记录的最优调度回路中选择最终的最优回路，计算最优回路的距离，输出调度回路的访问顺序，输出调度过程的自行车数变化情况。与普通的旅行商问题相比，自行车调度优化的蚁群算法主要进行了以下修改：①每经过1个站点后，重新计算调度车上自行车数量；②选择下一站点之前，考虑了调度车容量约束和下一站点补给约束，清理不满足约束的站点。2.4简易模型构建
    1600120050080025040025050050040040090090020090070030040040040040040090090090090025025025030050050012001200120012001200120090050030030030030080080080080080025025025025020025020045045060012345500678910111218292427171913141516212825262223203050070050根据这张简单的30个自行车租用点的位置，计算出每个点的坐标如下：[7001950;20001950;30001950;35001950;41751950;2001450;6001450;01050;12501050;20001050;22001050;24001050;33001100;35001050;39001050;42001050;3000850;2000800;2800800;2500600;3000600;3800600;4200600;2100350;2800300;3800300;230050;280025;1600200;410025];城市的坐标矩阵
    【自行车需求调度表】租赁点序号12345678910自行车需求+12+16-20-42-25+26+31-12-20-13租赁点序号11121314151617181920自行车需求-20-18-7-19+62+22-18-11-1+2租赁点序号21222324252627282930自行车需求-21+15+17-160-14+32+6-19+552.5蚁群算法的matlab实现%蚁群算法求解TSP问题的matlab程序clearallcloseallclc%初始化蚁群m=30;%蚁群中蚂蚁的数量，当m接近或等于城市个数n时，本算法可以在最少的迭代次数内找到最优解C=[7001950;20001950;30001950;35001950;41751950;2001450;6001450;01050;12501050;20001050;22001050;24001050;33001100;35001050;39001050;42001050;3000850;2000800;2800800;2500600;3000600;3800600;4200600;2100350;2800300;3800300;230050;280025;1600200;410025];%城市的坐标矩阵Nc_max=200;%最大循环次数，即算法迭代的次数，亦即蚂蚁出动的拨数（每拨蚂蚁的数量当然都是m）alpha=1;%蚂蚁在运动过程中所积累信息（即信息素）在蚂蚁选择路径时的相对重要程度，alpha过大时，算法迭代到一定代数后将出现停滞现象beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度rho=0.5;%0
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料