掃描法在車輛路徑問題中的應(yīng)用

曹茜 文喬

摘 要：隨著經(jīng)濟(jì)的高速發(fā)展，物流行業(yè)發(fā)展也進(jìn)入了加速前進(jìn)的步伐中，而想要在加速前進(jìn)中不被時(shí)代落下，就必須不斷優(yōu)化物流環(huán)節(jié)，使總成本達(dá)到最小化。物流企業(yè)往往會(huì)在車輛路徑的選擇方面進(jìn)行多方面的考慮，文章主要研究了車輛路徑問題，它是運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的研究熱點(diǎn)問題之一。主要通過掃描法來解決車輛路徑問題，其中運(yùn)用了EXCEL的規(guī)劃求解方法。同時(shí)結(jié)合安吉汽車物流有限公司的車輛路徑問題的案例，用掃描法給出了相應(yīng)的最優(yōu)路徑方案。

關(guān)鍵詞：VRP模型；掃描法；規(guī)劃求解

中圖分類號(hào)：U116.2 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： With the rapid development of economy， the development of logistics industry has also entered the pace of accelerating the pace of progress. And we must continue to optimize logistics links， so that the total cost to be minimized and not fall in the era of accelerated advance. The logistics enterprises tend to be considered in the selection operation of the routing. This paper mainly considers the vehicle routing problem， it is one of the hot topics in the field of operations research and combinatorial optimization. The scanning method is used to solve the vehicle routing problem， which includes EXCEL programming solver methods. Meanwhile， the case of the vehicle routing problem for Anji automotive logistics company is given， and the optimal routing is obtained by using scanning method.

Key words： vehicle routing problem； scanning method； programming solver

0 引 言

在物流企業(yè)中，物流運(yùn)輸?shù)某杀編缀跽剂苏麄€(gè)物流環(huán)節(jié)的一半，為了獲取更加可觀的利益，企業(yè)往往會(huì)在運(yùn)行線路的選擇方面進(jìn)行多方面的考慮，由此引申出了車輛路徑問題。

車輛路徑問題（Vehicle Routing Problem， VRP）是1959年[1]由Dantzig和Ramser提出的，它一般是指對(duì)一系列裝貨點(diǎn)和卸貨點(diǎn)，在對(duì)一定的約束條件（如貨物的需求量、車輛的容量限制等）滿足的情況下，組織安排合適的行車路線，使合理的車輛能夠有序地通過它們，達(dá)到一定的理想目標(biāo)（如最短的路程、最少的費(fèi)用成本、最少的時(shí)間成本、最少的車輛使用數(shù)等）。本文通過掃描法來對(duì)具體的安吉物流有限公司的案例進(jìn)行分析求解，掃描法最初是由Gillett和Miller在1974年[2]提出來的，它體現(xiàn)的是一種逐次逼近的方法，下面將給出掃描法的具體思路。

1 掃描法

掃描法的基本原理是從最開始出發(fā)的供貨點(diǎn)向其任意方向的外沿延伸出一條直線，再?gòu)倪@條直線開始通過規(guī)定的順時(shí)針或者逆時(shí)針旋轉(zhuǎn)方式來進(jìn)行旋轉(zhuǎn)，這樣當(dāng)旋轉(zhuǎn)完一周回到原來的位置時(shí)，所有需要配送貨物的點(diǎn)都已經(jīng)經(jīng)過，而在配送過程中車輛的承載貨物不能超過規(guī)定容量，這就形成了分組的辦法。

掃描法步驟：

（1）設(shè)計(jì)一個(gè)極坐標(biāo)系，其中供貨點(diǎn)即最開始出發(fā)的點(diǎn)被當(dāng)做極坐標(biāo)系的原點(diǎn)，再通過將原點(diǎn)與連通圖中出現(xiàn)的任意一個(gè)需求點(diǎn)相連的線的角度作為零度。在極坐標(biāo)系中準(zhǔn)確找到每一個(gè)需求點(diǎn)的位置，并將其通過計(jì)算得出相應(yīng)度數(shù)來轉(zhuǎn)換成極坐標(biāo)系。

（2）對(duì)全部需求點(diǎn)進(jìn)行分組。從零度即最小角度的需求點(diǎn)開始，設(shè)定一個(gè)需求點(diǎn)的集合，然后按照逆時(shí)針的方向，依次旋轉(zhuǎn)將需求點(diǎn)加入到那個(gè)集合內(nèi)，當(dāng)需求點(diǎn)的需求量累計(jì)超過了車輛規(guī)定的容量時(shí)，這個(gè)集合將不再允許加入新的需求點(diǎn)，從而建立一個(gè)新的需求點(diǎn)集合，繼續(xù)逆時(shí)針旋轉(zhuǎn)，對(duì)需求點(diǎn)進(jìn)行收集。

（3）重復(fù)之前的步驟（2），直到所有的需求點(diǎn)都已經(jīng)加入到不同或者相同的組合中為止。

（4）路徑優(yōu)化。當(dāng)所有的分組結(jié)果已經(jīng)出現(xiàn)的時(shí)候，對(duì)于每一個(gè)組的需求點(diǎn)而言，將變成獨(dú)立的旅行商問題（Traveling Salesman Problem，TSP），這就需要進(jìn)行TSP模型分析優(yōu)化，從而得出一個(gè)較合理的優(yōu)化路線。TSP問題可以描述如下：在已知的一個(gè)具有n個(gè)頂點(diǎn)且其中線路連接方式可以有向或無向的網(wǎng)絡(luò)中，被要求通過計(jì)算找出一個(gè)閉合回路，這個(gè)閉合回路必須由起點(diǎn)出發(fā)經(jīng)過所有的頂點(diǎn)后再回到起點(diǎn)。本文用EXCEL的規(guī)劃求解功能來求出相應(yīng)的TSP模型的解。

2 建立模型

安吉汽車物流有限公司成立于2000年8月，是上汽集團(tuán)旗下的全資子公司，它為上海大眾汽車提供穩(wěn)定的配送服務(wù)。大眾汽車根據(jù)各城市之前月份的銷售記錄，對(duì)下一個(gè)月的銷量進(jìn)行預(yù)測(cè)，并且制定出了下一月份需要安吉物流配送的運(yùn)輸訂單量，而安吉物流在接到訂單開始，將需要制定出一份詳細(xì)的配送路線，使運(yùn)輸成本最低，以達(dá)到利潤(rùn)的最大化。其中配送供應(yīng)點(diǎn)為濱州，目前一次能夠配送的能力不超過330千輛，而需要進(jìn)行配送的地區(qū)的需求量和每個(gè)地區(qū)間的距離分別如表1和表2所示。

3 利用掃描法求解

（1）建立極坐標(biāo)系，其中以濱州作為極坐標(biāo)系的原點(diǎn)，得出表3：

（2）對(duì)全部需要配送的城市進(jìn)行分組。首先從零度開始，進(jìn)行逆時(shí)針旋轉(zhuǎn)掃描，可以通過對(duì)位置圖的觀察了解到，第一個(gè)被分組的城市是本溪，此時(shí)配送量Load1為36千輛；繼續(xù)旋轉(zhuǎn)，下一個(gè)被分組的是長(zhǎng)春，此時(shí)Load1=36+63=99千輛，而因?yàn)榕渌土窟€未超過一次性允許配送的荷載能力，故繼續(xù)旋轉(zhuǎn)；下一個(gè)被分組的是北京，此時(shí)Load1=36+ 63+20=119千輛<330千輛，繼續(xù)旋轉(zhuǎn)；下一個(gè)被分組的是滄州，此時(shí)Load1=36+63+20+52=171千輛<330千輛，故繼續(xù)旋轉(zhuǎn)；下一個(gè)被分組的是保定，此時(shí)Load1=36+63+20+52+30=201千輛<330千輛，故繼續(xù)旋轉(zhuǎn)；下一個(gè)被分組的是昌吉，此時(shí)Load1=36+63+20+52+30

+55=256千輛<330千輛，故繼續(xù)旋轉(zhuǎn)；下一個(gè)被分組的是長(zhǎng)治，此時(shí)Load1=36+63+20+52+30+55+65=321千輛<330千輛，故繼續(xù)旋轉(zhuǎn)；下一個(gè)被分組的是成都，此時(shí)Load1=36+63+20+52+30+55+65+86=407千輛>330千輛，所以停止旋轉(zhuǎn)，第一個(gè)分組已經(jīng)得出結(jié)果，即第一組內(nèi)需要經(jīng)過的城市有本溪、長(zhǎng)春、北京、滄州、保定、昌吉、長(zhǎng)治七個(gè)城市。重復(fù)以上步驟，可以得到第二個(gè)組內(nèi)的城市為成都、常德、潮州、巢湖、常州五個(gè)城市。

（3）通過以上的計(jì)算，安吉物流可以安排分別兩個(gè)不同的路徑對(duì)需求城市進(jìn)行配送，其中兩個(gè)路徑中包含的城市分別為：

T■=本溪、長(zhǎng)春、北京、滄州、保定、昌吉、長(zhǎng)治；

T■=成都、常德、潮州、巢湖、常州。

（4）分別對(duì)兩個(gè)組的車輛運(yùn)行路線即TSP問題進(jìn)行規(guī)劃求解。

①對(duì)第一組城市進(jìn)行規(guī)劃求解。首先在EXCEL中輸入城市間距離矩陣的數(shù)據(jù)，如圖1所示：

再建立連通狀態(tài)矩陣如圖2，其中每一個(gè)城市間的連通狀態(tài)由二進(jìn)制來表示，即連通表示為1，不連通表示為0，將最初輸入的值都設(shè)定為0，而因?yàn)槊恳粋€(gè)城市都需要進(jìn)行配送，所以城市經(jīng)過的次數(shù)為1，需要注意的是城市經(jīng)過的次數(shù)為矩陣中對(duì)應(yīng)城市所配送經(jīng)過的總和；此外相同的一個(gè)城市不能相連，即對(duì)角線不能為1。

而為了防止兩個(gè)城市之間雙向互連，輸入了一個(gè)矩陣如圖3，其中的數(shù)值為連通矩陣圖中對(duì)應(yīng)的兩個(gè)城市間的雙向連通情況之和，而這個(gè)和必須小于或者等于1，例如保定到北京的數(shù)值等于連通狀態(tài)矩陣中北京到保定與保定到北京的連通狀態(tài)之和。

根據(jù)設(shè)定連通順序的限制條件，如圖4，其主要原理為：

接入點(diǎn)的順序-接出點(diǎn)的順序+N（城市總個(gè)數(shù)）*所求兩點(diǎn)間的連通狀態(tài)（1為連通、0為不連通）<=N-1，根據(jù)這個(gè)原理，在EXCEL中輸入公式，進(jìn)行計(jì)算。

由于目標(biāo)函數(shù)為各城市的連通順序與連通狀態(tài)，所以還需要設(shè)計(jì)條件所求的連通順序?yàn)檎麛?shù)，且在最小數(shù)1和最大數(shù)8（城市總數(shù)）之間。而在這里還需要設(shè)置一個(gè)目標(biāo)，即最小總路程，最小總路程==SUMPRODUCT（距離矩陣，連通矩陣）。

最后將上述的條件都設(shè)定完成，通過規(guī)劃求解，如圖5所示。

得到的結(jié)果如圖6所示。

故規(guī)劃求解得出的第一組城市的配送路徑為：濱州→滄州→北京→本溪→長(zhǎng)春→昌吉→長(zhǎng)治→保定→濱州，該路線的總里程為7 285km，配送貨物總量為321千輛。

②用上述方法對(duì)第二組城市進(jìn)行規(guī)劃求解，得到第二組城市的配送路徑為：濱州→成都→常德→潮州→巢湖→常州→濱州，該路線的總里程為4 750km，配送貨物總量為274千輛。

4 結(jié)束語

本文闡述分析了掃描法在車輛路徑問題中的運(yùn)用，同時(shí)對(duì)安吉汽車物流有限公司的車輛路徑相關(guān)問題建立了模型，并通過掃描法及使用EXCEL的規(guī)劃求解功能給出了最終求解方案，從而達(dá)到路徑優(yōu)化的目的。

參考文獻(xiàn)：

[1] Dantzig G， Ramser J. The truck dispatching problem[J]. Management Science， 1959（13）：80-91.

[2] Gillett BE， Miller LR. A heuristic algorithm for the vehicle dispatch problem[J]. Operations Research， 1974（22）：340-349.