基于多目標(biāo)的TSP模型在物流配送中的應(yīng)用

韋美雁

（湖南科技學(xué)院 計(jì)算機(jī)與通信工程系，湖南 永州 425100）

基于多目標(biāo)的TSP模型在物流配送中的應(yīng)用

韋美雁

（湖南科技學(xué)院 計(jì)算機(jī)與通信工程系，湖南 永州 425100）

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

運(yùn)輸線路；TSP模型；PSO算法；物流配送

1 問題的提出

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

2 多目標(biāo)TSP模型

2.1 基本多目標(biāo)TSP數(shù)學(xué)模型[2]

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

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

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

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

2.2 基于PSO算法的滿意度

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

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

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

定義3 通過對(duì)各目標(biāo)進(jìn)行單目標(biāo)優(yōu)化來獲得各個(gè)目標(biāo)的最優(yōu)解，將其作為評(píng)價(jià)多目標(biāo)優(yōu)化解的指標(biāo)，稱這些解為理想解。

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

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

3 TSP模型在永州市物流配送設(shè)計(jì)中的應(yīng)用

3.1 模型的實(shí)例研究

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

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

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

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

首先用PSO對(duì)三個(gè)目標(biāo)的單目標(biāo)最優(yōu)值進(jìn)行優(yōu)化，作為對(duì)多目標(biāo)優(yōu)化解的對(duì)比標(biāo)準(zhǔn)，即理想解。三個(gè)單目標(biāo)最優(yōu)值如下：

以距離最短為目標(biāo)，最短距離為628.6公里，配送點(diǎn)訪問次序?yàn)椋?-3-4-2-5-6-8-9-10-7-11

以費(fèi)用最少為目標(biāo)，最少費(fèi)用為472.5元，配送點(diǎn)訪問次序?yàn)椋?-4-3-2-5-6-9-8-7-11-10

以時(shí)間最短為目標(biāo)，最少時(shí)間為9.05小時(shí)，配送點(diǎn)訪問次序?yàn)椋?-3-4-2-5-6-8-9-7-11-10．

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

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

表3.2 以距離和費(fèi)用為目標(biāo)的Pareto最優(yōu)解集

表3.3 以時(shí)間和費(fèi)用為目標(biāo)的Pareto最優(yōu)解集

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

表3.4 三個(gè)目標(biāo)優(yōu)化的Pareto最優(yōu)解集

其中，滿意度最高的解對(duì)應(yīng)的景點(diǎn)訪問次序?yàn)椋?-4-3-2-5-6-9-8-7-11-10，對(duì)應(yīng)的景點(diǎn)順序?yàn)椋?/p>

冷水灘—東安—祁陽—零陵—雙牌—道縣—江華—江永—寧遠(yuǎn)—藍(lán)山—新田。

3.2 模型分析

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

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

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

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

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

4 結(jié)束語

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

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

[2]蘇晉榮.基于智能優(yōu)化算法的TSP問題研究及應(yīng)用[D].山西:山西大學(xué)學(xué)報(bào),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

項(xiàng)目資助：永州市科技計(jì)劃項(xiàng)目。

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

（責(zé)任編校：何俊華）