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

《公共自行车调度问题-数学建模论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录一、问题引入3二、问题分析32.1第一问分析42.2第二问分析42.3第三问分析4三、模型假设和符号说明53.1模型假设53.2符号系统6四、模型建立64.1模型分类64.2租赁点分配方案建模74.3调度车调度方案建模84.3.1一辆调度车调度方案84.3.2多辆调度车调度方案94.4租赁点数目和位置的确定114.5调度时间的模型12五、模型的求解135.0经纬度转换为横纵坐标135.1求解最短路径135.2模型一次运行后的单车重分配求解145.3求解分配方案的预估—校正算法165.4求解调度方案的启发式算法165.

2、4.1算法简介165.4.2算法内容175.4.3约束条件185.4.4算法流程图195.5租赁点位置205.6计算结果205.6.1第一问结果205.6.2第二问结果215.6.3第三问结果23六、模型检验26七、模型优缺点以及改进267.1分配方案的优点277.2调度方案的缺优点277.3新增节点模型的优缺点277.4模型和算法的改进28-36-7.4.1算法的改进287.4.2模型的改进28八、参考文献30附录30-36-一、问题引入近年来，随着经济的发展，我国各级城市的机动车保有量都进入了持续高速增长时期，但由此

3、所引发的道路拥堵、空气污染也引起了政府以及百姓的极大关注。众所周知，建立快速、便捷的城市公共交通体系是解决这一问题的有效手段之一。然而，居民居住地和交通站点通常都有一段距离，这段不远的距离以及现实存在的公共交通拥挤现象则使居民乘坐公共交通的意愿降低，而将公共自行车租赁服务系统纳入城市公共交通体系，能够从一定程度上缓解这一现象。西安市经济开发区公共自行车服务系统于2011年4月开始建设，到目前为止，已建成租赁点30个，自行车总量达到850辆。目前正在筹备第三期建设，请你针对如下问题建模：（1）根据目前经开区网点自行车需求情

4、况等信息，要求调度平均耗时尽量少，针对已有的30个租赁点设计最优车辆分配方案、调度方案，给出完成调度所耗费的时间。（2）假设经开区公共自行车服务系统三期建设准备投入建设经费200万元，据此建立数学模型，确定新增租赁点数目、位置以及合适的放置车辆数目。（3）针对问题（2），进一步研究，如果要求在150min内完成调度，确定是否需要增加调度车辆（购置调度车辆费用由其它项目经费解决，不包含在三期建设提供的200万元经费中间），并给出该情形下的自行车调度方案。二、问题分析首先，题目给出的初始条件为经度和纬度，我们利用地球的坐标系

5、统将其转换为平面坐标，后续的计算都在平面坐标的基础上进行。-36-2.1第一问分析第（1）问对对应前两期工程，30个租赁点已知，因此在已知的点上根据需求量确定自行车的分配方案和调度方案。这个问题是在已知节点具体的位置的条件下求解两个问题：每个节点的自行车分配问题和调度问题。这两个问题可以分开来求解。第(1)问要求调度时间尽量少，我们从计算两点的最短路径入手，将最短路径计算出后考虑将早中晚三个时间段内的高峰期取平均值后再最初计算。我们建立反比例函数关系式：p=Kd，再根据归一化条件求得2km内的概率系数K。随后，算出每个点

6、以需求量的数目的前提下会向2km内的各个租赁点送出多少辆单车，并以负反馈的方式经多次计算得出一个稳定解，即大部分租赁点的单车数量满足110%的要求，少部分租赁点单车数目远远超出需求量，还有少部分单车数目几乎为零（奇点）。最后，将计算所得的几个奇点分块，从单车数量超出40或大量超出需求量的地点运送单车至奇点并计算运送时间。2.2第二问分析第（2）问对应第三期工程，根据投入的建设费用等确定新增的租赁点的数目和每个租赁点的分配方案。这些新增的租赁点是在规定的70个点中选取的，而且每个待选点的需求量是给定的，因此在需求量和工程费

7、用的限制下，求实现服务系统最优的选点方案和分配方案。建立新的一定数目的租赁点，我们首先将另外70个点的数据列出，考虑到是否选择一个点与这个点的平均需求量和最大需求量均有关，所以将早中晚三个时间段的需求量的平均值和三个时间段需求量的最大值列出，然后将这两个数据以一定比例加权平均，最后得出的数字排序，由上到下计算出每个点的需求金额，截止到2000000元时。租赁点即为截止前的点，相对应的数目即为每个点对应的数目。2.3第三问分析-36-第（3）问建立在第（2）问的基础上，同第（1）问，类似，在解第（3）问前，租赁点的具体位置

8、和需求量已知了，并且，这些租赁点的分配方案也已将求得，很容易求得每一个租赁点需要调度的具体数值，在这些已知条件下，要求在给定时间内完成调度，给出调度方案。如调度车辆不够，则给出增加的车辆数目和调度方案。问题类似于第（1）问的给出分配方案后求调度的问题。根据以上分析，我们要解决的问题主要有以下几个部分：1、求出任意两个