体操出场安排中的数学模型.docx
《体操出场安排中的数学模型.docx》由会员分享，可在线阅读，更多相关《体操出场安排中的数学模型.docx（36页珍藏版）》请在冰点文库上搜索。
体操出场安排中的数学模型
2011高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。
如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）：
A
我们的参赛报名号为（如果赛区设置报名号的话）：
5905
所属学校（请填写完整的全名）：
国防科学技术大学
参赛队员（打印并签名）：
1.贺云岳
2.李际超
3.范长俊
指导教师或指导教师组负责人（打印并签名）：
日期：
2011年7月6日
赛区评阅编号（由赛区组委会评阅前进行编号）：
2011高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
评
阅
人
评
分
备
注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
摘要
出于对电梯运行的实时性要求，本文摒弃了计算量大的复杂算法，转而用较简单的调度方案，使得调度实时性和实用性增强。
对于问题一，本文从三个阶段讨论单轿厢电梯系统的运行效率，提出电梯的效率应和员工普遍满意度挂钩，在此基础上分别给出了不同的效率评价指标，在这些指标的指引下，通过估算与仿真结合的方法找到了可以有效提高电梯系统运行效率的合适方案。
对于问题二，首先从安全角度出发，在对冲突的高效处理中提高双轿厢的运行效率；其次，在安全有保证时，我们优化调度方案，进一步提高效率。
理论计算和仿真实验都表明，本文中的双轿厢调度方案，较之单轿厢调度方案，能够提高效率4成左右。
在模型的进一步讨论中，我们探讨了采用基于细胞自动机的电梯运动模型模拟来设计双轿厢调度方案的可能性。
关键字：
员工普遍满意度运行效率调度方案跳跃式分段分区跳跃式细胞自动机朴素双轿厢调度分段双轿厢调度仿真
一、问题重述：
现有一座商务楼，设计地上层数为28层，地下停车楼2层，每层的建筑面积为1500平方米，楼内有7个电梯井道，其中一个电梯井道用于安装消防电梯，其余的均设计为客梯使用。
电梯按照商务楼建筑面积15至20平方米每人的标准来设计。
第1层的楼层高为4.8米，其余层均为3.2米，设计电梯的平均运行速度1.6米/秒。
问题一：
用6个单轿厢电梯设计一套调度方案，使得在高峰期和非高峰期时，有尽可能高的运行效率。
问题二：
用6个双轿厢电梯设计一套调度方案，使得在高峰期和非高峰期时，有尽可能高的运行效率。
并与单轿厢方案作对比。
二、问题的分析：
问题一：
单轿厢电梯系统在工作日时间里一般有三个使用阶段：
上班高峰期，下班高峰期，工作时间里正常的上下楼层间的业务交流（非高峰期）。
提高电梯的运行效率，也就是分别提高这三个阶段的电梯运行效率。
这里首先给出我们对于电梯运行效率的理解。
在电梯的三个使用阶段里，我们认为电梯运行效率的评价指标还是有所差异的。
但是不管差异如何，有一点是相同的：
电梯运行效率应以这座商务楼的所有员工的普遍满意度为基本衡量准则。
在上班高峰期，由于员工都在底层等电梯，本着“先到者先进电梯先上楼”的原则，各员工的候梯时间没有客观的差异，因而此时电梯的运行效率可用六部电梯将所有人都运往目的地所消耗的时间来评价。
显然，该时间越短，员工的普遍满意度越高，电梯在上班高峰期的运行效率越高。
而在下班高峰期，由于各员工所在楼层不一样，而传统的电梯运送有优先关系（假设各层楼的员工在下班后会同时向电梯发出下行请求），一般电梯会将高楼层的员工运完后才会运送低楼层的员工，此时若仍以电梯将所有人运到底层的时间作为电梯的运行效率的评估，难以令所有人信服。
因为对于中楼层员工而言，他们既不能像高楼层员工那样很快坐到电梯，又不能像低楼层员工那样选择通过楼梯下楼（假设低楼层员工都是理智人，因为他们候梯加坐梯时间比他们直接乘楼梯下楼时间要长，而中楼层员工的候梯加坐梯时间则要少于他们直接走楼梯所需的时间），中楼层员工必须等到电梯将高楼层的员工都送完，这不公平，此时中楼层员工的普遍满意度较低，因为大家都是同时下班，同时向电梯发出下行请求，却在候梯时间上差异显著，此时即使电梯将所有人运到底层的时间再短，由于存在楼层运送的优先关系，这种差异还是无法消除。
因而在这个阶段，我们选择中楼层员工的候梯时间为衡量电梯运行效率的指标，该时间越短，员工的普遍满意度越高（因为低楼层员工与高楼层员工的满意度相比之前并没有减弱多少，而中楼层员工的满意度却显著提高），此时，可认为电梯的运行效率越高。
在非高峰期，主要考虑单个员工从向电梯发出请求到到达目的层所需的时间，用该指标衡量电梯的运行效率。
问题二：
双轿厢的调度问题，第一是保证安全，在安全的基础上追求效率的最大化。
当出现冲突时如何以最高效的方式解决冲突，是要解决的首要问题。
而怎样能够减少冲突的发生，就成了调控时提高效率的有效途径。
在前面的工作做好了以后，就要考虑怎样改善运行方式以进一步提高电梯系统的运行效率。
三、模型假设：
1．由于上、下班时人比较多，所以电梯每次都是满载。
2．假设下班时所有人都一齐下班回家
3.假设每个电梯最大容量为20人。
4.每层楼人数按100人算。
四、符号说明：
：
第i个电梯一次向上运行的时间
：
第i个电梯一次向下运行的时间
：
第i个电梯的运行周期
：
第i个电梯在一个运行周期里的停留次数
：
第i个电梯在一个运行周期里在各层停留的时间之和
：
第i个电梯在整个上班高峰期的运行时间
：
第i个电梯在整个上班高峰期的搭载人数
：
第i个电梯在上班高峰期时所能到达的最高楼层
：
下班高峰期时在传统的电梯调度方案下第k层员工等到电梯所需要的时间
：
第k层员工坐电梯到底层所需要的时间
：
第k层员工步行下楼梯到底层所需要的时间（包括心理时间
：
下班高峰时中楼层分配的电梯数
：
下班高峰期时高楼层分配的电梯数
：
电梯平均运行速度
：
冲突处理时间
：
一趟运行中期望停靠次数
：
电梯开关一次们所用时间
：
一个电梯厢内的乘客容量
：
每一位乘客下进出电梯用时；
五、模型的建立与求解：
问题一：
因为在电梯的三个使用阶段里电梯运行效率的评估指标不同，从尽可能提高电梯运行效率的角度出发，三个阶段的电梯运行方案也有所差异。
但是不论哪个阶段都要求算法的实时性较好，而且由于电梯问题的随机性较高，所以复杂的优化结果可能淹没在随机事件的不断冲击之中。
所以我们采用了比较简洁实用的方案。
下面进行具体分析：
经查资料得，每个乘客上、下电梯的平均时间约为0.8s和0.5s，开关电梯门的平均时间为3s，其它损失时间（如果考虑的话）为上面3部分时间总和的10％。
上班高峰期：
由以上资料可知，一个电梯的运行周期包括该电梯上下的运行时间和中间停留的时间，而停留的时间包括乘客进出的时间和电梯门开关的的时间，即：
那么一电梯的总运行时间（即它将它负责的所有员工都运往目的地所消耗的时间）为：
整个电梯系统的运行效率应以六部电梯中总运行时间最长的那个为衡量标准，以与员工普遍满意度挂钩。
传统的电梯运行方案中，电梯可以在每一楼层停下，员工可搭载任一电梯到达任一楼层。
显然这种方案在人多的时候比较耗时，因为电梯在任一楼层都有可能停留，停留次数较多，比较耽误时间，而且这种方案也容易发生员工争抢楼梯的现象，易导致混乱。
我们用仿真的方法计算出这种方案所需总的运送时间约为4532.06s.（见模型的检验部分）
为了提高电梯的运行效率，就需减少电梯的总的运行时间，电梯的趟次由于人数不变无法减少，就只能减少电梯的运行周期，而电梯的运行速度难以提高，因而只能尽量减少电梯在运行过程中的停留次数。
根据这个条件，我们可以设计方案使得六部电梯负责互不相同的楼层，且电梯只在自己负责的楼层停留。
这样一来，平均每台电梯只停留四到五次，就大大减少了其运行周期。
而让六部电梯负责不同楼层的方案也不唯一，我们结合所查阅的资料及现实中一些商务楼的具体实践提出了如下三种改进的调度方案，估计各自的运行效率并进行比较，在本文的模型检验中，又通过在VC上进行仿真，根据仿真结果进一步进行比较。
下面给出每种方案的电梯总的运行时间（此即运行效率）的计算方法：
其中
等于各电梯负责的楼层总数，
的原因是电梯的运行是匀速的
方案一：
跳跃式的调度，即各电梯负责的楼层是跳跃的，间隔的。
在日常生活中，这种方案比较常见的形式是奇偶停靠。
在本题中，六层电梯负责28层楼，因而其间隔可稍取大点，以减少各电梯的停靠次数。
我们选用的间隔是6层。
具体的方案及估算的效率如下表所示：
电
梯
标
号
停靠层数
（负责的层数
）
运行周期
（
/s）
运完所负责楼层员工消耗的时间（
/s）
该方案电梯效率（
/s）
1
39152127
151.1
3777.5
3877.5
2
410162228
155.1
3877.5
3
5111723
131.8
2636
4
6121824
135.8
2716
5
7131925
143.1
2862
6
8142026
143.8
2876
可见该方案相比传统方案而言，电梯的运行效率的确得到了较大提高。
方案二：
分段调度，保证方案一中各楼层停靠次数不增多的条件下，通过适当降低部分电梯所能到达的最高楼层来减少其运行周期，进而达到提高电梯运行效率的目的。
电
梯
标
号
停靠层数
（负责的层数
）
运行周期
（
/s）
运完所负责楼层员工消耗的时间（
/s）
该方案电梯运行效率（
/s）
1
12345
22.51
562.75
3577.5
2
678910
83.1
2077.5
3
1112131415
103.1
2577.5
4
1617181920
123.1
3077.5
5
2122232425
143.1
3577.5
6
262728
148.5
2227.5
估计结果与理论预测相符，该方案电梯的运行效率比之方案一有一定提高。
方案三：
分区跳跃式调度，即结合方案二和三，将整个楼层分为几个区，每个区由若干个电梯负责，在每个区里实行跳跃间隔调度。
这种方案在现实中的用的较多，特别是在一些大城市里的楼层数较多的商务楼中普遍采用的是分区调度，如上海的金茂大厦中的电梯就实行分三段调度。
我们在这个方案中对楼层分了两个区，即1至15层由三个电梯负责，16至28层由另三个电梯负责，在每个区内以3为间隔对三个电梯进行跳跃间隔调度。
具体安排方案及估算结果如下表格：
电
梯
标
号
停靠层数
（负责的层数
）
运行周期
（
/s）
运完所负责楼层员工消耗的时间（
/s）
该方案电梯运行效率（
/s）
1
3691215
103.1
2577.5
3877．5
2
471013
91.8
1836
3
581114
95.8
1916
4
1619222528
155.1
3877．5
5
17202326
143.8
2876
6
18212427
147.8
2956
跟方案二比起来，该种情况电梯运行效率不增反减，与理论预测的不符，而且在实际中，得到应用的是该方案而不是方案二，因而其中必定存在原因。
经分析我们认为，实际的电梯运行速度不可能是全程匀速的，而是有加速有减速又有匀速的运动，且达到最大速度所需的最小距离一般为8米多，在本题中，每层楼高3.2米，在现实中，若如方案二般电梯上一层就停一层，那么电梯的平均速度就会很小，其效率自然无法提高，而且频繁的在短距离内变速，也容易导致电梯的故障，这可能也是方案二没有在现实中得到应用的原因；而对于方案三，电梯相邻两次停靠距离相差三层楼高，即9.6米，在这个距离内电梯足以达到最大速度，并以这个速度匀速运行一段时间，在这种情况下，电梯的平均速度自然较之方案二有较大提高，且较之方案一又考虑到使一部分电梯不到达高层，缩短其运行周期，进而提高整体的运行效率，因而从实际出发，方案三应该是三者中较优的。
其实，如果对方案三稍加改进，我们称之为改进的分区跳跃式调度，即可有效提高电梯的运行效率，如下表：
电
梯
标
号
停靠层数
（负责的层数
）
运行周期
（
/s）
运完所负责楼层员工消耗的时间（
/s）
该方案电梯运行效率（
/s）
1
3691215
103.1
2577.5
3307.4
2
471013
91.8
1836.0
3
581114
95.8
1916.0
4
16192225（24*
）
139.8
3075.6
5
17202326（24*
）
143.8
3307.4
6
182127（28）
144.5
2890.0
即4号电梯不用到达28层楼，6号电梯不用到达24层楼，在28层楼工作的员工可乘坐6号电梯到达27层楼，再通过楼梯上到28层楼，而在24层楼工作的员工可乘坐4号电梯到达25层，或乘坐5号电梯到达23层，在通过楼梯到达目的地。
在估算的时候，我们假设选择5号乘到23层下的员工比较多（因为早上上班一般都较匆忙，员工们可能更愿意在23层下再走上去，也不愿意多坐两层再下再走下来）不妨设24层工作的100名员工中有60十人选择5号电梯，40人选择4号电梯，这样变得到了如上表所示的结果。
可发现电梯的运行效率得到了明显的提高。
在上面的表格中我们也发现有的电梯早早就结束了工作，如1、2、3号电梯，如果能在它们工作完而其它三个电梯仍在工作的这阶段里充分利用这些空缺资源，再用这些闲置的电梯，通过调控指令使得它们也可到达高层，以减轻另三个电梯的压力，从而这套电梯系统能够更早的使所有员工“各归其位”，其运行效率自然也将得到更大提高。
下班高峰期：
在问题分析中，我们确定将中楼层员工的平均候梯时间作为此阶段电梯系统的运行效率。
因为下楼层员工不需要电梯，故电梯的分配方案只针对中高楼层。
现在有两个问题需要解决：
1.下、中楼层的分解层是哪层？
2.中、高楼层的电梯分配方案如何？
下面来逐个解答：
首先对于第一个问题，关键点是分界层的选取应遵循什么原则。
我们认为，下班了，大家都急于回家，因而他们会采取能使他们最快到达底层的方法，而下楼层的员工之所以选择走电梯，是因为在传统的电梯调度方案中，他们等梯加坐梯的时间比他们走楼梯的时间还要长，因而这个分界层应该满足这样的条件：
在这层工作的员工候梯加坐梯的时间与他们走楼梯到底层的时间相等（此时候梯时间是在传统电梯调度方案下计算得到的）。
不妨设此分界层为第k层，则满足：
，其中：
下面来解释公式的含义：
考虑到下楼层员工下班回家心切，争着下楼梯，可能出现拥堵现象，再结合人一般的步行速度及每层楼高，我们假设人步行下楼每层需耗时60s,再考虑一般下班后人经历一天工作后比较累，惰性比较强，因而当等梯加坐梯时间之和与下楼梯时间之和接近时，他们往往倾向于选择坐电梯，换个角度说，在员工的心里，下楼梯的时间往往比实际下楼梯的时间要长，而且楼层越高，因为下楼梯越累，因而他们心里的下楼梯时间越长，可见这个步行下楼时间还要再进行修正，即得到上式：
，而结合生活经验，可取a=
，这样
，对于
，其第一项表示k层以上所有员工进出电梯消耗的时间，第二项表示电梯在将k层以上所有员工运往底层的过程中电梯所有的停留消耗的时间，其中
表示电梯总的停靠次数，最后一项表示电梯将k层以上所有员工运往底层的总的运行时间（只考虑电梯来来回回的运动时间），在这里做了一个简化：
我们假设这个运输过程实际可相当于所有的员工都集中在
层，然后电梯每次都在底层和
层间往返运动，
表示电梯总共需要的趟次（这里假设六部电梯同上同下，可看成一个整体）。
由上面的等式可计算出k=11.2，因而我们可取第11层为分界层，其上为中高楼层。
由于中高楼层都需坐电梯，因而可用均分原则确定其分界点，即第20层为中高层的分界层。
这样一来，1-11层为低楼层，12-19层为中楼层，20-28层为高楼层。
对于第二个问题，中高楼层的电梯分配问题，我们认为为了提高员工普遍满意度，分配的电梯应尽量能同时将中高楼层的所有员工运到底层。
根据这个要求可得到：
在这里做了和上面一样的简化处理：
即看成是电梯从中、高楼层的中间层16层、24层将所有员工运到底层，这样一来
，因此中层分配两部电梯，高层分配四部电梯，具体的电梯调度方案可以在每层采用跳跃式方案。
最终得到下班高峰期的单轿厢电梯系统的运行方案如下：
十一层楼以下的（包括十一层楼）员工通过楼梯步行下楼，六部电梯分别负责将12-15层，16-19层，20-21层，22-23层，24-25层，26-28层的员工运到底层。
非高峰期：
在问题分析中，我们以单个员工从向电梯发出请求到到达目的层所需的时间作为衡量该阶段电梯运行效率的指标。
对于传统的电梯调度方案，经过一段时间，最终所有的电梯基本停靠在底层或最高层，这样一来，一旦中楼层的员工想到某个楼层，发出请求后，需要经过较长的等待时间，这样的效率显然不高。
我们想是否能让电梯实行自动停靠功能，即每个电梯都有自己的特定停靠位置，在履行完自身的使命后，即自动归位。
如果将六部电梯的自动停靠位置分散在整个楼层，那么即使任一楼层的员工发出请求后，离他最近的电梯便会迅速赶来，使得他的等待时间不会很长，从而缩短了他到达目的层的时间，提高了电梯的运行效率。
因此在非高峰期，我们提出一个比较合适且能提高电梯运行效率的单轿厢运行方案：
即让每个电梯在送完乘客后自动停靠在某个特定的楼层，为确保均匀覆盖，可让一号电梯自动停在1楼，2号电梯停在6楼，三号电梯停在11楼，四号电梯停在16楼，五号电梯停在22楼，六号电梯停在28楼。
综上所述，为了尽可能提高单轿厢电梯系统的运行效率，我们分成了三个阶段予以考虑：
上班高峰期，下班高峰期，非高峰期。
在每个阶段我们本着提高员工普遍满意度的原则，找到了不同的衡量电梯系统运行效率的指标，在这些指标下，我们提出了比较合适的单轿厢客梯的运行方案：
上班高峰期：
不同的电梯负责运往不同的楼层：
一号电梯负责3、6、9、12、15层，
二号电梯负责4、7、10、13层，
三号电梯负责5、8、11、14，
四号电梯负责16、19、22、25层，
五号电梯负责17、20、23、26层，
六号电梯负责18、21、27层。
（其中工作在28层的员工可乘六号电梯坐到27层，工作在24层的员工可乘四号电梯到25层或乘五号电梯到23层，且一、二、三号电梯工作完后可以帮助间四、五、六号电梯的压力）
下班高峰期：
十一层楼以下的（包括十一层楼）员工通过楼梯步行下楼，六部电梯分别负责将12-15层，16-19层，20-21层，22-23层，24-25层，26-28层的员工运到底层。
非高峰期：
让每个电梯在送完乘客后自动停靠在某个特定的楼层，一号电梯自动停在1楼，2号电梯停在6楼，三号电梯停在11楼，四号电梯停在16楼，五号电梯停在22楼，六号电梯停在28楼。
问题二：
双轿厢是最近几年的新兴产物，它的诞生，是为了更充分利用井道内的空间。
但是两个轿厢同时在一个井道内运行，安全性成了首要问题，一切的讨论都是基于安全的前提下进行的。
所以当两个轿厢发生冲突时，建立一个样的冲突处理就成了关键问题。
我们对双轿厢问题的讨论重点是，在安全的前提下，如何进一步提高效率的问题。
1.冲突的安全处理：
安全永远是第一位的，有了安全才有效率。
冲突可以分为五类，即单个轿厢将载人冲突、单个轿厢正载人冲突、双轿厢都将载人冲突、双轿厢一正载人一将载人冲突和双轿厢都正载人冲突。
下面，分别对这几个冲突进行相应的处理。
（1）单个轿厢将载人冲突
此种冲突是指，同一个井道内两个轿厢，一个刚刚由调度系统分配载人任务，正前往载人的路上，另一个电梯空闲。
很显然，在保证安全和效率的前提下，空闲的电梯应主动为有任务的电梯让路。
（2）单个轿厢正载人冲突
此种冲突是指，同一个井道内两个轿厢，一个正在执行运输任务（有乘客在厢内），正前往目标楼层，另一个电梯空闲。
同上一种情况，应采取让路的措施。
（3）双轿厢都将载人冲突
这种冲突是指，两个轿厢都前往需求产生楼层。
此时为避免发生安全问题，调度系统应自动将上轿厢调去回应较上方的需求楼层，下轿厢则回应下面的楼层。
这样可以尽量避免冲突的出现，并且保证了需求的及时满足。
（4）双轿厢一正载人一将载人冲突
这种冲突是指，一个轿厢正载人前往目标楼层，另一个电梯也将去呼应需求，两个电梯相向而行。
应保证有人的轿厢的需求，没有人的轿厢则需为其让路。
当然如果采用群控电梯系统，可以通过调用不同井道的轿厢来响应需求。
（5）双轿厢都载人冲突
这种冲突是指，同一井道的两个轿厢同时执行载人任务相向而行。
此时应考虑将离冲突楼层最近的目标楼层最为首要保证楼层，即目标近的轿厢优先。
这样可以保证一定效率。
当然如果才用群控电梯系统，应从源头上减小这种情况的出现，也就是说在提前了解了客户需求的情况下，应该将可能发生的冲突尽量得避免。
2.早高峰的调度:
早晨，写字楼的电梯需求多来自地下停车场和一楼大厅，而传统的单轿厢电梯的运力不足就凸显了出来。
所以此时可以采用双轿厢电梯，充分利用井道内的空间。
（1）早高峰双轿厢电梯的朴素调度：
针对早高峰时段的特点，最简洁的方案，是将同一个井道的两个轿厢，一个负责从地下停车场运送，另一个负责从一楼大厅运送。
而同一井道内的两个电梯，可以到达整栋大楼的每一层，具体要到哪一层，根据需求而定。
再次基础上，井道与井道之间的电梯是完全相互独立的。
这种方案下，电梯的运行情况主要就取决于用户的需求。
而如果假设用户没有对哪一部电梯有偏好，那么电梯的运行情况基本一致。
假设去每一层楼得需求一样多，那么20个用户的需求的最大值分布就是每一趟电梯厢的运行最高目标楼层。
由概率论的知识可知
Y是该电梯厢在一趟任务中所到最高层的随机变量。
带入数值可计算的：
如此可知：
也就是说，单趟运行一般是到达27楼后才返回。
根据对称性，可估计此时电梯发生冲突的概率。
因为，每个电梯厢内的用户的需求服从同一分布，所以同一个井道内的电梯发生冲突的概率：
综上，可得单趟运行的估计时间：
代入数值计算，可得：
由此可知，用朴素双轿厢调度方案，单次运行任务徐总耗时235秒，看起来好像比单轿厢的效率低。
但是这里拥有12个轿厢，虽然每一个轿厢的运行时间有所上升，但是总体的运输效果应该
升级会员 