【文章內容簡介】 化，其基本原理、優(yōu)缺點。適用范圍、計算方法如下文介紹。 節(jié)約算法的原理節(jié)約算法（Saving Algorithm）是用來解決運輸車輛數(shù)目不確定的VRP問題，它是目前用來解決VRP模型最有名的啟發(fā)式算法。節(jié)約算法的優(yōu)點：是一種簡便易行的方法，一方面體現(xiàn)出優(yōu)化運輸?shù)倪^程，與一般方法對比縮短了運輸路程；另一方面。它也體現(xiàn)了物流配送網絡的優(yōu)勢，實現(xiàn)了企業(yè)物流活動的整合，而且思路清晰簡單，便于試行。節(jié)約算法的缺點：①過于強調節(jié)約路程，而沒有考慮行程中的時間因素。②不能對顧客的需求進行靈活多變的處理，節(jié)約算法更適合需要需求穩(wěn)定或需求的時間不緊迫，這顯然不能滿足現(xiàn)代多變的市場環(huán)境。節(jié)約算法的核心思想是將運輸問題中存在的兩個回路（0，… ，i，0）和（0，j，… ，0）合并成一個回路（0，… ，i，j，…，0）。在上面的合并操作中，整個運輸問題的總運輸距離會發(fā)生變化，如果變化后總運輸距離下降，則稱節(jié)約了運輸距離。相應的變化值，叫做節(jié)約距離，如式（1）所示。 （1）調整過程如圖21所示。jji 00i 調整前 調整后 圖21 節(jié)約算法的圖像描述 節(jié)約里程算法主要步驟已知條件:需求點集={1,2,…, n},各點需求量,各點間最短距離。第一步,形成一個初始解。確定各車輛配送點集令, =1,2,…,n (先采取單點配送)。第二步,進行節(jié)約度的計算。計算所有點對的節(jié)約度△Cij，然后對計算結果進行升序排列。第三步，進行回路的合并。從升序排列的節(jié)約度序列中的最上面的值開始，直到節(jié)約里程△Cij的隊列空為止,重復下列步驟:按照節(jié)約里程△Cij隊列從大到小的順序,分析客戶i和j之間合并的可能性(是否滿足裝載限制條件、不在同一路徑內以及合并次數(shù)不超過2),將i, j連接起來,即可令。如果不是這樣,則從節(jié)約里程隊列中去除當前的節(jié)約里程，分析下一個客戶對。 改進后的最近插入法TSP模型是單回路運輸問題的最為典型的一個模型，它的全稱是Traveling Salesman Problem1，中文叫做旅行商問題。它是一個典型的NPHard問題，對于大規(guī)模的線路優(yōu)化問題，無法獲得最優(yōu)解。最近插入法就是一種解決此問題的啟發(fā)式算法。最近插入法是Rosenkrantz和Stearns等人在1977年提出的一種用于解決TSP(旅行商)問題的算法?；趨⒖键c的插入法對參考點的選擇有很大的依賴性，一個簡單的改進方法是基于多個隨機參考點進行的多次搜索，進而選出性能最好的解，但這顯然勢必會大大增加搜索量，另外對于大規(guī)模問題參考點的位置的改變對性能的改進也很有限。最近插入法由四步完成：（1）找到最小的節(jié)點，形成一個子回路（subtour）。（2）在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點。（3) 在子回路中找到一條?。╥，j）,使得+最小，然后將節(jié)點插入到節(jié)點，之間，用兩條新的弧(i，k)，（k，j）代替原來的弧（i，j），并將節(jié)點加入到子回路中。（4）重復步驟（2）、（3），直到所有的節(jié)點都加入到子回路中。這樣，子回路就演變?yōu)榱艘粋€TSP的解。由于最近插入法解決的是單回路運輸問題，故在此方法基礎上進行改進和修正，使其能解決多回路運輸VRP問題。有改進的方法如下：（1）找到最小的節(jié)點，形成一個子回路（subtour）。（2）在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點。若此時回路的總貨運量未超過車的載重限制，則繼續(xù)步驟（3），否則，轉（1）尋找新的一條回路。（3）)在子回路中找到一條?。╥，j）,使得+最小，然后將節(jié)點插入到節(jié)點，之間，用兩條新的弧(i，k)，（k，j）代替原來的弧（i，j），并將節(jié)點加入到子回路中。若此時該回路的總路程為未超過車輛的行程限制，則繼續(xù)步驟（4），否則轉步驟（1），尋找新的一條回路。（4）重復步驟（2）和（3），直到每一個節(jié)點都被歸入某一個子回路中。 掃描算法掃描算法（Sweep Algorithm）是Gillett和Miller在1974年首先提出來的，它也是用于求解車輛數(shù)目不限制的CVRP問題。掃描法分為先分組后路徑和先路徑后分組兩種，本文采用的是先分組后路徑的方法。掃描法是一種逐次逼近法，該方法不一定能求得物流配送車輛路勁優(yōu)化問題的最優(yōu)解，但是能有效的求得問題的滿意解。對于某個具體的物流配送車輛路徑優(yōu)化問題，由于存在多種客戶編號方法，當僅選擇一種客戶編號方案用掃描法求解時，其計算量相對較小，但相應的解的質量可能不會很高；當選用多種客戶編號方案用掃描法求解時，一般能得到質量很高的滿意解，但相應的計算量會成倍增加。研究表明，對于物流配送車輛線路優(yōu)化問題，當每條線路上的客戶數(shù)目大體相同且配送路線不太多時，用掃描法求解是非常有效的。掃描算法分四個步驟完成：（1）以起始點作為極坐標系的原點，并以連通圖中的任意一顧客點和原點的連線定義為角度零，建立極坐標系。然后對所有的顧客所在的位置，進行坐標系的變換，全部都轉換為極坐標系。（2）分組。從最小角度的顧客開始，建立一個組，按逆時針方向，將顧客逐個加入等到組中，直到顧客的需求總量超出了負載限制，然后建立一個新的組，繼續(xù)按逆時針方向，將顧客繼續(xù)加入到組中。（3）重復（2）的過程，直到所有的顧客都被分類為止。（4）路徑優(yōu)化。對各個分組內的顧客點，就是一個個單獨的TSP模型的線路優(yōu)化問題，可以用前面介紹的TSP模型的方法對結果進行優(yōu)化，選擇一個合理的線路。第3章 德邦物流配送線路優(yōu)化設計 線路優(yōu)化基礎數(shù)據(jù)處理根據(jù)上文德邦物流的配送線路現(xiàn)狀，我們已知n=9,m=3,W1=7,W2=W3=11，L1=L2=L3=60，令W4 =W5 =W6 =W7 =W8 =W9 =7，L4 =L5 =L6 =L7 =L8 =60下圖31為德邦物流與顧客分布的連通圖0123456879圖31 德邦與顧客點分布的連通圖解：（1）通過各點之間的最短距離計算,我們得到了個點間的最短距離,如下表31中所示：表31 各點間的最短距離表縣市V0V1V2V3V4V5V6V7V8V9V00V10V20V30V40V50