大眾運輸排班系統之研究

Abstract

由於藉由時刻表及需求分析來對車隊做管理、對人員做排班是短期內最容易提升客運業者營運績效的方式，所以本研究的目的為建構數學模式，以最佳解為基礎（Optimization Based ）設計演算法求解模式，提升客運業者人員排班營運效率。 在研究中，先將客運業的車輛營運狀況以時空網路圖來表示，基於此時空網路圖將車輛排程及人員排班問題建構為集合分割(Set Partitioning)問題模式，並針對此模式設計求解演算法。演算法包含以拉氏鬆弛法切入問題、修正放鬆後集合切割限制、車輛起迄相同的限制、工作時間的限制等限制條件。並配合一演算流程，以C++語言撰寫演算法並利用CPLEX6.0中的網路簡捷法功能來求解。 在演算法求解階段，由於排班模式屬於NP-Hard性質的問題，根據過去文獻中將模式放鬆成純網路問題並以網路簡捷法求解可以自動滿足整數限制加快求解速率。本研究引入拉氏鬆弛法的想法將模式中的額外限制式放鬆使問題成為一個純網路問題。由於限制式放鬆後會造成解的不合理性，所以本研究採用一些方式基於Optimization Based作調整，這是跟以往文獻中所不同的作法。（1）調整網路架構使其滿足集合分割的限制：對時空網路圖調整，利用節線的流量限制來滿足此限制。（2）利用權重來滿足起迄要相同場站的限制：將拉氏乘數值轉換成處罰權重值，使其盡量滿足此一限制。（3）根據工作時間限制來限制每個pattern的候選結束節線集合：將pattern根據班表的特性分為已知必定要發車時刻者與可以自由選擇發車時刻者，對已知發車時刻者根據工作時間對結束節線集合做限制，對可自由選擇者以窮舉的方式來搜尋滿足限制之解。 為測試模式及演算法的實際績效，本研究以實際國內客運業排班之營運資料為例，作實例測試分析與修正。實務上客運業者可以針對企業著重之目標，設計較合適的目標式結構，以求演算法能符合業者追求的目標。

As a result, the bus company drivers scheduling operations were not usually efficient. This research thus attempts to develop a model that helps bus company in timetable drafting so that their operations can be improved. This thesis proposes an algorithm to improve the efficiency for solving the drivers scheduling problem of the mass transport company. We formulate this problem as a set-partitioning problem. A three phases algorithm, Lagrangean relaxation, network simplex, and a adjusted strategy algorithm built by myself , is then developed for solving this model. First, We use Lagrangean relaxation technique to relax all side constraints then the model become a pure network problem. Second, a adjusted strategy algorithm is applied to solve the solution’s unreasonableness which is caused by relaxing the constraints. Finally, we use network simplex technique to obtain the integer. In order to evaluate the model and algorithm in practice, a case study concerning the operation of major bus companies in Taiwan is performed. The results show that our algorithm could get better solutions with higher operational feasibility than the current one does.