标题: 市区公车排班与即时机动调度之研究-以新竹客运为例
The Study on urban Bus Scheduling and Real Time Rescheduling - A Case Study of hsinchu Transportation Company
作者: 刘方旗
Liu, Fang-Chyi
王晋元, 陈慧芬
Jin-Yuan Wang, Hui-Fen Chen
运输与物流管理学系
关键字: 公车排班;模拟;随机最佳化;机动调度;先进公共运输系统;任务产生;Scheduling;Simulation;Stochastic Optimization;Rescheduling;Column generation;GPS
公开日期: 1997
摘要: 本研究探讨有关市区公车排班以及即时机动调度两个课题,在市区公车
方面,在车队大小与营运策略以及需求不变的情况下,针对市区内公车之
排班问题,即在一起迄点相同之公车路线,求解全时段单一班距及多时班
之最佳时刻表。在行车随机系统中车辆容量固定、旅客在等候线等候时有
时间有上限(Reneging)、旅客到达过程服从非均匀波以松过程、旅客下车
服从二项式分配、公车站间旅行时间服从韦伯分配以及旅客上下车时间为
一常数。本研究将目标函数定义为客运公司之利润,即收入减成本,其中
收入为票价收入,成本为营运成本加上乘客等候成本。模式分为两种:单
一班距及多班距。针对单一班距,本论文以随机寻根问题 (Stochastic
Root Finding Problem; SRFP) 之相关求解方法(Bounding
Retrospective algorithm; Bounding RA) 为基础并略做修正, 使其应
用于求解排班问题之最佳班距。在多班距最佳班距求解上,则是在各时段
内利用单一班距所发展之随机最佳化方法求解最佳发车班距。在发展排班
问题之最佳班次之演算法上,根据本研究对目标函数之特性探讨发现目标
函数为一不连续的函数,而其不连续点发生在发车频率变动之时,因此本
研究先找出最佳发车频率,然后在最佳发车频率中找最佳发车班距。以新
竹客运之一路线的试调资料为依据,对本研究所发展之随机最佳化方法做
测试,结果发现在旅客到达过程为均匀时,本研究发展之方法能保证找到
最佳班距,然在旅客到达过程为非均匀以及等候成本过大时,演算法对起
始解敏感,然在给定适当之起始解,皆能找到最佳发车班距。班表规划出
来之后,在实际派车调度时常发生塞车或突发状况导致即定之班表无法按
时发车,因此针对实际派车时之突发状况,本研究发展一公车即时机动调
度系统,系统中主要是藉由GPS卫星定位讯号获知目前车辆所在位置,并
根据即时道路行驶速度计算出车辆回站时间,当发现车辆无法在预定的时
间回来执行下一个班次时,即启动机动调度模式,产生调度方案供调度者
参考。在机动调度模式,主要处理当站内皆无任何预备车可用时,机动调
度其它路线之车辆来支援发生扰动的班次。在模式中根据使用者给定之系
统回复时间定义出机动调度路网,根据此一路网,我们将机动调度问题转
换成一集合分割的问题并发展一以Column generation为基础的最佳化方
法来产生可行之调度方案。在调度方案的产生上,本研究允许班表延误的
情形,因此增加延误节点至机动调度路网之中。针对此一路网,本研究利
用各节点之成本/对偶值、时间距以及延误成本定义出各节点间之成本后
求解最短路径,所得之最短路径即为一可行之调度方式。以实际班表模拟
测试发现本研究所发展之机动调度模式能迅速地产生最佳调度方案,而与
人工调度的情形,本研究所发展之机动调度模式在非尖峰时段能增加80%
的营运效率,在尖峰时段中则是改善了17%。
This thesis is study on urban bus scheduling problem and real
time reschedulin-g problem. On urban bus scheduling problem,
fixed fleet size and captive dema-nd are considered. Finding
optimal single headway model and multiple headway model are
discussed in this thesis. In stochastic bus system, passenger
rene-ging, non-homogeneus arrvial process , weibull travel time
and constant passen-ger upload/depart time are considered.The
object function is define as profit of bus company. It equals
ticket revenue minus operating cost and passengers t-otal
waiting cost. Single headway model and multiple headway
mathematics model are proposed. Finding optimal headway is a
stochastic optimization problem. F-or single headway model, the
algorithm of stochastic optimization base on boun-ding RA.。Same
algorithm is also applied to multiple headway model in each tim-
e interval..According to object function is not discontinuous
and disconnected point is occurred on frequency changed. Two
stage optimization is proposed. I-n the first stage, optimal
frequency is found. In the second stage, optimal he-adway is
found in optimal frequency.Empirical results show that modified
bound-ing RA can find optimal headway in homogeneous arrival
process. In non-homogen-eous arrival process and higher fare/
waiting cost ratio, algorithm is sensitiv-e with initial
solution.Although schedule is setuped, traffic conjection and u-
nexpected situation that cause journey can not be dispatched on
given time are often happened. For these situation, real time
bus dispatching and rescheduli-ng system are developed in this
thesis. In system, real time bus location can be achieved by GPS
signal and expected return time of bus is calculated by rea-l
time travel speed of each road. When perturbation journey
occurred, system w-ill active bus rescheduling module
automatically and provides optimal dispatch-ing alternatives.
Rescheduling module is deal with the situation that there is no
reserved bus in bus station. It will dispatch bus belonged to
other route t-o run perturbation journey. In module,
rescheduling network model is constru-cted by system recovery
time given by dispatcher. Based on the network, SPP(Se-t
Partition Problem) is formulated. For the SPP, a column
generation approach is proposed to generate available duties.
Delay alternative is considered in ge-nerating available duties,
thus delay nodes of each journey are appended to re-scheduling
network. For the argumentation network, node-to-node cost matrix
is calculated. Arc cost is define as sum of node cost/dual
price, time distance and delay cost. After cost matrix is
constructed, algorithm find the shortest path for given origin
and destination. Each path is an available duty.Empiric-al
result show that the column generation algorithm can generate
optimal resch-eduling alternative efficiently. Comparing to
manual dispatching, rescheduling module can improve 80% bus
usage rate in un-peak period, 17% in peak period.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT860118038
http://hdl.handle.net/11536/62636
显示于类别:Thesis