公共自行车租赁.docVIP

光电26队数模模拟训练1 对“城市公共自行车租赁服务系统规划”问题的研究 学院：光电 指导教师：杨春德 西安市经开区公共自行车服务系统设计 摘 要 本文研究的是西安市经开区公共自行车的分配和调度优化问题，通过建立0—1整数规划模型，线性规划模型以及自行车分配调度模型，设置合理的分配方案和调度方案，以满足所有租赁点对自行车的数量需求，同时车辆调度花费时间力求最短。最后，通过最小生成树算法得到最优路径和最短时间。 对于第一问，根据目前经开区网点自行车需求情况，若要求调度平均耗时尽 量少，请针对已有的30个租赁点设计最优车辆分配方案、调度方案，并给出完成调度所耗费的时间。 依据租赁点的需求和约束条件对自行车进行初始；依据经纬度和Floyd算法求出各租赁点之间的距离，引入0—1变量表示租赁点间是否发生调度、，采用最小生成树算法，经过租赁点的时间及装卸自行车的时间为权重，通过MATLAB编程采用避圈法求解最小生成树，求得的路径就是最佳行车路线，其中每辆车调度一次平均用时135分钟，完成一天的调度总时间为806分钟。 对于第二问，约束为投入经费总数和租赁点自行车需求，目标是设置的租赁点能够覆盖更大的面积，而且整个调度花费时间较少，用excel将备选租赁点需求量由大到小排序，选取自行车需求较多的网点，应用动态规划算法，设新增租赁点数为k,代入经费约束即可得到k值不大于25，通过调整新增租赁点采用启发式有哪些信誉好的足球投注网站求新增网点和车辆的合适分配方案，编程得出新增网点为24个，自行车总数751辆 ，总耗资195.1万。 对于第三问，通过增加调度车来减少调度时间，首先，我们同问题一一样确定了调度车的路线，考虑到最大限度提高调度的效率，于是，同时对应着附件所给的地图做出了相应的调整，尽量让一辆调度车在某一个区域中调度，从而覆盖全范围。新增调度车k辆，根据问题二的分配结果用问题一的模型计算调度花费的时间，各分区内都采用最小生成树算法求解最优调度路线，改变k值和分区，直到所有分区都能满足150分钟内调度完毕，即为新增调度车数。 关键词：最优分配 VRP模型 最小生成树避圈法 启发式有哪些信誉好的足球投注网站 0-1变量 一、问题背景与重述 近年来，随着经济的发展，我国各级城市的机动车保有量都进入了持续高速增长时期，但由此所引发的道路拥堵、空气污染也引起了政府以及百姓的极大关注。众所周知，建立快速、便捷的城市公共交通体系是解决这一问题的有效手段之一。然而，居民居住地和交通站点通常都有一段距离，这段不远的距离以及现实存在的公共交通拥挤现象则使居民乘坐公共交通的意愿降低，公共自行车服务系统已被证明能够从一定程度上缓解这一现象。西安市经开区前两期建设的租赁点有30个，出租自行车达850辆，而且每个租赁点放置车不超过40辆，车辆总数超过需求量的10%。调度车有2辆，每次运载50辆自行车。目前正筹备第三期租赁点的建设，请你就如下问题建模： （1）根据目前经开区网点自行车需求情况等信息，若要求调度平均耗时尽 量少，请针对已有的30个租赁点设计最优车辆分配方案、调度方案，并给出完成调度所耗费的时间。 （2）假设经开区公共自行车服务系统三期建设准备投入建设经费200万元， 据此建立数学模型，确定新增租赁点数目、位置以及合适的放置车辆数目。 （3）针对问题（2），进一步研究，如果要求在150min内完成调度，是否需 要增加调度车辆（购置调度车辆费用由其它项目经费解决，不包含在三期建设提供的200万元经费中间）？并给出该情形下的自行车调度方案。 附加问：（如有时间，参赛者可以选作，在评阅时作为附加分参考） （4）经开区计划建设公共自行车借还在线查询网站（参考神木县公共自行 车网站/map.asp或其它类似网站），实现借还数据的实时更新。届时，自行车调度专员需要根据系统实时数据进行实时调度。如果要求站点自行车数量超过90%就必须下架一部分车，站点自行车数量不足20%时，就要补车，保证用户任何时间都能取车还车。请考虑动态的车辆调度方案设计，给出此时的自行车调度模型并模拟计算。 二、问题分析 针对以上问题，我们首先要根据题目给出的经纬度与位置坐标，通过MATLAB计算出两两之间的距离。 问题一分析：本问题可以看成是单目标规划问题，我们的目标是使公交车行驶的路程最短，再将路程转换成时间来进行计算求解。考虑到在一次调度车全程收集和分配自行车总数不相上下的情况，即在一次调度中，不管你选择的路径如何，其装载或卸载的自行车的时间可以看做一个常数。从而目的是要找到一条最短的公交行驶路径。我们用0-1变量来表示公交车是否从租赁点i到达租赁点j，而且每时每刻调度车上的自行车数不得超过限载量50辆。通过对本问题的分