淺談成品油二次配送路徑優化問題

(西南石油大學 四川 成都 610500)

一、成品油二次配送的概念

成品油二次配送是指將油品從油庫配送至加油站的過程，屬于車輛路徑規劃問題的一個分支。成品油二次配送屬于末端配送，是成品油運輸的最后一個環節，與末端客戶(加油站)直接接觸，其配送是否及時到位，對加油站的服務質量和城市居民的日常生活都有著重大的影響，建立合適的配送路徑優化模型對公司相關信息系統的建設也有著理論上的指導意義。因此，通過科學合理的手段制定滿意的配送路線，在現實和理論方面都有著重要的意義。

成品油配送的優化一般可以分為系統優化、庫存管理優化、需求預測優化、配送中心選址優化、車輛調度優化等，各類方向均有學者進行了深入研究，如：系統優化方面，賀振更在研究和分析成品油的配送體系的基礎上，設計了成品油配送的優化系統，以解決需求預測和車輛路徑優化問題[1]；庫存管理優化方面，陳樂群針對成品油配送過程中的庫存管理方面的問題，引入了VMI思想，闡述了該模式的應用要點，建立了VMI庫存管理方法[2]；需求預測優化方面，魏巧云等通過分析石化企業的配送實例，總結了成品油配送的需求特點，并基于此建立了需求預測模型，用以預測次日的配送需求及運力調配計劃，為構建成品油主動配送模型提供了理論支持[3]；配送中心選址優化方面，吳勤旻等在油庫選址問題中考慮油庫的建設成本因素和二次配送成本因素，將該問題歸納為一個二層優化模型，提出了確定理想選址區域和可行點的選址方法[4]。

車輛調度優化是近年來成品油配送優化的主要研究方向，現有文獻對車輛調度優化的研究主要集中在建立成品油配送車輛路徑模型并利用相關求解方法進行計算方面，其核心思想是VRP問題。Cornillier等對帶時間窗的成品油車輛路徑問題進行了研究，設計啟發式算法并進行求解，并通過實例驗證了通過優化可以縮短20%以上的行程[5]；Lahyani等研究了不同級別橄欖油配送中的多車艙車輛路徑問題，并利用分支界定法算法對問題進行了求解，證明了優化的有效性[7]。

蘇娟等以配送路徑最短為目標建立了多車型成品油二次配送優化模型，通過lingo軟件和遺傳算法進行求解，得出了合理的車型及路線安排；趙慧英等在研究成品油配送優化模型時，考慮了城區貨車交通管制的約束，并以最低運輸費用和風險為目標構建了多目標的路徑優化模型；王博弘等對國內外成品油二次配送的研究成果進行了調研，詳細敘述了成品油二次配送的常用模型、算法以及最新研究成果等，將VRP問題應用于成品油二次配送，探討成品油二次配送算法改進與發展的空間，給出了優化建議。

二、車輛路徑問題求解方法

由對于VRP問題直接求最優解耗時較長，20 世紀 80 年代以來，使用已知信息，在較短時間內求得VRP問題滿意解的啟發式算法成為學者研究的重點，經過多年的發展，研究者提出了許多VPR問題的求解方法，目前比較成熟的應用求解方法主要有精確算法和啟發式算法兩種，其中啟發式算法在不斷的發展中，又分為了傳統啟發式算法和智能啟發式算法兩種。

精確算法在客戶數量不大時可以求解VRP問題，當客戶點超50個時，其往往難以求得VRP問題的最優解。隨著啟發式算法的發展，智能啟發式算法由于具有更大的搜索能力，被越來越多的學者用于VRP問題的求解之中，常見的智能啟發式算法有FredGlover提出的禁忌搜索算法，Kirkpatrick等提出的模擬退火算法，Dorigo提出的蟻群算法，Kennedy和Eberhart提出的粒子群優化算法，Holland提出的遺傳算法等。

在遺傳算法求解VRP問題方面，Sivaram等建立了以最小行駛距離、最少配送車輛為目標函數的帶時間窗VRP問題整數規劃模型，在適應度函數和交叉算子等方面改進了遺傳算法，并進行了求解驗證；Mohammed等通過研究國際特赦組織利用公交車接送學生的路徑規劃問題，利用改進的遺傳算法求解CVRP問題的最優路徑，提出了基于混合交叉操作的最佳路徑選擇方法，發現以所有公共汽車每日總行駛距離為目標函數可以節約更多里程。

三、模型求解方法

(一)遺傳算法的數學模型可以描述出實現遺傳算法的整體性框架，但該描述是抽象化的描述，仍需要對模型中的各個要素進行具體明確，才能夠實現遺傳算法的優化功能。遺傳算法求解計算的核心內容由編碼、初始種群、適應度函數、遺傳操作、控制參數五個要素組成，本節將結合國內成品油配送路徑優化模型，對這幾個要素進行具體的明確。

(二)本章根據國內成品油配送的現狀及特點，建立相應的路徑優化模型，并對用于求解的遺傳算法相關要素進行了確定。首先對國內的配送需求進行了描述，以公司配送量最大的油品為對象，建立單配送中心下、汽油的成品油配送路徑優化模型；然后根據 國內實際，建立總里程最短的優化目標并建立相應目標函數，同時，通過對國內成品油配送有關的條件進行假設，設立約束條件函數，基于此建立國內成品油配送路徑優化模型；針對國內配送車型較多的特點，使用合理的多車型分配原則來提高車輛的實載率；對模型的遺傳算法求解方法進行了分析，合理地確定了編碼、初始種群、適應度函數、遺傳操作、控制參數等要素，以與國內成品油配送路徑優化模型相適應。