数学建模结课论文Word文档下载推荐.docx
《数学建模结课论文Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数学建模结课论文Word文档下载推荐.docx（28页珍藏版）》请在冰点文库上搜索。
3、求出给定租赁点的系统的自行车调度方案。
4、在给定约束下求租赁点的数目和位置。
解决以上三个问题，本题所要求的问题就可以解决了。
三、模型假设和符号说明
3.1模型假设
1、每个租赁点调度需求量为负，有多余的自行车可以提供给调度车则为正数；
2、假设两个停车场就在某两个租赁点上，则选取的两个租赁点必须是有自行车盈余的点，并且调度车出发后，车上装载的自行车的数量就是租赁点的调度量。
由于每个租赁点的自行车最大分配量小于调度车的最大装载量，所以总是能够将盈余量全部装在调度车上；
3、每辆调度车从固定的某租赁点出发，最后又回到原来的点，以方便下次调度
但是回到原点的时间可以不计。
因为只有在调度完成后才会回到原点，此时不
需要调度，不再受时间限制；
4、同一辆调度车只能经过同一个租赁点一次（除了作为车站的租赁点）；
5、每次到达下一个租赁点时，调度车上的自行车数量满足该租赁点需求，即对于需求点来说，只需用调度一次就完成调度；
对于盈余点来说，调度车到达这些点要尽量多装。
如果未达到调度车的限量就将该租赁点所有的盈余自行车装载，如果多出，则装满。
3.2符号系统
G------租赁点的集合
------调度总时间（不包括完成调度后调度车返回原点的时间）。
------调度车编号
------租赁点间的最短距离
------第k辆车调度完i后是否再调度j
------是否使用调度车k
------租赁点j的需要调度的量
------i和j间的距离是否大于M千米
------t时间段内租赁点j的需求量
------j点的需求量占总需求量的比例
------从i点出发到达j租赁点的自行车数量
------i点的单车数量
a------建立一个租赁点耗资
b------维护每辆自行车耗资
p------每一个租赁点的耗资数
P------新增租赁点的耗资总数
四、模型建立
4.1模型分类
影响租赁点自行车分配的因素有：
各租赁点的需求量、从租赁点离开的自行车、从其他租赁点起来的自行车等。
若仅考虑需求量对租赁点分配自行车数目的影响，有如下模型：
（1）式确定按照最终的需求量，以按比例分配的方式确定租赁点的分配量。
（2）式给出需求量占总需求量的比例。
以仅考虑需求量的方式确定的分配方式显然不是最佳方案。
分配方案还和租赁点之间的距离有关。
由题意可知，从在某个租赁点还车的概率与租车点和还车点的距离成反比，且假设居民的骑行距离不超过Mkm，由此可得出下式：
式（4-2-3）首先按照（4-2-1）式的方式产生一组分配方案，然后让其按照自行车间行驶的规则再次分配，产生新的一组分配方案，然后用（4-2-4）式校正，最终得到优化了的分配方案。
4.3.1一辆调度车调度方案
在我们的求解问题中，第一问中调度车辆问2辆，为了问题是建模化简，我们先考虑调度车为一辆的情况，然后推广到多量的情况，这样就可以给对第一问和第三问的调度问题建立实际的解题模型。
设拥有最大负荷为Q的调度车从指定的节点出发，对集合为G的节点进行调度。
完成任务后返回原点。
调度需求量和租赁点间的距离已经求得。
整个调度方案可以由下列一组方程和约束条件确定：
（4-3-1）式为目标函数，求出最短距离；
（4-3-2）确定了出发点，即必须从出发点出发，然后再回到出发点；
（4-3-3）-（4-3-4）确定了调度车对特定节点只能调度1次，不能重复经过一个节点；
（4-3-5）式保证调度车调度时调度车上的数量能够满足任意节点的调度需求量，同时装载量不能超过调度车的最大载重；
（4-3-6）式确定了某一节点的总需求量就是从该租赁点离开去往其他租赁点的自行车的数量之和；
（4-3-7）式确定了每一节点的调度量；
（4-3-8）式给出总需求量、分配量、调度量从该节点出发的自行车数目和到达该节点的自行车的数量之间的关系。
4.3.2多辆调度车调度方案
设拥有最大负荷为Q的k调度车从指定的节点出发，对集合为G的节点进行调度。
（3-4-9）式为目标函数，求出最短距离；
（3-4-10）式确定调度车的数目；
（3-4-11）确定了出发点；
（3-4-12）-（3-4-13）确定了每辆调度车对特定节点只能调度1次，不能重复经过一个节点；
（3-4-14）式保证每次调度时调度车上的数量能够满足任意节点的调度需求量，同时装载量不能超过调度车的最大载重；
（3-4-15）式确定了某一节点的总需求量就是从该租赁点离开去往其他租赁点的自行车的数量之和；
（3-4-16）式确定了每一节点的调度量；
（3-4-17）式给出总需求量、分配量、调度量从该节点出发的自行车数目和到达该节点的自行车的数量之间的关系。
（3-4-18）式保证不同的调度车不能再同一时刻到达同一个租赁点。
根据以上一组方程和约束条件，就可以将调度问题相对完整的描述出来。
这是一个优化问题，在求解过程中由众多的算法可以采用，但是考虑到算法的复杂性可标称的简洁性，我们采用的算法是启发式算法，这将在模型求解中详细讨论。
题目中新增的租赁点是在已知的若干点中选取的，因此，分析清楚选取租赁点的约束条件，就可以从最优解的角度得到新增的节点。
建立租赁点时首先考虑的是各个点的需求量（已知），由于在不同时段的需求量不同，所以应当考虑平均需求、不同时段需求。
所以首先我们应当确定加权平均比例，一保证确定的租赁点在全天达到最优。
在这里引入一个加权平均比，取决于我们实际问题的要求和调度问题的特点。
首先将数据加权平均，有：
再将每一个租赁点的耗资数额按照公式（4-4-1）求出
最后将耗资数额加和，即求得满足式（5-2-2）的最大k值。
考虑了需求量对新租赁点的影响之后，我们还需要考虑骑行规律对租赁点选取的影响。
所谓运输规律就是：
居民可以在任意一个租赁点还车，在某个租赁点还车的概率与租车点和还车点的距离成反比，且假设居民的骑行距离不超过M。
于是仅考虑运输规律，我们引入一个方便因数，定义如下：
Con用来衡量新设置的租赁点的合理程度，它与租赁点的分配量、常数
、
的乘积之和有关，其中，常数
的定义如下：
表示i租赁点能够到达其他节点的数目之和，
越大表明该节点的辐射能力越强，也越合理。
在路程不超过M的范围内，租赁点i能够到达的节点越多，则常数
越大。
还要保证新增的节点数k尽可能地少。
在新增租赁点的过程中不考虑随后的调度方案，因此在总建设经费的限制下，可以按照优化的方法求出方便因数的最小值。
在三期建设中，为了实现经开区更大的网点覆盖面积，进一步增设站点，新增了一批租赁站点并购进自行车。
然而，更多的站点可能会导致部分租赁点的自行车短缺或堆积现象，从而降低了资源利用效率。
为了探讨这个问题，我们必须对现有调度方案进行检验和矫正，更好的实现资源利用最大化。
故对调度时间进行了计算，发现用两辆调度车进行自行车调度很难满足调度需求,调配时间超过限制时间，必须购置更多的调度车辆，虽然会增加一定成本，但对整体的统筹有很大的意义。
将原有的站点与新增站点进行混合，重新根据密集度，自行车需求量等因素进行分组，根据分组情况配备调度车辆。
若所分组数增多，则增加调度车辆的数目可以更快捷地实现调度需求。
然后对每一组的调度方案进行独立分析，即求解
则总调度时间：
（k代表组数）
具体建模思想与第一问的求解相似。
Floyd算法的描述如下：
设
为从i到j的只以
集合中的节点为中间节点的最短路径的长度。
若最短路径经过点k，则
；
若最短路径不经过点k，则
。
因此，
if（
）
综上,最短路径矩阵为：
（单位：
km）
if
else
k=k+1;
根据反比例关系不难得出每个租赁点向2km内的各个租赁点发送的单车数量为：
根据归一化条件：
综上可得出求得2km内的概率系数K的算法：
s=0;
if
;
K=[Ks];
根据各个租赁点发送出的单车概率可求得运行一次后的各个租赁点单车数目：
据此可得出求解运行一次后的各个租赁点单车数目的算法：
t=0;
5.4求解调度方案的启发式算法
5.4.1算法简介
启发式算法是依据有限的知识在短时间内找到问题解决方案的一种技术。
在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解。
在搜寻问题中，每个节点都有b个选择以及到达目标的深度d，一个毫无技巧的算法通常都要搜寻bd个节点才能找到答案。
启发式算法借由使用某种切割机制降低了分叉率（branchingfactor）以改进搜寻效率，由b降到较低的b'
分叉率可以用来定义启发式算法的偏序关系，例如：
若在一个n节点的搜寻树上，h1（n）的分叉率较h2（n）低，则h1（n）<
h2（n）。
启发式为每个要解决特定问题的搜寻树的每个节点提供了较低的分叉率，因此它们拥有较佳效率的计算能力。
我们主要应用启发式算法的这个优点来解决本题的调度问题。
算法的流程图如下：
图5-4-3
5.4.2算法内容
以指定租赁店点为初始站点，对该租赁点的下一租赁点，搜索路径，搜索规则如下：
（1）查找与初始点距离最近的N个租赁点（N值按照题目适当确定），并且按照距离由小到大的规律排序；
（2）依次遍历排好序这N个租赁点，如果这个租赁点为需求点且需求量大于车上的剩余自行车（无法满足一次性完成调配），则删除该节点，并重新得到新的N个租赁点。
（3）计算每一层的自行车调度数量（取绝对值）和走过的距离，并求出两者的比值。
（4）以搜索到的满足条件的N个租赁点分别为初始点，重复第
（1）-（3）步。
搜索深度为N。
（5）求出每一次搜索路径自行车调度数量和走过距离的比值后，求和，选取比值之和最大的那条路径，则这条路径中初始节点对应的下一节点为调度方案的下一个调度点。
（6）以下一个点为起始点，重复第
（1）-（5）步，直到所有的车辆都被搬运完毕。
算法如图所示：
1、综合考虑租赁点的数目，搜索深度根据不同分组的站点数目N取3~5。
2、如果租赁点是调度需求点，则调度车上的自行车数目必须满足需求，一次性完成该租赁点的需求；
如果该点是盈余点，则在不超过调度车最大负载的情况下，调度车要尽可能地多装；
3、调度的出发点选为某一个租赁点，从这一点出发完成调度后，需要返回原来的租赁点，但是返回租赁点的耗时不必计入总耗时；
4、两辆调运车不能同时到达一个租赁点。
5.4.4算法流程图
该算法的程序流程图如下：
图5-4-1
启发式算法能够解决在租赁点确定后的调度问题，在第一问、第三问中应用。
5.5租赁点位置
因为建立租赁点时应当考虑平均需求、最大需求两点，所以首先我们应当确定加权平均比例，我们认为，在两者比较中更加重要的是平均需求量，而最大需求量次之。
我们经过查资料得知，有一些类似的问题多采用0.6与0.4的比例，但是我们认为此次问题的影响因素中平均值的价值不仅仅为0.6。
经过我们的讨论，我们决定采用0.65与0.35的比例
六、模型检验
1.问题一中求解最短路径采用Floyd-Warshall算法，以动态规划为手段，解决任意两点间的最短路径，并通过Matlab求解；
2.问题一求解最短调度时间采用启发式算法，通过C++程序设计穷举算法，并搜索最佳调度方案，由于上述结果是通过穷举得到的，必然全局最优；
3.问题二引入方便因数，全面综合各方面因素，所以得到的站点分配为最优解。
4.问题三的方法与问题一和问题二相似，故所求调度方案为最佳调度方案。
七、模型优缺点以及改进
在确定自行车的分配方案和调度方案时，这个问题是在已知节点具体的位置的条件下求解两个问题。
我们对两个问题分开求解，即先确定最分配方案，再根据最优分配方案确定对应的最优调度方案。
然而根据数学模型和实际情况得这两者并不是相互独立的，即问题最优解并非简单地两者最优解的结合。
因此，我们的最优结果可能和实际情况存在偏差。
为了方便问题的求解，我们做出了一些假设，比如假设每辆调度车从固定的某租赁点出发，最后又回到原来的点，而实际情况中会更局具体情况选择车辆停靠点。
这些假设方便了求解，但实际上简化了问题的复杂度。
7.1分配方案的优点
租赁点自行车分配中，我们采用了一种创新的分配方案，在分配中不仅考虑了需求量对分配的影响，而且还按照动态的目光，先给出合理的分配初值，然后让其按照自行车的骑行规律（即在某个租赁点还车的概率与租车点和还车点的距离成反比）自动分配若干次，每一次得出一个新的分配方案后和原来的方案比较，然后做出调整，最终得出最优的分配方案。
这个分配方案的优点是突出的，主要体现在以下几点：
1、首先考虑了需求量对分配方案的影响，使之从一开始就是合理的，兼顾重要因素。
2、由于即在某个租赁点还车的概率是一个常数，所以常数因子对分配方案的影响可以通过一次优化最终补偿，最终的结果是形成的调度方案是满足骑行规律的最优解。
3、这个模型还有一个优点是，在校正后，能够使得需要调度的自行车数目达到最小，从而在计算调度量时，为最优解提供保证。
7.2调度方案的缺优点
调度方案的优点是在租赁点不大的情况下，按照启发式算法一次性可以把相对来说最优的调度方案解出来，建模简单，求解也相对比较容易。
调度方案的缺点重要体现在算法的局限性上。
而启发式算法则试图一次提供全部目标。
例如通常能发现很不错的解，但是也没办法证明它不会得到较坏的解；
它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。
总的来说，启发式算法有一定的不稳定性。
可以用性能更好的遗传算法或者退火算法解决。
7.3新增节点模型的优缺点
在求解新增节点时，我们巧妙地引入了一个“方便因数”，用来衡量新增的租赁点的合理程度，用求解最优解的思路来求解新增的租赁点和分配的自行车数目，模型简单明了，容易用现成的算法实现。
但是方便因数并没有将影响新增租赁点的所有的因素都考虑进去，仅仅考虑了分配值、节点数、和邻近该租赁点的其他租赁点的数目。
其他因素如是否能达到调配量最小等因素没有考虑，其次定义的一些量如
不尽合理，原因是只考虑了新增加的单个节点所收到的影响，不没有考虑新增的节点间的相互影响，因此所得的结果有可能和最优解有一定的差距。
7.4模型和算法的改进
7.4.1算法的改进
由于启发式算法的局限性，可以采用收敛速度更快的遗传算法（GeneticAlgorithm，简称GA）和退火算法（StimulatedAnnealing，简称SA）。
与启发式算法相比较其优点有：
计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题。
在本题中，由于数据量相对较小，启发式算法还能够满足要求，为了使结果更加稳定，可以考虑退火算法和遗传算法。
7.4.2模型的改进
我们可以把调度问题看成一个赋有权值的图G，先要求出图G的最小生成树，使树上各边的总权和达到最小。
然后基于最早生成树生成一个可行的最短行车路径。
对上述30个租赁点重新编号，依次为1-30，用集合R表示。
我们用0-1变量
来表示公交车是否从租赁点i到租赁点j,即
目标函数为寻找一条从起始点开始到各个节点生成的最优树，要求各条线路的权值和最小，即
约束方程为：
求解最小生成树的方法有破圈法、避圈法、Dijkstra算法等。
这里我们用避圈法求解，避圈法是指将图G中的边按照权数大小逐条考察，按不构成圈的原则加入到T（树）中，直到
为止，即T的边数=G的顶点数-1为止。
避圈法的算法是：
1.把G的边按权的大小整理成
令
.
2.若
含圈，则转3，否则转4.
3．令
，若
则转2；
否则停止，G不存在最小生成树。
4.令
，
5.若
，结束，
是最小生成树；
否则转3.
八、参考文献
[1]ClarkeGandWrightJ.Schedulingvehiclesfromacentraldepottonumberofdeliverypoints[J].Operationsresearch,1964,12（4）:
12-18
[2]刘登涛,方文道,章坚民,等.公共自行车交通系统调度算法[J].计算机系统应用,2011,20（9）:
112-116.
[3]崔宏志,龚加安.带时间窗车辆路径问题的改进节约算法[J].纯粹数学与应用数学,2011,27（5）:
688-693..
[4]柳祖鹏,丁卫东,程逸旻.公共自行车系统站间调度优化研究[J].城市公共交通,2011
（1）:
39-42.
[5]肖华勇.实用数学建模与软件应用.西安：
西北工业大学出版社2008.11
附录
距离计算：
distance=zeros（53）;
fori=1:
1:
53
k=1;
forj=1:
53
ifi~=j
distance（i,k）=abs（x1（i,1）-x1（j,1））+abs（x1（i,2）-x1（j,2））;
end
k=k+1;
end
概率系数计算：
K=[]；
s=0;
ifz（i,j）~=0
s=s+1/z（i,j）;
%输出概率的K
s=1/s;
K=[Ks];
分块距离矩阵计算：
distanceMb=zeros（20）;
20
20
distanceMb（i,k）=abs（x1（Mb（i）,1）-x1（Mb（j）,1））+abs（x1（Mb（i）,2）-x1（Mb（j）,2））;
启发式算法代码：
#include<
iostream>
cmath>
fstream>
stdlib.h>
#defineZD20//定义站点数ZD=ZhanDian
#defineDE3//搜索深度
usingnamespacestd;
intnum[ZD];
//各个站点相应的多余、缺少的车辆的数目
introute[10*ZD];
//车行走的路径
boolIsEnd（intnum[]）{//判断是否所有的车都已经调度完毕
inti;
for（i=0;
i<
ZD;
i++）{
if（num[i]!
=0）returnfalse;
elsereturntrue;
}
intPathfinding（intfirst,intvol,intdepth）{//寻路找到下一个路径最优的站点
doubledistance[ZD][ZD];
//各个站点之间的距离
if（depth<
=0）
return-1;
inttemp_distance[ZD];
inti,j,k;
i<
i++）
temp_distance[i]=i;
//存储站点号码
for（j=i;
j<
j++）{
if（distance[first][temp_distance[i]]>
distance[first][temp_distance[j]]）{
k=temp_distance[i];
temp_distance[i]=temp_distance[j];
temp_distance[j]=k;
}
}//排序保留的是距离从小到大的站点号码
intbound=DE;
//设置
升级会员 