臺灣博碩士論文加值系統

近年來，由於物流產業需求持續增加，物流作業扮演的角色越來越重要。而配送成本在物流業中所佔成本比例甚高，因此良好的路徑規劃，可以有效地降低物流運輸成本。在需求點只能拜訪一次的限制下，同時收送貨可以避免不必要的時間與成本浪費。因此本研究之目的是透過2-Opt區域搜尋法 (Local Search) 與和弦搜尋演算法 (Harmony Search, HS) 的結合，發展一套適於求解具同時收送貨之旅行推銷員問題 (Traveling Salesman Problem with Pickup and Delivery, TSPPD) 之演算法，以達到最小總配送距離的目標。本研究根據隨機產生初始解與節省法產生初始解兩種方法，順序式編碼與節點式編碼兩種編碼方式組成四種不同的HS方法，透過參數分析及標準例題測試，分析比較四種方法的求解績效優劣，並使用Minitab分析不同的初始建構解及編碼方式彼此的統計顯著性。結果發現，不同的編碼方式對於求解TSPPD有顯著性差異。此外，與文獻所提出的 TS2、UB2 進行比較 (300 測試題)，發現使用節省法產生初始解與節點式編碼在求解 TSPPD 時明顯優於文獻所提出之方法。因此，本研究所提出的HS能迅速且穩定求得較佳的解。

Nowadays, as the increasing demand in the logistics industry, logistics operations play an important role in the logistics system. Distribution cost accounts for the large percentage of total cost in logistics activities. Hence, a well designed path planning can reduce the transportation cost. Under the limit of just visiting once for demand points, the pickup and delivery simultaneously can avoid unnecessary waste of time and cost. This study aims to combine the Harmony Search (HS) and the 2-Opt local search (2-Opt LS) to solve the Traveling Salesman Problem with Pickup and Delivery (TSPPD) problem with the objective of minimum transportation distance. Based on the tour construction (Random Generation and Savings Method) methods and encoding of solution (Order-based Encoding and Node-based Encoding), our HS can be divided into four categories and then tested their computational performances by the statistical software MINITAB. The results showed that the Node-based Encoding is better than the Order-based Encoding significantly. The computational performance of the proposed HS is tested on 300 benchmark test problems that were obtained from the literature. The computational results showed that the Savings Method with Node-based Encoding outperformed the other two competing heuristics, (i.e., TS2 and UB2), which were proposed in the literature. Hence, the proposed heuristics can provide a fast and stable, and better solution on the TSPPD problem.

中文摘要 i
ABSTRACT ii
誌謝 iv
目錄 v
圖目錄 vii
表目錄 ix
第一章　緒論 1
1.1　研究動機與背景 1
1.2　研究目的 2
1.3　研究範圍及假設 3
1.4　研究流程 4
第二章　文獻回顧 6
2.1　物流相關概念 6
2.1.1　物流之定義 6
2.1.2　物流中心 7
2.2　旅行推銷員問題相關文獻回顧 8
2.2.1　旅行推銷員問題 8
2.2.2　同時收送貨之途程問題 9
2.2.3　具收送貨之旅行推銷員問題 11
2.3　旅行推銷員問題之求解方法 13
2.3.1　傳統啟發式解法 13
2.3.2　巨集啟發式解法 20
2.4　和弦搜尋演算法 21
2.4.1　和弦搜尋法發展背景與原理 22
2.4.2　和弦搜尋法步驟與流程 23
2.4.3　和弦搜尋法之相關應用 26
第三章　模式建立與求解流程 28
3.1　問題描述與定義 28
3.2　和弦搜尋演算法之設計 31
3.2.1　初始解之建構方法 33
3.2.2　和弦搜尋演算法之編碼 37
3.2.3　和弦搜尋演算法之產生新解 38
3.2.4　區域搜尋法 43
第四章　實驗結果與分析 47
4.1　測試例題說明 47
4.2　程式介面說明 48
4.3　實驗設計 51
4.4　各方法之分析比較 67
4.4.1　初始解機制比較 70
4.3.2　編碼機制比較 73
4.4.3　迭代數分析 77
4.5　標準例題測試 80
4.6　小結 85
第五章　結論與未來研究方向 86
5.1　結論 86
5.2　未來研究方向 87
參考文獻 88
附錄　測試例題之詳細結果 93

朱經武、周偉禮，「以啟發式演算法求解單一場站多車種同時收送貨之車輛途程問題」，航運季刊，pp. 63-88, 2006。
李宗儒、林正章、周宣光，「當代物流管理-理論與實務」，滄海書局，2002。
邱仕銘，「同時收送貨車輛配送問題之研究」，長榮大學經營管理研究所碩士論文，2006。
洪振創、湯玲郎，「物料管理」，高立圖書有限公司，2003。
高世昌，「考量同時送貨及收貨之多場站車輛途程問題」，逢甲大學工業工程學所碩士論文，2001。
陳冠樺，「螞蟻記憶系統應用於旅行銷售員問題」，逢甲大學交通工程與管理學系碩士班碩士論文，2005。
陳建緯，「大規模旅行銷售員問題之研究：區域搜尋法與巨集啟發式解法之應用」，交通大學運輸工程與管理學系碩士班碩士論文，2001。
莊英群，「應用禁忌搜尋法於混合收送貨之車輛途程問題」，逢甲大學工業工程學所碩士論文，2002。
曹餘偉，「應用禁忌搜尋法求解多車種多物流中心之區位途程問題」，元智大學工業工程研究所，碩士論文，2006。
敖君瑋，「禁制搜尋法於軟性時窗限制之車輛途程問題研究」，元智大學工業工程研究所，碩士論文，1999。
許晉嘉，「宅配業貨物配送路線規畫問題之研究」，成功大學交通管理科學學系碩士班碩士論文，2003。
張有恆，「現代物流管理」，華泰文化事業股份有限公司，2005。
張福榮，「物流經營管理」，五南出版，2000。
彭冠儒，「考量同時送貨及收貨之車輛途程問題」，逢甲大學工業工程學所碩士論文，2001。
鄭雁嬬，「混合式演算法應用於同時收送貨之車輛途程問題」，元智大學工業工程學研究所碩士論文，2009。
劉向邦，「以和弦搜尋演算法為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究」，中央大學土木工程學系碩士論文，2008。
羅冠君，「基於和聲搜尋演算法與離散拉格朗日法之混合演算法於結構最佳化設計的研究」，中央大學土木工程研究所碩士論文，2008。
羅敏華，「蟻群最佳化演算法於載重限制之車輛途程問題的研究」，元智大學工業工程研究所，碩士論文，2002。
Alshamrani, A., Mathur, K., and Ballou, R. H., “Reverse logistics :simultaneous design of delivery routes and return strategies,” Computers & Operations Research, Vol. 34, No. 3, pp. 595-619, 2007.
Althofer, I. and Koschnick, K. U., “On the Convergence of Threshold Accepting,” Applied Mathematics and Optimization, Vol. 24, No. 1, pp. 183-195, 1991.
Anily, S. and Mosheiov, G., “The Traveling Salesman Problem with Delivery and Backhauls,” Operations Research Letters, Vol. 16, No. 1, pp. 11-18, 1994.
Baldacci, R., Hadjiconstantinou, E. and Mingozzi, A., “An Exact Algorithm for the Traveling Salesman Problem with Deliveries and Collections,” Networks, Vol. 42, No. 1, pp. 26-41, 2003.
Bodin, L. D., Golden, B. L., Assad, A. A. and Ball, M. O., “Routing and Scheduling of Vehicles and Crews. The State of the Art,” Computers & Operations Research, Vol. 10, No. 2, pp. 63-211, 1983.
Casco, D.O., Golden, B.L. and Wasil, E.A., “Vehicle Routing with Backhauls: models, algorithms, and case studies. In: Golden, L. and Assad, A. (eds),” Vehicle Routing: Methods and Studies, North-Holland, Amsterdam, pp.127-147, 1988.

Çinar, V., Öncan, T. and Süral, H., “A Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery Using Depot Removal and Insertion Moves,”Lecture Notes in Computer Science, Vol. 6025, pp. 431-440, 2010.
Clarke, G. and Wright, W., “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, No. 4, pp. 568-581, 1964.
Garey, M. R. and Johnson D.S., Computers and Intractability. “A Guide to the Theory of NP Completeness,” W. H. Freeman & Co., Mew York, 1979.
Geem, Z. W., Kim J. H. and Loganathan, G.V., “A New Heuristic Optimization Algorithm: Harmony Search,” Simulation, Vol. 76, No. 2, pp. 60-68, 2001.
Geem, Z. W., Lee, K. S. and Park, Y. “Application of Harmony Search to Vehicle Routing,” American Journal of Applied Sciences, Vol. 2, pp. 1552-1557, 2005.
Gendreau, M., Laporte, G. and Vigo D., “Heuristics for the Traveling Salesman Problem with Pickup and Delivery,” Computers & Operations Research, Vol. 26, No. 7, pp. 699-714, 1999.
Gillett, B. E. and. Miller, L. R., “A Heuristic Algorithm for the Vehicle-Dispatch Problem,” Operations Research, Vol. 22, No. 2, pp. 340-349, 1974.
Golden, B., Assad, A., Levy, L. and Gheyaens, F., “The Fleet Size and Mix Vehicle Routing Problem,” Computers & Operations Research, Vol. 11, No. 1, pp. 49-66, 1984.
Gribkovskaia, I., Laporte, G. and Shyshou, A., “The Single Vehicle Routing Problem with Deliveries and Selective Pickups,” Computers & Operations Research, Vol. 35, No. 9, pp. 2908-2924, 2008.
Halse, K., “Modeling and Solving Complex Vehicle Routing Problems.,” Ph.D. Dissertation, no.60, IMSOR, The Technical University of Denmark. 1992.
Held, M. and Karp, R. M., “A Dynamic Programming Approach to Sequencing Problems,” Journal of Society Industrial and Applied Mathematics, Vol. 10, pp. 196-210, 1962.
Hernández-Pérez H. and Salazar-González J. J., “Heuristics for the One-commodity Pickup-and-Delivery Traveling Salesman Problem.,” Transportation Science, Vol. 38, No. 2, pp. 245-255, 2004.
Hernández-Pérez H. and Salazar-González J. J. “The One-commodity Pickup-and-Delivery Traveling Salesman Problem: Inequalities and Algorithms.,” Networks, Vol. 50, No. 4, pp. 258-272, 2007.
Hoff, A. et.al., “Lasso Solution Strategies for the Vehicle Routing Problem with Pickups and Deliveries,” Computer & Operations Research , Vol. 192, No. 3, pp. 755-766, 2009.
Lin, S., “Computer Solutions of the Traveling Salesman Problem,” Bell System Tech. J, Vol. 44, pp. 245-2269, 1965.
Min, H., “The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-up points,” Transportaion Research. Part A, Vol. 23, No. 5, pp. 377-386, 1989.
Mole, R. and Jameson, S., “A Sequential Route-Building Algorithm Employing A Generalized Savings Criterion,” Operational Research Quarterly, Vol. 27, No. 2, pp. 503-511, 1976.
Mosheiov, G., “The Traveling Salesman Problem with Pickup and Delivery,” European Journal of Operational Research, Vol. 79, pp. 299-310, 1994.
Omran, M.G.H. and Mahdavi, M., “Global-best Harmony Search.,” Applied Mathematics and Computation, Vol. 198, No. 2, pp. 643–656, 2008.
Or. I., “Traveling Salesman-type Combinatorial Problems and Their Realation on the Logistics of Regional Blood Banking,” Ph.D. Dissertation, Northwestern University, 1976.
Parragh, S.N., Doerner, K.F., and Hartl, R.F.,” A Survey on Pickup and Delivery Problems. I.” Transportation between customers and depot, J Betriebswirtschaft, Vol. 58, No. 1, pp. 21–51, 2008.

Parragh, S.N., Doerner, K.F. and Hartl, R.F., “A Survey on Pickup and Delivery Problems. II.” Transportation between pickup and delivery locations, J Betriebswirtschaft, Vol. 58, No. 2, pp. 81–117, 2008.
Salhi, S. and Nagy, G., “A Cluster Insertion Heuristic for Single and Multiple depot Vehicle Routing Problems with Backhauling.” Journal of the Operational Research Society, Vol. 50, No. 10, pp. 1034-1042, 1999.
Schruben, L. W. and Clifton, R. E., “The Lockset Method of Sequential Programming Applied to Routing Delivery and Pickup Trucks,” American Journal of Agricultural Economics, Vol. 50, No. 4, pp. 854-867, 1968.
Thompson, P. M., Psaraftis, H., “Cyclic Transfer Algorithms for Multi-Vehicle Routing and Scheduling Problems,” Operations Research, Vol. 41, pp. 935-946, 1993.
Wren, A., “Computers in Transport Planning and Operation,” Ian Allan, London, 1971.
Wren, A., Holiday, A., “Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points,” Operational Research Quarterly, Vol. 23, No. 3, pp. 333-344, 1972.
Whitney, H., “Analytic Extensions of Function Defined in Closed Sets,” Transactions of the American Mathmatical Society, Vol. 36, pp. 63-89, 1934.
Zhao F.-G., Sun J.-S., Li S.-J., Lin W.-M.,“A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery,” International Journal of Automation and Computing, Vol. 6, No. 1, pp. 97-102, 2009.