（北京物資學院 信息學院，北京 101149）

1 引言

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

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

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

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

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

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

(xi,yi)：第i個中轉油庫的位置坐標；

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

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

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

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

3 算法設計

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

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

3.1 第一階段的算法步驟

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

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

第4步：根據分組以后的結果，計算每組加油站對應的重心點坐標。將每組加油站對應的重心點作為新的中心點，轉第3步。

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

3.2 第二階段的算法

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

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

其中第一項表示從煉油廠到中轉油庫的總運費，第二項表示中轉油庫到該組中各個加油站的總運費。

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

4 算例分析

4.1 小規(guī)模算例

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

表1 煉油廠及加油站位置坐標和需求量

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

表2 油庫位置及服務的加油站序號

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

表3 各個油庫服務的加油站序號

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

4.2 大規(guī)模算例

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

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

表4 油庫位置及服務的加油站序號

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

5 結語

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

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