物流與運輸?shù)幕靖拍?資料下載頁
2025-02-21 12:09本頁面
【正文】 分派，所以 VRP至少比TSP要難。因為 TSP是 NP困難 (NP hard)問題 ,所以 VRP也是 NP困難問題。因而 , VRP的解法通常都用啟發(fā)式解法。 最簡單的啟發(fā)式解法有節(jié)省成本法 (saving method)和一般化分配法 (generalized assignment heuristic)。節(jié)省成本法 (saving method)174。 saving法就是對相隔距離很近的兩個配送地 ,順便一起配送的方法。例如，有 a,b兩個配送地的時候，分別從倉庫向 a,b兩地送貨然后分別返回時的總配送距離為 5 2+6 2=22,若是把a,b兩地聯(lián)系起來，巡回配送的時候，總配送距離就變成 5+3+6=14，這比單獨分別配送少了８ 單位的距離。這８個單位距離稱為點 a,b的節(jié)約值 (saving value),一般情況下，把倉庫看做０，兩點間距離用 dij表示的話， i,j兩個配送地的節(jié)約值可用以下的式子求出一般 化分配法(GAH:Generalized Assignment heuristics)174。 雖說節(jié)約法計算的時候非常簡單，而且可以同時求出順路，但由于節(jié)約法只是考慮對距離的節(jié)約，當載重量 大小相差比較大的時候，就有可能使得安排車輛的臺數(shù)變多。另外，因為配送路線也是由節(jié)約值來決定的，所以有時盡管在兩個配送地之間有直通的大道，可是由于距離相隔的較遠 ,有時也不會被安排到同一輛車上，為了解決以上的問題，把配送地點編成小組，然后再考慮載重量的問題。其代表性的方法就是一般化分配法 (GAH)．種子點174。 最初的種子點，選擇距離物流中心最遠的售貨機 1號。接下來，求出從 2,3,4,5,6,7,8,9,10號售貨機到 1號和物流中心的綜合距離 ∶, , , , , , , , ，選擇其中最大的值 7號售貨機作為第二個種子點。第三個種子點是根據(jù)到物流中心，１號售貨機， 7號售貨機的最大的綜合距離(, , , , , , )，最大值所對應(yīng)的售貨機為４號售貨機，所以第三個種子點是４號售貨機。根據(jù)同樣的計算方法選出第四個種子點為９號售貨機。按照需求量從大到小的順序排列得 ,2,3,5,6,8,10謝謝觀看 /歡迎下載BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAITH
教學課件相關(guān)推薦
鄂ICP備17016276號-1