基于蒙特卡洛法的大学食堂排队问题模拟

基于蒙特卡洛法的大学食堂排队问题模拟

0简介:窗口的排他性和待时间学生食堂的队列是学生们非常关注的问题。学生们希望增加窗口数量，减少订单等待时间。然而，从食堂的角度来看，增加窗口可以减少团队的等待时间，这提高了学生对食堂的信心，赢得了更多的学生去食堂吃饭，但这也增加了食堂的运营成本。因此，如何比较这两个方面，以找到最佳的窗口数量非常重要。蒙特卡罗方法，计算机随机模拟方法，是基于“随机数”的计算方法。在这项工作中，我们使用蒙特卡罗法建立了动态模型，并模拟了食堂窗口上的队列。如果只有一个窗口服务，第一个学生将不完整，第二个学生必须等待，直到第一个学生离开服务台，第二个学生必须服务。1模拟量的变化情况在Excel下建立模拟模型,分别模拟单一窗口W1和两个窗口W2的模拟量变化情况.通过对比两个窗口的平均等待时间T等模拟量,做出决策是否增加窗口:.其中,tiw为第i个学生的等待时间.1.1第i个学生的服务时间令ti为第i个学生的到达时刻;ξ为第i个学生的到达间隔,它通常是一个随机数;tis为第i个学生的服务开始时刻;tiE为第i个学生的服务完成时刻;η为第i个学生的服务时间,它通常是一个随机数;tiw为第i个学生的等待时间;tit为第i个学生的逗留时间时间.(1)学生到达间隔,服务时间学生到达间隔及服务时间为不可控变量,用蒙特卡洛法产生随机数.(2)到达时刻(3)开始服务时刻(4)等待时间(5)完成时刻(6)总逗留时间1.2计算文明的循环描述为在本文模拟中出现的Excel函数如下:(1)产生按历史数据统计规律分布的随机数公式:=VLOOKUP(RAND(),表左上角地址;表右下角地址,变量所在列)公式中第一项为逻辑判断语句,随后分别为正确时的返回值和错误时的返回值.(3)COUNTIF函数:=COUNTIF(range,criteria)该公式用于统计在一定判断标准下满足条件的个数,其中公式中第一项为数据所在范围;第二项为判断标准;既满足第二项条件的第一项数据的个数.(4)其他常用函数:2此算法的示例是算法的示例2.1在一所大学的食堂窗口中模拟服务根据统计,某大学学生达到食堂窗口的时间间隔分布和服务时间分布见表1.2.2把这层打造成第2第1和2.根据1.1中对模型各变量的分析,在Excel单元格中输入各变量:到达间隔:在B10中输入公式:=VLOOKUP(RAND(),$B$3:$D$8,3),将该公式复制到单元格B11:B1009.到达时刻:在C10中输入公式:=B10;在C11中输入公式:=C10+B11,将该公式复制到单元格C12:C1009.开始服务时刻:在D10中输入公式:=C10;在D11中输入公式:=MAX(C11,G10),将该公式复制到单元格D12:D1009.等待时间:在E10中输入公式:=D10-C10,将该公式复制到单元格E11:E1009.服务时间:在F10中输入公式:=VLOOKUP(RAND(),$F$3:$H$7,3),将该公式复制到单元格F11:F1009.完成时刻:在G10中输入公式:=D10+F10,将该公式复制到单元格G11:G1009.总逗留时间:在H10中输入公式:=G10-C10,将公式复制到单元格H11:H1009.2.3运营结果按式(1)～(5)模拟1000次,得到结果如表2.2.4需要待的概率本例进行了1000次模拟,统计结果为:平均逗留时间49.14s;平均等待时间20.54s;需要等待571人;需要等待的概率0.57;等待时间大于30s231人;等待时间大于30s的概率0.23.从中可知当只有一个窗口的情况下,学生的平均等待时间为20.54s,其中有57%的人需要等待,有23%的人要等待30s以上.因为等待的人数较多,可以考虑增加一个窗口,以下是对两个窗口的情况进行模拟.2.5窗口向的闲置两个窗口和单个窗口相比,其余各变量不变,只有开始服务时刻有所变化.在两个窗口的情况下,判断何时能够开始服务要看两个窗口的状态.当学生到达时刻比两个窗口的开始空闲时刻都早时,学生需排队等待,直到至少有一个窗口达到空闲状态才开始接受服务,所以这时的“开始服务时刻”应等于先进入空闲状态的那个窗口的“开始空闲时刻”(即最早开始空闲时刻);当学生到达时刻比任意一个窗口的开始空闲时刻晚时,窗口可以立刻开始服务,所以这时的“开始服务时刻”应等于学生到达时刻.综上所述,在两个窗口的模拟问题中,我们需要在Excel中新增两列,分别为“窗口一的空闲时刻”和“窗口二的空闲时刻”,并且“开始服务时刻”的公式也要有所改变.窗口一的空闲时刻:在第一个学生被服务时,窗口二保持空闲.所以窗口一的空闲时刻等于第一个学生的完成时刻.当学生陆续到达后,如果窗口一早于窗口二到达空闲状态,则学生来到窗口一,这时窗口一的下一个开始空闲时刻等于该学生的服务完成时刻,窗口二的开始空闲时刻不变;如果窗口二早于窗口一达到空闲时刻,则该学生将来到窗口二,这是窗口二的下一个开始空闲时刻等于该学生的服务完成时刻,而窗口一的开始空闲时刻不变.窗口二的空闲时刻:第一个学生来时,假定被窗口一服务,所以窗口二的空闲时可为零;第二个学生到达时,如果窗口一和窗口二的开始空闲时刻相等,则窗口二的下一个开始空闲时刻不变;否则,当窗口二比窗口一先达到空闲状态时,窗口二的下一个开始空闲时刻等于该学生的服务完成时刻,当窗口二比窗口一后空闲时,则窗口二的下一个开始空闲时刻不变.模型建立:同单一窗口,B、C、E、F、G、H列的公式不变.开始服务时刻:在D10中输入公式:=C10;在D11中输入公式:=IF(C11<=MIN(I10,J10),MIN(I10:J10),C11),将该公式复制到单元格D12:D1009.窗口一空闲时刻:在I10中输入公式:=G10;在I11中输入公式:=IF(I10=MIN(I10:J10),G11,I110),将该公式复制到单元格I12:I1009.窗口二空闲时刻:在J10中输入公式:=0;在J11中输入公式:=IF(J10=110,J10,IF(J10=MIN(I10:J10),G11,J10)),将公式复制到单元格J12:J1009.按此方法模拟1000次,结果如表3.统计结果为:平均逗留时间29.49s;平均等待时间1.03s;需要等待100人;需要等待的概率0.10s;等待时间大于30s的4人;等待时间大于30s的概率0.00.2.6增加了平均等待时间根据以上对比可以发现,在窗口增加至两个时,学生的平均逗留时间为29.49s,平均等待时间为1s左右,只有100人需要等待,其中等待时间超过30s的只有4人.与单一窗口相比,大大的减少了平均等待时间,服务水平有明显改善,为学生节省了很多不必要的排队时间.3窗口排放系数的确定根据蒙特卡洛法模拟食堂窗口的排队结果表明,在当前的水平下,食堂开设两个窗口可以满足服务需求,因此增加一个窗口是可取的方案.通过以上模拟可以发现,用蒙特卡洛法在Excel上对食堂窗口排队问题进行模拟具有简便,易行,实用性强的特点,为做出决策