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

1 引言

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

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

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

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

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

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

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

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

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

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

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

3 算法設(shè)計(jì)

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

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

3.1 第一階段的算法步驟

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

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

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

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

3.2 第二階段的算法

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

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

其中第一項(xiàng)表示從煉油廠到中轉(zhuǎn)油庫(kù)的總運(yùn)費(fèi)，第二項(xiàng)表示中轉(zhuǎn)油庫(kù)到該組中各個(gè)加油站的總運(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點(diǎn)的函數(shù)值，x0是初始參數(shù)，exitfalg是返回算法的終止標(biāo)志，fun是目標(biāo)函數(shù),options設(shè)置優(yōu)化選項(xiàng)參數(shù)。

4 算例分析

4.1 小規(guī)模算例

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

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

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

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

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

表3 各個(gè)油庫(kù)服務(wù)的加油站序號(hào)

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

4.2 大規(guī)模算例

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

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

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

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

5 結(jié)語(yǔ)

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

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