臺灣博碩士論文加值系統

本文以台灣飼料產業為例，探討如何設計規劃一套符合公司政策規範，滿足客戶需求、司機運送意願以及硬體環境限制，且降低整體運送成本的電腦化派車與路線規劃系統。
運用系統分析與設計的方法及工具，本研究從下列構面著手進行系統規劃與設計：(1) 公司政策的檢討與擬定：配合新的規劃技術與理念的引進，對公司原有的政策進行有系統的檢討與重擬。(2) 資料的搜集：滿足司機意願與客戶需求是系統規劃的兩項重要目標。本研究透過個別訪談、問卷調查、統計方法與資料探勘等技術，擷取司機意願與客戶需求。(3) 運輸網路資料的建置：有別於以往以距離為考量，本研究採用行車時間進行規劃，運用電子地圖、衛星定位與迴歸分析等工具及技術建置運輸網路資料。(4) 核心問題的求解：本研究運用初始解的概念，搭配一個新的先分群再定路線啟發式解法與隨機搜尋機制，求解核心的多桶格車輛途程問題。(5) 系統的連結與測試：設計本系統與公司內相關系統的連結介面，並進行測試分析。

Aiming at a goal of using technology to create intellectual operation system, of which not only satisfies the customer insight, but also soothes the truck drivers’ petition by conquering the limitation of hardware and without conflicting with company’s policy, we are making a project by constructing a vehicle routes planning system to provide a workable and efficient program for one animal feed plant solving the long-ago troublesome problem of transportation distribution. In addition, there are two more achievements of timing and expenses saving as well.
In the paper, we will explore the real problems and work out the solutions during constructing such a system based on the following issues: (1) what is the company’s purpose：bringing in a brand-new concept to redraft and improve the previous system; (2) who is the target：to satisfy the requirements of truck drivers and customers with the new system, based on the relative digital information collected and analyzed through data mining and interview etc; (3) how to run the mechanism：using the measure method of car speed, instead of the distance as it used to be, and the tools of electronic map, GPS and Regression Analysis, to build the database of transportation network; (4) which problem should be solved: to work out a solution for the core problem of vehicle routing distribution by re-dividing category, heuristic solutions and random mechanism proposed a cluster-first route-second procedure for the multi-compartment vehicle routing problem; and (5) where to run the process: connecting the interface between the company’s internal related systems and the new one, to execute the further test and analysis.

摘要 iv
致謝 vi
目次 viii
圖目錄 x
表目錄 xi
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機與目的 1
1.3 研究範圍 2
1.4 研究架構與步驟 3
1.5 研究方法 6
1.6 章節簡介 7
第二章 系統分析與設計 8
2.1 瞭解問題與擷取需求 9
2.2 派車作業的需求與限制條件 12
2.3 人工派車產生的問題 15
2.4 系統功能之設計 16
2.5 資料庫的設計 21
2.6 系統軟硬體之需求 29
2.7 系統架構 30
第三章 運輸網路資料的建置 31
3.1 場站與客戶所在位置的定位 31
3.2 進行行車時間的抽樣 33
3.3 找出樣本中各地點間的路況 36
3.4 建立行車時間與距離間的迴歸模式 37
3.5 建立運輸網路圖 40
3.6 計算各地點間行車時間 41
第四章 核心問題求解 44
4.1 車輛途程問題的文獻回顧 44
4.2 問題建模 45
4.3 啟發式解法 47
4.3.1 數值範例 52
4.4 初始解 60
第五章 系統測試與政策配套 65
5.1 系統連結與測試 65
5.2 公司政策的檢討與擬定 67
第六章 結論與後續研究建議 70
參考文獻 73
附錄 76
附錄A 司機問卷調查表 76

中文部分：
1.行政院農業委員會 (2006)，94年臺灣地區配合飼料產量調查報告，中華民國行政院農業委員會。
2.台北市飼料及動物用藥商業同業公會 (2005)，飼料管理手冊，修訂本九，台北市飼料及動物用藥商業同業公會。
3.吳仁和、林信惠 (2004)，系統分析與設計：理論與實務應用，第三版，智勝文化事業有限公司。
4.吳亮瑩 (1999)，單一物流中心配送車輛途程問題之研究--以遺傳演算法求解，碩士論文，國立成功大學，工業管理研究所。
5.簡世釗 (2001)，時窗與容量限制下車輛途程問題之研究，碩士論文，國立成功大學，工業管理研究所。
6.陳建甫 (2006)，以基因搜尋法求解多桶格車輛途程問題，碩士論文，南台科技大學，工業管理研究所。
英文部分：
1.Ahuja, R.K., T.L. Magnanti and J.B. Orlin (1993), Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Englewood Cliffs, New Jersey.
2.Ball, M.O., T.L. Magnanti, C.L. Monma, and G.L. Nemhauser (eds.)(1995), Handbooks in Operations Research and Management Science, Volume 8: Network Routing, Elsevier Science, Amsterdam.
3.Bramel, J. and D. Simichi-Levi (2002), Set-covering-based algorithms for the capacitated VRP, in: P. Toth and D. Vigo (eds.), The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, Philadelphia, 85−108.
4.Christofides, N. (1976), Worst case analysis of a new heuristic for the travelling salesman problem, Research Report, Carnegie-Mellon University, Pittsburgh.
5.Christofides, N. (1985), Vehicle routing, in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D. Shmoys (eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, Chichester, 431‐448.
6.Desrochers, M., J.K. Lenstra, and M. Savelsberg (1990), A classification scheme for vehicle routing and scheduling problems, Journal of the Operational Research Society 46, 322−332.
7.Garey, M.R. and D.S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco.
8.Gendreau, M., G. Larporte, J.-Y. Potvin (2002), Metaheuristics for the capacitated VRP, in: P. Toth and D. Vigo (eds.), The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, Philadelphia, PA, 129−154.
9.Golden, B.L. and A.A. Assad (eds.) (1988), Vehicle Routing: Methods and Studies, Elsevier Science Publisher B.V., North-Holland.
10.Han, J. and M. Kamber (2001), Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers, San Francisco.
11.Kaplan, R.S. and D.P. Norton (1996), The balanced scorecard: Translating Strategy into Action, Harvard Business School Press, Boston Mass.
12.Laporte, G. (1992), The vehicle routing problem: An overview of exact and approximate algorithms, European Journal of Operational Research 59 (3), 345−358.
13.Laporte, G. (1997), Vehicle routing, in: M. Dell’Amico, F. Maffioli, and S. Martello (eds.), Annotated Bibliographies in Combinatorial Optimization, Wiley, Chichester, UK.
14.Laporte, G. and Y. Nobert (1987), Exact algorithms for the vehicle routing problem, in: S. Martello, G. Laporte, M. Minoux, and C. Ribeiro (eds.), Surveys in Combinatorial Optimization (as Annals of Discrete Mathematics 31), North-Holland, Amsterdam, 147−184.
15.Laporte, G. and I.H. Osman (1995), Routing problems: A bibliography, Annals of Operations Research 61, 227−262.
16.Laporte, G. and F. Semet (2002), Classical heuristics for the capacitated VRP, in: P. Toth and D. Vigo (eds.), The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, Philadelphia, PA, 109−128.
17.Lin, K.-C., C.-F. Chen, and C.-C. Tsai (2006), A hybrid genetic algorithm for the multi-compartments vehicle routing problem, Working paper, Department of Management and Information Technology, Southern Taiwan University of Technology, Taiwan.
18.Montgomery, D.C., E.A. Peck, and G.G. Vining (2001), Introduction to Linear Regression Analysis, Third edition, John Wiley & Sons, New York.
19.Naddef, D. and G. Rinaldi (2002), Branch-and-cut algorithms for the capacitated VRP, in: P. Toth and D. Vigo (eds.), The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, Philadelphia, 53−84.
20.Papadimitriou, C.H. and K. Steiglitz (1976), Some complexity results for the Traveling Salesman Problem, Proceedings of the eighth annual ACM symposium on theory of computing (STOC’76), 1-9.
21.Prim, R.C. (1957), Shortest connection networks and some generalizations, Bell System Technical Journal 36, 1389-1401.
22.Reinelt, G. (1994), The Traveling Salesman: Computational Solutions for TSP Applications, Springer-Verlag, Berlin.
23.Toth, P. and D. Vigo (2002a), Models, relaxations and exact approaches for the capacitated vehicle routing problem, Discrete Applied Mathematics 123, 487-512.
24.Toth, P. and D. Vigo (eds.) (2002b), The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, Philadelphia, PA.
25.Whitten, J.L., L.D. Bentley, and K.C. Dittman (2004), Fundamentals of Systems Analysis and Design Methods, McGraw-Hill, Boston.