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

目录

一、问题引入 ..................................................................................................................................... - 3 - 二、问题分析 ..................................................................................................................................... - 3 -

2.1第一问分析 ................................................................................................................... - 4 - 2.2第二问分析 ................................................................................................................... - 4 - 2.3第三问分析 ................................................................................................................... - 4 -

三、模型假设和符号说明 ................................................................................................................. - 5 -

3.1模型假设 ....................................................................................................................... - 5 - 3.2符号系统 ....................................................................................................................... - 6 -

四、模型建立 ..................................................................................................................................... - 6 -

4.1模型分类 ....................................................................................................................... - 6 - 4.2 租赁点分配方案建模 .................................................................................................. - 7 - 4.3 调度车调度方案建模 .................................................................................................. - 8 -

4.3.1一辆调度车调度方案 ....................................................................................... - 8 - 4.3.2多辆调度车调度方案 ....................................................................................... - 9 - 4.4租赁点数目和位置的确定 ......................................................................................... - 11 - 4.5 调度时间的模型 ........................................................................................................ - 12 -

五、 模型的求解 ............................................................................................................................. - 13 -

5.0经纬度转换为横纵坐标 ............................................................................................. - 13 - 5.1 求解最短路径 ............................................................................................................ - 13 - 5.2 模型一次运行后的单车重分配求解 ........................................................................ - 14 - 5.3 求解分配方案的预估—校正算法 ............................................................................ - 16 - 5.4 求解调度方案的启发式算法 .................................................................................... - 16 -

5.4.1算法简介 ......................................................................................................... - 16 - 5.4.2算法内容 ......................................................................................................... - 17 - 5.4.3约束条件 ......................................................................................................... - 18 - 5.4.4算法流程图 ..................................................................................................... - 19 - 5.5租赁点位置 ................................................................................................................. - 20 - 5.6计算结果 ..................................................................................................................... - 20 -

5.6.1第一问结果 ..................................................................................................... - 20 - 5.6.2第二问结果 ..................................................................................................... - 21 - 5.6.3第三问结果 ..................................................................................................... - 23 -

六、模型检验 ................................................................................................................................... - 26 - 七、模型优缺点以及改进 ............................................................................................................... - 26 -

7.1分配方案的优点 ......................................................................................................... - 27 - 7.2调度方案的缺优点 ..................................................................................................... - 27 - 7.3新增节点模型的优缺点 ............................................................................................. - 27 - 7.4模型和算法的改进 ..................................................................................................... - 28 -

- 1 -

7.4.1算法的改进 ..................................................................................................... - 28 - 7.4.2模型的改进 ..................................................................................................... - 28 -

八、参考文献 ................................................................................................................................... - 30 - 附录 ................................................................................................................................................... - 30 -

- 2 -

一、问题引入

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

（1）根据目前经开区网点自行车需求情况等信息，要求调度平均耗时尽量少，针对已有的30个租赁点设计最优车辆分配方案、调度方案，给出完成调度所耗费的时间。

（2）假设经开区公共自行车服务系统三期建设准备投入建设经费200万元， 据此建立数学模型，确定新增租赁点数目、位置以及合适的放置车辆数目。 （3）针对问题（2），进一步研究，如果要求在150min内完成调度，确定是否需要增加调度车辆（购置调度车辆费用由其它项目经费解决，不包含在三期建设提供的200万元经费中间），并给出该情形下的自行车调度方案。

二、问题分析

首先，题目给出的初始条件为经度和纬度，我们利用地球的坐标系统将其转换为平面坐标，后续的计算都在平面坐标的基础上进行。

- 3 -

2.1第一问分析

第（1）问对对应前两期工程，30个租赁点已知，因此在已知的点上根据需求量确定自行车的分配方案和调度方案。这个问题是在已知节点具体的位置的条件下求解两个问题：每个节点的自行车分配问题和调度问题。这两个问题可以分开来求解。

第(1)问要求调度时间尽量少，我们从计算两点的最短路径入手，将最短路径计算出后考虑将早中晚三个时间段内的高峰期取平均值后再最初计算。我们建立反比例函数关系式：p=Kd，再根据归一化条件求得2km内的概率系数K。随后，算出每个点以需求量的数目的前提下会向2km内的各个租赁点送出多少辆单车，并以负反馈的方式经多次计算得出一个稳定解，即大部分租赁点的单车数量满足110%的要求，少部分租赁点单车数目远远超出需求量，还有少部分单车数目几乎为零（奇点）。最后，将计算所得的几个奇点分块，从单车数量超出40或大量超出需求量的地点运送单车至奇点并计算运送时间。

2.2第二问分析

第（2）问对应第三期工程，根据投入的建设费用等确定新增的租赁点的数目和每个租赁点的分配方案。这些新增的租赁点是在规定的70个点中选取的，而且每个待选点的需求量是给定的，因此在需求量和工程费用的限制下，求实现服务系统最优的选点方案和分配方案。

建立新的一定数目的租赁点，我们首先将另外70个点的数据列出，考虑到是否选择一个点与这个点的平均需求量和最大需求量均有关，所以将早中晚三个时间段的需求量的平均值和三个时间段需求量的最大值列出，然后将这两个数据以一定比例加权平均，最后得出的数字排序，由上到下计算出每个点的需求金额，截止到2000000元时。租赁点即为截止前的点，相对应的数目即为每个点对应的数目。

2.3第三问分析

第（3）问建立在第（2）问的基础上，同第（1）问，类似，在解第（3）问

- 4 -

前，租赁点的具体位置和需求量已知了，并且，这些租赁点的分配方案也已将求得，很容易求得每一个租赁点需要调度的具体数值，在这些已知条件下，要求在给定时间内完成调度，给出调度方案。如调度车辆不够，则给出增加的车辆数目和调度方案。问题类似于第（1）问的给出分配方案后求调度的问题。

根据以上分析，我们要解决的问题主要有以下几个部分： 1、求出任意两个租赁点之间的最短路径。 2、求出给定租赁点的分配方案。

3、求出给定租赁点的系统的自行车调度方案。 4、在给定约束下求租赁点的数目和位置。

解决以上三个问题，本题所要求的问题就可以解决了。

三、模型假设和符号说明

3.1模型假设

1、每个租赁点调度需求量为负，有多余的自行车可以提供给调度车则为正数； 2、假设两个停车场就在某两个租赁点上，则选取的两个租赁点必须是有自行车盈余的点，并且调度车出发后，车上装载的自行车的数量就是租赁点的调度量。由于每个租赁点的自行车最大分配量小于调度车的最大装载量，所以总是能够将盈余量全部装在调度车上；

3、每辆调度车从固定的某租赁点出发，最后又回到原来的点，以方便下次调度 但是回到原点的时间可以不计。因为只有在调度完成后才会回到原点，此时不 需要调度，不再受时间限制；

4、同一辆调度车只能经过同一个租赁点一次（除了作为车站的租赁点）； 5、每次到达下一个租赁点时，调度车上的自行车数量满足该租赁点需求，即对于需求点来说，只需用调度一次就完成调度；对于盈余点来说，调度车到达这些点要尽量多装。如果未达到调度车的限量就将该租赁点所有的盈余自行车装载，

- 5 -