掃描法在車輛路徑問題中的應用

曹茜 文喬

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

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

中圖分類號：U116.2 文獻標識碼：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è)中，物流運輸?shù)某杀編缀跽剂苏麄€物流環(huán)節(jié)的一半，為了獲取更加可觀的利益，企業(yè)往往會在運行線路的選擇方面進行多方面的考慮，由此引申出了車輛路徑問題。

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

1 掃描法

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

掃描法步驟：

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

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

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

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

2 建立模型

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

3 利用掃描法求解

（1）建立極坐標系，其中以濱州作為極坐標系的原點，得出表3：

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

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

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

T■=本溪、長春、北京、滄州、保定、昌吉、長治；

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

（4）分別對兩個組的車輛運行路線即TSP問題進行規(guī)劃求解。

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

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

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

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

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

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

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

得到的結果如圖6所示。

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

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

4 結束語

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

參考文獻：

[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.