汽車客運多場站車輛排程問題之研究

Abstract

近年來臺灣地區受到私人運具過度成長與使用影響，大眾運輸之經營環境逐漸惡化，因此在外部環境開闢客源不易之情形下，規劃良好營運車輛排程以降低客運業者的內部成本支出，則被視為另一項可行辦法。但過去文獻中所提出多場站車輛排程問題(Multiple-Depot Vehicle Scheduling Problem, MDVSP)數學模式多存在不符實務之假設與限制，其相關假設與限制為：(1)各場站所配置營運車輛數目上限為已知；(2)相關營運成本被簡化為單一型式目標函數；(3)車輛空駛之處理並未提供足夠彈性；(4)勤務中車輛營運路線之轉換次數並未處理等四項假設與限制，上述假設與限制雖使得MDVSP於問題定式與模式求解較為容易，卻限制此類模式於臺灣地區汽車客運實務應用上之實用性，因此如何增加客運業者競爭力，並解決上述假設與限制對於處理實務問題時所造成之困難，產製出有效率之車輛排程勤務規劃，實為一大挑戰。 有鑑於此，本研究以具有多場站營運特性之汽車客運業者為研究對象，改善過去文獻中數學模式所建立假設與限制，構建符合臺灣地區汽車客運營運現況之多場站車輛排程模式，並依據所提出多場站車輛排程模式之特性，提出一啟發式解法—變數固定法(variable fixing heuristic)進行模式求解之工作。本研究並選取具有多場站多路線營運特性之金門縣公共車船管理處為測試對象，其測試結果顯示，本研究所構建之多場站車輛排程模式不僅可滿足臺灣地區汽車客運業者實際需求，而所提出之變數固定啟發式解法於處理較大型之車輛排程問題時，亦極具效率，顯示本研究之模式構建、參數特性證明、求解流程與測試結果等研究成果，具有提供國內汽車客運業者與學術界之參考價值。

The multiple-depot vehicle scheduling problem (MDVSP) address the work of assigning vehicle to serve a given set of time trips with the consideration of certain requirements representing the market rules. Extensive studies in the literature address the MDVSP, but because of the complexity of the problem, the findings made by those researches are still not enough to represent real world situations in Taiwan. Formulation for the MDVSP typically contains the following assumptions: (1) the size of fleet or maximum number of available vehicles at each depot is known already, (2) all trip serving costs are usually simplified as a single term in the objective function, which fails to reflect public transit operator concerns, (3) the applied deadheading strategy is static less flexibility, (4) without discussing of the difference of route change frequency in the problem. This study presents a new MDVSP model to address the above issues. A variable fixing heuristic algorithm based on the divide-and-conquer technique is also proposed to solve the MDVSP effectively. Computational tests are performed on the Kinmen Bus Administration (KBA) and results demonstrate that the proposed new model and the greedy heuristic algorithm for the MDVSP are effective in solving real world problems.