跳到主要內容

臺灣博碩士論文加值系統

(100.28.227.63) 您好!臺灣時間:2024/06/16 21:41
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林政宏
研究生(外文):Cheng Hung Lin
論文名稱:智慧型手機上多點實際道路路徑規劃
論文名稱(外文):Practical Route Planning for Multiple Destinations on the Smartphones
指導教授:詹景裕詹景裕引用關係
指導教授(外文):Gene Eu Jan
口試委員:詹景裕紀新洲高明達呂紹偉何善輝
口試委員(外文):Gene Eu JanHsin-Chou ChiMing-Tat KoShao-Wei LeuShan Hui Ho
口試日期:2013-07-25
學位類別:碩士
校院名稱:國立臺北大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:中文
論文頁數:25
中文關鍵詞:旅行銷售員問題TSP多點實際路徑規劃智慧型手機
外文關鍵詞:Android,Traveling Salesman Problemuniversal model for route planningDijkstra algorithm
相關次數:
  • 被引用被引用:3
  • 點閱點閱:251
  • 評分評分:
  • 下載下載:4
  • 收藏至我的研究室書目清單書目收藏:0
這幾年來,電子商務業蓬勃發展,造成了新興的購物模式-配送服務。消費行為轉移,市場需求擴大,為了減少運輸成本的開銷,必須規劃出良好的運輸路線。在本文中主要的對象則是宅配業者的配送運輸網路,而目前的業者大多是採取經驗法則去規劃各自的配送路線,但所需考量交通因素過多,很容易規劃出運輸成本較高的路徑,因此僅僅只是依靠經驗法則是不夠的。研究相關領域的文章之後,我們可以歸納出以下的問題:(1) 大部分送貨員都以自我經驗為基準去規劃路徑,但由於營業據點的急速擴散,時常需要更動配送路線,因此僅僅依靠經驗法則是不夠的;(2) 在實際的道路情況底下,影響耗油及速度的因素不單只是距離大小,還有轉彎成本、路燈波、迴轉道等因素;(3) 若在不對的時間點經過繁雜壅塞的區域,便會增加其運輸成本;(4) 抵達須配送的目的地時,還須考量去卸貨時間成本;(5) 隨時隨地將導航裝置安置於任何車體上的便利性。這些問題對於配送規劃是皆是重要因素。本文以各種道路通用模組為基礎,以完善的單點路徑規劃作為參考依據,擴展至多點路徑規劃。本文以宅配業者作為服務的對象,去改善傳統以經驗法則為主的配送路線規劃,透過整體的規劃後,就可大大的減少運輸成本。甚至更進一步加入分時分區的概念,便可以解決在上下班潮避開壅塞區的問題。
As the e-business becomes very popular in the world, the rise of the home- delivery commerce has changed the business model of transportation industry since the traditional transportation service can’t meet demand of modern life. The logistics planning on the smartphones is presented in this article based on the concept of Traveling Salesman Problem and our recent works regarding to the fastest practical and the most economical path-planning to balance the path length, traffic congestion, gradient, turns, green wave section, Stop signs, bands of roads, viaduct, fuel, road width, toll fee etc on the streets of metropolitan.
Meanwhile, we implemented the route-planning algorithms of Traveling Salesman Problem with and without the constrains of rush hours and traffic jams on the smartphones under Android operating system with the time complexity of O(M2√("NlogC" )), where M is the number of destinations, N is the number of raster cells on the streets of metropolitan and C is the maximum weight of links.

目錄
謝辭 …………………………………………………………………………………Ⅰ
口試委員簽名單 ……………………………………………………………………Ⅱ
中文論文提要 ………………………………………………………………………Ⅲ
英文論文提要……………………………………………………………………… Ⅳ
目 錄 ………………………………………………………………………………Ⅵ
圖目錄 ………………………………………………………………………………Ⅷ
表目錄 ………………………………………………………………………………Ⅸ
第一章 緒論 …………………………………………………………………………1
第二章 背景與相關研究 ……………………………………………………………3
第一節Traveling Salesman Problem ………………………………………......…3
第二節 Complete Graph ……………………………………………………....…4
第三節Edge Weight ……………………………………………………………...5
第四節Node Weight ……………………………………………………………..5
第五節 物流架構 ……………………………………………………………......…6
第三章 TSP多點實際路徑規劃演算法 ……………………………………………8
第一節 變數表 ………………………………………………………………......…8
第二節 TSP多點實際路徑規劃演算法 …………………………………….......…9
第四章 避開壅塞區之TSP多點實際路徑規劃演算法……………………………11
第一節 變數表…………………………………………………………………......11


第二節 避開壅塞區之TSP多點實際路徑規劃演算法 ……………….........……12
第五章 效能分析…………………………………………………………..………16
第一節 時間複雜度…………………………………………………….….....……16
第二節 空間複雜度……………………………………………………......…...…16
第六章 智慧型手機應用實例與分析……………………………………..………18
第一節 智慧型手機應用實例……………………………………………......……18
第二節 實例分析………………………………………………………….....……18
第七章 結論與未來研究………………………………………………..…………22
參考文獻 …………………………………………………………………..………23
著作權聲明 ………………………………………………………………..………26


[1] Google Maps Navigation http://www.google.com/mobile/navigation/
[2] L. Bodin, B. Golden, A. Assad and M. Ball, “Routing and scheduling of vehicles and crews: the state of the art,” Computers and Operations Research, Vol. 10, pp. 63- 211, 1983.
[3] D. Chen, S. Li, F. Qiu and N. Xu, “Research on hub-and-spoke logistics network construction: An empirical analysis from Zhejiang Province in China,” International Conference of Logistics Systems and Intelligent Management, Vol. 2, pp.1003-1007, 2010.
[4] M. Dorigo, V. U. Vrije, B. Brussels and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, no. 1, pp. 53-66, 1997.
[5] M. M. Flood, “The Traveling Salesman Problem,” Operations Research, Vol.4, pp. 61-75, 1995.
[6] M. R. Gaery and D. S. Johnson, Computers and intractability: A guide to the theory of NP- completeness, W. H. Freeman and Company, 1979.
[7] M. Held and R. M. Karp, “A dynamic programming approach to sequencing problems,” Journal of Society Industrial and Applied Mathematics, Vol. 10, pp. 196-210, 1962.
[8] G. E. Jan, M. C. Lee, S. C. Hsieh and Y. Y. Chen, “Transportation Network Navigation with Turn Penalties,” IEEE/ASME International Conference on Advanced Intelligent Mechatronics, No. 0421, pp. 1224- 1229, July 2009.
[9] G. E. Jan, K. Y. Chang and I. Parberry, “Optimal Path Planning for Mobile Robot Navigation,” IEEE/ASME Transaction on Mechatronics, Vol. 14, No. 9, pp. 925- 936, Aug. 2008.
[10] G. E. Jan, M. C. Lee, Y. S. Huang and B. S. Lin, “Practical Route Planning on the Smart phones,” World Academy of Science, Engineering and Technology, pp. 24-26, Jun. 2011.
[11] G. E. Jan, Y. S. Huang, H.Y. Chen, J. J. Hong and J. L. He, “The Most Economical Route Planning on the Smartphone,” 2010 Conference and Annual Meeting of Chinese Institute Transportation, Fon Chia Univ., Taichung, Taiwan, pp. 1169-1182, Dec. 2010.
[12] G. E. Jan, M. C. Lee, Y. S. Huang and B. S. Lin, “Practical Route Planning on the Smart phones,” 2011 World Academy of Science, Engineering and Technology, Paris, France, pp. 24-26, Jun. 2011.
[13] G. E. Jan, K. Y. Chang and I. Parberry, “Optimal Path Planning for Mobile Robot Navigation,” IEEE/ASME Transaction on Mechatronics, Vol. 14, No. 9, pp. 925- 936, 2008.
[14] G. Laporte, “The Traveling Salesman Problem:An overview of exact and approximate algorithms,” European Journal of Operational Research, Vol. 59, pp. 231-247, 1992.
[15] P. Larrañaga, C. M. H. Kuijpers, R. H. Murga, I. Inza and S. Dizdarevic, “Genetic algorithm for the traveling salesman problem: a review of representations and operators,” Artificial Intelligence Review, Vol. 13, no. 2, pp. 129-170, 1999.
[16] S. Lin and B. W. Kernighan, “An Effective Heuristic Algorithm for the Traveling Salesman Problem,” Operations Research, Vol. 21, pp. 498-516, 1973.
[17] S. Lin, “Computer Solutions of the Traveling Salesman Problem,” The Bell System Technical Journal, Vol.44, pp. 2245-2269, 1965.
[18] J. Liu, L. Haihua and G. Kai, “Navigation Algorithm Reference to Real-Time Traffic Information,” International Conference on Management and Service Science, pp. 1-3, 2011.
[19] L. Liu, Y. Jing, Z. Chi, J. Chen and Chao Ma, “Design and implementation of Android Phone Based Group Communication and Navigation System,” International Conference on Communications and Networks, pp. 3174 - 3177, 2012.
[20] C. Mlandraki and R. B. Dial1, “A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem,” European Journal of Operational Research, Vol. 90, Issue 1, pp. 45- 55, 1996.
[21] M. Miroslaw, G. Mohan and P. Mihir, “Serial and parallel simulated annealing and tabu search algorithms for the Traveling Salesman Probliem,” Annals of Operations Research, Vol. 21, pp. 59-84, 1989.
[22] J. P. Norback and R. F. Love, “Geometric Approach to Solving the Traveling Salesman Problem,” Management Science, Vol. 23, pp.1208-1223, 1977.
[23] D. J. Rosenkrantz, R. E. Stearns and P. N. Lewis, “An Analysis of Several Heuristics for the Traveling Salesman Problem,” SLAM Journal on Computing, Vol. 6, pp. 561-581, 1977.
[24] M. Sniedovich, “A dynamic programming algorithm for the travelling salesman Problem,” ACM SIGAPL APL Quote Quad, Vol. 23, no. 4, 1993.
[25] T. Volgenant and R. Jonker, “A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation,” European Journal of Operational Research, Vol. 9, Issue 1, pp. 83- 89, 1982.
[26] Q. Wang, L. Xiong, H. Liu and J. Liang, “Improved particle swarm algorithm for TSP based on the information communication and dynamic work allocation,” Asian Journal of Information Technology, Vol. 5, no. 11, pp. 1191-1196, 2006.
[27] G. J. Woeginger, “Exact Algorithms for NP-Hard Problems: A Survey,” Lecture Notes in Computer Science, Vol. 2570, pp. 185-207, 2003.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top