考量重疊服務區域與容量限制之車輛路徑問題

Capacitated Vehicle Routing Problem with Overlapping Service Regions

謝宗桓(Chung-Huan Hsieh)

指導教授 ： 姚銘忠 ； 林春成

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

摘要

本研究所探討的「考量重疊服務區域與容量限制之車輛路徑問題」為傳統車輛路徑問題之延伸，在已知分區且考量重疊服務區域之架構下，求解物流公司配送顧客貨物需求之最佳車輛路徑決策，其中包含在分區中使用該分區之原有車輛、跨分區車輛或外包車輛與車輛路徑之安排。本研究提出一個創新的「廣義型重疊服務區域」，其乃是將過去研究所運用僅有兩分區彼此重疊之「鏈狀重疊服務區域」，允許多個分區相互重疊，增加車輛路徑安排與物流車隊運用之彈性，提供物流公司配送作業創新之模式。
本研究依照「考量重疊服務區域與容量限制之車輛路徑問題」之情境，建構數學模型。而由於車輛路徑問題為NP-hard問題，本問題有更高的複雜度，故本研究另提出基因演算法求解本問題。透過本研究所提出基因演算法染色體編碼之資料結構，可以直觀且容易地掌握廣義型重疊服務區域之特性與描述對應的情境，且本研究設計一區域搜尋機制加強基因演算法之搜索能力。本研究以傳統車輛路徑問題之標竿題庫，加上廣義型重疊服務區域的特性，運用隨機產生之例題進行數據實驗分析。數據實驗的結果顯示，本研究所提出的基因演算法及區域搜尋機制確實具有優異的求解品質與效率，且驗證本研究採用之廣義型重疊服務區域確實能有效地降低物流公司之配送成本最多至10%。

關鍵字

廣義型重疊服務區域 ； 車輛路徑問題 ； 基因演算法 ； 區域搜尋

並列摘要

This study investigates the capacitated vehicle routing problem with overlapping service regions, which is an extension of the conventional vehicle routing problem (VRP). We are interested in solving the optimal decisions including the fleet deployment using the vehicles in the original region, the trans-regional vehicles and the vehicles from outsourcing and the corresponding vehicle routes for logistics companies to satisfy customers’ demand with pre-determined and overlapping service regions. We present a new districting concept of “general overlapping service regions” (GOSR) in this study, that is a more generic version of the “chain-type overlapping service regions” than that presented in a previous study. GOSR allows more than two service regions overlapping with each other, increases the flexibility in vehicle routing and fleet deployment, and serves as a novel model of the distribution operations for logistics companies.
We formulate a mathematical model following the scenario of the capacitated VRP with overlapping service regions. It is well known that the conventional VRP is NP-hard. Therefore, the concerned problem in this study is more complicated and hence, more difficult, and we propose a genetic algorithm (GA) as our solution approach. The Data structure of chromosome encoding in our GA is not only comprehensive, but also easy to deal with the situation of GOSR. In addition, we also develop a local search mechanism to enhance the search ability of our GA. We randomly generate our instances in our numerical experiments by referring to the benchmark problems for the conventional VRP and taking into account of the characteristics of GOSR. Our experimental results show that our proposed GA with the proposed local search mechanism is able to obtain solutions with excellently quality effectively, and making use of GOSR may save distribution cost up to 10% for logistics companies.

並列關鍵字

General overlapping service regions ； vehicle routing problem ； genetic algorithm ； local search

參考文獻

1. Augerat, P., Belenguer, J. M., Benavent, E., Corberán, A., Naddef, D., & Rinaldi, G. (1995). Computational results with a branch and cut code for the capacitated vehicle routing problem. Technical Report 949-M, Université Joseph Fourier.

2. Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787-800.

3. Barbarosoglu, G., & Ozgur, D. (1999). A tabu search algorithm for the vehicle routing problem. Computers & Operations Research, 26(3), 255-270.

4. Bard, J. F., Jarrah, A. I., & Zan, J. (2010). Validating vehicle routing zone construction using Monte Carlo simulation. European Journal of Operational Research, 206(1), 73-85.

5. Bell, J. E., & McMullen, P. R. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced engineering informatics, 18(1), 41-48.