智慧型手機上多點實際道路路徑規劃

這幾年來，電子商務業蓬勃發展，造成了新興的購物模式-配送服務。消費行為轉移，市場需求擴大，為了減少運輸成本的開銷，必須規劃出良好的運輸路線。在本文中主要的對象則是宅配業者的配送運輸網路，而目前的業者大多是採取經驗法則去規劃各自的配送路線，但所需考量交通因素過多，很容易規劃出運輸成本較高的路徑，因此僅僅只是依靠經驗法則是不夠的。研究相關領域的文章之後，我們可以歸納出以下的問題：(1) 大部分送貨員都以自我經驗為基準去規劃路徑，但由於營業據點的急速擴散，時常需要更動配送路線，因此僅僅依靠經驗法則是不夠的；(2) 在實際的道路情況底下，影響耗油及速度的因素不單只是距離大小，還有轉彎成本、路燈波、迴轉道等因素；(3) 若在不對的時間點經過繁雜壅塞的區域，便會增加其運輸成本；(4) 抵達須配送的目的地時，還須考量去卸貨時間成本；(5) 隨時隨地將導航裝置安置於任何車體上的便利性。這些問題對於配送規劃是皆是重要因素。本文以各種道路通用模組為基礎，以完善的單點路徑規劃作為參考依據，擴展至多點路徑規劃。本文以宅配業者作為服務的對象，去改善傳統以經驗法則為主的配送路線規劃，透過整體的規劃後，就可大大的減少運輸成本。甚至更進一步加入分時分區的概念，便可以解決在上下班潮避開壅塞區的問題。

關鍵字

旅行銷售員問題、TSP多點實際路徑規劃、智慧型手機

並列摘要

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.

並列關鍵字

Android, Dijkstra algorithm, universal model for route planning, Traveling Salesman Problem

參考文獻

[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.

[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.

國際替代計量

智慧型手機上多點實際道路路徑規劃

未授權

主題瀏覽