交通部運輸研究所Institute of Transportation, MOTC

       本研究針對一般共乘問題 General Share a ride Problem, G SARP 問題進行延伸，以充電式 (Plug in) 電動計程車及汽油計程車之混合車隊進行運輸與配送服務， 此一延伸問題稱為使用電動車 Electric Vehicles, EVs 之一般共乘問題G SARP EVs 。本研究以計程車營運業者的角度出發，於特定範圍內進行服務，考量 營運時間內混合計程車隊與人貨配送需求之配對 、 車輛排程與電動計程車充電之規劃，以營運業者利潤 最大化為目標，在固定且已知的車隊數量及車輛容量限制下，僅針對營運時間 前完成預約之乘客及貨物需求進行服務 。
       根據G SARP EV s 問題之特性， 本研究 建構時空網路 (Time Space Networks)描述人流、物流與車流在時空維度上面的移動情形，並將時空網路分成需求面 包含人流及物流 與供給面 包含電動車流及汽油車流 時空網路 ，其中供給面時空網路以每輛車輛作為分層依據，以有效進行車輛排程之描述及電動計程車之電量追蹤法 (Simulated 提升大規模問題之求解效率。為驗證及測試 本研究發展之使用電動車之一般共 乘 問題最佳化模式 及啟發式演算法 之 應用績效 ，本研究 以 業者 提供之 實際營運資料， 進行 調整後產出 不同規模之測試範例， 並 以 最佳化軟體 Gurobi 進行 G SARP EVs 模式 構建與求解；模擬退火法則以 Python 語言進行撰寫及求解，完成測試後 輸出 結果 並進行比較與分析 。小規模範例測試 中，不論是 Gurobi 或是模擬退火法 皆能於短時間內求得最佳解，並輸出車輛排程及充電規劃結果 ；中、 大規模範例測試 中， 可驗證本研究發展之 模擬退火法 的求解效率大幅領先最佳化求解軟體 Gurobi 。