一類基于客戶滿意的LRP問題研究

吳建文，孫桂林（北京交通大學(xué)，北京 100044）

隨著全球貿(mào)易的快速增長，集成化物流管理的概念被越來越多的企業(yè)所接受，提高分銷效率成為了企業(yè)在激烈的競爭中，獲得戰(zhàn)略制高點(diǎn)的必由之路。定位—運(yùn)輸路線安排問題（LRP問題）相對與獨(dú)立的定位—配送問題（LA問題）和運(yùn)輸路線安排問題（VRP）更貼近目前的集成化物流管理系統(tǒng)的實(shí)際特征，對其研究有很大現(xiàn)實(shí)的意義[1]。

1 定位—運(yùn)輸路線安排問題（LRP）的定義及研究現(xiàn)狀

1.1 定位—運(yùn)輸路線安排問題（LRP）的定義

運(yùn)輸路線安排問題（Location-Routing Problem，LRP）可以表示為給定與實(shí)際問題相符的一系列潛在的設(shè)施點(diǎn)，在這些潛在的點(diǎn)中確定出一系列的設(shè)施位置，同時(shí)要確定出一套以各個(gè)設(shè)施到各個(gè)客戶點(diǎn)的運(yùn)輸路線，確定的依據(jù)是滿足問題的目標(biāo)（通常是總的費(fèi)用最小）?？蛻酎c(diǎn)的位置和客戶的需求量是已知的或可估算的，貨物有一個(gè)或多個(gè)設(shè)施點(diǎn)位置已知，問題的目標(biāo)是把那些潛在的設(shè)施建立起來，以使總的費(fèi)用最小[2]。

1.2 LRP問題的研究現(xiàn)狀

國外，在20世紀(jì)70年代初期就開始了對LRP問題的研究。Cooper[4]把定位問題與運(yùn)輸問題結(jié)合起來，提出了運(yùn)輸—定位問題（Transportation-Location problem），降低了運(yùn)輸成本。Tapiero[5]于1971年改善了Cooper的研究工作，把時(shí)間的復(fù)雜度引入普通運(yùn)輸定位模型中。到了70年代中期，Watson-Gandy和Dohrn[6]將運(yùn)輸車輛多點(diǎn)停留特性與定位運(yùn)輸網(wǎng)絡(luò)結(jié)合起來開展了研究。后來Bookbinder和Reece[7]定義了三層多商品配送體系，建立了非線性混合整數(shù)規(guī)劃模型，并將問題分解為定位配給和運(yùn)輸問題兩部分。

我國對定位—運(yùn)輸路線安排問題的研究是在20世紀(jì)90年代后期才慢慢開始興起，比國外滯后了30多年。現(xiàn)在對于問題的研究依舊處于起步階段。汪壽陽，趙秋紅[3]等是較早在國內(nèi)開始LRP問題研究的學(xué)者，在其論文中詳細(xì)介紹了國外對于集成物流管理系統(tǒng)中LRP問題的研究進(jìn)展，分析了的主要內(nèi)容和特征，提出有關(guān)求解問題的算法分類，并對以后該領(lǐng)域的研究方向提出了幾點(diǎn)建議，該文獻(xiàn)對我國在該領(lǐng)域的研究起了指引作用。張潛，高立群等[8]從算法優(yōu)化的角度出發(fā)，對LRP問題中的定位配給、運(yùn)輸車輛路線安排、定位—運(yùn)輸路線安排三類問題的具體優(yōu)化方法進(jìn)行了分析和比較，并在此基礎(chǔ)之上提出兩階段啟發(fā)式算法來求解LRP問題。張長星等采用遺傳算法來求解定位—運(yùn)輸路線安排問題。其特點(diǎn)在于沒有采用普遍的兩階段求解的思路，而是將其看作一個(gè)整體進(jìn)行求解，避免了在求解過程中出現(xiàn)局部最優(yōu)解的情況，為求解LRP問題和其他相關(guān)大規(guī)模組合優(yōu)化問題提出了一條新的思路。黃春雨等建立了以縮短物流多階響應(yīng)周期和成本優(yōu)化為目標(biāo)的多目標(biāo)模型。與其他模型所不同的是，在該模型之中加入了對不同運(yùn)輸方式的選擇，同時(shí)在成本計(jì)算時(shí)，考慮了訂貨成本和分揀中心的處理成本。李鑫麗[9]建立了以準(zhǔn)時(shí)到達(dá)和總成本最小的多目標(biāo)模型，并在此基礎(chǔ)上加入了逆向物流的概念，從定位、路線選擇、回收幾個(gè)方面綜合對LRP問題進(jìn)行了研究，取得了很好的效果。

通過上述分析，我們發(fā)現(xiàn)國內(nèi)對問題的研究具有以下一些特點(diǎn)：

（1）起步較晚，研究的團(tuán)體不多，所取得的成果也較少；

（2）主要集中于算法的研究上，理論性較強(qiáng)；

（3）對于模型的構(gòu)造多以單目標(biāo)為主，以及運(yùn)用模型來解決實(shí)際問題的研究則較少。

2 LRP模型的建立

2.1 建模思想

在傳統(tǒng)的多目標(biāo)LRP問題研究中，主要從準(zhǔn)時(shí)到達(dá)和總成本最小或者利潤最大的角度對問題進(jìn)行研究，取得了非常好的效果。實(shí)際上，作為物流商，配送貨物到客戶的主要目的就是讓客戶滿意，不光是準(zhǔn)時(shí)到達(dá)就能讓客戶滿意，準(zhǔn)時(shí)到達(dá)只是客戶滿意的一個(gè)方面，象產(chǎn)品質(zhì)量、包裝、是否和要求相符等一系列指標(biāo)都是客戶是否滿意的衡量指標(biāo)。本文就從客戶滿意和利潤最大的角度對LRP問題進(jìn)行研究。

2.2 模型的建立

本文建立一個(gè)最基本的三級模型（如圖1），其中A為生產(chǎn)廠家，B為配送中心，C為客戶，帶箭頭的連線為貨物流動(dòng)方向。

圖1 一個(gè)三級物流鏈模型

本文LRP模型做如下假設(shè)：

（1）客戶的需求量一定且為已知；

（2）有多個(gè)潛在的配送中心，如果能滿足約束條件

則建立配送中心，否則不建立配送中心；

（3）配送中心之間不存在相互配送；

（4）一個(gè)客戶只接受一輛車的服務(wù)；

（5）一輛車從一個(gè)配送中心出發(fā)并且在配送過程中不再經(jīng)過任何配送中心；

（6）生產(chǎn)地A能滿足客戶C的需求；

（7）配送中心的選擇與其固定投資無關(guān)；

（8）配送中心無容量限制；

（9）任意兩點(diǎn)之間單位運(yùn)輸成本相同。

2.3 數(shù)學(xué)模型的建立

2.3.1 模型中參數(shù)的含義

S1＝｛si/ 1 ≤i≤I｝為潛在的物流中心點(diǎn)的集合；S2=｛sj/I+1≤j≤I+J｝為需要物流服務(wù)的客戶節(jié)點(diǎn)；S=｛S1｝∪｛S2｝為潛在物流中心節(jié)點(diǎn)與客戶節(jié)點(diǎn)數(shù)的總和；V=｛vk/1 ≤k≤K｝為物流中心擁有的車輛的集合；Fi為在i（i=1,2,…,I）處建立物流中心的成本；Wi為在i（i=1,2,…,I）處建立物流中心的運(yùn)營成本；Zi（?i∈ G）表示是否在i處建立物流中心，如果是，則Zi=1，否則便為零；dij為從物流中心節(jié)點(diǎn)i到客戶節(jié)點(diǎn)j的距離；Qk為車輛k的容量；xijk（i∈S1,j∈S,k∈V,i≠j）表示車輛k是否從節(jié)點(diǎn)i到節(jié)點(diǎn)j，如果是，則xijk=1，如果否，則為零；e為客戶對產(chǎn)品的期望滿意度，按照Parasuraman A等提出的7點(diǎn)標(biāo)定法標(biāo)定客戶滿意度，分別為：非常滿意（very satisfied 7），滿意（satisfied 6），稍滿意（somewhat satisfied 5），中立（mid-level 4），稍不滿意（somewhat dissatisfied 3），不滿意（dissatisfied 2），非常不滿意（very dissatisfied 1）。我們?nèi)〉膃值為集合｛非常滿意7，滿意6，稍滿意5｝中元素。qj（e）為客戶j的物流需求量，與e成正比；任意兩節(jié)點(diǎn)之間的平均單位運(yùn)輸成本為C（e）；

2.3.2 建立模型

目標(biāo)函數(shù)是：

約束條件為：

模型中各式的簡要說明：目標(biāo)函數(shù)表示對總成本求極小值，式（1）中第1項(xiàng)表示運(yùn)輸成本，第2項(xiàng)表示建設(shè)和運(yùn)營物流中心所需的成本；約束條件中式（2）表示每個(gè)客戶僅有一輛車提供服務(wù)；式（3）表示每輛車配送的客戶需求量之和不超過其裝載量；式（4）保證運(yùn)輸路線具有空間連續(xù)性；式（5）保證能配送到任何一個(gè)客戶；式（6）保證每輛車的運(yùn)輸路線都源自于物流中心；式（7）表示每輛車的運(yùn)輸路線上只能有一個(gè)物流中心；式（8）表示客戶滿意度的取值范圍。

3 基于客戶滿意的LRP模型的優(yōu)化求解

3.1 指導(dǎo)思想

通常，物流配送系統(tǒng)的LRP包含選擇配送中心、選擇運(yùn)輸車輛、確定車輛配載、選擇行車路線、確定發(fā)車時(shí)間等幾個(gè)方面的規(guī)劃問題，因此在解決這些問題的時(shí)候，采用分而治之的解決思路。即把整個(gè)LRP分解成幾個(gè)子問題，先考慮各個(gè)子問題的解決方法，然后再考慮問題的整體性，綜合起來就得到問題的解決方法。為了簡化起見，將本文研究的LRP問題分解為以下兩個(gè)子問題：一是配送中心的分派子問題，二是車輛運(yùn)行路線安排子問題。其中配送中心的分派子問題是指選擇出貨物配送中心的問題，求所有客戶點(diǎn)對于配送中心的一個(gè)分派（即確定客戶應(yīng)該歸屬于那個(gè)配送中心）；車輛運(yùn)行路線安排子問題是在選擇配送中心子問題的基礎(chǔ)上進(jìn)一步安排每個(gè)選定的配送中心的車輛問題。這包括決定每個(gè)配送中心將采用哪幾輛車參加運(yùn)貨；每輛車裝載那幾個(gè)客戶的貨物；每輛車的發(fā)車時(shí)間以及行車路線等。

對LRP進(jìn)行分解之后，這兩個(gè)子問題不是彼此孤立的，而是密切聯(lián)系的。此LRP問題是一個(gè)整數(shù)規(guī)劃問題，對它進(jìn)行分解的目的是為了求解方便。分解后的子問題之間是緊密聯(lián)系在一起的。車輛運(yùn)行路線安排子問題是在選擇配送中心子問題的基礎(chǔ)上進(jìn)行求解的，只有在選擇配送中心子問題之后，車輛運(yùn)行路線安排子問題才能進(jìn)行求解。解決選擇配送中心子問題的關(guān)鍵是使車輛運(yùn)行路線安排子問題的求解結(jié)果最優(yōu)，使整個(gè)問題求解的資源消耗盡量小，各個(gè)子問題的求解過程是循環(huán)遞進(jìn)的。當(dāng)選擇配送中心子問題解決后，得到的結(jié)果除了選定的點(diǎn)之外，還有在構(gòu)建配送中心子問題的啟發(fā)函數(shù)時(shí)考慮車輛運(yùn)行路線，即解決分配問題。在這個(gè)基礎(chǔ)上，解決車輛運(yùn)行路線問題，就是決定每個(gè)配送中心中的每輛車裝載那幾個(gè)客戶的貨物、何時(shí)發(fā)車、車輛如何行使（即行車路線安排）等問題[10]。

3.2 問題求解的兩階段啟發(fā)式算法

對于配送中心分派子問題的求解步驟，一般情況下，客戶應(yīng)該由距離其最近的配送中心供貨才是最合理的。當(dāng)貨運(yùn)量一定且客戶的信息確定后，就可以把N個(gè)客戶按照就近原則分配給M個(gè)配送中心。計(jì)算方法是通過求每個(gè)客戶點(diǎn)到每個(gè)配送中心的距離，然后取其距離的最小值，由此確定的啟發(fā)函數(shù)如下：

其中Lij是客戶j到配送中心i的距離。這樣，第一階段的如何分配配送中心子問題就解決了。對于已經(jīng)分派的配送中心和其要配送的用戶，采用遺傳搜索算法搜尋優(yōu)化運(yùn)輸路線。

遺傳算法（Genetic A lgorithm,GA）是20世紀(jì)60～70年代美國密歇根大學(xué)的霍蘭德（Holland）教授及其學(xué)生莫伊生物進(jìn)化機(jī)制發(fā)展起來的優(yōu)化搜索算法，該算法將操作對象看做是一個(gè)生物群體，經(jīng)過多代進(jìn)化后選擇出優(yōu)秀個(gè)體作為系統(tǒng)的最優(yōu)解[11]。本系統(tǒng)個(gè)體是由M個(gè)子串構(gòu)成，客戶號采用自然數(shù)編碼，即敘述編碼，對于長度為n的染色體，每位在1到n中取互不相同的值，對于車輛調(diào)度問題，設(shè)配送中心序號從1到M，依次對各客戶點(diǎn)編號形成染色體，該染色體表示了車輛調(diào)度，路線安排等各種信息，例如染色體5655315，表示一條路線是從配送中心點(diǎn)5出發(fā)，依次經(jīng)過客戶6、5后，回到配送中心5；另一條路線從該配送中心出發(fā)，依次經(jīng)過客戶5、3、1后，回到配送中心5。

染色體的適應(yīng)度是反映染色體性能優(yōu)劣的唯一指標(biāo)，適應(yīng)度越大，表明在以后遺傳中存活幾率就越大，車輛運(yùn)輸路線的染色體適應(yīng)度是根據(jù)其目標(biāo)函數(shù)得到，對于遺傳編碼中個(gè)體k的適應(yīng)度fk為：

則個(gè)體k被選中的概率為：

其中L是群體大小數(shù)，通過計(jì)算染色體的選擇概率產(chǎn)生0～1的隨機(jī)數(shù)，選中對應(yīng)的染色體，并復(fù)制到下一代。

染色體的交叉和變異算子都局限在子串內(nèi)進(jìn)行。交叉體現(xiàn)了有性繁殖，用于組合出新個(gè)體，交叉操作采用部分映射交叉和類似OX交叉相結(jié)合；變異操作采用啟發(fā)式變異，過程為：對于需要變異的染色體，隨機(jī)選出λ個(gè)基因，列出所有選出基因的可能換位產(chǎn)生的領(lǐng)域，評估所有的領(lǐng)域點(diǎn)，選出最好的作為變異產(chǎn)生的后代進(jìn)行車輛優(yōu)化的變異操作。

4 算例分析

有4個(gè)待選配送中心和8個(gè)客戶節(jié)點(diǎn)。選擇出合適的配送中心并給出車輛配送路線。

首先，對配送中心和客戶進(jìn)行編號，其中1～8表示客戶，9～12表示配送中心。配送中心和客戶、配送中心之間、客戶之間的最短距離以及配送中心的建設(shè)和運(yùn)營費(fèi)用及客戶的配送需求量見表1。采用同種型號的車輛，且容量為8t，車輛的單位平均運(yùn)輸成本為2元/t·km。

表1 基本參數(shù)數(shù)據(jù)

其計(jì)算步驟為：

（1）根據(jù)客戶應(yīng)該由距離其最近的配送中心供貨才是最合理的原理，首先找出確定每一個(gè)客戶由對應(yīng)的配送中心配送。

（2）設(shè)定群體規(guī)模n=8,交叉概率Pc=0.7,變異概率Pm=0.005。

（3）計(jì)算每一條配送線路的適應(yīng)度值。

（4）遺傳操作（選擇適應(yīng)度值大的個(gè)體保留，按照一定概率進(jìn)行交叉和變異操作）。

通過編制MATLAB程序[12]對該算例進(jìn)行求解，最后得到的結(jié)果為（9 1 3 4 10 8 10 2 5 11 6 7），即編號為9 10 11的配送中心按照一定的車輛路徑所構(gòu)成的物流通道為客戶提供物流服務(wù)的費(fèi)用最小。

5 結(jié)束語

目前我國物流服務(wù)業(yè)整體水平不高，對于物流網(wǎng)絡(luò)的優(yōu)化研究主要還停留在對成本優(yōu)化的階段。本文從成本和客戶滿意兩個(gè)角度建立了基于客戶滿意、總成本最低的多目標(biāo)優(yōu)化LRP數(shù)學(xué)模型，然后用啟發(fā)式兩階段法對模型求解。希望本文提出的模型可以為企業(yè)物流配送問題提供一些有益的啟示。

[1]張潛，高立群，胡祥培.集成化物流中的定位—運(yùn)輸路線安排問題（LRP）優(yōu)化算法評述[J].東北大學(xué)學(xué)報(bào)，2003,24(1):31－32.

[2]林巖，胡祥培，王旭茵.物流系統(tǒng)優(yōu)化中的定位—運(yùn)輸路線安排問題（LRP）研究評述[J].管理工程學(xué)報(bào)，2004，18（4）：45－46.

[3]汪壽陽，趙秋紅，夏國平.集成物流管理系統(tǒng)中的定位—運(yùn)輸線路安排問題的研究[J].管理科學(xué)學(xué)報(bào)，2000,3(2):69－75.

[4]Leon Cooper.An efficient heuristic algorithm for the transportation－location problem[J].Journal of Regional Science,1976,16(3):305－309.

[5]Tapiero C S.Transportation－location－allocation problems over time[J].Journal of Regional Science,1971,11(3):377－384.

[6]Watson－Gandy C,Dohrn P.Depot location with van salesman－A practical approach[J].Omega,1973,1(3):321－329.

[7]Bookbinder J H,Reece K E.Vehicle routing considerations in distribution system design[J].European J of Operation Research,1988,37(2):204－213.

[8]張潛，高立群，劉雪梅,等.定位—運(yùn)輸路線安排問題的兩階段啟發(fā)式算法控制與決策[J].控制與決策，2004,19(7):773－777.

[9]李鑫麗.LRP及其圖論模型研究[D].南京：南京信息工程大學(xué)（碩士學(xué)位論文），2007.

[10]郭伏，王紅梅，羅丁.城市物流配送系統(tǒng)的多目標(biāo)優(yōu)化LRP模型研究[J].工業(yè)工程管理，2005(5):3－4.

[11]程賜勝，蒲云虎，王正武.高速公路物流網(wǎng)絡(luò)規(guī)劃LRP模型及算法研究[J].長沙交通學(xué)院學(xué)報(bào)，2008,24(1):37－43.

[12]王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.