關(guān)于送貨路線設(shè)計(jì)問題的分析(編輯修改稿)
2025-04-20 12:01 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 243127392731260總的時(shí)間為：。二、局部全排列窮舉法模型前30個(gè)貨物的運(yùn)送共涉及到22個(gè)站點(diǎn)數(shù)據(jù)量較大，直接采用全排列窮舉法難以實(shí)現(xiàn)，因此我問現(xiàn)將其分塊，并在每塊內(nèi)部采用局部全排列窮舉法得到局部最佳路徑，在通過固定每一塊路徑的起始點(diǎn)的方法是所有塊的路徑連接成一個(gè)整體。（具體模型算法見下文問題二）最佳路徑為：O181319243127273927313134404545454249424343383638353232322323161417212626O總的時(shí)間為：。由此兩種模型的結(jié)果比較明顯可得分塊后利用窮舉法得到的結(jié)果優(yōu)于前者，因此，前30個(gè)貨物的送貨路徑選擇局部全排列窮舉法：O1813192431272739273131344045454542494243433836383532323223231614172126O總時(shí)間為：。路徑如圖1—2所示：圖1—2 前30個(gè)貨物的最佳運(yùn)輸路線圖 問題二模型的建立于求解本題利用分塊思想，應(yīng)用局部全排列窮舉法求解每一塊的最佳路徑。由于考慮到送貨時(shí)間運(yùn)輸限制，我們優(yōu)先考慮送貨時(shí)間，即以送貨時(shí)間對(duì)所有貨物進(jìn)行分塊，并在每一塊內(nèi)部采用局部全排列窮舉法求取路徑，并判斷其總的送貨時(shí)間是否滿足指定的時(shí)間。其基本步驟為：(1) 第一時(shí)間段為8:00——9:00之間送到的站點(diǎn)為：1132227，不計(jì)重復(fù)站點(diǎn)，總共有5個(gè)站點(diǎn)，利用窮舉法比較 次得到最佳路徑為：1813242739。(2) 第二時(shí)間段為9:00——9:30之間送到的站點(diǎn)為：3334445，不計(jì)重復(fù)站點(diǎn)，總共有4個(gè)站點(diǎn)，利用窮舉法比較 次得到最佳路徑為：31344045, 。(3) 第三時(shí)間段為9:30——10:15之間送到的站點(diǎn)為：444438，不計(jì)重復(fù)站點(diǎn)，總共有4個(gè)站點(diǎn)，利用窮舉法比較 次得到最佳路徑為：4249434338, 。(4) 第四時(shí)間段為10:15——12:00之間送到的站點(diǎn)為：332111226，不計(jì)重復(fù)站點(diǎn)，總共有8個(gè)站點(diǎn)，利用窮舉法比較 次得到最佳路徑為：3632231614172126, 。因此，根據(jù)題目所給的時(shí)間段分塊所得結(jié)果如表1所示：站點(diǎn)分塊表第一時(shí)間段貨物號(hào)送達(dá)地點(diǎn)重量體積時(shí)間最佳路徑時(shí)間（含交貨時(shí)間）/分1139:00182189:001313399:002419279:002720249:002722279:0039第二時(shí)間段3319:303111459:303114459:303421319:304024349:304525409:304526459:3045第三時(shí)間段103810:1542124310:1549154210:1543164310:1543274910:1538第四時(shí)間段42612:003652112:003261412:003271712:003282312:00
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1