4第四章城市物流配送規(guī)劃與決策(精品ppt)-資料下載頁
2025-10-15 19:25本頁面
【正文】 定使配送車輛(chēli224。ng)總的運輸本錢到達或接近最小的配送方案。,第五十八頁，共七十一頁。,2024/10/20,kevin,59,節(jié)約算法用來解決(jiěju233。)VRP問題,節(jié)約算法〔Savings Algorithm〕是 Clarke和Wright在 1964年提出的，它是目前用來解決VRP模型最有名的啟發(fā)式算法。 節(jié)約算法可以解決運輸車輛數目(sh249。m249。)不確定〔運輸車輛數目(sh249。m249。)在VRP問題中是一個決策變量〕的VRP問題，這個算法對有向和無向問題同樣有效。,第五十九頁，共七十一頁。,2024/10/20,kevin,60,第六十頁，共七十一頁。,2024/10/20,kevin,61,節(jié)約(ji233。yuē)法,1. 選擇企業(yè)配送中心作為起點，并記為 “0〞. 2. 計算節(jié)約值 Sij = Ci0 + C0j Cij 3. 從最大到最小排序節(jié)約值. 4. 根據節(jié)約連接消費者形成路線(l249。xi224。n). 不要破壞先前連接的任何連線. 當所有消費者連接在一條路線上時，停止.,第六十一頁，共七十一頁。,2024/10/20,kevin,62,節(jié)約算法用來解決VRP問題(w232。nt237。)的步驟,一、計算相互之間的最短距離 二、計算各個用戶之間的節(jié)約里程 三、對節(jié)約里程進行(j236。nx237。ng)排序 四、連線、形成配送線路,第六十二頁，共七十一頁。,2024/10/20,kevin,63,把節(jié)約量從大到小的順序依次把客戶連成一條回路，直到整個回路各個用戶的需求量之和不超過(chāogu242。)這輛載重車的載重量，就組成了一條節(jié)約量最大的配送回路，派出一輛車。然后再在剩下的用戶中同樣按節(jié)約量從大到小的順序繼續(xù)組織配送回路，派出車輛，這樣下去一直到所有的用戶都組織完畢為止，就做完了一個完整的配送方案。,第六十三頁，共七十一頁。,2024/10/20,kevin,64,節(jié)約算法案例 例如，某月某日，長江(ch225。nɡ jiānɡ)物流公司接受的武漢某商場給武漢市十個用戶送貨的任務單，多個品種運量共80噸，各個用戶的需求量如表，各點之間的路程如圖7－5所示。公司現有十噸車二輛、5噸車假設干輛。需要制定配送方案。,,,第六十四頁，共七十一頁。,2024/10/20,kevin,65,,,表7－5各個用戶之間的路程(l249。ch233。ng)〔路程(l249。ch233。ng)單位：公里〕,制定(zh236。d236。ng)配送方案的第一步，首先按排直送，把大運量用戶先用專車直送，剩下的小運量用戶再統一安排配送。 由圖7－5可以看出，物流中心A到用戶P1的路程僅10公里，可以由一輛10噸車來回運送4次，一天可以完成。剩下的20噸加上的10噸可以由另一輛10噸車運送3次。,派一輛10噸車專為P1用戶來回(l225。ihu237。)運送四趟，每趟運10噸，來回(l225。ihu237。)算20公里。工作量為：10噸＊20公里＊4＝800噸公里。 第二輛10噸車專為P1送20噸，為P2送10噸，來回運三次。其工作量為： 10噸＊20公里＊2+10噸＊12公里＊2＝640噸公里。 把這些大運量用戶直送安排完后，P2還剩下2噸，其余小運量用戶再安排配送，制定配送方案。,第六十五頁，共七十一頁。,2024/10/20,kevin,66,解決VRP問題(w232。nt237。)的幾種智能〔啟發(fā)式〕算法,第六十六頁，共七十一頁。,2024/10/20,kevin,67,郵遞員每次要走遍他所負責街區(qū)的每一條道路，投遞完畢后仍須回到郵局，他應走什么路線才能使總路程最短。這個問題是由我國山東師范學院管梅谷教授在1962年首次提出的，所以國際(gu243。j236。)上通稱為中國郵遞員問題。 中國郵遞員問題可以抽象為一個連通圖，每個邊都有一個非負權數，試求一個圈，過每邊至少一次，并使圈的總權數最小。,六、中國(zhōnɡ ɡu243。)郵遞員問題,第六十七頁，共七十一頁。,2024/10/20,kevin,68,定義：給一個連通多重圖G，假設存在一條鏈〔圈〕過每邊一次且僅一次，那么稱這條鏈〔圈〕為歐拉鏈〔圈〕。 定義：一個圖如果存在歐拉圈，那么稱之為歐拉圖。 顯然，一個圖假設能一筆不重復地畫出，那么這個圖就是歐拉圖或含有歐拉鏈。 定理：連通多重圖G是歐拉圖，當且僅當圖中無奇點。 這個定理的結論是顯然的，因為歐拉圖從某一點(yī diǎn)出發(fā)又回到原來的出發(fā)點，這就要求與每個頂點相關聯的邊數應是偶數，從而才能保證從一條邊進入該點，從與該點相關聯的另一條邊出去。,第六十八頁，共七十一頁。,2024/10/20,kevin,69,歐拉圖問題起源與著名的哥尼斯堡七橋問題，它的實質是如何判斷一個連通圖能否一筆不重復地畫出。這個問題是由大數學家歐拉解決(jiěju233。)的，所以稱為歐拉圖問題。 推論：連通多重圖G有歐拉鏈，當且僅當G恰有兩個奇點。 上面的定理和推論提供了識別一個圖能否一筆不重復畫出的簡單方法。如以下圖，有兩個奇點，所以能一筆不重復地畫出，從奇點V2開始一筆畫到奇點V5 。,第六十九頁，共七十一頁。,2024/10/20,kevin,70,解此問題的根本思路是：假設街區(qū)路無奇點，顯然按歐拉圖定理可以不重復地走遍所有街道回到出發(fā)位置。如果圖中有奇點，每邊只走一次又回到出發(fā)點是不可能的。如果要回到原地就得走些重復路，也就是在原來(yu225。nl225。i)的街區(qū)圖上添加一些邊，使有奇點的圖轉換成無奇點的圖。由于我們要求總權數最小，所以必須尋找使新增加的邊的總權數最小的方案。我們稱增加重復邊使圖中無奇點的方案為可行方案，稱總權數最小的方案為最優(yōu)方案。 詳細解法請參閱?運籌學?，清華大學出版社,第七十頁，共七十一頁。,內容(n232。ir243。ng)總結,第四章 城市物流配送規(guī)劃與決策。kevin。物流企業(yè)擁有一定規(guī)模(guīm243。)的運輸工具〔自有或合同外協〕，再根據業(yè)務規(guī)模(guīm243。)到市場上臨時租賃車輛。以行程最短為確定車輛路線行程的評價指標。目標函數：以行程最短為確定車輛路線行程的評價指標。要求確定：需多少條路線〔即多少輛送貨車〕。初始路線——線路里程。3. 從最大到最小排序節(jié)約值.。4. 根據節(jié)約連接消費者形成路線.。推論：連通多重圖G有歐拉鏈，當且僅當G恰有兩個奇點,第七十一頁，共七十一頁。
環(huán)評公示相關推薦
鄂ICP備17016276號-1