资源预览内容
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
第9页 / 共9页
亲,该文档总共9页全部预览完了,如果喜欢就下载吧!
资源描述
.公交车的调度杜克勤童颜李科摘要:本文解决的是一个公交车调度问题,目的是用尽可能少的车来运送乘客,同时不能让乘客等待时间过长,也不能超载。文中提出了一种解决本问题的新颖的模型。通过分析知,一个时区内需要的车只与该时区内车站的最大转移客流量有关,于是我们对题目所给的数据进行一系列变换处理,求出每个时段发的车的最大转移客流量,得到一个新的表格。根据最大转移客流量,用线性规划的方法可以求出我们这个模型需要发车次数的最小值,然后综合考虑乘客的等待时间等我们可以给出各个时区的发车次数,进而确定全天发车时间表,由发车时间表,我们同样用线性规划方法求出需要的最少车辆数。用我们构造的模型,求出了一个可行的调度计划,并给出了发车时刻表。每个方向的全天发车次数为237,需要的57辆公交车。通过编程模拟得出平均等待时间2.17min和平均满载率81.6%,对这个解进行了评价,说明了本模型的特点,并指出了进一步优化改进的方向。最后用一个模拟搜索方法又求出一个解,并与第一个解相比较。一问题的提出这是一个公共汽车调度问题。题目给出了来自我国一座特大城市某条公交线路的客流调查和运营资料。该条公交线路上行方向共14站,下行方向共13站,题目给出的是典型的一个工作日两个运行方向各站上下车的乘客数量统计。公交公司配给该线路同一型号的大客车,每辆标准载客100 人,据统计客车在该线路上运行的平均速度为20公里/小时。运营调度要求,乘客候车时间一般不要超过10分钟,早高峰时一般不要超过5分钟,车辆满载率不应超过 120%,一般也不要低于50%。我们的目标就是根据题目所给的这些统计资料,把调度问题抽象成一个明确完整的数学模型,并求解,根据我们的解,给公交公司制定一个公交车调度方案和起点站的发车时刻表,使公交公司能够有效降低成本,但又不能牺牲乘客的利益。二基本假设1. 1.候车队伍有良好的秩序;即要保证乘客先来先乘车的原则;2. 2.忽略其它情况对公交车的影响,即公交车以20公里/小时的速度匀速行驶;不计乘客上、下车的时间及公交车起动、加速、滑行、制动时间因为题中给的是平均速度;3. 3.从时间段内到达某站的乘客数服从均匀分布;4. 4.公交公司只对公交车进行调度但在允许的范围内不限制乘客上车;既只要该车乘客数不大于120则允许乘客上车,直到达到120为止;5. 5.每个时间段的发车间隔时间是确定的而且平均的。三符号说明与概念引进3.1 概念引进1 1时区-我们规定两相邻正点之间的单位时间间隔为一个时区,并给之编号5:00-6:00 时区6:00-7:00 时区 21:00-22:00 17时区22:00-23:00 18时区2 2跨时区-当一辆公交车从时区出发在到达目的地之前已经进入下一个时区时,我们就称为产生了跨时区。3 3站间转移客流量-有多少乘客乘坐时区发出的车经过j车站到达车站包括在车站上车的乘客,。4 4如果一个乘客是在时区来到车站乘车的,我们称该乘客来自时区3.2 符号说明 1 分别代表各个时区内发车的时间间隔 2 分别代表各个时区内发车的总次数 3 :在时区车站的净上车客流量 4 :站间转移客流量见上面定义 5 :车站来自时区的人被发自时区的车运走的数量 6 :时区内发出的所有车在车站运走的净乘客数量上车人数减下车人数。四问题的分析我们应该在满足乘客的等待时间要求的前提下,合适地安排发车次数,得到发车时刻表,使得发车次数尽可能的少,而且用到的车辆尽可能少。我们的目标是求每一个时区内发车的次数,发车的次数由在该时区内发出的车要要运送的乘客数量决定,那么我们就要求各个时区发出的车分别要运送的乘客数。知道了要运送的乘客数,就可以用线性规划求发车车次。知道了发车车次,我们进而可以列出发车时刻表,通过时刻表,可以用线性规划求最少车辆。五模型的建立和求解起点 Ak 点5:005.1 模型一示意图见右。箭头表示车在一定时间内从起点开到终点。6:00由于公交车有跨时间段的问题例:起点到第Ai站要用t的时间,则在i:00到i+t时间内到达Ak站的乘客可由i-1:00i:00时间段内发出的公交车运走。为了方便解决问题,i:00在i时区到达车站的这部分乘客将被i-1时区发出的车运走我们以第i时区发出的公交车来重新划分乘客,在i时区到达车站的这部分乘客由i时区发出的车运走找出各个站点上由这些车运送的乘客数量i+1:00则从第j时区发出的车在Ak站点所要运走的乘客数量为:22:00当j=1时,上车的乘客数为:;下车的乘客数为:23:00当时,上车的乘客数为:下车的乘客数为:图 1当j=18时,上车的乘客数为:下车的乘客数为:我们再引入两个附加假设:附加假设一:假设时区发出的第一辆与最后一辆车到达车站的时刻分别为,在到这个时间间隔内,乘客的到来服从均匀分布。原来假设一个时区里来人是均匀的;当求出在到内来的人数后,再认为这段时间内来人均匀附加假设二:假设时区发出的车能够把-这个时间间隔内来到车站的乘客全部运走。下面我们要解决的问题:具体求出时区发出的车要运多少乘客命题一:在考虑车站转移客流量时,在一个站我们分别考虑上下车人数与我们考虑净上车人数是等价的。命题二:每个时区内公交车的发车次数的下限由这个时区内相邻两站间最大转移客流量max决定。证明: max表示在时区要经由车站向下的乘客,我们要保证人能被运走,但又不能超载,即满载率不能超过120%,那么如果,必然导致该站的部分乘客滞留。命题三:在第时区来车站的乘客是被发自时区和发自时区的车共同运走的,而且被时区的车运走的乘客占车站总乘客的比例由车站距始发站的距离决定。推论:第时区内发的车从车站运走的乘客来自于时区和时区,运送的时区的乘客占总乘客的比例也由车站距始发站的距离决定。由这四个命题我们可以得出的一个算法:1) 1计算时区车站净上车人数=;2) 2计算和为在时区来的乘客被时区发出的车运走的数量,为从时区发的车运送的在时区来的乘客3) 3计算时区发出的车需从车站运走的乘客的数量,=-+4) 4计算时区车站的转移客流量,=对于上行方向来说,即i时区内发出的车从起点站到j站的净上车人数之和。5) 5据时区内各车站的最大转移客流量max和需要的发车次数的关系: max*120从而确定的最小值。用以上算法,将原表格变换成为一个新的表格,用来求发车次数。我们编了一个程序来计算每个车站由时区出发的车的转移客流量,最后求的结果列表如下:各个时区的最大转移客流量用粗体标出表1:上行方向的各个车站的转移客流量站名A13A12A11A10A9A8A7A6A5A4A3A2A11371445512556679723645563670660685718442199022792514262029962944259421062209207420201908409336264038432644854912475342593589363834983422324519654206422732445250526672577226719031911184117891682845511861308139614231519142212109821002960925864289692310241093112312111134975774819780755712208795710811180122713461289114398110419959689324588873969105710901190113810228999459158998744839779878941958104210139228048388127967674051062569576379687686176561163760558355521311635734803834924890733509548513476432-195121493171618751938214820521805147015571476432133529213201122652444249527002527230520202099203119911922128914691767823833886826726575599572547520264153503914234354644403882993022872762639916304337362373405394354282277264254241111172092302462502652462191671591491411317341819191917145-4-16-19-20-24-27-36由以上数据,我们可以建立一规划模型来求解min目标函数: min s.t: 经过求解,对所得数据进行近似及权衡乘客等待时间,我们得到了以下一组时区车次安排表2:上行方向的各个时区的车次安排时区123456789101112131415161718车次624412313111210988182386664总共需发车237次同理我们可以求得下行方向的车次安排表3:下行方向的各个车站的转移客流量站点A0A2A3A4A5A6A7A8A9A10A11A12122294856473931-317-23-38-101279586910141062975878609515509299212-343
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号