（北京物資學(xué)院 信息學(xué)院，北京 101149）

1 引言

成品油配送分為一次配送和二次配送，一次配送是成品油從煉油廠運(yùn)輸?shù)街修D(zhuǎn)油庫的過程；二次配送指成品油從中轉(zhuǎn)油庫運(yùn)到加油站或最終用戶的過程。中轉(zhuǎn)油庫是連接成品油一次配送和二次配送的重要環(huán)節(jié)。中轉(zhuǎn)油庫選址位置直接影響成品油一次配送和二次配送的物流成本。

針對中轉(zhuǎn)油庫選址問題已有部分學(xué)者開展了研究工作。辜勇等利用重心法研究了單個和多個油庫選址問題[1]；杜樂樂等利用最大覆蓋模型研究了擬建造油庫數(shù)量有限情況下的選址問題[2]；姜玉梅等基于安全環(huán)保角度對擬建油庫的選址和設(shè)計進(jìn)行了研究[3]；吳勤旻等構(gòu)建了一個二層優(yōu)化模型，針對油庫建設(shè)成本和二次運(yùn)輸成本提出了確定理想選址區(qū)域和可行點的相關(guān)方法[4]；米曉芳等研究了考慮碳成本的油庫選址問題[5]；李橫等[6]和張衛(wèi)明等[7]結(jié)合軍用油庫的特殊性，分別研究了基于遺傳算法和基于改進(jìn)粒子群算法的軍用油庫選址優(yōu)化問題。以上研究大部分以成品油二次配送成本極小化為主要目標(biāo)，很少同時考慮成品油一次配送和二次配送總成本，而且以上研究都是從已有的油庫備選點中選擇油庫位置，文獻(xiàn)中尚未發(fā)現(xiàn)關(guān)于不考慮備選點情況下的油庫選址問題的研究結(jié)果。由于實際進(jìn)行油庫選址時可能并沒有現(xiàn)成的油庫備選點，因此有必要在沒有油庫備選點的前提下綜合考慮成品油一次配送和二次配送成本，研究成品油中轉(zhuǎn)油庫選址問題。

本文將在沒有油庫備選點的情況下，同時考慮成品油一次配送和二次配送成本，以擬建油庫位置坐標(biāo)為決策變量、成品油一次配送和二次配送成本和油庫運(yùn)行成本之和極小化為目標(biāo)，建立成品油中轉(zhuǎn)油庫選址問題的混合整數(shù)規(guī)劃模型，并設(shè)計求解模型的兩階段算法，尋求中轉(zhuǎn)油庫的最佳位置。

2 成品油中轉(zhuǎn)油庫選址問題的數(shù)學(xué)模型

成品油中轉(zhuǎn)油庫選址問題可以描述為：在某一地區(qū)有一座煉油廠（序號為0），n個加油站（序號分別為1,2,…,n）。已知煉油廠的位置坐標(biāo)為(a0,b0)，加油站j的位置坐標(biāo)為(aj,bj)，加油站j的需求量為qj,為了建立成品油配送網(wǎng)絡(luò)，擬在該區(qū)域內(nèi)最多建立m個中轉(zhuǎn)油庫。第i個中轉(zhuǎn)油庫建設(shè)費(fèi)用為ci，最大容量為Pi，已知從煉油廠到中轉(zhuǎn)油庫的單位運(yùn)輸費(fèi)為e（元/t·km）, 從中轉(zhuǎn)油庫到加油站的單位運(yùn)輸費(fèi)為h（元/t·km）。問如何選擇中轉(zhuǎn)油庫位置，才能使成品油一次配送和二次配送成本以及中轉(zhuǎn)油庫建設(shè)成本之和最低？

為了建立數(shù)學(xué)模型，定義如下決策變量：

(xi,yi)：第i個中轉(zhuǎn)油庫的位置坐標(biāo)；

fij：從中轉(zhuǎn)油庫i運(yùn)往加油站j的成品油數(shù)量；

ri：從煉油廠運(yùn)往中轉(zhuǎn)油庫i的成品油數(shù)量。

成品油中轉(zhuǎn)油庫選址問題可以表示成如下混合整數(shù)非線性規(guī)劃模型:

目標(biāo)函數(shù)（1）表示極小化成品油一次配送和二次配送成本以及油庫建設(shè)成本之和；約束條件（2）表示滿足各個加油站的需求量；約束條件（3）為中轉(zhuǎn)油庫流量平衡約束；約束條件（4）表示從中轉(zhuǎn)油庫運(yùn)往各個加油站的成品油之和不超過其最大容量限制；約束條件（5）表示中轉(zhuǎn)油庫的建立條件；約束條件（6）-（8）表示變量取值約束。

3 算法設(shè)計

成品油中轉(zhuǎn)油庫選址問題的數(shù)學(xué)模型是一個混合整數(shù)非線性規(guī)劃模型，對于小規(guī)模問題可以直接利用Lingo軟件編程求解，對于大規(guī)模問題直接求解混合整數(shù)非線性規(guī)劃運(yùn)行時間太長，因此需要設(shè)計求解模型的快速有效算法。本節(jié)將根據(jù)成品油中轉(zhuǎn)油庫選址問題數(shù)學(xué)模型的特點，設(shè)計求解問題的兩階段算法。

第一階段：確定擬建立的中轉(zhuǎn)油庫個數(shù)并根據(jù)加油站的位置和需求量將加油站進(jìn)行分組，使得每組加油站恰好由一個中轉(zhuǎn)油庫提供配送服務(wù)。第二階段：根據(jù)煉油廠和每組加油站的信息，確定每個中轉(zhuǎn)油庫的位置坐標(biāo)。

3.1 第一階段的算法步驟

第2步：隨機(jī)選擇K個加油站作為分組的中心點，確定每個分組擬建立的中轉(zhuǎn)油庫容量。

第3步：計算每個加油站到各個中心點的距離，在考慮中轉(zhuǎn)油庫容量限制的前提下按照加油站到中心點的距離由近到遠(yuǎn)將各個加油站劃分到一個最佳的分組中。方法是：對于每一個加油站，首先選擇離其最近的分組，判斷將加油站加入該分組以后，分組中加油站的總需求量是否超過油庫最大容量限制，如果不超過，則將加油站加入該分組，否則考慮下一個分組，直到選擇出一個合適的分組為止。

第4步：根據(jù)分組以后的結(jié)果，計算每組加油站對應(yīng)的重心點坐標(biāo)。將每組加油站對應(yīng)的重心點作為新的中心點，轉(zhuǎn)第3步。

重復(fù)第3、4步，直到分組結(jié)果穩(wěn)定或迭代次數(shù)達(dá)到預(yù)先設(shè)定的最大值。

3.2 第二階段的算法

經(jīng)過第一階段分組之后，每組加油站恰好被劃分到一個分組中，每組加油站恰好可以由一個中轉(zhuǎn)油庫提供服務(wù)。由于每組中包含的加油站位置坐標(biāo)、需求量、煉油廠位置坐標(biāo)等信息均已知，確定各組加油站對應(yīng)的中轉(zhuǎn)油庫最佳位置的問題可以表示成一個無約束優(yōu)化問題。

假設(shè)第k組包含的加油站序號集合為Gk，則第k組加油站的總需求量為，為該組加油站提供服務(wù)的中轉(zhuǎn)油庫最佳位置(xk,yk)是下列無約束優(yōu)化問題的最優(yōu)解：

其中第一項表示從煉油廠到中轉(zhuǎn)油庫的總運(yùn)費(fèi)，第二項表示中轉(zhuǎn)油庫到該組中各個加油站的總運(yùn)費(fèi)。

該模型可以直接利用Matlab優(yōu)化工具箱中的fminunc函數(shù)求解。其調(diào)用格式為[x,fval,exitflag,output]=fminunc('fun',x0,options)；其中fval是返回目標(biāo)函數(shù)在最優(yōu)解x點的函數(shù)值，x0是初始參數(shù)，exitfalg是返回算法的終止標(biāo)志，fun是目標(biāo)函數(shù),options設(shè)置優(yōu)化選項參數(shù)。

4 算例分析

4.1 小規(guī)模算例

某地區(qū)有一個煉油廠（序號為0）和12個加油站（序號為1-12），煉油廠和加油站的位置坐標(biāo)及需求量見表1。各個油庫的最大容量均為40t，每個油庫建設(shè)費(fèi)用為13萬元，從煉油廠到中轉(zhuǎn)油庫的單位運(yùn)輸費(fèi)用為30元/t·km，從中轉(zhuǎn)油庫到加油站的單位運(yùn)輸費(fèi)用為50元/t·km。試確定該地區(qū)的中轉(zhuǎn)油庫位置使得成品油配送總成本最低。

表1 煉油廠及加油站位置坐標(biāo)和需求量

（1）利用Lingo軟件求解混合整數(shù)規(guī)劃模型得到精確最優(yōu)解。首先利用Lingo11.0軟件編程求解混合整數(shù)規(guī)劃模型，程序運(yùn)行100h仍未結(jié)束，手動終止程序，記錄程序運(yùn)行得到的局部最優(yōu)解為：一共需要建立兩個油庫，兩個油庫的位置分別為（8.279 1，5.765 4）和（4.5，5.5），兩個油庫服務(wù)的加油站總需求量分別為34t，40t。建設(shè)兩個油庫及成品油一、二次配送費(fèi)用總和為277 199.6元。各個油庫位置及服務(wù)的加油站序號見表2，其中加油站4同時由兩個油庫提供服務(wù)。

表2 油庫位置及服務(wù)的加油站序號

（2）利用兩階段算法求近似最優(yōu)解。利用兩階段算法求解本例，用matlab編程，在AMD A10-8700P Radeon R6，10 Compute Cores 4C+6G 1.80GHz處理器上運(yùn)行，經(jīng)過0.585s，得到問題的近似最優(yōu)解：共需要建立2個油庫，兩個油庫的位置坐標(biāo)分別為：（4.5，5.5），（6.231 1，7.725 5）；油庫建設(shè)成本和一次配送、二次配送總成本為277 067.754 9元。各個油庫服務(wù)的加油站序號見表3。

表3 各個油庫服務(wù)的加油站序號

比較兩種算法的計算結(jié)果可以看出，一方面，lingo程序求解混合整數(shù)規(guī)劃模型無法在短時間內(nèi)得到全局最優(yōu)解，經(jīng)過100h運(yùn)算得到的仍然是局部最優(yōu)解，兩階段算法的總運(yùn)行時間不足1s，因此兩階段算法具有明顯的計算時間優(yōu)勢；另一方面，兩階段算法得到的近似最優(yōu)解總費(fèi)用比lingo程序運(yùn)算100h得到的局部最優(yōu)解更好，其目標(biāo)函數(shù)值減少了131.845 1元，因此，兩階段算法的計算效果也明顯優(yōu)于直接求解混合整數(shù)規(guī)劃模型的結(jié)果，因此兩階段算法適合大規(guī)模問題的求解。

4.2 大規(guī)模算例

根據(jù)北京地區(qū)100個加油站的位置信息構(gòu)造大規(guī)模算例驗證模型和算法的有效性。100個加油站位置分布情況如圖1所示，各個加油站的需求量取5-20（t）的隨機(jī)數(shù)，煉油廠坐標(biāo)為（116.6,40.2），假設(shè)每個油庫的建設(shè)費(fèi)用均為20萬元，擬建的中轉(zhuǎn)油庫最大容量均為260t，從煉油廠到中轉(zhuǎn)油庫的單位運(yùn)輸費(fèi)用為40元/t·km，從中轉(zhuǎn)油庫到加油站運(yùn)輸費(fèi)用為60元/t·km。

根據(jù)以上數(shù)據(jù)，利用兩階段算法求解，程序運(yùn)行0.74s得到近似最優(yōu)解，該地區(qū)需要建設(shè)5個中轉(zhuǎn)油庫為加油站提供服務(wù)，油庫建設(shè)成本及一、二次配送成本之和為1 021 333.65元，油庫位置及服務(wù)加油站的情況見表4和圖1。由同一個中轉(zhuǎn)油庫服務(wù)的加油站用相同的圖形表示在圖1中，其中實心圖形表示中轉(zhuǎn)油庫，對應(yīng)空心圖形表示油庫所服務(wù)的加油站。從圖1可以看出，由同一個中轉(zhuǎn)油庫服務(wù)的加油站位置較為集中，該結(jié)果與北京地區(qū)實際中轉(zhuǎn)油庫及加油站的分組情況大體一致。

表4 油庫位置及服務(wù)的加油站序號

圖1 北京地區(qū)5個中轉(zhuǎn)油庫的選址位置及服務(wù)的加油站情況

5 結(jié)語

本文研究了中轉(zhuǎn)油庫選址問題，綜合考慮了成品油一次配送、二次配送成本以及中轉(zhuǎn)油庫建設(shè)成本，以中轉(zhuǎn)油庫位置坐標(biāo)為決策變量、總成本極小化為目標(biāo)函數(shù)，建立了混合整數(shù)規(guī)劃模型，并設(shè)計了求解模型的兩階段算法。利用具體算例驗證了模型和算法的有效性，模擬計算結(jié)果顯示，對于小規(guī)模問題，運(yùn)行兩階段算法不足1s就可以得到近似最優(yōu)解，其目標(biāo)函數(shù)值優(yōu)于用lingo軟件直接求解混合整數(shù)規(guī)劃模型運(yùn)行100h得到的局部最優(yōu)解。對于包含100個加油站的大規(guī)模算例，兩階段算法仍然可以在短時間內(nèi)得到近似最優(yōu)解。

本文研究中，僅考慮了一個煉油廠的情況，且沒有考慮煉油廠到中轉(zhuǎn)油庫的道路運(yùn)輸能力限制，實際中可能有多個煉油廠，煉油廠到中轉(zhuǎn)油庫的道路運(yùn)輸能力可能有限制，而且在不同位置建立中轉(zhuǎn)油庫的建設(shè)成本也會有較大的差別，后續(xù)研究中我們將考慮多個煉油廠、道路運(yùn)輸能力限制以及油庫建設(shè)成本與地理位置關(guān)系等因素，建立不同場景下的中轉(zhuǎn)油庫選址問題的數(shù)學(xué)模型，并設(shè)計求解模型的算法，為解決實際問題提供決策依據(jù)。