以工作量均衡為目標(biāo)的成品油配送路徑優(yōu)化問題研究

陳偉峰

[摘 要]文章以成品油配送路徑優(yōu)化問題為背景，研究了以工作量均衡為主要目標(biāo)的成品油配送路徑優(yōu)化問題（Refined Oil Distribution Route Optimization Problem）。在考慮車輛容載量、加油站允許卸油時(shí)間窗、加油站服務(wù)時(shí)間、加油站需求量等約束的前提下，將各個(gè)車輛的工作時(shí)間盡可能均衡作為主要目標(biāo)，建立了以車輛的最大工作時(shí)間最小化為目標(biāo)函數(shù)的成品油配送路徑優(yōu)化問題的整數(shù)規(guī)劃模型，編寫了求解模型的Lingo程序。文章進(jìn)一步用隨機(jī)生成的方式，產(chǎn)生了10個(gè)加油站的計(jì)算實(shí)例，利用Lingo軟件求出了局部最優(yōu)解。通過Lingo軟件求得的局部最優(yōu)解表明了模型的可行性。文章的研究結(jié)果為調(diào)度部門制訂成品油配送計(jì)劃提供了理論依據(jù)。

[關(guān)鍵詞]工作量均衡；硬時(shí)間窗；庫(kù)存路徑優(yōu)化；數(shù)學(xué)模型

[DOI]10.13939/j.cnki.zgsc.2017.15.241

庫(kù)存和運(yùn)輸是物流系統(tǒng)最重要的功能要素，是物流獲得“時(shí)間價(jià)值”和“空間價(jià)值”的兩大主要環(huán)節(jié)，它們的耗費(fèi)約占物流總成本的2/3。[1]經(jīng)典的庫(kù)存路徑問題主要研究一個(gè)供應(yīng)商向多個(gè)顧客提供配送服務(wù)時(shí)，在保證顧客的需求量、顧客的配送時(shí)間窗以及庫(kù)存容量限制等約束條件的前提下，使總成本達(dá)到最小。對(duì)于IRP問題，國(guó)內(nèi)外已經(jīng)有較多的學(xué)者去研究并得出了豐富的理論。Clauclia Archetti[2]等人提出了離散時(shí)間下的配送問題，以庫(kù)存和運(yùn)輸成本最小化作為目標(biāo)函數(shù)。Pieter Vansteenwegen[3]等人研究了單車輛循環(huán)庫(kù)存路徑問題，考慮單車輛循環(huán)配送問題，不考慮有無(wú)限車輛可以使用的情況，是以總成本的最小化作為主要考慮因素。Kunpeng Li[4]等人研究了成品油配送過程中的庫(kù)存路徑問題，在每個(gè)加油站只能被服務(wù)一次且采用最大補(bǔ)貨量原則的前提下，以總運(yùn)輸時(shí)間最小化作為主要的目標(biāo)函數(shù)，建立了數(shù)學(xué)模型并設(shè)計(jì)了禁忌搜索算法對(duì)模型進(jìn)行求解。李相勇[5]于2007年提出了帶時(shí)間窗和隨機(jī)旅行時(shí)間車輛路徑問題，并設(shè)計(jì)了基于隨機(jī)模擬的禁忌搜索算法。蔣波[6]在研究帶時(shí)間窗車輛路徑優(yōu)化問題時(shí)，給出了以配送總成本最小化為目標(biāo)的帶懲罰函數(shù)的VRPTW優(yōu)化模型，并用遺傳算法進(jìn)行了求解。

1 問題描述

本文主要以油庫(kù)向各個(gè)加油站配送成品油作為主要的研究背景?？紤]由加油站管理庫(kù)存的成品油配送物流系統(tǒng)，基于工作量均衡的成品油配送庫(kù)存路徑優(yōu)化問題可以描述為：一座油庫(kù)為n個(gè)加油站供應(yīng)某種型號(hào)的成品油，假設(shè)油庫(kù)的庫(kù)存量足夠大，已知油庫(kù)擁有K輛運(yùn)輸車，每輛運(yùn)輸車輛的容載量已知；一輛運(yùn)輸車在油庫(kù)裝滿成品油以后，由油庫(kù)出發(fā)依次為若干個(gè)加油站配送成品油，配送結(jié)束后返回到油庫(kù)；每個(gè)加油站都有一個(gè)固定的卸油時(shí)間窗，運(yùn)輸車必須在加油站的規(guī)定時(shí)間窗內(nèi)為加油站卸油；如果運(yùn)輸車輛早于加油站最早服務(wù)時(shí)間到達(dá)，則運(yùn)輸車必須等待；如果運(yùn)輸車晚于加油站的最晚時(shí)間到達(dá)，則會(huì)造成加油站斷貨，因此不允許車輛晚于加油站最晚服務(wù)時(shí)間到達(dá)加油站；同一加油站的需求量可以由多輛運(yùn)輸車進(jìn)行配送；已知每輛運(yùn)輸車的容載量、加油站對(duì)成品油的需求量、油庫(kù)和加油站之間以及各個(gè)加油站之間的最短運(yùn)輸距離、每個(gè)加油站卸油（服務(wù)）所需時(shí)間以及加油站的時(shí)間窗。如何安排運(yùn)輸車的運(yùn)輸路徑及運(yùn)輸量才能使各輛運(yùn)輸車的工作時(shí)間盡可能均衡？

2 基于工作量均衡的庫(kù)存路徑優(yōu)化問題的數(shù)學(xué)模型

目標(biāo)函數(shù)（1）表示極小化所有車輛完成配送任務(wù)的最長(zhǎng)時(shí)間；

約束（2）表示每個(gè)加油站至少被一輛運(yùn)輸車服務(wù)；

約束（3）～（4）表示每一輛運(yùn)輸車的運(yùn)輸路徑起點(diǎn)和終點(diǎn)都必須是油庫(kù)；

約束（5）表示一輛運(yùn)輸車進(jìn)入某個(gè)加油站，則必然要從該加油站離開；

約束（6）表示運(yùn)輸車輛所裝載的成品油的總量不超過運(yùn)輸車的容載量；

約束（7）表示同一運(yùn)輸路徑上相繼兩個(gè)加油站的車輛到達(dá)時(shí)間之間的關(guān)系；

約束（8）表示車輛到達(dá)加油站的時(shí)間必須在加油站的時(shí)間窗內(nèi)；

約束（9）表示所有車輛運(yùn)至某一加油站的成品油數(shù)量等于其需求量；

約束（10）表示所有車輛回到油庫(kù)的時(shí)間均不超過最長(zhǎng)時(shí)間；

約束（11）～（12）表示變量的取值約束。

3 算例及求解

假設(shè)有一油庫(kù)為10個(gè)加油站配送成品油，序號(hào)0表示油庫(kù)，序號(hào)1～10表示加油站，油庫(kù)共有3輛運(yùn)輸車，運(yùn)輸車的行駛速度均為50km/h，每輛運(yùn)輸車的容載量不相同。每輛車的容載量見表1，每個(gè)加油站的需求量、服務(wù)時(shí)間及硬時(shí)間窗見表2，每個(gè)加油站之間以及加油站與油庫(kù)之間的距離見表3，每個(gè)加油站之間以及加油站與油庫(kù)之間的車輛行駛時(shí)間見表4，問如何安排配送路徑才能使3輛車的工作時(shí)間盡可能均衡？

根據(jù)本文建立的整數(shù)規(guī)劃模型，利用Lingo軟件編程求解，當(dāng)求解選項(xiàng)設(shè)置為全局最優(yōu)解時(shí)，Lingo經(jīng)過30個(gè)小時(shí)的程序運(yùn)行之后得到全局最優(yōu)解，具體結(jié)果如下所示：

由表5可以得知：車輛1的工作時(shí)間為2.42h，車輛2的工作時(shí)間為2.42h，車輛3的工作時(shí)間為2.42h。

每輛運(yùn)輸車給各個(gè)加油站配送的成品油數(shù)量如表6所示。

通過Lingo求得局部最優(yōu)解的用時(shí)較長(zhǎng)，無(wú)法滿足短時(shí)間內(nèi)求得最優(yōu)解的要求。

4 結(jié) 論

庫(kù)存路徑優(yōu)化問題是制訂成品油配送計(jì)劃的關(guān)鍵問題，在實(shí)際安排成品油配送方案的時(shí)候，經(jīng)常需要考慮各個(gè)配送車輛的工作時(shí)間的均衡問題。本文研究的基于工作量均衡的庫(kù)存路徑優(yōu)化問題的目標(biāo)就是盡可能使配送車輛的工作時(shí)間均衡。本文首先建立了該問題的數(shù)學(xué)模型，并編寫了求解模型的Lingo程序，進(jìn)一步設(shè)計(jì)了求解模型的啟發(fā)式算法。本文的模型和算法為制訂成品油配送計(jì)劃提供了理論依據(jù)。

參考文獻(xiàn)：

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

[2]Clauclia Archetti，Nicola Bianchessi，Stefan Irnich，et al.Formulations for an Inventory Routing Problem[J].International Transactions in Operational Research，2014（21）：353-374.

[3]Pieter Vansteenwegen，Manuel Mateo.Aninterated Search Algorithm for the Single-Vehicle Cyclic Inventory Routing Problem[J].Operational Research，2014，237（3）：802-813.

[4]Kunpeng Li，Bin Chen，Appalyer Sirakumar，et al..An inventory-Routing Problem with the Objective of Travel Time Minimization[J].European Journal of Operational Research，2013，236（3）：936-945.

[5]李相勇.車輛路徑問題模型及算法研究[D].上海：上海交通大學(xué)，2007：91-105.

[6]蔣波.基于遺傳算法的帶時(shí)間窗車輛路徑優(yōu)化問題研究[D].北京：北京交通大學(xué)，2010：8-44.