B题公交车调度方案的优化设计

B题：公交车调度方案的优化设计摘要本文利用某一特大城市某条公交路线上的客流调查运营资料，以乘客的平均抱怨度、公司运营所需的总车辆数、公司每天所发的总车次数以及平均每车次的载客率为目标函数，建立了的分时段等间隔发车的综合优化调度模型。在模型求解过程中，采用了时间步长法、等效法以及二者的结合的等效时间步长法三种求解方法，尤其是第三种求解方法既提高了速度又改善了精度。结合模型的求解结果，我们最终推荐的模型是分时段等间隔发车的优化调度方案。在建立模型时，我们首先进行了一些必要假设和分析，尤其是针对乘客的抱怨程度这一模糊性的指标，进行了合理的定义。既考虑了乘客抱怨度和等待时间长短的关系，也照顾了不同时间段内抱怨度对等待时间的敏感性不同，即乘客在不同时段等待相同时间抱怨度可能不一样。主要思想是通过逐步改变发车时间间隔用计算机模拟各个时间段期间的系统运行状态，确定最优的发车时间间隔，但计算量过大，对初值依赖性强。等效法是基于先来先上总候车时间和后来先上的总候车时间相等的原理，通过把问题等价为后来先上的情况，巧妙地利用“滞留人数”的概念，把原来数据大大简化了。很快而且很方便地就可求出给定发车间隔时的平均等待时间，和在给定平均等待时间的情况下的发车间隔，但该方法只能对不同时段分别处理。结合前两种方法的优点提出等效时间步长法，即从全天时段内考虑整体目标，使用等效法为时间步长法提供初值，通过逐步求精，把整个一天联合在一起进行优化。通过对模型计算结果的分析，我们发现由于高峰期乘车人数在所有站点都突然大量增加，而车辆调度有滞后效应，从而建议调度方案根据实际情况前移一段适当的时间。在模型的进一步讨论和推广中，我们还对采集运营数据方法的优化、公共汽车线路的通行能力以及上下行方向发车的均衡性等进行了讨论。在求具体发车时刻表时，利用等效时间步长法，较快地根据题中所给出的数据设计了一个较好的照顾到了乘客和公交公司双方利益的公交车调度方案，给出了两个起点站的发车时刻表（见表二），得出了总共需要49辆车，共发440辆次，早高峰期间等待时间超过5分钟的人数占早高峰期间总人数的0.93%，非早高峰期间等待时间超过10分钟的人数占非早高峰期间总人数的3.12%。引入随机干扰因子，使各单位时间内等车人数发生随机改变。在不同随机干扰水平下，对推荐的调度方案进行仿真计算，发现平均抱怨度对10%的随机干扰水平相对改变只有0.53%，因此该方案对随机变化有很好的适应性，能满足实际调度的需要。1．问题的提出公共交通是城市交通的重要组成部分，做好公交车的调度对于完善城市交通环境、改善市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。下面考虑一条公交线路上公交车的调度问题，其数据来自我国一座特大城市某条公交线路的客流调查和运营资料。该条公交线路上行方向共14站，下行方向共13站，题中给出了典型的一个工作日两个运行方向各站上下车的乘客流量统计。公交公司配给该线路同一型号的大客车，每辆标准载客100人，据统计客车在该线路上运行的平均速度为20公里/小时。运营调度要求，乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过120%，一般也不要低于50%。试根据这些资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益。2．模型假设与说明1．题目中所给出的一个工作日的乘客流量统计数据是具有代表性的；2．工作日每天同一时间的乘客流量大致相等；3．在任何时刻车辆上的人数不能多于120人；4．每个乘客都严格遵守先到先上车的规则；5．在公交线路上所有车辆总能正常通行，不考虑诸如堵车、交通事故等意外情况；6．不考虑公交车在各站的停车时间，即乘客上下车均在瞬间完成；7．公交车在公路上行驶速度处处相等，都等于题目中给出的平均速度；3．符号系统l上：公交路线上行方向的总路程；l下：公交路线下行方向的总路程；v：客车行驶的平均速度；上it：上行车辆第i段时间内的发车时间间隔；下it：下行车辆第i段时间内的发车时间间隔；ρ：乘客的抱怨度；N：一共需要的车辆数；S：一天总的发车次数；η：平均每车次的载客率；总inum：在第i时间段内上车的总人数；总num：一天的乘车总人数；4．问题分析与模型的建立4.1问题分析本题要求设计全天(工作日)的公交车调度方案，这里需要考虑乘客和公交公司两方面的利益，是一个多目标的优化问题。其中可以供选择的目标函数主要有：1)乘客候车时间要尽量短；2)候车时间超过5分钟乘客数要尽量少；3)公交公司所需的总车辆数尽量少；4)全天范围内，发车的总次数尽量少；5)平均每车次的载客率尽量高等等。以上的目标可以用乘客利益和公司利益分为两类，这两类目标是相互冲突的，不可能同时达到最大。工作日的早高峰正是多数乘客上班的时间，也是一天中乘坐公交车人数的高峰期，所以这段时间里所需的车辆数也是最多的。从乘客的方面考虑，早上上班迟到对他的利益的损失相当大，因此乘客希望候车时间一般不要超过5分钟。这时应以乘客的抱怨程度尽量小为主要目标，求得公交公司在早高峰期间的所需的最少车辆数。在其余时间段里，乘客候车时间一般不要超过10分钟，这时考虑到公交公司的利益使其在这段时间内所发的总共发车的车次总数最少，以及提高每车次的载客率为主要目标。因此我们首先确定出早高峰期，针对早高峰期的数据，在一定的乘客抱怨水平下，求出共需多少辆车，然后再根据全天其它时段的数据，并综合其它指标求出两个起点站的发车时刻表。由于题目中所给出的仅是各站一个小时上下车人数的数据，对于我们的计算而言太过粗糙。首先想到的是运用题中的数据对每一车站在各时段上车和下车的人数进行分布拟合，但这样做也有很大的缺点，因为各时段每个站点上下车人数受上下班时间以及道路沿线工厂等因素影响很大，从而导致各时段前后相关性很小。而对各时段上车和下车的人数进行分布拟合就人为的增加了各时间段的上下班人数的相关性，与实际情况不符。实际中如果把统计做的更细致或者知道那些影响上下车人数分布的因素，就可以较好的求出这些分布；由于缺乏我们对这些情况得了解，所以我们假设各站的上下车人数在各个时间段（一小时）内分布是均匀的，即E[numik（t，Δti）]=λ（Δti）=numik/Δti其中numik（t，Δti）表示在[t，Δti]内上车的人数。4.2模型的建立为了更好的建立模型，首先要明确下面几个问题：1）时间段的划分：假设在题目中给出的各时段（一小时）内，各车站上下车的乘客人数分布均匀，这样就可将全天分为18个时间段，分别对每一个时间段进行考虑，并认为每个时间段内的发车间隔时间Δti上和Δti下分别为常数，但两者不一定相等。2）对下行方向的处理：从题中数据可以看出上行方向比下行方向多一个车站A1，我们对此的处理是在下行方向同样也补上一个车站A1，并且令这个车站在任何时段上车和下车的人数均为0。3）对乘客平均抱怨度的定义：考虑到一个人的抱怨程度是一个模糊的表述，它与候车时间的长短有关，候车时间越长，抱怨程度越大，但候车时间足够短时又不会抱怨。经过分析可以定义第i个时间段上行的（或下行的）第j个乘客的抱怨度为：10,107,75,54,4,0),(4321ijiijiijiijiij上或10,107,75,54,4,0),(4321ijiijiijiijiij下式中i1，i2，i3，i4表示当此乘客不同等待时间wij对应不同的抱怨度。可以看出抱怨度不仅与等待时间的长短有关，而且还会与所在的时间段i有关。很明显，早高峰期间和平时时段里等待同样长的时间，前者给乘客造成的损失可能更大些，因此抱怨度也会相应大一些。有了每个乘客抱怨度的定义，第i时间段的平均抱怨度为：总下上总inumjiijijinum1)),(),((1一天内的平均抱怨度为：181iii式中ωi表示第i段时间内区间的平均抱怨度对总平均抱怨度的权重，可取1181iiiinumnum，使得总总。其中wij是由Δti上或Δti下及numik（t，Δti）决定的，其中numik（t，Δti）是一个随机量，故wij也是一个随机量，从而一天内的平均抱怨度ρ也是一个随机量，可表示为f（Δti上，Δti下）。4)总车辆数的确定:一天所需的总车辆数N等于各时段所需的总车辆数Ni中的最大值，即N=g（Δti上，Δti下）=max{N1，N2，…，N18}，而每一时段所需的总车辆数由上行车辆数、下行车辆数，加开车辆数三部分组成，有Ni=Ni上+Ni下+Ni加其中下上下上下上iiiitvlNtvlN,下上上下上下下下上上下下上上加iiiiiiiiiiiiiiittttttvlTttttttvlTN],)[(],)[(这里[·]表示对括号内的数取整。5)对平均每车次的载客率的定义：考虑到每车次的运营成本基本不变，这样平均每车次的载客数目的多少就能反映公司的利益。于是我们定义平均每车次载客率定义为：η=num总/S即：)(181181141下上上iiiiiijijTTnum式中上ijnum代表第i时段在第j车站到上车人数（包括上行和下行）；iT代表第时段的时间间隔；i第i时段上行或下行的发车时间间隔。平均每车次的载客率的高低直接反映了一个调度方案对于公交公司的收益率。一般地乘坐公交车是按次计费的，所以总上车人数即反映了公交公司一天的收入，而总发车次数则反映了公交公司一天的支出。6）据以上分析，我们建立如下模型：目标：minE[ρ]=E[f（Δti上，Δti下）]minN=g（Δti上，Δti下）min])/[]/([181下上iiiiitTtTS这里[•]表示对括号内的数取整maxη=num总/S调度要求：1．每辆车上承载的人数不超过120人；2．在给定时间段Ti＝60（分）内Δti上，Δti下为定值。5．模型的求解5.0解法分析在我们建立的模型中的多个目标中，总共需要的车辆数N涉及到公司建立一条公交线路的初始投资，每辆车所需的资金巨大，应被首先考虑。而要确定总共需要的车辆数，只需求出早高峰期（我们根据题中给出的数据，假设早高峰期为7：00—8：00和8：00—9：00两个时段）内所需的车辆数即可。考虑到实际求解过程中，对于前面模型中所定义的抱怨度在各个时间段内对于不同等待时间长度取值问题，可以通过实际的调查数据得到；简化地想，如果对应所有的区间，顾客等待时间长度大于5分钟时都取1，而小于5时都取0，那么这是所定义的抱怨度直观意义就是指所有时间内等待时间超过5分钟的人数占总人数的比值，但显然着这种定义太粗糙；由于缺乏实际的调查，我们在以下求解过程中对抱怨度在各个时间段内对于不同等待时间长度取值作以下假定：早高峰期间γi1--γi4分别取[00.311.52.4]；而其它时间段内γi1--γi4分别取[00.150.50.751.2]。5.1解法一：时间步长法总体思路：在给定的假设原则下，通过逐步改变发车时间间隔用计算机模拟各个时间段期间的系统运行状态，确定最优的发车时间间隔。为简化计算，可以设定每个车站单位时间内上下车人数分别正比于该车站在这个时间段上下车的总人数，即numik（t，Δti）=λ（Δti）=numik/Δti。运行步骤：1)初始发车时间间隔it，i=1,2,…,18；2)设置初始状态。模拟时钟00T、终点时间60eT3)设置每个车站等车人数以及待发车辆的最初状态，将每个车站的等车人按其等待时间的长短分为以下几类：10ijw、21ijw、32ijw、54ijw、65ijw、…；4)判断是否需要发车以及是否有车到站，并更改一次各车站等车人数及运行车辆的状态。其中运行车辆的状态