金驍

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

[關鍵詞]成品油配送；路徑優(yōu)化；時間窗；數學模型

[DOI]1013939/jcnkizgsc201718184

1引言

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

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

2問題描述

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

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

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

5結論

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

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

參考文獻：

[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]趙達，李軍，馬丹祥，李妍峰求解硬時間窗約束下隨機需求庫存-路徑問題的優(yōu)化算法[J].運籌與管理，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