科研训练公交车调度算法.doc

科研训练 题目：公交调度算法研究 2012年12月26 文献资料名称 序号篇名作者刊名年/期公交调度优化模型及其解法研究曹丽雅实验科学与技术2011/04 2 公交车和驾驶员集成调度算法研究刘波涛计算机工程与科学2011/04 3 基于双层规划的公交车调度问题的模型与算法晏烽兰州交通大学学报2008/06 4 快速公交调度算法与研究李艳东北大学2010/12 5 城市公交车辆组合调度问题的研究陈明明兰州交通大学2007/11 6 城市公交调度优化方法研究覃运梅合肥工业大学2006/07 摘选内容 内容1 各站候车乘客数和下车率的分布函数 各站点乘客的流量是制订车辆调度表的基础。以某城市的一条公交线路上公交车的调度问题为例。该条线路共n 站，每天的运营时间分为k 个时段，获得的数据是一个典型工作日各站在各个时段内上车的乘客数量和下车人数占车上总人数的比例。由于所采集的数据只是各时段的累积人数而实际上乘客密度并不均匀，为了处理方便，假定在第i 个站点从每天的起始时刻到t 时刻达到的乘客总数为一个二阶导数连续的函数Fi( t) ，因此可据第i 个站点提供的k 个时段的到达乘客数依次累加得k个型值点，调用matlab 中的三次样条插值函数，得到Fi(t) 的表达式( i = 1，2，…，n) ，曲线形式如下图 图1 车站上车人数曲线 考虑出行特征随时间变化的规律性，模型所需要的车站乘客预计下车人数，可首先通过既有统计客流数据建立各站下车率随时间变化的函数曲线Gi( t) 的表达式( i = 1，2，…，n) ，然后再计算下车人数的方法获取。下车率曲线横坐标为时间，纵坐标为下车率，其建立过程与乘客到站曲线相同。 内容2多目标公交调度问题的数学模型 一般情况下, 车辆调度工作优先于驾驶员调度工作, 驾驶员调度就是安排一组驾驶员来完成一日内的全部车辆运营工作。一辆车的运营工作就是从车场出发, 在线路上运营若干趟以后, 最终返回车场的过程。在车辆的运营线路上有若干个指定的驾驶员换班地点, 称为“换班点”, 一个换班点与车辆到达该地点的时间结合起来就构成一个“换班机会”。在任意一个换班机会, 驾驶员都可以交接班。由于车辆到达一个换班点时, 通常会停留一段时间, 这段时间被称为“时间窗”。时间窗与相应的换班点结合构成一个“换班机会窗”, 驾驶员在换班机会窗内任意时刻都可以交接班。两个连续换班机会窗之间, 不允许驾驶员换班, 这段时间被称为“小驾驶段”。多目标公交调度就是要构造一组驾驶班次来覆盖一日内的全部车辆运营工作, 一个班次代表一位驾驶员一天的运营工作。这是一个复杂的组合优化问题, 它需要同时满足以下条件:(1) 每一班次必须是有效的。班次的有效性由一组国家和企业制定的劳动法规制约(如一天的总工时不许超过8 小时) , 满足全部劳动法规的班次才是有效班次。(2) 驾驶员只能在指定的换班机会窗进行交接班。换班机会窗相对单一的的换班机会为驾驶员提供了更多的换班机会, 但是增加了调度的复杂性。(3) 追求最少的驾驶班次以及最小的运营成本。每种类型的班次的成本计算方法不同, 而一个驾驶员可能有不同类型的班次, 这就使得减少班次与减少运营成本这两个目标有时会冲突。本文采用基于集合覆盖的方法来描述多目标。 内容3　乘客平均候车时间 在拥挤的情况下,存在乘客等多次车的情况,在第j 趟客车过站后, 留在站上的乘客数可用如下公式计算: μj = 2/ 3 ·μj - 1 + vi - (λ- ( Σi- 1n = 1vn ·t - Σin = 2un) ) 假定未被滞留的乘客平均等车时间为t/ 2 ,滞留n 趟未上车的乘客平均候车时间t/ 2 + n ·t ( n = 1 ,2) ,可以求出在一个时间段内的第j 次公交车经过第i 个站点时,上车的乘客平均候车时间为 ti , j =2/ 3 ·μj - 1 ·( t/ 2 + t) + 2/ 3 ·μj - 2 ·t + vi ·t ·( t/ 2)2/ 3 ·μj - 1 + vi ·t 进一步可求出线路上行路线所有乘客从等车到下车的平均乘车时间为 t1 = Σt′/ tj =1 Σm- 1i =1t1i, j ·(λ- ( Σi - 1n =1vjn·t - Σin =2ujn) ) /Σt′/ tj =1Num1j+Δt (3) 式中: Num1j= Σmi = 1v1i, j ·t. 同样的方法, 可以求出线路下行路线上所有乘客从等车到下车的平均时间.乘客的综合满意度可以为乘客的平均乘车时间与乘客在公交车上