第四章城市物流配送規(guī)劃與決策-資料下載頁
2024-12-29 16:11本頁面
【正文】 配送路線上為止，形成一條可行的配送路線。按照線路的合理判斷準(zhǔn)則，對可行配送路線進(jìn)行合理化改進(jìn)，就得到一條優(yōu)化的配送路線。 2023/1/16 54 kevin 設(shè)企業(yè)車輛一次配送 5個客戶，客戶接受貨物時間無特別要求。企業(yè)配送中心用■表示，客戶用●表示，配送中心與客戶之間的相對距離如圖 337所示。 2023/1/16 55 kevin 2023/1/16 56 kevin 2023/1/16 57 kevin （ 3）解決 VRP 問題的節(jié)約法 （ The Savings Method） 利用里程節(jié)約法確定配送線路的主要出發(fā)點(diǎn)是，根據(jù)配送方的運(yùn)輸能力及其到客戶之間的距離和各客戶之間的相對距離，來制定使配送車輛總的運(yùn)輸成本達(dá)到或接近最小的配送方案。 2023/1/16 58 kevin 節(jié)約算法用來解決 VRP問題 ? 節(jié)約算法 （ Savings Algorithm） 是 Clarke和 Wright在 1964年提出的 ， 它是目前用來解決 VRP模型最有名的啟發(fā)式算法 。 ? 節(jié)約算法可以解決運(yùn)輸車輛數(shù)目不確定 （ 運(yùn)輸車輛數(shù)目在 VRP問題中是一個決策變量 ） 的 VRP問題 ， 這個算法對有向和無向問題同樣有效 。 2023/1/16 59 kevin 節(jié)約法的原理 初始路線 —— 線路里程 BOOBAOOA dddd ????將兩個站點(diǎn)合并到同一路線上的里程 BOABOAddd ??節(jié)約的距離為 S=dAO+dOBdAB A B O A B O 2023/1/16 60 kevin 節(jié)約法 1. 選擇企業(yè)配送中心作為起點(diǎn)，并記為 “ 0” . 2. 計(jì)算節(jié)約值 Sij = Ci0 + C0j Cij 3. 從最大到最小排序節(jié)約值 . 4. 根據(jù)節(jié)約連接消費(fèi)者形成路線 . 不要破壞先前連接的任何連線 . 當(dāng)所有消費(fèi)者連接在一條路線上時，停止 . 2023/1/16 61 kevin 節(jié)約算法用來解決 VRP問題的步驟 ? 一、計(jì)算相互之間的最短距離 ? 二、計(jì)算各個用戶之間的節(jié)約里程 ? 三、對節(jié)約里程進(jìn)行排序 ? 四、連線、形成配送線路 2023/1/16 62 kevin ? 把節(jié)約量從大到小的順序依次把客戶連成一條回路 ，直到整個回路各個用戶的需求量之和不超過這輛載重車的載重量 ， 就組成了一條節(jié)約量最大的配送回路 ，派出一輛車 。 然后再在剩下的用戶中同樣按節(jié)約量從大到小的順序繼續(xù)組織配送回路 ， 派出車輛 ， 這樣下去一直到所有的用戶都組織完畢為止 ， 就做完了一個完整的配送計(jì)劃 。 2023/1/16 63 kevin 節(jié)約算法案例 例如，某月某日，長江物流公司接受的武漢某商場給武漢市十個用戶送貨的任務(wù)單，多個品種運(yùn)量共 80噸，各個用戶的需求量如表，各點(diǎn)之間的路程如圖 7－ 5所示。公司現(xiàn)有十噸車二輛、 5噸車若干輛。需要制定配送計(jì)劃。 2023/1/16 64 kevin 表 7－ 5各個用戶之間的路程（路程單位：公里） 制定配送計(jì)劃的第一步，首先按排直送，把大運(yùn)量用戶先用專車直送，剩下的小運(yùn)量用戶再統(tǒng)一安排配送。 由圖 7－ 5可以看出，物流中心 A到用戶 P1的路程僅 10公里，可以由一輛 10噸車來回運(yùn)送 4次，一天可以完成。剩下的 20噸加上的 10噸可以由另一輛10噸車運(yùn)送 3次。 派一輛 10噸車專為 P1用戶來回運(yùn)送四趟，每趟運(yùn) 10噸，來回算 20公里。工作量為： 10噸＊ 20公里＊ 4＝ 800噸公里。 第二輛 10噸車專為 P1送 20噸，為 P2送 10噸，來回運(yùn)三次。其工作量為： 10噸＊ 20公里＊ 2+10噸＊ 12公里＊ 2＝ 640噸公里。 把這些大運(yùn)量用戶直送安排完后， P2還剩下 2噸，其余小運(yùn)量用戶再安排配送，制定配送計(jì)劃。 2023/1/16 65 kevin 解決 VRP問題的幾種智能（啟發(fā)式）算法 2023/1/16 66 kevin 郵遞員每次要走遍他所負(fù)責(zé)街區(qū)的每一條道路，投遞完畢后仍須回到郵局，他應(yīng)走什么路線才能使總路程最短。這個問題是由我國山東師范學(xué)院管梅谷教授在 1962年首次提出的，所以國際上通稱為中國郵遞員問題。 中國郵遞員問題可以抽象為一個連通圖，每個邊都有一個非負(fù)權(quán)數(shù)，試求一個圈，過每邊至少一次，并使圈的總權(quán)數(shù)最小。 六、中國郵遞員問題 2023/1/16 67 kevin 定義： 給一個連通多重圖 G，若存在一條鏈（圈）過每邊一次且僅一次，則稱這條鏈（圈）為 歐拉鏈（圈） 。 定義： 一個圖如果存在歐拉圈，則稱之為 歐拉圖 。 顯然，一個圖若能一筆不重復(fù)地畫出，則這個圖就是歐拉圖或含有歐拉鏈。 定理： 連通多重圖 G是歐拉圖，當(dāng)且僅當(dāng)圖中無奇點(diǎn)。 這個定理的結(jié)論是顯然的，因?yàn)闅W拉圖從某一點(diǎn)出發(fā)又回到原來的出發(fā)點(diǎn)，這就要求與每個頂點(diǎn)相關(guān)聯(lián)的邊數(shù)應(yīng)是偶數(shù)，從而才能保證從一條邊進(jìn)入該點(diǎn)，從與該點(diǎn)相關(guān)聯(lián)的另一條邊出去。 2023/1/16 68 kevin 歐拉圖問題起源與著名的哥尼斯堡七橋問題，它的實(shí)質(zhì)是如何判斷一個連通圖能否一筆不重復(fù)地畫出。這個問題是由大數(shù)學(xué)家歐拉解決的，所以稱為歐拉圖問題。 推論： 連通多重圖 G有歐拉鏈，當(dāng)且僅當(dāng) G恰有兩個奇點(diǎn)。 上面的定理和推論提供了識別一個圖能否一筆不重復(fù)畫出的簡單方法。如下圖，有兩個奇點(diǎn)，所以能一筆不重復(fù)地畫出，從奇點(diǎn)V2開始一筆畫到奇點(diǎn) V5 。 2023/1/16 69 kevin 解此問題的基本思路是：若街區(qū)路無奇點(diǎn)，顯然按歐拉圖定理可以不重復(fù)地走遍所有街道回到出發(fā)位置。如果圖中有奇點(diǎn)，每邊只走一次又回到出發(fā)點(diǎn)是不可能的。如果要回到原地就得走些重復(fù)路，也就是在原來的街區(qū)圖上添加一些邊，使有奇點(diǎn)的圖轉(zhuǎn)換成無奇點(diǎn)的圖。由于我們要求總權(quán)數(shù)最小，所以必須尋找使新增加的邊的總權(quán)數(shù)最小的方案。我們稱增加重復(fù)邊使圖中無奇點(diǎn)的方案為可行方案，稱總權(quán)數(shù)最小的方案為最優(yōu)方案。 詳細(xì)解法請參閱 《 運(yùn)籌學(xué) 》 ，清華大學(xué)出版社 2023/1/16 70 kevin 謝謝觀看 /歡迎下載 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 FAIT
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1