臺灣博碩士論文加值系統

國際快遞業首重遞送物品的「時效性」，對快遞業者而言，延後截件時間及提早送達的服務承諾，即是時效性的表現，而只有高效率的取件作業，才能實現這樣的服務承諾；取件作業效率與運務員取件路線安排和個人責任區劃分息息相關；由於顧客需求的產生具隨機性，這使得本研究課題比傳統的旅行銷售員問題更為複雜。
本研究係探討當顧客需求呈隨機分佈時，如何事先規劃一最適的取件路線，使運務員在面臨不同需求分佈時，仍依照事先規劃的路線，進行取件服務，唯不經過沒有需求的顧客點，藉由此方式使運務員均能在規定時間內完成取件作業，以維持良好的取件服務水準，滿足快遞業追求時效服務的目標。
本研究的目的即是針對具旅行總時間限制之運務員隨機取件路線規劃問題(Probabilistic traveling salesman problem with route duration restrictions)，提出明確的定義，並建構適合的研究模式，同時利用基因演算法進行實例求解。
研究結果指出本研究所建構的問題模式「PTSP-DC」有別於傳統的PTSP模式，其設計概念更符合國際快遞業追求時效性的目標；根據個案公司實際資料的求解結果顯示，利用「PTSP-DC」模式設計得出的服務路線，的確比傳統PTSP求出的路線解，更有助於提昇運務員取件的效率。

For international express service industry, it is very import to delivery good efficiently. The efficiency of pick-up service is mainly influenced by the courier service route design and duty area partition. The presence of uncertain customer demand creates the need to design a priori tour instead of finding optimal tour everyday.
This thesis focuses on route design for courier service. The objective is to minimize the probability of that the total tour duration exceeds the given duration constraints, with the strategy of service a random subset of customers in the same order as they appear in the a priori tour.
This thesis clarifies the meanings of “Probabilistic Traveling Salesman Problem with Route Duration Restrictions (PTSP-DC)”and develops a mathematical model, as well as computationally feasible methods for obtains solutions in realistic situations. In a series of test problem, we solve this problem by Genetic Algorithms to produce a good approximate solution in a short time.
In the case study, we find that the solution of PTSP-DC is not only better than the solution of PTSP but also the solution of TSP, in terms of the probability of that the total tour duration exceeds the given duration constraints.

摘 要 i
Abstract ii
誌 謝 iv
目 錄 v
圖目錄 vii
表目錄 viii
壹、緒論 1
1.1研究背景與動機 1
1.2研究目的 3
1.3研究範圍 4
1.4研究架構與流程 4
貳、文獻回顧 6
2.1國際快遞服務業概述 6
2.1.1主要廠商簡介 7
2.1.2國際快遞相關研究 8
2.2旅行銷售員問題(TRAVELING SALESMAN PROBLEM，TSP) 9
2.2.1 TSP之定義與數學模式 9
2.2.2 TSP求解相關研究 11
2.3隨機旅行銷售員問題(PROBABILISTIC TRAVELING SALESMAN PROBLEM，PTSP) 13
2.3.1 PTSP之定義與數學模式 13
2.3.2 PTSP求解相關研究 14
參、問題描述與模式建構 16
3.1問題描述 16
3.2建構本研究模式—PTSP-DC 17
3.2.1目標函數之建立 17
3.2.2 PTSP-DC之數學模式 18
3.3驗證PTSP-DC模式 18
3.4 測試範例 21
3.5小結 23
肆、PTSP-DC模式求解設計 24
4.1基因演算法(GENETIC ALGORITHMS，GA) 24
4.2基因演算法則原理 25
4.3顧客需求分佈模擬 27
4.4基因演算法求解PTSP-DC之操作 30
4.4.1問題對照 30
4.4.2演算設計 30
4.5範例演算說明 33
4.5.1演算程序 34
4.5.2演算結果與分析 39
4.6小結 40
伍、個案公司實例求解 41
5.1實例資料 41
5.2求解說明 43
5.2.3參數設定 43
5.2.2演算過程 44
5.4求解結果與分析 45
陸、結論與未來研究方向 48
6.1研究結論 48
6.2建議與未來研究方向 48
中文文獻 50
英文文獻 50
錄 附 53

中文文獻
1. 林正章(1999)。貨物運輸網路研究之回顧與展望。運輸網路分析。五南圖書出版公司，2，35-65。
2. 邱佩諄(1991)。快遞運務員動態調派模擬分析。國立交通大學交通運輸研究所碩士論文。
3. 徐為元(2000)。複合式自我學習之基因演算法應用於旅行推銷員問題。國立台灣大學資訊工程學研究所碩士論文。
4. 趙庭賢(2002)。快遞業之複數型限時收件路徑規劃。東吳大學商用數學系碩士論文。
5. 韓復華、卓裕仁(1999)。網路節點服務TSP與VRP問題回顧。運輸網路分析。五南圖書出版公司。8，201-223。
6. 韓復華、張靖、卓裕仁(1996)。車輛路線問題研究：SA、TANMSSS與交換型啟發式方法之綜合應用分析。運輸學刊，9(3)，103-129。
7. 韓復華、楊智凱 (1996)。門檻接受法在TSP問題上之應用。運輸計劃季刊。25(2)，163-188。
英文文獻
1. Bellmore, M., and Nemhauser, G.L. (1968), The Traveling Salesman Problem: A Survey, Operations Research, 16(3), 538-558.
2. Bertsimas, D.J., Jaillet, P. and Odoni, A.R. (1990), A Priori Optimization, Operations Research, 38(6), 1019-1033.
3. Bianchi, L., Gambardella, L. M. and Dorigo, M. (2002), Solving the Homogeneous Probabilistic Traveling Salesman Problem by the ACO Metaheuristic, Ant Colonies to Artificial Ants: Third International Workshop on Ant Algorithms, volume 2463 of Lecture Notes in Computer Science, 176-187.
4. Bodin, L., Golden, B., Assad, A. and Ball M. (1983), Routing and Scheduling of Vehicle and Crews. The state of the art, Computers and Operations Research, 10(2), 63-211.
5. Clarke, G. and Wright, J. W. (1964), Scheduling of Vehicles from A Central Depot to A Number of Delivery Points, Operations Research, 12(4), 568-581.
6. Dantzig, G.B., Fulkerson, D.R. and Johnson S.M. (1954), Solution of a large-scale Traveling Salesman problem, Operations Research, 2(4), 393-410.
7. Flood, M. (1956), The Traveling Salesman Problem, Operations Research, 4, 61-75.
8. Gendreau, M., Laporte G. and Seguin, R. (1996), Invited Review: Stochastic Vehicle Routing, European Journal of Operational Research, 88, 3-12.
9. Goldberg D. E., (1989), Genetic Algorithms in Search, Optimization and Machine Learning, Reading, Mass Addison-Wesley Pub.
10. Grefenststte, J.J., (1986), Optimiztion of Control Parameters for Genetic Algorithms, IEEE Transactions. System, Man, and Cybernetic, 16(1), 122-128.
11. Jaillet, P. (1985), Probabilistic Traveling Salesman Problems, Technical Report, 185, Operations Research Center, MIT, Cambridge, Mass.
12. Jaillet, P. (1988), A Priori Solution of a Traveling Salesman Problem in which a Random Subset of The Customers Are Visited, Operations Research, 36(6), 929-936.

13. Karp, R. (1972), Reducibility among Combinatorial Problems, Complexity of Computer Computations, Plenum Press, 85-104.
14. Michalewicz, (1996) Genetic Algorithms + Data Structures = Evolution Programs, Third, Revised and Extended Edition, Springer.
15. Laporte, G., Louveaux, F.V. and Mercure, H. (1994), A Priori Optimization of the Probabilistic Travelilng Salesman Problem, Operations Research, 42(3), 543-549.
16. Powell, W., Jaillet, P. and Odoni, A. (1995), Stochastic and Dynamic Networks and Routing, Chapter 3 in Ball, M. Magnanti, T. Monma, C. and Nemhauser, G. (eds.) Network Routing, Handbooks in Operations Research and Management Science 8, 141-295.
17. Rosenkrantz, D.J., Streans, R.E. and Lewis, P. N. (1977), An analysis of Several Heuristics for the Traveling Salesman Problem, SLAM Journal on Computing, 6, 563-581.