應用變數產生法求解電動公車車輛排程問題

A Column Generation Approach for Electric Bus Scheduling Problem

陳玥心(Iue-Shin Chen)

指導教授 ： 王晉元

國立交通大學/管理學院/運輸與物流管理學系/碩士(2013年)

https://doi.org/10.6842/NCTU.2013.00798

摘要

本研究之目的即是針對未來電動公車所需車輛數大於充電座個數的情況下，使客運業者可針對電動公車的充電特性等產生成本最小的車輛排程表，其排程表除了需配合公車發車時刻表執行所有的任務外，也需考量電動公車之續航力、充電時間、夜間充電及充電座個數等。本研究將電動公車車輛排程問題（Electric Bus Scheduling Problem）建構為一集合分割問題，並提出一套以變數產生法（Column Generation）為基礎的演算法求解。此演算法以變數產生法、分支定限法與解決重複涵蓋問題的啟發式解法三大部分所組成。本研究將子問題設計為考慮充電特性的最短路徑問題，使用修正後的Dijkstra’s演算法與啟發式解法求解。
測試範例利用模擬情境的方式，針對發車頻率、路線長度、充電座個數及充電種類之不同，設計多個情境並測試本研究模式在各情境之表現。分析結果發現，使用快充及增加充電座個數的方式在大多數的情況下可有效的減少使用車輛數，使成本最小化。在條件許可，建置完成所有任務所需之車輛數目的充電座最為節省成本；但電動公車實行擴展後，此方式是不可行的，在未來種種環境的限制下，如：土地使用限制等，充電座的個數勢必遠小於所使用的車輛數，此時使用本研究的模式可提供一個成本最小且車輛數最少的車輛排程表。

關鍵字

電動公車車輛排程問題 ； 集合分割問題 ； 變數產生法

並列摘要

Due to the rapid development of electric buses, electric bus scheduling becomes an important issue for many bus carries. We first formulate this problem as a set-partitioning problem. The column generation based algorithms are proposed for solving this model. The algorithm consists of three phases: column generation, branch and bound, and heuristic local search. The column generation sub-problem is formulated as a multi-attribute shortest path problem with extra side constraints. We also propose a multi-label shortest path algorithm based on the Dijkstra’s algorithm for generating new column.

This study uses simulated testing problems to evaluate the performance of the algorithm. The simulated problems consist of four characteristics: service frequency, path length, number of electric charging stations and type of charging station. The testing results show the proposed model and the associated solving technique are sound and promising. The numerical experiments also show that the increment of charging stations could effectively decrease the number of buses required.

並列關鍵字

Electric bus scheduling problem ； Set-partitioning problem ； Column generation

參考文獻

[15] 林至康，「汽車客運多場站車輛排程問題之研究」，國立交通大學運輸科技與管理學系博士論文，民國九十八年三月

[16] 葉珮婷，「應用變數產生法求解有時間窗限制的收送貨問題」，國立交通大學運輸科技與管理學系碩士論文，民國九十八年七月。

[2] Bunte, S. and Kliewer, N., “An overview on vehicle scheduling models”, Journal of Public Transport, Vol. 1, No. 4, pp. 299-317, 2009.

[3] Dantzig, G. B. and P. Wolfe “The Decomposition Algorithm for Linear Programming”, Operations Research, Vol. 8, pp. 101-111, 1960.

[4] Desroched, Martin and Soumis, Francois, “A Column Generation Approach to the Urban Transit Crew Scheduling Problem”, Transportation Science, Vol. 23, No. 1, pp. 1-13, 1989.