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