以工作量均衡為目標的成品油配送路徑優化問題研究

陳偉峰

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

[關鍵詞]工作量均衡；硬時間窗；庫存路徑優化；數學模型

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

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

1 問題描述

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

2 基于工作量均衡的庫存路徑優化問題的數學模型

目標函數（1）表示極小化所有車輛完成配送任務的最長時間；

約束（2）表示每個加油站至少被一輛運輸車服務；

約束（3）～（4）表示每一輛運輸車的運輸路徑起點和終點都必須是油庫；

約束（5）表示一輛運輸車進入某個加油站，則必然要從該加油站離開；

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

約束（7）表示同一運輸路徑上相繼兩個加油站的車輛到達時間之間的關系；

約束（8）表示車輛到達加油站的時間必須在加油站的時間窗內；

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

約束（10）表示所有車輛回到油庫的時間均不超過最長時間；

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

3 算例及求解

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

根據本文建立的整數規劃模型，利用Lingo軟件編程求解，當求解選項設置為全局最優解時，Lingo經過30個小時的程序運行之后得到全局最優解，具體結果如下所示：

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

每輛運輸車給各個加油站配送的成品油數量如表6所示。

通過Lingo求得局部最優解的用時較長，無法滿足短時間內求得最優解的要求。

4 結 論

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

參考文獻：

[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].上海：上海交通大學，2007：91-105.

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