臺灣博碩士論文加值系統

分割配送車輛路線問題 (Split Delivery Vehicle Routing Problem, SDVRP) 允許單一顧客的需求可分批被多部車輛服務;它是傳統車輛路線問題的衍生問題。由於配送限制的放鬆，SDVRP具有降低運輸成本的效益，進可提昇企業之競爭力。但就實務而言，需求分割配送會造成顧客的不便，亦伴隨作業成本的增加。有鑑於此，如何使SDVRP兼顧成本效率與服務品質是一重要議題。近年巳有文獻 (Gulczynski et al. [29]) 將最小配送量列入考慮，提出最小配送量限制之分割配送車輛路線問題 (SDVRP with minimum delivery amounts, SDVRR-MDA)。本研究則首次提出以配送次數作為限制的「具配送次數限制的分割配送車輛路線問題」(SDVRP with limited number of deliveries, SDVRP-LND)，以期分割配送能有更高的應用價值。
針對分割問題特性，本研究提出一套一體適用於求解SDVRP，SDVRP-MDA與SDVRP-LND的多重起點啟發式解法，稱為SRC+IMP (Split-delivery Route Construction + solution IMProvement)。SRC為起始解構建模組，適應性地選擇「插入路線」或是「新增路線」的方式逐點構建起始路線。IMP為多鄰域求解改善模組，其中包含一套針對分割問題特性新設計的驅逐鏈鄰域搜尋法。整個演算法SRC+IMP則採用多重起點策略整合SRC與IMP以兼顧搜尋的深度與廣度。
SRC+IMP演算法以目前所有SDVRP相關之國際標竿題庫進行測試，在IMP模組部分採用變動鄰域下降 (Variable Neighborhood Decent,VND) 與隨機變動鄰域下降 (Randomized VND, RVND) 兩種方式執行。測試結果發現SRC+RVND的績效較SRC+VND佳；其結果在SDVRP方面，對32個標竿題求解的平均誤差為0.36%，其績效僅次於ILS (Silva et al. [44])；在SDVRP-MDA方面，對128個標竿題求解的平均誤差為-0.27%，且求得81題並突破36題已知最佳解；在SDVRP-LND方面，22題標竿例題中則求得5題已知最佳解並突破5題，平均求解誤差為0.07%。
本研究亦分析配送次數上限kmax對成本的影響，結果發現當kmax  3時，SDVRP-LND的成本節省效益為4.11%，其與無次數限制的SDVRP相差僅0.06%；這顯示以最多配送三次執行SDVRP-LND可對物流界提供相當的實用價值。

The split-delivery vehicle routing problem (SDVRP), in which the demand of a customer can be split and delivered by several vehicles, would result in less cost than the conventional vehicle routing problem. However, split deliveries also incur extra work for logistics operations and undesirable distractions to customers. How to tradeoff cost efficiency and customer service in the split-delivery related problems thus is an important issue. Recently, Gulczynski et al. [29] proposed a variant of the SDVRP called the SDVRP-MDA, in which the customers each require a minimum delivery amount (MDA) every time they are visited. In this dissertation, we propose a new variant of the SDVRP, i.e., the spit-delivery VRP with limited number of deliveries (SDVRP-LND), which considers the number of deliveries for each customer is restrained to kmax.
We propose a unified multi-start heuristic method, i.e., SRC+IMP (Split-delivery Route Construction + solution IMProvement), to solve the SDVRP and its variants of the SDVRP-MDA and the SDVRP-LND. The initial-solution generator SRC adaptively applies either node-insertion or route-addition procedures, which were designed specifically for the SDVRP and its variants, to generate an initial solution. The IMP conducts local search with multiple neighborhoods for solution improvement, in which we developed a novel node ejection-chain operator for the split-delivery related problems. The overall SRC+IMP combines the SRC and the IMP modules to implement a multi-start solution procedure with a single parameter to control the restart.
The proposed SRC+IMP algorithms are tested with all the related benchmark problems. We conduct the IMP module with two variable neighborhood descent methods, i.e., VND and RVND. It is found that the performance of the SRC+RVND is better than that of the SRC+VND. The results of the SRC+RVND for the SDVRP show that, out of 32 instances tested, the average deviation from the best known solutions (BKS) is 0.36%, which is only second to the ILS algorithm (Silva et al. [44]). For the SDVRP-MDA, out of the 128 instances tested, the results reveal 81 BKS and 36 new best solutions; the average deviation is -0.27%. For the SDVRP-LND, out of the 22 instances tested, we find 5 BKS and 5 new best solutions; the average deviation is 0.07%.
We also investigate the impact of kmax to the potential cost saving of the SDVRP-LND. It is found that, for kmax=3, the average cost saving is 4.11%, which is only 0.06% less than that of the SDVRP. This implies that the SDVRP-LND with kmax=3 can provide a valuable and easy-to-implement tool for logistics operations.

中文摘要 i
英文摘要 ii
誌 謝 iii
目 錄 iv
圖目錄 vi
表目錄 vii
第一章、前言 1
1.1 研究動機與目的 1
1.2 研究流程與步驟 3
1.3 章節簡述 5
第二章、文獻回顧 6
2.1 啟發式解法回顧 6
2.1.1 起始解路線構建方法 6
2.1.2 鄰域搜尋法 7
2.2 分割配送相關車輛路線問題啟發式解法回顧 14
第三章、分割配送相關車輛路線問題數學定義與問題性質 23
3.1 分割配送相關車輛路線問題數學模式 23
3.1.1 分割配送車輛路線問題定義與數學規劃模式 23
3.1.2 具最小配送量限制之分割配送車輛路線問題定義與數學規劃模式 24
3.1.3 具配送次數限制之分割配送車輛路線問題定義與數學規劃模式 25
3.2 分割配送車輛路線相關問題整數解性質與潛在效益 26
3.2.1 分割配送車輛路線問題特性 26
3.2.2 具最小配送量限制之分割配送車輛路線問題特性 27
3.2.3 具配送次數限制之分割配送車輛路線問題特性 28
第四章、SRC+IMP多重起點啟發式演算法設計 30
4.1 SRC+IMP多重起點啟發式演算法整體架構說明 30
4.2 分割配送起始解構建模組設計 (SRC) 31
4.2.1 NIRA模組設計 33
4.3 鄰域改善模組設計與應用 (IMP) 35
4.3.1 IMP模組之變動鄰域策略：VND與RVND 36
4.3.2 傳統鄰域搜尋法(鄰域編號N1  N4) 37
4.3.3 分割配送節點驅逐鏈交換法SNEC (鄰域編號N5) 38
第五章、分割配送相關車輛路線問題標竿題庫與參數設定 43
5.1 標竿題庫說明 43
5.2 測試環境與參數設定 44
第六章、SRC+IMP於SDVRP測試結果與績效分析 46
6.1 SDVRP標竿題庫C求解績效分析 46
6.2 SDVRP標竿題庫B求解績效分析 48
6.3 SDVRP標竿題庫C與B綜合求解績效比較分析 50
第七章、SRC+IMP於SDVRP-MDA測試結果與績效分析 51
7.1 SDVRP-MDA標竿題庫G求解績效分析 51
7.2 SDVRP-MDA標竿題庫B求解績效分析 54
7.3 SDVRP-MDA標竿題庫G與B綜合求解績效比較分析 57
第八章、SRC+IMP於SDVRP-LND測試結果與績效分析 59
8.1 SDVRP-LND標竿例題之kmax參數設定與已知最佳解建立 59
8.2 SDVRP-LND標竿題庫B求解績效分析 59
第九章、綜合比較與探討 62
9.1 SRC多重起點起始解多樣性說明 62
9.2 有無SNEC鄰域搜尋法對求解之影響比較 64
9.3 SRC+VND與SRC+RVND求解績效比較 64
9.4 有無次數限制之分割配送車輛路線問題潛在效益之評估 66
第十章、結論與建議 67
參考文獻 69
附錄A SDVRP標竿例題SD16_144最佳結果 73
附錄B SDVRP-MDA標竿例題S76D4_75 (p = 0.2) 最佳結果 74
附錄C SDVRP-LND標竿例題S76D2_75 (kmax = 2) 最佳結果 75

1 7-Eleven. (2017). Takeout service order. from https://www.7-11.com.tw/service/takeout.asp
2 Ahuja, R., Magnanti, T. and Orlin, J. (1993). Network Flows: Theory, Algorithms, and Applications: Prentice Hall.
3 Aleman, R. E. and Hill, R. R. “A Tabu Search with Vocabulary Building Approach for the Vehicle Routing Problem with Split Demands.” International Journal of Metaheuristics, Vol. 1, No. 1, pp. 55-80, 2010.
4 Aleman, R. E., Zhang, X. and Hill, R. R. “An Adaptive Memory Algorithm for the Split Delivery Vehicle Routing problem.” Journal of Heuristics, Vol. 16, No. 3, pp. 441-473, 2010.
5 Archetti, C., Bianchessi, N. and Speranza, M. G. “Branch-and-cut Algorithms for the Split Delivery Vehicle Routing Problem.” European Journal of Operational Research, Vol. 238, No. 3, pp. 685-698, 2014.
6 Archetti, C., Bianchessi, N. and Speranza, M. G. “A Column Generation Approach for the Split Delivery Vehicle Routing Problem.” Networks, Vol. 58, No. 4, pp. 241-254, 2011.
7 Archetti, C., Mansini, R. and Speranza, M. G. “Complexity and Reducibility of the Skip Delivery Problem.” Transportation Science, Vol. 39, No. 2, pp. 182-187, 2005.
8 Archetti, C., Savelsbergh, M. W. P. and Speranza, M. G. “To Split or not to Split: That is the Question.” Transportation Research Part E: Logistics and Transportation Review, Vol. 44, No. 1, pp. 114-123, 2008.
9 Archetti, C., Savelsbergh, M. W. P. and Speranza, M. G. “Worst-Case Analysis for Split Delivery Vehicle Routing Problems.” Transportation Science, Vol. 40, No. 2, pp. 226-234, 2006.
10 Archetti, C. and Speranza, M. G. “Vehicle Routing Problems with Split Deliveries.” International Transactions in Operational Research, Vol. 19, No. 1-2, pp. 3-22, 2012.
11 Archetti, C., Speranza, M. G. and Hertz, A. “A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem.” Transportation Science, Vol. 40, No. 1, pp. 64-73, 2006.
12 Archetti, C., Speranza, M. G. and Savelsbergh, M. W. P. “An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem.” Transportation Science, Vol. 42, No. 1, pp. 22-31, 2008.
13 Belenguer, J. M., Martinez, M. C. and Mota, E. “A Lower Bound for the Split Delivery Vehicle Routing Problem.” Operations Research, Vol. 48, No. 5, pp. 801-810, 2000.
14 Berbotto, L., García, S. and Nogales, F. J. “A Randomized Granular Tabu Search Heuristic for the Split Delivery Vehicle Routing Problem.” Annals of Operations Research, Vol. 222, No. 1, pp. 153-173, 2014.
15 Boudia, M., Prins, C. and Reghioui, M. (2007). An Effective Memetic Algorithm with Population Management for the Split Delivery Vehicle Routing Problem. In T. Bartz-Beielstein, M. J. Blesa Aguilera, C. Blum, B. Naujoks, A. Roli, G. Rudolph, & M. Sampels (Eds.), Hybrid Metaheuristics: 4th International Workshop, HM 2007, Dortmund, Germany, October 8-9, 2007. Proceedings (pp. 16-30). Berlin, Heidelberg: Springer Berlin Heidelberg.
16 Bräysy, O., Hasle, G. and Dullaert, W. “A Multi-Start Local Search Algorithm for the Vehicle Routing Problem with Time Windows.” European Journal of Operational Research, Vol. 159, No. 3, pp. 586-605, 2004.
17 Chen, S., Golden, B. and Wasil, E. “The Split Delivery Vehicle Routing Problem: Applications, Algorithms, Test Problems, and Computational results.” Networks, Vol. 49, No. 4, pp. 318-329, 2007.
18 Clarke, G. and Wright, J. W. “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points.” Operations Research, Vol. 12, No. 4, pp. 568-581, 1964.
19 Cordeau, J.-F. and Laporte, G. (2005). Tabu Search Heuristics for the Vehicle Routing Problem. In R. Sharda, S. Voß, C. Rego, & B. Alidaee (Eds.), Metaheuristic Optimization via Memory and Evolution: Tabu Search and Scatter Search (pp. 145-163). Boston, MA: Springer US.
20 Croes, G. A. “A Method for Solving Traveling-Salesman Problems.” Operations Research, Vol. 6, No. 6, pp. 791-812, 1958.
21 Dantzig, G. B. and Ramser, J. H. “The Truck Dispatching Problem.” Management Science, Vol. 6, No. 1, pp. 80-91, 1959.
22 Derigs, U., Li, B. and Vogel, U. “Local Search-based Metaheuristics for the Split Delivery Vehicle Routing problem.” Journal of the Operational Research Society, Vol. 61, No. 9, pp. 1356-1364, 2010.
23 Dror, M. and Trudeau, P. “Savings by Split Delivery Routing.” Transportation Science, Vol. 23, No. 2, pp. 141-145, 1989.
24 Dror, M. and Trudeau, P. “Split Delivery Routing.” Naval Research Logistics, Vol. 37, No. 3, pp. 383-402, 1990.
25 Gendreau, M., Hertz, A. and Laporte, G. “New Insertion and Postoptimization Procedures for the Traveling Salesman Problem.” Operations Research, Vol. 40, No. 6, pp. 1086-1094, 1992.
26 Glover, F. (1992). New Ejection Chain and Alternating Path Methods for Traveling Salesman Problems. In O. Balci, R. Sharda, & S. A. Zenios (Eds.), Computer Science and Operations Research (pp. 491-509). Amsterdam: Pergamon.
27 Groër, C., Golden, B. and Wasil, E. “A Parallel Algorithm for the Vehicle Routing Problem.” INFORMS Journal on Computing, Vol. 23, No. 2, pp. 315-330, 2011.
28 Gulczynski, D. (2010). Integer Programming-Based Heuristics for Vehicle Routing Problems. (Ph.D.), University of Maryland.
29 Gulczynski, D., Golden, B. and Wasil, E. “The Split Delivery Vehicle Routing Problem with Minimum Delivery Amounts.” Transportation Research Part E: Logistics and Transportation Review, Vol. 46, No. 5, pp. 612-626, 2010.
30 Han, A. F.-W. and Chu, Y.-C. “A Multi-start Heuristic Approach for the Split-delivery Vehicle Routing Problem with Minimum Delivery Amounts.” Transportation Research Part E: Logistics and Transportation Review, Vol. 88, No., pp. 11-31, 2016.
31 Ho, S. C. and Haugland, D. “A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows and Split Deliveries.” Computers & Operations Research, Vol. 31, No. 12, pp. 1947-1964, 2004.
32 Jin, M., Liu, K. and Bowden, R. O. “A Two-stage Algorithm with Valid Inequalities for the Split Delivery Vehicle Routing Problem.” International Journal of Production Economics, Vol. 105, No. 1, pp. 228-242, 2007.
33 Jin, M., Liu, K. and Eksioglu, B. “A Column Generation Approach for the Split Delivery Vehicle Routing Problem.” Operations Research Letters, Vol. 36, No. 2, pp. 265-270, 2008.
34 López-Sánchez, A. D., Hernández-Díaz, A. G., Vigo, D., Caballero, R. and Molina, J. “A Multi-Start Algorithm for a Balanced Real-World Open Vehicle Routing Problem.” European Journal of Operational Research, Vol. 238, No. 1, pp. 104-113, 2014.
35 Lin, S. “Computer Solutions of the Traveling Salesman Problem.” Bell System Technical Journal, Vol. 44, No. 10, pp. 2245-2269, 1965.
36 Lin, S. and Kernighan, B. W. “An Effective Heuristic Algorithm for the Traveling-Salesman Problem.” Operations Research, Vol. 21, No. 2, pp. 498-516, 1973.
37 Mladenović, N. and Hansen, P. “Variable Neighborhood Search.” Computers & Operations Research, Vol. 24, No. 11, pp. 1097-1100, 1997.
38 Mota, E., Campos, V. and Corberán, Á. (2007). A New Metaheuristic for the Vehicle Routing Problem with Split Demands. In C. Cotta & J. van Hemert (Eds.), Evolutionary Computation in Combinatorial Optimization: 7th European Conference, EvoCOP 2007, Valencia, Spain, April 11-13, 2007. Proceedings (pp. 121-129). Berlin, Heidelberg: Springer Berlin Heidelberg.
39 Or, I. (1976). Traveling Salesman-type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking. (Ph.D. Dissertation), Northwestern University.
40 Osman, I. H. “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem.” Annals of Operations Research, Vol. 41, No. 4, pp. 421-451, 1993.
41 Potvin, J.-Y. and Rousseau, J.-M. “An Exchange Heuristic for Routeing Problems with Time Windows.” The Journal of the Operational Research Society, Vol. 46, No. 12, pp. 1433-1446, 1995.
42 Rego, C. “Node-ejection Chains for the Vehicle Routing Problem: Sequential and Parallel Algorithms.” Parallel Computing, Vol. 27, No. 3, pp. 201-222, 2001.
43 Rosenkrantz, D. J., Stearns, R. E. and Lewis, P. M. (1974, 14-16 Oct. 1974). Approximate Algorithms for the Traveling Salesperson Problem. Paper presented at the 15th Annual Symposium on Switching and Automata Theory (swat 1974).
44 Silva, M. M., Subramanian, A. and Ochi, L. S. “An Iterated Local Search Heuristic for the Split Delivery Vehicle Routing Problem.” Computers & Operations Research, Vol. 53, No., pp. 234-249, 2015.
45 Solomon, M. M. “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints.” Operations Research, Vol. 35, No. 2, pp. 254-265, 1987.
46 Subramanian, A., Drummond, L. M. A., Bentes, C., Ochi, L. S. and Farias, R. “A Parallel Heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery.” Computers & Operations Research, Vol. 37, No. 11, pp. 1899-1911, 2010.
47 Tesco. (2017). Delivery Options. from http://www.tesco.com/groceries/zones/default.aspx?name=delivery-options
48 Xiong, Y., Gulczynski, D., Kleitman, D., Golden, B. and Wasil, E. “A Worst-case Analysis for the Split Delivery Vehicle Routing Problem with Minimum Delivery Amounts.” Optimization Letters, Vol. 7, No. 7, pp. 1597-1609, 2013.
49 Yellow, P. C. “A Computational Modification to the Savings Method of Vehicle Scheduling.” Operational Research Quarterly, Vol. 21, No. 2, pp. 281-283, 1970.