城市配送TSP問題的LINGO求解

徐麗蕊

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

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

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

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

1 城市配送中的TSP問題

城市配送的基本問題[2-3]可以簡化為一輛車從一個配送中心出發為若干需求點的客戶送貨，在現有的城市路網中，選擇合適的線路，安排一個最恰當的順序完成所有客戶的送貨，從而達到既能按時完成任務，同時總成本最小，因此可以用旅行商問題（Traveling Salesman Problem，TSP）來解決。

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

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

2 數學模型的建立

2.1 基本假設

為了建立[3]該問題的數學模型，現做以下假設：

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

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

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

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

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

2.2 數學表述

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

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

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

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

2.3 約束條件

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

3 LINGO求解算法

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

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

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

4 物流配送實例

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

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

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

DATA:

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

ENDDATA

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

圖2 TSP問題的最優解Fig.2 The optimal solution of TSP

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

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

圖3 TSP問題的優化路線Fig.3 The optimal route of TSP

5 結論

1)建立了城市配送中路線優化問題的數學模型；

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

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

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

[1]鄧愛民.城市配送系統優化研究[D].武漢:武漢理工大學,2005.

[2]嚴晨,王直杰.以TSP為代表的組合優化問題研究現狀與展望[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]謝金星,薛 毅.優化建模與 Lindo/Lingo軟件[M].北京:清華大學出版社，2005.

[5]李曉川，朱曉敏，趙乃東.基于Lingo的運輸優化系統設計與開發[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數據導入數據庫的設計實現[J].現代電子技術，2013（12）：71-73.WANG Xu-hui.Design of database to import data from Excel[J].Modern Electronics Technique，2013（12）：71-73.