公共自行车调度问题(16)

《公共自行车调度问题(16)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：公共自行车调度问题

2、我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：公共自行车调度问题摘要本文研究的是利用公交车对公共自行车进行调度的问题，选择最佳的公交车行驶路径，使得花费的总时间最小，且每个自行车租

3、赁点的自行车能够满足市民的要求。对于第一问，我们将求最佳公交车路径问题转化为求花最少时间的公交路径问题，并建立最小生成树模型。先求出居民区以及交通圈内11个点两两之间的距离，进而求出连通所需要的时间，将时间最为两点间的权重；接着利用避圈法，通过Matlab编程求出最小生成树；最后我们结合公交车行驶的方向性，找出连通区域内17个租赁点的回路，这个回路就是我们要求的最佳行车路线：公交站→30→1→3→5→9→10→11→18→6→4→26→23→21→22→24→5→7→2→29→28→27→2→公交站，需要的时间为59.04分。对于两辆公交车，我们将这17个点分

4、为两组进行考虑，类比一辆公交车的分析方法以及模型求解。我们提出了两种分组方案，并引入均衡度的概念进行比较分析，选择均衡度较小的方案。最终确立的两条路线为：第一组路线：公交站→1→3→5→9→10→11→18→6→2→公交站；花费的时间为：24.92分钟；第二组：公交站→30→29→28→23→21→22→24→25→5→7→8→2→公交站；花费时间为：28.28分钟。（粗体表示公交车经过但不停车）对于第二问，我们同样分组考虑。经过分析我们知道公交车最多只能开3趟，由此我们根据聚集程度将租赁点分为3个小组，用第一问的模型进行求解。分组的方案我们考虑了两种，比较两

5、个中方案能够运送的最大自行车数量，选择能运较多自行车数的方案。对于第三问，我们引入了VRP模型，这一模型是用于解决物流配送问题，和我们要解决的用公交车对自行车调度问题很相似。由于这属于NP难问题，我们无法求出最优解，因此要用启发式算法进行搜索求解，以行驶时间最短、搬运车数最多为目标，进行全局域范围的考虑，对公交车的可选路线进行搜索，找到最优的可行路线，得到一个近似解。关键字：最小生成树避圈法均衡度VRP模型启发式算法Matlab编程151.问题的背景与重述1.1问题背景地铁时代的来临将给杭州公共自行车带来更突出的上下班高峰潮汐现象。早晨大量市民骑车到地铁站，造

6、成地铁交通圈集中大量的公共自行车，而居民住宅区无车借用情况；傍晚从地铁站骑车回家，造成地铁站周围无车可借而居民区却因车子停满无处还车。因此，需要对自行车管理提出更高的要求。1.2问题重述目前，杭州公交集团一般用拆掉作为的公交车运送自行车到各个自行车租赁点，每辆公交车可装50辆自行车。设高峰时段公交车行驶速度为30km/h,减速停靠路边的所需时间1分钟，每送出或取回一辆自行车往返所需时间为0.3分钟（设搬运车辆从L5路东侧公交总站出发，完成搬运任务后返回公交总站，公交总站具体位置见附录表1）。且假设每个十字路口或三岔路口公交车直行等待时间为1分钟，左拐等待绿灯的

7、时间为1.5分钟，右拐等待绿灯时间为0.5分钟。试解决一下问题：1.分别针对一辆搬运车和两辆搬运车的情况找出从地铁2号地铁交通圈自行车租赁点将多余自行车送到居民区租赁点的最佳公交行车路线（图中马路都是双向道，不考虑穿马路搬车，路口和马路中间不允许公交车掉头，21号点所在的断头路可掉头）。2.如果1号自行车租赁点积聚了200辆多余的自行车，居住区虚线框内11个租赁点都是空的，问一辆公交车应该以怎样的顺序向着这些租赁点搬运自行车？请列出行车路线以及具体的搬运顺序与数量，并计算所需的时间（公共自行车租赁点一般要求停车桩内自行车数量不少于停车桩总数的20%，不多于停车

8、桩总数的80%，多余车辆要移到停车桩外