物流配送問題講義-展示頁
2025-01-13 23:28本頁面
【正文】 II III Ⅳ 圖 8 5 矩陣圖決策法 現(xiàn)代配送模式的選擇 (1)確定型決策 例 81，某企業(yè)在選擇配送模式時主要考慮了四個方面的目標，如表 8 2所示。根據(jù)以上資料計算各模式的綜合價值系數(shù) 。 現(xiàn)代配送模式的選擇 (2)非確定型決策 例 82，某企業(yè)計劃通過提高配送效率，滿足客戶對配送的要求，來擴大經營規(guī)模。 解： 自營模式銷售額： 1000 +800 +500 =840(萬元 ) 互用模式銷售額： 1200 +700 +400 =890(萬元 ) 第三方模式銷售額： 1500 +1000 +300 =1110(萬元 ) 結論：第三方配送模式的期望值最大為 1110萬元，故該模式可作為企業(yè)比較滿意的模式。 因此，單回路運輸問題的兩個顯著特點是： （ 1）單一性（只有一個回路）； （ 2）遍歷性（不可遺漏）。 TSP問題描述： 一個貨郎擔著商品去他所在的區(qū)域內的所有村鎮(zhèn)進行推銷，他應怎樣選擇一條總路程最短的行走路線使每個村鎮(zhèn)恰好去一次或者至少去一次？ 或 一個推銷員要到若干個城市推銷產品，然后回到出發(fā)點，已知每兩個城市之間的距離，他應如何選擇其旅行路線，使每個城市經過一次且僅僅一次或者至少經過一次，并且總的行程最短？ TSP問題的圖論語言描述： 在給定的連通加權無向圖（ G,w）中找出一條最小權的 Hamilton圈或者找出一條經過 G中每個頂點并且有最小權的閉鏈。 一般來說，貨郎擔問題的這兩種定義會產生不同的解。 單回路運輸 —— TSP模型及求解 TSP模型的求解方法： （ 1）枚舉法 → n!或 (n1)! （ 2）整數(shù)規(guī)劃（分枝定界法、割平面法等） → 小規(guī)模 TSP問題 （ 3）啟發(fā)式算法 → 適各種規(guī)模的 TSP問題 TSP模型 單回路運輸 —— TSP模型及求解 最近鄰點法 1 最近鄰點法是由 Rosen Krantz和 Stearns等人在 1977年提出的一種用于解決 TSP問題的算法。由于該算法計算快捷，但精度低，可以作為進一步優(yōu)化的初始解。 （ 2）找到離剛剛加入到回路的上一個頂點最近的一個頂點，并將其加入到回路中。 （ 4）最后，將最后一個加入的頂點和起點連接起來。 最近鄰點法 單回路運輸 —— TSP模型及求解 最近鄰點法求解： 最近鄰點法 1 2 3 4 5 6 總距離 f=6+5+15+4+12+15=57 單回路運輸 —— TSP模型及求解 最近插入法 2 最近插入法是由 Rosen Krantz和 Stearns等人在 1977年提出的另外一種用于解決 TSP問題的算法。 最近插入法也包括四個步驟： （ 1）找到 c1k最小的節(jié)點 vk，形成一個子回路（ subtour），T={v1,vk,v1}. （ 2）在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點 vk。 （ 4）重復步驟（ 2）和（ 3），直到所有的節(jié)點都加入到子回路中。 多回路運輸 —— VRP模型及求解 多回路運輸問題 ，也稱 車輛路徑問題（ Vehicle Routing Problem， VRP） ，是現(xiàn)實中十分普遍的一種調配問題，特別是對于有大量服務對象的實體。 車輛路徑問題最早是由 Dantzig和 Ramser于 1959年首次提出的。 約束條件 ：如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等。 多回路運輸 —— VRP模型及求解 多回路運輸 —— VRP模型及求解 物流配送車輛路徑問題 的描述： 從某物流中心用多臺配送車輛向多個客戶送貨，每個客戶的位置和貨物需求量一定，每臺配送車輛的載重量一定，每臺車的一次配送的最大行駛距離一定，要求合理安排車輛配送路線，使目標函數(shù)得到優(yōu)化，并滿足以下條件： （ 1）每條配送路徑上各客戶的需求量之和不超過配送車輛的載重量限制； （ 2）每條配送路徑的長度不超過配送車輛一次配送的最大行駛距離； （ 3）所用車輛路線均起始并終止于配送中心，每個客戶的需求必須滿足，且只能由一臺配送車輛送貨； （ 4）車輛的行車路線的總耗時不超過一個事先定下的數(shù)值，以滿足客戶對供貨時間的要求； （ 5）對某個客戶點，車輛到達時間限制在某一時間段內（軟限制），如果此約束不滿足，則引入懲罰函數(shù)。 多回路運輸 —— VRP模型及求解 掃描算法（ Sweep Algorithm）是 Gillett和 Miller在 1974年提出的，也是解決車輛數(shù)目不限制的 VRP問題的一種啟發(fā)式算法。然后對
教學課件相關推薦
鄂ICP備17016276號-1