韋美雁

（湖南科技學院 計算機與通信工程系，湖南 永州 425100）

基于多目標的TSP模型在物流配送中的應用

韋美雁

（湖南科技學院 計算機與通信工程系，湖南 永州 425100）

本文以永州市為例，從配送中心的角度出發(fā)，以時間、費用、距離三個為參數(shù)指標，采用分支定界法建立多目標 TSP模型，然后使用基于粒子群算法的滿意度模型對其進行評價，得到了最佳運輸線路的設計方案，為配送中心設計運輸線路提供理論依據(jù)和實用參考價值。

運輸線路；TSP模型；PSO算法；物流配送

1 問題的提出

20世紀90年代末以來，隨著國民經(jīng)濟的發(fā)展，我國物流業(yè)的發(fā)展勢頭迅速。物流配送中心作為物流供應鏈上的中心環(huán)節(jié)，上連供應商，下連終端客戶，起著舉足輕重的作用。而車輛作為物流配送中心重要的作業(yè)資源，其調(diào)度是否優(yōu)化、行走路徑是否合理，大大影響著物流中心的經(jīng)營成本和服務質(zhì)量。物流配送中心的車輛調(diào)度和運輸路線安排的科學性[1]，直接影響企業(yè)的整體效益。因此，進行物流中心車輛調(diào)度和運輸路線的優(yōu)化研究是十分必要的。本文主要從物流配送中心的角度出發(fā)，考慮車輛調(diào)度和運輸路線的優(yōu)化設計中的距離、費用、時間等多個因素，建立了一個多目標TSP優(yōu)化模型，并把該模型應用于湖南省永州市的物流配送中心車輛調(diào)度和運輸路線的優(yōu)化設計中，為永州市的物流配送中心車輛調(diào)度和運輸路線的優(yōu)化提供理論基礎和參考依據(jù)。

2 多目標TSP模型

2.1 基本多目標TSP數(shù)學模型[2]

TSP是個典型的組合優(yōu)化問題，屬于NP完全問題（NP—Complete）之一。當問題的規(guī)模較大時，很難得到全局最優(yōu)解或滿意解，而且隨著問題規(guī)模的增大，算法的計算時間將以指數(shù)速度增加。

多目標優(yōu)化問題可以描述為求：

式中x為決策向量，y為目標向量，g(x)i為第j個約束，S為決策變量可行解域。本文中對旅游線路進行優(yōu)化決策時，考慮三個指標：距離、時間和費用。其目標函數(shù)描述如下：

其中，xij=l表示從城市i到城市j的路徑，xij=0表示沒有這條路徑，dij為第i個城市到第j個城市的距離，tij為從第i個城市到第j個城市消耗的時間，cij為第i個城市到第j個城市的費用。

2.2 基于PSO算法的滿意度

在求解單目標優(yōu)化時，人們尋找的是一個最好的解，這個解比其它所有的解都要好。當我們求解多目標優(yōu)化問題時，由于有多個目標且存在目標之間的無法比較和沖突現(xiàn)象，要使所有的目標函數(shù)同時達到最大（或最?。┦遣豢赡艿?，一個解可能在其中某個上是最好的，但在其他目標上是最差的，不一定有在所有目標上都是最優(yōu)的解，但是，可以存在這樣的解：對一個或幾個目標函數(shù)不可能進一步優(yōu)化，對其他目標函數(shù)不至于劣化，這樣的解稱之為非劣最優(yōu)解（Pareto optimal）。情況下，最優(yōu)解不只一個，而是一個最優(yōu)解集。多目標算法的工作就是，構(gòu)造非支配集，并使非支配集不斷逼近Pareto最優(yōu)解集，最終達到最優(yōu)。

定義1 對于最小化問題，若'x是搜索空間中一點，當且僅當不存在i（在搜索空間中）使得成立，說'x為非劣最優(yōu)解。

定義2 所有非劣最優(yōu)解組成的集合稱為多目標優(yōu)化問題的最優(yōu)解集（Pareto optimal set），也稱為可接受解集或有效解集。

定義3 通過對各目標進行單目標優(yōu)化來獲得各個目標的最優(yōu)解，將其作為評價多目標優(yōu)化解的指標，稱這些解為理想解。

定義4 多目標優(yōu)化解的滿意度為

其中，mω為慣性權(quán)重，用來調(diào)節(jié)距離、時間、費用三個優(yōu)化目標的相對重要性，為第m個指標的理想解，fm為多目標優(yōu)化得到的第m個指標的解。我們把滿意度較高的解稱為滿意解。

3 TSP模型在永州市物流配送設計中的應用

3.1 模型的實例研究

為了突出配送點的代表性，我們以冷水灘區(qū)為中心，構(gòu)造向其他區(qū)縣配送的車輛調(diào)度和運輸路線。對各區(qū)縣的編號如下：1、冷水灘，2、零陵，3、祁陽，4、東安，5、雙牌，6、道縣，7、寧遠，8、江永，9、江華，10、新田，11、藍山。

實驗中我們假設以汽車為交通工具，交通道路以國道公路和省道公路為主?；贕PS，得到11個區(qū)縣距離矩陣如D所示：

兩兩配送點之間的費用主要由交通、餐飲和住宿所產(chǎn)生，由于餐飲、住宿的不確定性因素很大，可以估算出總費用并將其平均到每個邊上，這樣每個邊的餐飲、住宿費用與所訪問的城市次序無關(guān)，而交通費用與公路等級有關(guān)，因此我們只考慮交通費用，按照國道公路1.0元每公里，省道公路0.5元每公里，結(jié)合距離矩陣，估算出交通費用如矩陣C所示：

由于把路況分為平地和山區(qū)兩種，我們假設平地路段汽車行駛速度為80公里/小時，山區(qū)路段行駛速度50公里/小時估算時間，得到時間矩陣如T所示：

首先用PSO對三個目標的單目標最優(yōu)值進行優(yōu)化，作為對多目標優(yōu)化解的對比標準，即理想解。三個單目標最優(yōu)值如下：

以距離最短為目標，最短距離為628.6公里，配送點訪問次序為：1-3-4-2-5-6-8-9-10-7-11

以費用最少為目標，最少費用為472.5元，配送點訪問次序為：1-4-3-2-5-6-9-8-7-11-10

以時間最短為目標，最少時間為9.05小時，配送點訪問次序為：1-3-4-2-5-6-8-9-7-11-10．

兩目標優(yōu)化時，令兩個慣性權(quán)重相等，都為0.5，結(jié)果如表3.1、表32和表3.3所示：

表3.1 以距離和時間為目標的Pareto最優(yōu)解集

表3.2 以距離和費用為目標的Pareto最優(yōu)解集

表3.3 以時間和費用為目標的Pareto最優(yōu)解集

三個目標一起優(yōu)化時，慣性權(quán)重的選擇不同會產(chǎn)生不同的優(yōu)化結(jié)果，取三個權(quán)重均分區(qū)間[0,1]，即，1ω=0.33，2ω =0.33，3ω =0.34，得到Pareto最優(yōu)解如表3.4所示：

表3.4 三個目標優(yōu)化的Pareto最優(yōu)解集

其中，滿意度最高的解對應的景點訪問次序為：1-4-3-2-5-6-9-8-7-11-10，對應的景點順序為：

冷水灘—東安—祁陽—零陵—雙牌—道縣—江華—江永—寧遠—藍山—新田。

3.2 模型分析

該模型是基于多目標的TSP問題的數(shù)學模型，它主要針對于當前對單目標研究運輸線路中的不足而提出來的，其綜合考慮了距離、時間、費用等因素在模型中的影響，并根據(jù)滿意度評價模型而獲得綜合Pareto最優(yōu)解。最后，我將該模型應用到永州市物流配送中心車輛調(diào)度和運輸路線的優(yōu)化系統(tǒng)中，實現(xiàn)了部分功能，對永州市l(wèi)1個區(qū)縣進行了時間、距離、費用的目標優(yōu)化，得到了較滿意的Pareto最優(yōu)解。為永州市的物流配送中心車輛調(diào)度和運輸路線的優(yōu)化提供了理論依據(jù)和實用價值。但是，該模型還存在著很多不足之處，主要表現(xiàn)在如下：

（1）模型中權(quán)重系數(shù)沒有一個精確地確定方法；

（2）對求多目標模型的考慮因素還不全面，例如交通堵塞、天氣影響行程等。

（3）由于永州市的區(qū)縣較多，因此建模時考慮的配送點數(shù)也較多，沒有考慮配送過程中的休息，有一定的局限性。

如不考慮單線路配送，而考慮分組配送的話應可得到更優(yōu)化的配送線路。

4 結(jié)束語

物流中心配送路徑優(yōu)化問題是一個典型的車輛路徑問題，屬于NP—Complete問題之一。隨著節(jié)點數(shù)的增加，計算量將迅速增大，運用計算機工具和GPS信息是必不可少的。本文根據(jù)物流中心的實際情況，對物流中心的配送問題進行了相對簡單的模型建立和簡化，基于GPS信息靈活運用TSP的求解方式，來解決物流配送中心的車輛分配和運輸路徑的優(yōu)化，得到相對較為優(yōu)化的方案。

[1]齊少安,宋齊軍.基于TSP模型的物流配送中心車輛路徑優(yōu)化[J].郵電設計技術(shù),2006,6,（6）:62-64.

[2]蘇晉榮.基于智能優(yōu)化算法的TSP問題研究及應用[D].山西:山西大學學報,2007,5,22.

Based multi-objective TSP model’s application in Yongzhou city’s logistic distribution

Wei Mei-yan
(Dept. of Computer and Communication engineering, Hunan University of Science and Engineering, YongZhou, 425100, China)

In this paper, from the perspective of logistic center, we take Yongzhou City as an example. To distance, time, cost of indicators, adopting branch and round method to set up a multi-objective TSP model. Afterwards using based PSO algorithm satisfaction of degree model to evaluate satisfaction of degree, got the best design scheme of transportation routes, then provided a theoretical basis and reference for logistic center in mathematical model.

Transportation routes; TSP model; PSO algorithm; logistic distribution

TP39

A

1673-2219（2012）08-0035-04

2012－04－20

項目資助：永州市科技計劃項目。

韋美雁（1974－），女，湖南永州人，副教授，碩士，主要從事應用軟件和地理信息系統(tǒng)研究。

（責任編校：何俊華）