【文章內(nèi)容簡介】 調(diào)整后 圖 31 節(jié)約算法的圖像描述 節(jié)約里程算法主要步驟 已知條件 :需求點集 RN ={1,2,? , n},各點需求量 iR ,各點間最短距離 ijc 。 第一步 ,形成一個初始解。 確定各車輛配送點集 12, , , mI I I??? 令 ??jIj? , j =1,2,? ,n (先采取單點配送 )。 第二步 ,進(jìn)行節(jié)約度的計算。計算所有點對的節(jié)約度 ，然后對計算結(jié)果進(jìn)行升序排列。 第三步，進(jìn)行回路的合并。從升序排列的節(jié)約度序列中的最上面的值開始， 直到節(jié)約里程 的隊列空為止 ,重復(fù)下列步驟 :按照節(jié)約里程 隊列從大到小的順序 ,分析客戶 i 和 j 之間合并的可能性 (是否滿足裝載限制條件、不在同一路徑內(nèi)以及合并次數(shù)不超 過 2),將 i, j 連接起來 ,即可令 。i i j jI I I I? ? ? ? ?。 如果不是這樣 ,則從節(jié)約里程隊列中去除當(dāng)前的節(jié)約里程 ，分析下一個客戶對 [9]。 0 j i 0 j i 10 掃描算法 掃描算法 （ Sweep Algorithm） 也是用于求解車輛數(shù)目不限制的 VRP 問題，與節(jié)約算法不同的是，它屬于亞啟發(fā)式算法，而節(jié)約算法屬于構(gòu)造算法。 掃描算法的基本原理 掃描算法 是一種“先分組后路線”的算法。所謂分組，即指派給每輛車一組點。一種簡單的分組方法是將以配送中心為原點的坐標(biāo)平面劃分為多個扇形區(qū)域，并初步 將每個扇形區(qū)域的點分派給一輛車，然后擴(kuò)充路線。如果在進(jìn)行了一次“分組 路線”的路線構(gòu)造后，還存在未分配點，則再進(jìn)行“分組 路線”程序。如此反復(fù)，直到所有的點均已分配為止 [10]。 掃描算法的主要步驟 （ 1）以起始點 0點作為極坐標(biāo)系的原點， 并一連通圖中的任意一顧客點和原點的連線定義為角度零， 建立極坐標(biāo)系。 然后對所有的顧客所在的位置，進(jìn)行極坐標(biāo)變換。 （ 2）分組 從最小角度的顧客開始建立一個組，按逆時針方向，將顧客逐個加入到組中，直到顧客的需求總量超出了負(fù)載的限制。然后繼續(xù)建立一個新的組，繼續(xù)按逆時 針方向，將客戶加入組中。 （ 3）重復(fù)（ 2）中的過程，直到所有客戶都被分類為止。 （ 4）路徑優(yōu)化 對各個組內(nèi)的單回路進(jìn)行路徑優(yōu)化 [11]。 改進(jìn)后的最近插入法 TSP 模型是單回路運輸問題的最為典型的一個模型，它的全稱是 Traveling Salesman Problem1，中文叫做旅行商問題。它是一個典型的 NPHard 問題，對于大規(guī)模的線路優(yōu)化問題，無法獲得最優(yōu)解。最近插入法就是一種解決此問題的啟發(fā)式算法。 最近插入法 最近插入法是 Rosenkrantz和 Stearns等人在 1977年提出的一種用于解決 TSP(旅行11 商 )問題的算法。最近插入法由四步完成： （ 1）找到 0ic 最小的節(jié)點 iv ，形成一個子回路（ subtour）， ? ?00,kT v v v? 。 （ 2）在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點 kv 。 （ 3)在子回路中找到一條弧（ i， j） ,使得 ikc +kjc ijc 最小，然后將節(jié)點 iv 插入到節(jié)點 iv ， jv 之間，用兩條新的弧 (i， k)，（ k， j）代替原來的弧（ i， j），并將節(jié)點 kv 加入到子回路中。 （ 4）重復(fù)步驟（ 2）、（ 3），直到所有的節(jié)點都加入到子回路中。 這樣，子回路就演變?yōu)榱艘粋€ TSP的解 [12]。 由于最近插入法解決的是單回路運輸問題，故筆者在此方法基礎(chǔ)上進(jìn)行改進(jìn)和修正，使其能解決多回路運輸 VRP問題。有改進(jìn)的 方法 如下： 改進(jìn)的最近插入法 （ 1）找到 0ic 最小的節(jié)點 iv ，形成一個子回路（ subtour）， ? ?00,kT v v v? 。 （ 2）在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點 kv 。若此時回路的總貨運量未超過車的載重限制，則繼續(xù)步驟（ 3）。否則，轉(zhuǎn)（ 1）尋找新的一條回路。 （ 3） )在子回路中找到一條?。?i， j） ,使得 ikc +kjc ijc 最小，然后將節(jié)點 iv 插入到節(jié)點 iv ， jv 之間，用兩條新的弧 (i， k)，（ k， j）代 替原來的?。?i， j），并將節(jié)點 kv 加入到子回路中 。若此時該回路的總路程為未超過車輛的行程限制，則繼續(xù)步驟（ 4）。否則轉(zhuǎn) 步驟 （ 1），尋找新的一條回路。 （ 4）重復(fù)步驟（ 2）和 （ 3），直到每一個節(jié)點都被歸入某一個子回路中。 12 第 4 章 百源木業(yè) 有限公司配送路線優(yōu)化研究 建立 VRP 模型 多回路運輸問題時現(xiàn)實生活中十分 常見 的一種調(diào)配問題。此類調(diào)配問題 的核心問題是 車輛調(diào)度。因此 VRP模型也應(yīng)運而生，成了解決多回路問題的一個相當(dāng)成功的模型。據(jù)此對 百源木業(yè)有限 公司的配送系統(tǒng)建立 VRP模型。 基本條件： 百源木業(yè) 公司需給 9個客戶送貨，客戶依次為 1， 2，? ,9，現(xiàn)有 1輛 7噸（長 ,寬 ,高 ）的 貨 車 （每百公里油耗 21L） ， 2 輛 11 噸 (長 ,寬 ,高 )的貨車 (每百公里油耗 27L)， 柴油每升 元 ，司機(jī)每天工資 100 元。 模型目標(biāo)：確定所需要的車輛的數(shù)目 N、車輛類型 、司機(jī)數(shù)量 以及各車行走的路徑，并指派這些車輛到一個回路中，同時包括回路內(nèi)的路徑安排和調(diào)度，使得運輸總費用最小。 限制條件： （ 1）基于人性化與安全的考慮， 當(dāng)運輸里程超過 350 公里時 ， 需配備兩名司機(jī)，為防止突發(fā)運輸事件，車輛必須當(dāng)天回到公司，減去 去由于 裝卸貨等影響因素 ，各車最大運輸距離為 600公里。 （ 2） 每輛車完成任務(wù)之后都要回到源點 0處。 （ 3） 車輛的容量限制不能超過。 7噸的貨車最多可裝 300 張細(xì)木工板， 11 噸的最多可裝 500 張細(xì)木工板 。 11 噸貨車運輸單價比 7噸的低，優(yōu)先使用 11 噸車，若不超過300張細(xì)木工板，則使用 7噸貨車 。 百源木業(yè) 公司的配送線路 的分析與優(yōu)化 已知 百源木業(yè) 公司為 0點，分別向 9個 小 客戶 點 配送 細(xì)木工板 ，其擁有 一 輛 7噸的車和 兩 輛 11噸的車， 7 噸 卡車最大容量為 300 張細(xì)木工板 ， 11噸卡車最大載量為 500張 。 設(shè)各點間的距離為 ? ?, | , 1, 2 , 9ijC C c i j??，節(jié)約距離為 ijc? 。每輛 車的載 貨 量為 ir ，各點需求量為 ? ?1, 2 ,9iRi? ， 每輛車的行駛里程為 ? ?1, 2 ,9iLi? ， 600iL? 且公里，婺源 為 0 點，客戶點 1， 2，?， 9。 13 各縣 市的 細(xì)木工板 運量和配送距離如表 2所示 。 表 41 運輸任務(wù)表 客戶 1 景德鎮(zhèn) 2 樂平市 3 鷹潭市 4 貴溪市 5 德興市 6 上饒市 7 常山縣 8 開化縣 9 黃山市 貨運量（張 /周） 180 120 120 60 80 220 70 90 200 配送距離（ km） 原配送線路基本數(shù)據(jù)分析 目前， 百源木業(yè)有限公司 對小客戶公司采用的 配送模式 如圖 2 所示 。 各配送 線路低得 里程，所需司機(jī)數(shù)量 及 工資的基本情況如 表 3所示。 表 42 配送信息表 路線 運距 運貨量 車型 司機(jī) 0120 300 7噸貨車 1 0340 180 7噸貨車 2 0560 300 7噸貨車 1 0780 160 7噸貨車 1 090 200 7噸貨車 1 由上表可知，公司 每周需 7噸貨車 5車次配送， 司機(jī) 6人次，所需工資 600 元， 運輸總里程為 千米 ，消耗的 柴油 升，所需燃油費 元，一共花費 元 。 基于節(jié)約算法的企業(yè)配送路線優(yōu)化 首先，確定各 縣市 間的最短距離 ，縣市間最 距離表 4所示。 14 表 43 各縣市間最短距離表 （單位：千米） 縣市 0 婺源縣 1 景德鎮(zhèn) 2 樂平市 3 鷹潭市 4 貴溪市 5 德興市 6 上饒市 7 常山縣 8 開化縣 9 黃山市 0 婺源縣 0 1 景德鎮(zhèn) 0 2 樂平市 0 3 鷹潭市 0 4 貴溪市 0 5 德興市 0 6 上饒市 0 7 常山縣 0 8 開化縣 0 9 黃山市 0 數(shù)據(jù)來源 ： 谷歌地圖 然后，形成一初始解， 令 ??iIi? ， ? ?1,2, ,9i? ，最短路徑 2iL? 0ic （ i =1，?， 9），且 600iL? 公里， 載貨 量 iirR? ，且 500ir? ，對 9個客戶點進(jìn)行標(biāo)記 1 2 9 0B B B? ? ? ?，且 B2i? 。 其次， 求節(jié)約里程 。 根據(jù)最短距離表，根據(jù)式 （ 1） 計算 出用戶間的節(jié)約里程 ,并由大到小排列 ， 編制節(jié)約里 程 ijc? 順序 表 ，如 表 5 所示 。 15 表 44 節(jié)約里程順序表 （單位：千米） 連接點 節(jié)約 里程 連接點 節(jié)約 里程 連接點 節(jié)約 里程 連接點 節(jié)約 里程 34 35 14 27 46 12 38 28 36 56 48 18 23 13 79 69 67 37 15 19 24 47 57 17 78 26 58 49 45 25 59 29 68 89 16 39 最后， 按節(jié)約里程從大到小合并路徑 （ 1） 對于 34 :c km?? 34 120 60 180 500 ,rr? ? ? ? ? 3 4 34 3 4186 .7 * 2 170 .3 * 2 340 .6 373 .4 600 , 0L L c k m k m B B? ? ? ? ? ? ? ? ? ?。 故合并 3， 4兩點，則 ? ?1 3 4 1 1 3 4 3 43 , 4 , 1 8 0 , 3