徐麗蕊

（陜西工業(yè)職業(yè)技術學院 汽車與物流學院，陜西 咸陽 712000）

近年來，隨著我國物流業(yè)的快速發(fā)展，城市配送貨物的數(shù)量逐年劇增。作為物流活動最后一公里的配送業(yè)務由于直接面向客戶，直接影響到產(chǎn)品服務與物流服務的整體效率，直接關系到企業(yè)的經(jīng)濟效益和未來發(fā)展，因此，配送活動對企業(yè)尤為重要。同時，由于網(wǎng)上購物、商務活動及生活需求多樣化等帶來的多品種、少批量、多頻次的貨物配送越來越成為配送貨物的主要特征。利用市區(qū)道路，合理地安排配送路線，不僅可以控制物流成本，而且可限制車輛在城市中的運行時間，有效緩解城市交通負擔。以往配送人員根據(jù)經(jīng)驗或城市布局選擇的配送路線，缺乏系統(tǒng)的科學理論和技術指導，其配送效率和經(jīng)濟性急待提高。

因此，如何解決目前多品種、小批量、多頻次且時效性強的直接配送、住宅配送以及“門到門”配送的問題成了解決企業(yè)最終一公里配送（城市配送）的核心問題。

文中擬針對城市配送中最核心的路線優(yōu)化問題，抽象并建立對應的數(shù)學模型，編寫LINGO程序，最終為目前城市配送路線的優(yōu)化問題提供一種快速有效的求解方法。

1 城市配送中的TSP問題

城市配送的基本問題[2-3]可以簡化為一輛車從一個配送中心出發(fā)為若干需求點的客戶送貨，在現(xiàn)有的城市路網(wǎng)中，選擇合適的線路，安排一個最恰當?shù)捻樞蛲瓿伤锌蛻舻乃拓?，從而達到既能按時完成任務，同時總成本最小，因此可以用旅行商問題（Traveling Salesman Problem，TSP）來解決。

旅行商問題（TSP）又譯為旅行推銷員問題、貨郎擔問題，簡稱為TSP問題，是最基本的路線問題，該問題是在尋求單一旅行者由起點出發(fā)，通過所有給定的需求點之后，最后再回到原點的最小路徑成本。最早的旅行商問題的數(shù)學規(guī)劃是由Dantzing（1959）等人提出。TSP問題在物流中的描述是對應一個物流配送公司，欲將n個客戶的訂貨沿最短路線全部送到。如何確定最短路線。該問題是在尋求單一旅行者由起點出發(fā)，通過所有給定的需求點之后，最后再回到原點的最小路徑成本，TSP問題的示意圖如圖1所示。

圖1 TSP問題示意圖Fig.1 Schematic diagram of traveling salesman problem

2 數(shù)學模型的建立

2.1 基本假設

為了建立[3]該問題的數(shù)學模型，現(xiàn)做以下假設：

1)配送中心的位置確定；

2)各客戶的位置和需求量信息已知；

3)該配送中心的車輛容量已知；

4)忽略因自然原因及人為等因素造成的交通堵塞的可能；

5）司機在送貨途中沒有以外情況。

2.2 數(shù)學表述

一個有窮的集合 C={C1，C2，…，Cm}，C1為配送中心，其余為客戶點，對于每一對客戶之間或客戶與配送中心之間d(Ci，Cj)∈R+表示Ci與Cj之間的費用。

該問題的目標函數(shù)為完成一條路線上所有客戶的配送總費用最小，因此可以用下式表示：

其中，d(Ci，Cj)為 Ci到 Cj的費用，它的含義可以是距離、費用、時間等，一般根據(jù)實際情況確定；

X(Ci，Cj)(C為配送中心和客戶點的集合)為決策變量，表示車輛路線上是否從節(jié)點Ci向節(jié)點Cj進行配送，是為1，否則為0。

2.3 約束條件

每個客戶點必須經(jīng)過且只能經(jīng)過一次；路線從配送中心出發(fā)，最終返回配送中心；每個客戶的需求數(shù)量必須全部滿足，且只能由這一臺配送車輛一次完成送貨；配送路徑上各客戶的需求量之和不超過配送車輛的最大載重量；約束條件可以同以下關系來表述：

3 LINGO求解算法

LINGO（Linear Interactive and General Optimizer）即“交互式的線性和通用優(yōu)化求解器”，可以用于線性、非線性規(guī)劃和非線性方程組的求解[4-5]等，功能非常強大，是求解優(yōu)化問題數(shù)學模型的最佳選擇。同時，LINGO能方便的與EXCEL、數(shù)據(jù)庫進行數(shù)據(jù)交換，其內置建模語言提供了十幾個內部函數(shù)，能夠快速求解整數(shù)規(guī)劃問題，方便靈活。根據(jù)上述城市配送業(yè)務中TSP問題的目標函數(shù)、決策變量及約束條件，用LINGO軟件對其參數(shù)和集合做如下定義：

定義配送中心和客戶的集合為C，每個客戶的需求量為Q，某配送車輛到該點時的配送總量U，為了清楚地表示TSP模型中的配送順序以及每兩點間的費用，定義關系集合CXC(C,C)，屬性D表示每兩點間的距離；X=1表示兩點之間有配送車輛通過，X=0表示兩點之間無配送車輛通過。

根據(jù)Lingo軟件的語言語法，將TSP問題目標函數(shù)和約束條件寫成以下程序代碼：MODEL:

4 物流配送實例

選取Solomon測試數(shù)據(jù)R101系列中的配送中心和隨機產(chǎn)生的10個客戶數(shù)據(jù)進行計算，其位置及需求量的數(shù)據(jù)如表1所示，通過LINGO程序求解模型[7]找到最佳的配送先后順序。

表1 配送中心及客戶的相關數(shù)據(jù)Tab.1 The data of distribution center and customer

用語句D=@OLE('E:juli.xls',data1)對各點之間的距離進行初始化，即將EXCEL[8]文件“juli.xls”中的各點之間的距離數(shù)據(jù)賦值給D。數(shù)據(jù)初始化的LINGO代碼如下：

DATA:

D=@OLE('E:juli.xls',data1);

ENDDATA

運行以上程序，可以求得最優(yōu)化結果如圖2所示。

圖2 TSP問題的最優(yōu)解Fig.2 The optimal solution of TSP

由圖2可知，通過LINGO編程對TSP問題進行優(yōu)化計算，用時不到1 s，即可求得該問題的全局最優(yōu)解，其總成本為151.1，其對應的配送客戶的先后順序如下：

最佳配送路線為：配送中心→客戶7→客戶6→客戶9→客戶8→客戶11→客戶10→客戶4→客戶2→客戶5→客戶3→客戶1→配送中心，如圖3所示。

圖3 TSP問題的優(yōu)化路線Fig.3 The optimal route of TSP

5 結論

1)建立了城市配送中路線優(yōu)化問題的數(shù)學模型；

2)模型的建立不僅考慮了達到送貨路線最短，同時要求車輛最終要返回配送中心，實現(xiàn)了配送路線的閉合，為再次配送提供了方便，最終達到降低配送成本，提高配送效率的目的。

3)根據(jù)LINGO軟件的語法特點，編寫了求解TSP模型的程序代碼，為該類問題的求解提供了一種有效的思路；

4)實例表明，該模型及LINGO程序求解一般的路線優(yōu)化問題快速且高效。

[1]鄧愛民.城市配送系統(tǒng)優(yōu)化研究[D].武漢:武漢理工大學,2005.

[2]嚴晨,王直杰.以TSP為代表的組合優(yōu)化問題研究現(xiàn)狀與展望[J].計算機仿真,2007,24(6):171-174.YAN Chen,WANG Zhi-jie.Study on combinatorial optimization problem represented by TSP:Recent Research Work and Perspective[J].Computer Simulation,2007,24(6):171-174.

[3]周康,強小利,同小軍，等.求解TSP算法[J].計算機工程與應用,2007,43(29):43-47.ZHOU Kang,QIANG Xiao-li,TONG Xiao-jun,et al.Algorithm of TSP[J].Computer Engineering and Applications,2007,43(29):43-47.

[4]謝金星,薛 毅.優(yōu)化建模與 Lindo/Lingo軟件[M].北京:清華大學出版社，2005.

[5]李曉川，朱曉敏，趙乃東.基于Lingo的運輸優(yōu)化系統(tǒng)設計與開發(fā)[J].物流技術,2010(210-211):106-109.LI Xiao-chuan,ZHU Xiao-min,ZHAO Nai-dong.Design and development of optimized transportation system based on Lingo[J].Logistics Technology,2010(210-211):106-109.

[6]戴宗瑞.TSP問題在物流配送車輛運行路線中的應用分析[J].軟件導刊,2012,11(6):93-95.DAI Zong-rui.The application analysis of logistics distribution vehicle traveling route for TSP problem [J].Software Guide,2012,11(6):93-95.

[7]周俊.Cayley圖在比較模型下的可診斷性 [J].電子科技，2015（1）：89-92.ZHOU Jun.Diagnosability of Cayley graphs generated by transposition trees under the comparison diagnosis model[J].Electronic Science and Technology，2015（1）：89-92.

[8]王旭輝.Excel數(shù)據(jù)導入數(shù)據(jù)庫的設計實現(xiàn)[J].現(xiàn)代電子技術，2013（12）：71-73.WANG Xu-hui.Design of database to import data from Excel[J].Modern Electronics Technique，2013（12）：71-73.