物流配送問(wèn)題講義-文庫(kù)吧資料
2025-01-11 23:28本頁(yè)面
【正文】 它們，在滿(mǎn)足一定的約束條件下，達(dá)到一定的優(yōu)化目標(biāo)。解決此類(lèi)問(wèn)題時(shí)，核心問(wèn)題是如何對(duì)車(chē)輛進(jìn)行調(diào)度。 單回路運(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)的插入法以此類(lèi)推。 （ 3）在子回路中找到一條弧 (i,j)，使得 cik+ckjcij最小，然后將節(jié)點(diǎn)插入到 vi和 vj之間，用兩條新的弧 (i,k)和 (k,j)代替原來(lái)的弧 (i,j)，并將節(jié)點(diǎn) vk加入到子回路中。 最近插入法比最近鄰點(diǎn)法復(fù)雜，但是可以得到相對(duì)比較滿(mǎn)意的解。 單回路運(yùn)輸 —— TSP模型及求解 例 4 現(xiàn)有一個(gè)連通圖， |V|=6，各個(gè)頂點(diǎn)之間的距離矩陣如下表所示，假設(shè) i和 j兩點(diǎn)之間的距離是對(duì)稱(chēng)的。 （ 3）重復(fù)步驟（ 2），直到 V中所有頂點(diǎn)都加入到回路中。 最近鄰點(diǎn)法包括四個(gè)步驟： （ 1）從零點(diǎn)開(kāi)始，作為整個(gè)回路的起點(diǎn)。 該算法十分簡(jiǎn)單，但是它得到的解并不十分理想，有很大的改善余地。 TSP模型 單回路運(yùn)輸 —— TSP模型及求解 TSP模型的數(shù)學(xué)描述為： 連通圖 H，其頂點(diǎn)集為 頂點(diǎn)間的距離為 TSP模型 ???????????????????????? ???? ?? ???? ?VjVixVSSxVjxVixtsxczijSi Sjijniijnjijninjijij,},1,0{)3(,1)2(,1)1(,1..min111 1????屬于最優(yōu)路徑到從不屬于最優(yōu)路徑到從jijixij ,1,0VjicccccC iijiijijnnij ?????? ? ,0,][ },2,1{ nV ??約束式（ 1）和（ 2）意味著對(duì)每個(gè)點(diǎn)來(lái)說(shuō)，僅有一條邊進(jìn)和一條邊出；約束式（ 3）則保證了沒(méi)有任何子回路的產(chǎn)生。前者稱(chēng)為最優(yōu)圈（ Optimal Cycle），后者稱(chēng)為最優(yōu)鏈（ Optimal Chain）。 單回路運(yùn)輸 —— TSP模型及求解 旅行商問(wèn)題（ Traveling Salesman Problem， TSP），也稱(chēng)貨郎擔(dān)問(wèn)題，是單回路運(yùn)輸問(wèn)題的典型問(wèn)題，對(duì)于大規(guī)模的線路優(yōu)化問(wèn)題，無(wú)法獲得最優(yōu)解，只有通過(guò)啟發(fā)式算法獲得近似最優(yōu)解。 配送線路優(yōu)化問(wèn)題 —— TSP模型及求解 單回路運(yùn)輸問(wèn)題 是指在路線優(yōu)化中，設(shè)存在節(jié)點(diǎn)集合 D，選擇一條合適的路徑遍歷所有的節(jié)點(diǎn)，并且要求閉合?，F(xiàn)可供選擇的配送模式有三種，由于在未來(lái)幾年內(nèi)，企業(yè)對(duì)用戶(hù)要求配送的程度無(wú)法做出準(zhǔn)確的預(yù)測(cè)，只能大體估計(jì)為三種情況，且估算出三種模式在未來(lái)幾年內(nèi)三種自然狀態(tài)下的成本費(fèi)用 (見(jiàn)表 8 3)，但不知道這三種情況的發(fā)生概率，問(wèn)如何決策？ 現(xiàn)代配送模式的選擇 (2)非確定型決策 解： 第一種方法：按樂(lè)觀準(zhǔn)則來(lái)決策 第二種方法：按悲觀準(zhǔn)則來(lái)決策 第三種方法：按折衷準(zhǔn)則或赫維斯準(zhǔn)則來(lái)決策 第四種方法：按等概率準(zhǔn)則或拉普拉斯準(zhǔn)則來(lái)決策 第五種方法：按最小后悔值準(zhǔn)則來(lái)決策 現(xiàn)代配送模式的選擇 (3)風(fēng)險(xiǎn)型決策 例 83，某企業(yè)計(jì)劃通過(guò)加強(qiáng)配送效率，提高客戶(hù)滿(mǎn)意度來(lái)擴(kuò)大產(chǎn)品的銷(xiāo)售量，現(xiàn)有三種配送模式可供企業(yè)選擇，各種資料如表 8 5所示，問(wèn)企業(yè)應(yīng)選擇哪種配送模式。 解： V自營(yíng) =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é)論：自營(yíng)配送模式的綜合價(jià)值系數(shù)最大，是企業(yè)所要選擇的配送模式。第 8章 物流配送問(wèn)題 配送模式 配送模式及其選擇 現(xiàn)代配送模式的選擇 重要 不重要 配送對(duì)企業(yè)的重要性 企業(yè)配送能力 高 低 I
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1