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