标题: | 市区公车排班与即时机动调度之研究-以新竹客运为例 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 |