隨機旅行時間下車輛補貨路線規劃之研究

Routing for the truck replenishment problem under stochastic travel times

黃瀚正(Han-jheng Huang)

指導教授 ： 顏上堯

國立中央大學/工學院/土木工程學系/碩士(2011年)

摘要

在車輛補貨問題中，如何有效地調派車輛並將貨物準時送達，為一重要課題，過去有關車輛補貨相關研究，很少考量旅行時間之隨機性，大多以平均旅行時間做為排程之依據，在實際營運時若隨機擾動過大，將造成原本排程失去最佳性。而目前實務上車輛補貨排程，大多採規劃人員之經驗進行規劃，此種方式缺乏系統最佳化分析，往往在營運時造成資源的浪費因此，本研究主要於模式中加入旅行時間隨機性考量，建構隨機性車輛補貨路線規劃模式，以提供決策者輔助工具，可有效地規劃車輛補貨路線排程。
本研究利用時空網路流動的技巧，以總運送成本最小化為目標，並考量實際營運下旅行時間之隨機性，建立一隨機性模式，此模式包含車流網路與物流網路。此外，本研究進一步修正隨機性模式之旅行時間唯一固定平均旅行時間，發展一確定性模式。隨機性模式與確定性模式可定式為一含額外限制之整數多重貨物網路流動問題，屬NP-hard問題，當面對實務大規模問題，難以在有限時間內求得最佳解。因此，本研究透過問題分解，並配合數學規劃軟體CPLEX，發展一有效率之啟發式演算法。為評估確定性模式與隨機性模式於實際營運之績效，本研究發展一模擬評估方法，以比較兩模式之優劣。最後，為評估模式與演算法求解效率，本研究以台灣一供應商運送業者為例，進行範例測試，並進行不同參數之敏感度分析，結果顯示隨機模式表現比確定性模式為佳，於實際營運中可大幅地降低未滿足需求之額外處理量產生。

關鍵字

隨機性旅行時間 ； 多重貨物網路流動問題 ； 時空網路 ； 啟發解 ； 車輛補貨

並列摘要

In truck replenishment problem, how to deliver goods efficiently on time becomes a more important problem. In the past few years, many VRP under deterministic travel time has been discussed and researched by many scholars. But stochastic disturbances arising from variations in vehicle travel times in actual operations are neglected. Then the stochastic travel time will make the planned schedule lose its optimality. Therefore, we constructed a stochastic truck replenishment model that considered the influence of stochastic travel times.
We employed network flow techniques with the objective of minimizing total cost to construct the stochastic model that considered the stochastic travel times, including vehicle-flow and commodity-flow networks. Then, we modified the stochastic travel time in the stochastic truck replenishment model as an average travel to develop a deterministic model. Both stochastic model and deterministic model are formulated as the integer multiple commodity network flow problem, which is characterized as NP-hard. Since the problem sizes are expected to be huge in real practice, the models are difficult to be solved in a reasonable time. Therefore, we develop an effective heuristic algorithm by adopting a problem decomposition technique, coupled with a mathematical programming solver CPLEX. To evaluate how well the stochastic model and the deterministic model, we also developed a simulation-based evaluation method. Finally, we use a real data and suitable assumptions and sensitive analysis to test our model. The test results of stochastic model is better than deterministic model because stochastic model produces low shortage cost.

並列關鍵字

Stochastic travel times ； Time-space network ； Multiple commodity network flow problem ； Heuristics ； Truck replenishment

參考文獻

17.楊大輝、李綺容(2007)，「需求變動下之航空貨運網路規劃」，運輸學刊，第十九卷，第二期，第169-189頁。

10.張宗勝、溫日華、吳淑娟(2007)，「接駁轉運營運系統最佳營運策略之探討」，運輸學刊，第十九卷，第一期。

27.韓復華、楊智凱、卓裕仁(1997)，「應用門檻接受法求解車輛路線問題之研究」，運輸計畫季刊，第二十六卷，第二期，頁253-280。

3.卓裕仁、朱佑旌(2008)，「兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問題之研究」，運輸計劃季刊，第三十七卷，第四期，第405-430頁

6.邱明琦、陳春益、林佐鼎(2002)，「海運貨櫃排程模式之研究」，運輸計劃季刊，第三十一卷，第三期，第495-522頁。