查詢結果分析
來源資料
頁籤選單縮合
題 名 | 多重迴圈配送路徑與配送順序決策之兩階段演算方法=The PNP Method--A Two-Stage Approach for Multiloop Vehicles Routing Planning |
---|---|
作 者 | 詹弘康; 張光華; | 書刊名 | 科技學刊 |
卷 期 | 7:2 1998.04[民87.04] |
頁 次 | 頁129-138 |
分類號 | 446.93 |
關鍵詞 | 物流配送; 車輛巡迴路徑問題; PNP優先近點法; 節省法; 旅行者問題; Vehicle routing problem; VRP; Traveling salesman problem; Saving approach; Priority near point algorithm; |
語 文 | 中文(Chinese) |
中文摘要 | 傳統演算法在車輛配送路徑規劃問題( VRP, Vehicle Routingt Problem )上通 常只針對巡迴距離的單一目標進行求解搜尋,無法顧及客戶需求急迫性,客戶重要性與需求 數量等變化頻繁的因素,有鑑於此本研究將提出一套快速可行的啟發式演算法,稱之為優先 近點法(PNP, Priority Near Point)的兩階段演算法,以因應實務業者快速搜尋滿意之配 送路徑,順序與載具指派之決策模式需求。本研究之目的旨在優先考量業者最重視的顧客滿 意度(需求急迫性,需求數量,顧客重要性)之情況下,兼顧及運輸距離成本,係尋求多目 標妥協解,而非單一目標著重縮短巡迴路徑。此法第一階段為啟發式演算法,係先依據顧客 貨物的需求量、貨物需求的急切性以及顧客的重要性三項目標來計算融合決策權重,以決定 顧客的配送優先順序,然後再考量載具可用運輸能量進行載具指派工作,並結合相鄰最近點 最短距離的觀念以獲得初步多重迴圈( multiloop )的配送路徑, 順序與載具指派之決策 模式。 第二階段接著利用旅行者問題( Traveling Salesman Problem; TSP )的概念來消 除每個迴圈內圍多繞路徑的情形,而得最後平滑合理的配送路徑。本研究利用專家系統構建 工具來建立規則庫模式以及進行範例的測試與模擬, 再將 PNP 的二種階段結果與以縮短運 輸距離為單一目標之節省演算法( Saving Approach )作一嚴格比較, 以評估客戶優先模 式的效能。以國內大型儲運公司實際資料為基礎之模擬實驗結果顯示,優先考慮客戶滿意度 的 PNP 法所得多目標妥協路徑之總距離,比追求單一目標的節省法所得總距離要長些, 但 差距相當有限, 尤其在客戶數目多時兩者僅有 5% 之差距,顯示 PNP 法在複雜作業環境中 效果相當良好, 在優先顧及客戶需求之同時,並沒有犧牲太多的路徑長度做為代價。 此外 PNP 法易於交談式決策應用,決策過程完全符合人類思維模式,所演算結果甚易為配送業者 所理解接受,尤其在網路結構複雜且內外部參數條件快速變動的配送環境中,PNP 優先近點 法更易發揮快速求得滿意決策之功能。 |
英文摘要 | In order to solve the vehicle routing problem for practical application, this research develops a two-stage approach called Priority Near Point (PNP) algorithm. In the first stage, this algorithm first takes into account several factors, such as the total number of orders, quantity of delivering goods, the urgency of the order and the importance of the customers, to calculate the weighted distribution priority for each order. Then, with the nearest adjacent point concept, the distribution routing is determined one by one until all order are filled. In the second stage, the Traveling Salesman Problem (TSP) algorithm is introduced to eliminate the inner loop for each routing and then results in smoother and shorter route. The performance of PNP algorithm is compared with the performance generated by the Saving Approach algorithm which is dedicated for finding a shorter routing distance without considering other factor like customer's need. Results show that the total routing distance by PNP algorithm is only about 5% more than that by Saving Approach. It indicates that while taking several objectives into consideration PNP algorithm is able to generate a satisfactory and efficient solution, particularly when the number of service nodes increase, and is found useful in complex practical situations. |
本系統中英文摘要資訊取自各篇刊載內容。