成品油配送路徑優(yōu)化問(wèn)題研究

金驍

[摘要]成品油配送路徑優(yōu)化問(wèn)題是指在加油站需求量已知的情況下，石油公司利用多種型號(hào)的油罐車，從油庫(kù)出發(fā)為各個(gè)加油站配送成品油以滿足各個(gè)加油站需求的路徑優(yōu)化問(wèn)題。文章主要研究某石油公司的成品油配送車輛調(diào)配和路徑規(guī)劃問(wèn)題，在車輛數(shù)量充足、每輛車需從油庫(kù)出發(fā)在完成供油任務(wù)后回到油庫(kù)的前提下，考慮車輛的容量限制、加油站需求量、需求時(shí)間窗、卸油服務(wù)時(shí)間等條件，以系統(tǒng)運(yùn)行成本的最小化為目標(biāo)建立相應(yīng)問(wèn)題的數(shù)學(xué)模型。然后，利用1個(gè)油庫(kù)、10個(gè)加油站的算例對(duì)模型的正確性進(jìn)行了驗(yàn)證。

[關(guān)鍵詞]成品油配送；路徑優(yōu)化；時(shí)間窗；數(shù)學(xué)模型

[DOI]1013939/jcnkizgsc201718184

1引言

庫(kù)存和運(yùn)輸是物流系統(tǒng)最重要的功能要素，是物流獲得“時(shí)間價(jià)值”和“空間價(jià)值”的兩大主要環(huán)節(jié)，它們的耗費(fèi)約占物流總成本的2/3。[1]庫(kù)存路徑問(wèn)題主要是研究一個(gè)供應(yīng)商向多個(gè)顧客提供配送服務(wù)時(shí)，在滿足顧客的需求量、配送時(shí)間窗以及庫(kù)存容量限制等約束條件的情況下，使總成本達(dá)到最小。BirgerRaa[2-3]等人于2007年在研究庫(kù)存路徑問(wèn)題（Inventory Routing Problem）時(shí)，假設(shè)顧客的需求率是恒定的，在不引起缺貨的情況下，以平均配送和庫(kù)存成本最小化為目標(biāo)得出周期性補(bǔ)貨策略，并運(yùn)用粒子群算法對(duì)該模型進(jìn)行了求解。2008年又在模型中加入了車輛使用成本，同時(shí)運(yùn)用插入遺傳算法對(duì)模型分步進(jìn)行求解。Kunpeng Li[4]等人在解決成品油配送問(wèn)題時(shí)，考慮車輛容載量、加油站庫(kù)存容量、車輛數(shù)量等因素的情況下以最大路徑遍歷時(shí)間的最小化為目標(biāo)函數(shù)建立數(shù)學(xué)模型，并設(shè)計(jì)了禁忌搜索算法。趙達(dá)[5]等人在2006年以零售商系統(tǒng)下隨機(jī)需求的IRP為研究對(duì)象，提出了一種基于馬爾科夫決策過(guò)程與修正的C-W節(jié)約算法的啟發(fā)式分解算法。我們?cè)?016年以工作量均衡為目標(biāo)，研究了帶硬時(shí)間窗約束的成品油二次配送路徑優(yōu)化問(wèn)題，建立了整數(shù)規(guī)劃模型并設(shè)計(jì)了求解模型的算法。[6]

成品油配送問(wèn)題是一種典型的庫(kù)存路徑問(wèn)題，由于各個(gè)加油站的成品油均儲(chǔ)存在容量有限的油罐中，為加油站配送成品油的車輛也是特定的油罐車，為了滿足加油站的日常銷售，油庫(kù)需要每天向加油站配送成品油，才能保證銷售過(guò)程中不出現(xiàn)斷貨。在研究成品油庫(kù)存路徑問(wèn)題時(shí)，如果加油站的銷售速率為常數(shù)，則可以根據(jù)加油站當(dāng)前的存儲(chǔ)量確定出一段時(shí)間內(nèi)的需求量，進(jìn)一步根據(jù)配送車輛的容量以及油罐的容量限制，確定出配送時(shí)間窗。這種條件下成品油配送庫(kù)存路徑問(wèn)題就簡(jiǎn)化成了帶容量和時(shí)間窗限制的車輛路徑問(wèn)題。本文主要研究簡(jiǎn)化以后的成品油配送車輛路徑優(yōu)化問(wèn)題，建立該問(wèn)題的數(shù)學(xué)模型并設(shè)計(jì)求解模型的蟻群算法。

2問(wèn)題描述

成品油的配送路徑優(yōu)化問(wèn)題可以描述為：有一個(gè)油庫(kù)，同時(shí)向多個(gè)加油站提供某一種型號(hào)的成品油；已知加油站在某一時(shí)間段內(nèi)對(duì)成品油的需求量；每個(gè)加油站有對(duì)應(yīng)的硬時(shí)間窗，成品油配送車輛不能早于也不能晚于加油站時(shí)間窗進(jìn)行供油；配送車輛在每個(gè)加油站卸油均需要消耗一定的時(shí)間；為加油站配送成品油的油罐車為單艙車，且油罐車的數(shù)量充足；每輛油罐車的容載量、固定使用成本、單位距離行駛成本均不相同；每輛車可以同時(shí)向多個(gè)加油站供油，每個(gè)加油站只能接受一輛油罐車為其供油；每輛油罐車的平均行駛速度相同，均為50km/h。系統(tǒng)的目標(biāo)就是在已知各個(gè)加油站的需求量以及相互之間的距離的情況下，求使得系統(tǒng)總運(yùn)行成本最小的配送方案。

在成品油配送過(guò)程中，假設(shè)配送車輛從油庫(kù)出發(fā)為若干個(gè)加油站配送成品油，完成配送任務(wù)后返回油庫(kù)。同一輛配送車服務(wù)的若干個(gè)加油站的總需求量不能超過(guò)車輛的容載量。由于每個(gè)加油站只能接受一輛油罐車為其供油，因此為加油站供油的油罐車在該加油站的卸油量與加油站的需求量相等。油罐車在到達(dá)加油站時(shí)開始卸油，開始卸油的時(shí)刻應(yīng)處于該加油站的時(shí)間窗內(nèi)。每輛車在卸油時(shí)會(huì)耗費(fèi)一定的時(shí)間，卸油耗費(fèi)的時(shí)間與卸油量成正比，且當(dāng)車輛在一個(gè)加油站完成卸油時(shí)會(huì)立即駛往下一個(gè)加油站。

由于油庫(kù)的車輛數(shù)量充足以及每輛車的容量、固定成本及可變成本不同，因此，需要從可用車輛中選擇一部分為加油站送油，并進(jìn)一步確定出每一輛油罐車服務(wù)的加油站集合及配送路徑，使得總配送成本最低。每輛選中的油罐車的配送路徑可以用油庫(kù)及加油站的序號(hào)按照配送順序依次表示。如0-1-5-3-0表示一輛配送車輛從油庫(kù)0點(diǎn)出發(fā)，依次為加油站1、5、3配送成品油，配送結(jié)束后返回油庫(kù)。

5結(jié)論

成品油配送路徑優(yōu)化問(wèn)題是成品油二次配送過(guò)程中的關(guān)鍵的問(wèn)題。當(dāng)制訂成品油配送計(jì)劃時(shí)，在保證加油站不斷油的情況下，降低配送成本是最主要的考慮因素之一。本文研究了各個(gè)加油站的需求量確定的情況下，在滿足各個(gè)加油站需求量及服務(wù)時(shí)間窗限制的前提下，使系統(tǒng)的運(yùn)行成本最低的成品油配送路徑優(yōu)化問(wèn)題。建立了以系統(tǒng)總運(yùn)行成本最低為目標(biāo)的整數(shù)規(guī)劃模型，最后通過(guò)算例對(duì)模型進(jìn)行了驗(yàn)證。

本文只考慮了確定需求下單一品種成品油的配送問(wèn)題，未考慮車輛的分艙及滿載約束限制。在實(shí)際的成品油配送中，各個(gè)加油站的需求量往往是一個(gè)隨機(jī)變量，并且不同品種的成品油需求量服從的隨機(jī)變量分布不同，油罐車的容量和隔艙數(shù)也不同，而且要求滿載運(yùn)輸。另外，在本文為了簡(jiǎn)化問(wèn)題，假設(shè)一個(gè)加油站只能被一輛車服務(wù)，實(shí)際中一個(gè)加油站可以被多輛車服務(wù)。在后續(xù)的研究中，我們將逐漸加入這些約束條件，建立更加符合實(shí)際情況的成品油配送路徑優(yōu)化模型，為解決實(shí)際問(wèn)題提供理論依據(jù)。

參考文獻(xiàn)：

[1]Herer Y，Levy RThe Metered Inventory Routing Problem，an Integrative Heuristic Algorithm[J].International Journal of Production Economics，1997，51（1）：69-81

[2]BirgerRaa，El-HoussaineAghezzafA Practical Solution Approach for the Cyclic Inventory Routing Problem[J].European Journal of Operational Research，2007，1922：429-441

[3]BirgerRaaNew Models and Algorithms forthe Cyclic Inventory Routing Problem[J].4OR，2008，61∶97-100

[4]Kunpeng Li，Bin Chen，AppaIyer Sivakumar，Yong WuAn Inventory–routing Problem with the Objective of Travel Time Minimization[J].European Journal of Operational Research，2014：936-945

[5]趙達(dá)，李軍，馬丹祥，李妍峰求解硬時(shí)間窗約束下隨機(jī)需求庫(kù)存-路徑問(wèn)題的優(yōu)化算法[J].運(yùn)籌與管理，2014，23（1）：27-37

[6]Zhenping Li，Zhiguo WuStudy on the Inventory Routing Problem of Refined Oil Distribution Based on Working Time Equilibrium[J].American Journal of Operations Research，2016，6（1）：17-24