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