臺灣博碩士論文加值系統

冷凍車及油罐車在配送產品時，通常是使用兩個載具以上的車輛來儲存不同的特定產品，與一般常見之配送模式不同，因此衍生出多載具車輛途程問題(Multi-Compartment Vehicle Routing Problem; MC-VRP)。由於實務上，某些配送業者使用可調整車輛上載具空間之車輛，以期能夠節省更多的途程成本，本研究進一步延伸MC-VRP問題，定義可調式多載具的車輛途程問題(Adjustable Compartments Vehicle Routing Problem; AC-VRP)，並且建構AC-VRP的數學模型。因為最佳化軟體無法求解大型AC-VRP問題，不能滿足實際營運上之需求所以本研究亦發展了一套符合AC-VRP特性的演算法，以期能在一定時限內，求得不錯之解。此演算法以禁忌搜尋法為基礎，結合了若干特色，包括縮小搜尋的鄰近結構空間及加入指導策略來尋找最佳解，經過實驗的測試之後，結果顯示本研究所提出之演算法不但能夠找到不錯的AC-VRP解，在求解MC-VRP問題上，也略優於過去研究所提出之演算法。

Cold logistics and oil distributers often use special vehicles with multiple compartments to ship different products to customers. This special transportation mode results in a new type of vehicle routing problem, namely the multi-compartment vehicle routing problem (MC-VRP). In practice, some of these carriers adopted vehicles with adjustable compartments to further reduce transportation costs. Therefore, in this research, we extended the MC-VRP and defined the adjustable compartments vehicle routing problem (AC-VRP). We also developed a mathmatical programming model for this new problem. Since large-scale AC-VRP instances in practice are difficult to solve by commercial optimization software, we developed a heuristics algorithm based on tabu search for the AC-VRP so that quality solutions may be obtained within a reasonable amount of time. The proposed algorithm integrates certain problem specific features such as solution space reduction and guided search strategies. Results of computational experiments indicate that the proposed heuristic is capable of solving the AC-VRP efficiently. Moreover, it's performance on solving MC-VRP is slightly better than previous approaches in the literature.

目錄
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的與假設 3
1.2.1 研究目的 3
1.2.2 研究假設 4
1.3 研究方法與流程 5
第二章 文獻探討 2
2.1 VRP初始解之建構方法以及途程改善方法 3
2.2 應用禁忌搜尋法求解VRP 7
第三章 數學模型與演算法設計 11
3.1 AC-VRP描述以及定義 11
3.2 AC-VRP數學模型 12
3.3 求解AC-VRP演算法的設計 15
3.3.1. 建構初始解 18
3.3.2. 改善初始解之禁忌搜尋法 19
3.3.3. 鄰近結構 21
3.3.4. 候選名單 24
3.3.5. 禁忌名單 26
3.3.6. 指導策略 26
3.3.7. 局部搜尋法 27
3.4 AC-VRP問題特性 27
第四章 AC-VRP問題實驗測試與分析 30
4.1 AC-VRP問題設計 30
4.2 實驗參數測試 31
4.3 AC-VRP問題測試 40
第五章 結論與建議 43
5.1 結論 43
5.2 建議 44
5.3 研究貢獻 45
文獻探討 46
附錄A第一個題庫的途程結果 49
附錄B 第二個題庫的途程結果 57

圖目錄
圖1.1 1946-2009國際油價走勢圖(紅線為考量通貨膨漲因素後之走勢圖) 1
圖1.2研究流程圖 6
圖3.1演算法流程圖………………………………………………………………...17
圖3.2第一種交換結構 22
圖3.3第二種交換結構 23
圖3.4第三種交換結構 23
圖3.5第四種交換結構 24
圖3.6第五種交換結構 24
圖3.7途程內2-opt的交換 27
圖3.8第一種常見的情況 28
圖3.9第二種常見的情況 29

表目錄
表3.1節點間之距離cij 14
表3.2顧客之產品需求qjp 15
表4.1使用不同值求解最佳解的比較結果………………………………………...32
表4.2有無使用指導策略的比較 36
表4.3使用不同的懲罰參數 、 、 搜尋最佳解的比較 38
表4.4演算法使用的參數值 39
表4.5第一個題組比較禁忌搜尋法求解的結果 40
表4.6第二個題組比較禁忌搜尋法求解的結果 41

Archetti, C., Speranza, M. G., & Hertz, A. (2006). A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science, 40(1), 64-71.
Avella, P., Boccia, M., & Sforza, A. (2004). Solving a fuel delivery problem by heuristic and exact approaches. European Journal of Operational Research, 152(1), 170-179.
Beasley, J. (1983). Route first--Cluster second methods for vehicle routing. Omega, 11(4), 403-408.
Beullens, P., Muyldermans, L., Cattrysse, D., & Oudheusden, D. V. (2003). A guided local search heuristic for the capacitated arc routing problem European Journal of Operational Research, 147(3), 629-643.
Brandão, J., & Eglese, R. (2008). A deterministic tabu search algorithm for the capacitated arc routing problem Computers & Operations Research, 35(4), 1112-1125.
Brown, G. G., Ellis, C. J., Graves, G. W., & Ronen, D. (1987). Real-time, wide area dispatch of mobil tank trucks. Interfaces, 17(1), 107-120.
Brown, G. G., & Graves, G. W. (1981). Real-time dispatch of petroleum tank trucks. Management Science, 27(1), 19-32.
Chajakis, E. D., & Guignard, M. (2003). Scheduling Deliveries in Vehicles with Multiple Compartments Journal of Global Optimization, 26, 43-78.
Christofides, N., & Eilon, S. (1969). An algorithm for the vehicle-dispatching problem. Operations Research, 20(3), 309-318.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 88-99.
Dror, M., & Trudeau, P. (1989). Savings by split delivery routing. Transportation Science, 23(2), 141-146.
Fallahi, A. E., Prins, C., & Calvo, R. W. (2008). A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Computers & Operations Research, 35(5), 1725-1741.
Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
Gendreau, M., Hertz, A., & Laporte, G. (1992). New insertion and postoptimization procedures for the traveling salesman problem. Operations Research, 40(6), 1086-1094.
Gendreau, M., Hertz, A., & Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management Science, 40(10), 1276-1285.
Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22(2), 340-349.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13(5), 533-549.
Golden, B. L., & Wong, R. T. (1981). Capacitated arc routing problems. Networks, 11(3), 305-315.
Haouari, M. (2002). Arc routing: theory, solutions and applications Moshe Dror (editor) Kluwer Academic Publishers. IIE Transactions, 34(3), 331-333.
Hertz, A., Laporte, G., & Mittaz, M. (2000). A tabu search heuristic for the capacitated arc routing problem. Operations Research, 48, 129-135.
Muyldermans, L., & Pang, G. (2010). On the benefits of co-collection: experiments with a multi compartment vehicle routing algorithm. European Journal of Operational Research, 206(1), 93-103.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31(2), 1985-2002.
Rochat, Y., & Taillard, É. D. (1995). Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1(1), 147-167.
Ruiz, R., Maroto, C., & Alcaraz, J. (2004). A decision support system for a real vehicle routing problem. European Journal of Operational Research, 153(3), 593-606.
Taillard, É. (1993). Parallel iterative search methods for vehicle routing problems. Networks, 23(8), 661-674.
Toth, P., & Vigo, D. (2003). The granular tabu search and Its application to the vehicle-routing problem. Informs Journal on Computing, 15(4), 333-346.
Xu, J., & Kelly, J. P. (1996). A network flow-nased tabu search heuristic for the vehicle routing problem. Transportation Science, 30(4), 379-393.
Zachariadis, E. E., Tarantilis, C. D., & Kiranoudis, C. T. (2009). A guided tabu search for the vehicle routing problem with two-dimensional loading constraints European Journal of Operational Research, 195(3), 729-743.