物流配送問題講義-wenkub
2023-01-26 23:28:24 本頁面
【正文】 5+4+12+15=57 單回路運(yùn)輸 —— TSP模型及求解 最近插入法 2 最近插入法是由 Rosen Krantz和 Stearns等人在 1977年提出的另外一種用于解決 TSP問題的算法。 （ 2）找到離剛剛加入到回路的上一個(gè)頂點(diǎn)最近的一個(gè)頂點(diǎn)，并將其加入到回路中。 單回路運(yùn)輸 —— TSP模型及求解 TSP模型的求解方法： （ 1）枚舉法 → n!或 (n1)! （ 2）整數(shù)規(guī)劃（分枝定界法、割平面法等） → 小規(guī)模 TSP問題 （ 3）啟發(fā)式算法 → 適各種規(guī)模的 TSP問題 TSP模型 單回路運(yùn)輸 —— TSP模型及求解 最近鄰點(diǎn)法 1 最近鄰點(diǎn)法是由 Rosen Krantz和 Stearns等人在 1977年提出的一種用于解決 TSP問題的算法。 TSP問題描述： 一個(gè)貨郎擔(dān)著商品去他所在的區(qū)域內(nèi)的所有村鎮(zhèn)進(jìn)行推銷，他應(yīng)怎樣選擇一條總路程最短的行走路線使每個(gè)村鎮(zhèn)恰好去一次或者至少去一次？ 或 一個(gè)推銷員要到若干個(gè)城市推銷產(chǎn)品，然后回到出發(fā)點(diǎn)，已知每兩個(gè)城市之間的距離，他應(yīng)如何選擇其旅行路線，使每個(gè)城市經(jīng)過一次且僅僅一次或者至少經(jīng)過一次，并且總的行程最短？ TSP問題的圖論語言描述： 在給定的連通加權(quán)無向圖（ G,w）中找出一條最小權(quán)的 Hamilton圈或者找出一條經(jīng)過 G中每個(gè)頂點(diǎn)并且有最小權(quán)的閉鏈。 解： 自營模式銷售額： 1000 +800 +500 =840(萬元 ) 互用模式銷售額： 1200 +700 +400 =890(萬元 ) 第三方模式銷售額： 1500 +1000 +300 =1110(萬元 ) 結(jié)論：第三方配送模式的期望值最大為 1110萬元，故該模式可作為企業(yè)比較滿意的模式。根據(jù)以上資料計(jì)算各模式的綜合價(jià)值系數(shù) 。 解： V自營 =5/10 +220/220 +25/25 +98/99 = V互用 =5/8 +180/220 +17/25 +97/99 = V第三方 =5/5 +140/220 +15/25 +99/99 = 結(jié)論：自營配送模式的綜合價(jià)值系數(shù)最大，是企業(yè)所要選擇的配送模式。 配送線路優(yōu)化問題 —— TSP模型及求解 單回路運(yùn)輸問題 是指在路線優(yōu)化中，設(shè)存在節(jié)點(diǎn)集合 D，選擇一條合適的路徑遍歷所有的節(jié)點(diǎn)，并且要求閉合。前者稱為最優(yōu)圈（ Optimal Cycle），后者稱為最優(yōu)鏈（ Optimal Chain）。 該算法十分簡單，但是它得到的解并不十分理想，有很大的改善余地。 （ 3）重復(fù)步驟（ 2），直到 V中所有頂點(diǎn)都加入到回路中。 最近插入法比最近鄰點(diǎn)法復(fù)雜，但是可以得到相對比較滿意的解。 單回路運(yùn)輸 —— TSP模型及求解 最近插入法求解： 1 2 3 4 5 6 假如將 V5插入 V1和 V3之間： cik+ckjcij=c15+c53c13=7+76=8 假如將 V5插入 V3和 V2之間： cik+ckjcij=c35+c52c32=7+155=17 假如將 V5插入 V1和 V2之間： cik+ckjcij=c15+c52c12=7+1510=12 所以選最小的 8，即應(yīng)將 V5插入 V1和 V3之間，其他點(diǎn)的插入法以此類推。 該問題的 研究目標(biāo) 是對一系列的顧客需求點(diǎn)設(shè)計(jì)適當(dāng)?shù)穆肪€，使車輛有序地通過它們，在滿足一定的約束條件下，達(dá)到一定的優(yōu)化目標(biāo)。 綜合考慮運(yùn)輸路徑最短、總運(yùn)費(fèi)最少、總運(yùn)輸時(shí)間最短、空載車總運(yùn)行時(shí)間最少、完成任務(wù)所需的車輛最少這五個(gè)目標(biāo)時(shí)，總運(yùn)費(fèi)就不應(yīng)單單是距離的函數(shù)，而要考慮到即時(shí)配送、車輛成本、人員成本的問題。 （ 2）分組。 （ 4）路徑優(yōu)化。試用掃描算法對該運(yùn)輸問題進(jìn)行求解。如前圖所示。在第 2組中有顧客 3，繼續(xù)上面步驟，直到所有的顧客都被分配完畢。 8531 ???Load itLoadLoad lim1 1214653 ??????62 ?Load25 2023年 1月 23日星期一 圖 掃描算法求解結(jié)果 配送需求計(jì)劃 1． DRP的概念 DRP是配送需求計(jì)劃（ distribution requirement planning）的簡稱 ,它是流通領(lǐng)域中的一種物流技術(shù)，是 MRP在流通領(lǐng)域應(yīng)用的直接結(jié)果。 圖 1 倉庫、物流中心業(yè)務(wù)模式 倉庫、物流中心 生產(chǎn)企業(yè) 1 用戶需求 下屬物流中心需求 生產(chǎn)企業(yè) 1 生產(chǎn)企業(yè) 1 ? 即含有物流業(yè)務(wù)的企業(yè)，如儲運(yùn)、配送、商貿(mào)連鎖企業(yè)等 ? 這些企業(yè)涉及到儲存和運(yùn)輸?shù)臉I(yè)務(wù)，即進(jìn)貨與送貨的業(yè)務(wù) ? DRP可以使企業(yè)商品流通中的總費(fèi)用最省，資源（車輛、倉庫等）利用率最
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1