物流配送車輛精細化多目標調度方法*

□ 曾 強，林 凱，王科峰

(1.河南理工大學 工商管理學院，河南 焦作 454000；2.河南理工大學 能源科學與工程學院，河南 焦作 454000)

1 引言

車輛調度是物流配送的關鍵問題之一。車輛調度直接影響著物流配送的成本、客戶滿意度、社會效益和經濟效益。車輛調度問題(Vehicle Scheduling Problem，VSP)最早由學者Dantzig和Ramser于1959年提出[1]，已被證實為NP-Hard難題[2-3]，近年來一直是學術界的一個研究熱點。

現有關于VSP的研究所涉及的優化目標主要有配送里程最少[4]、耗油量最低[5]、總運輸時間最少[6-7]、客戶滿意度最大[8]等。這些研究在量化優化目標方面不夠精細化，如成本目標、客戶滿意度目標等。對于成本目標，文獻[6-7]僅把運輸成本區分為固定成本和行駛成本。筆者認為，更為精細的方法是把運輸成本細分為調車費、人工成本、車輛折舊成本、輪胎消耗費、耗油費、高速過路費等，而這些成本或費用直接與裝車方案、配送路徑、配送順序有關。除此之外，現有研究在計算運輸成本時未區分普通路段和高速路段[9]，這也與實際不符。實際上，高速過路費是根據車輛自重、當前車輛載重量和行駛里程進行計算的，這將直接影響到運輸成本的準確性。對于客戶滿意度目標，它主要是由物料送達時間決定的，而物料送達時間取決于車輛出發時間、行駛時間和上一個客戶的服務時間等，研究時應詳細考慮其邏輯關系，從而更為有效地確定物料的送達時間，最終確定客戶滿意度。

在工程實踐中，考慮到各種現實約束，VSP變得更為復雜。現有關于VSP的研究多集中于單目標、單車型優化問題，而對于多目標、多車型問題的研究很少。對多目標VSP算法主要有粒子群算法[10]、禁忌搜索算法[11]、NSGA II算法(Non-dominated Sorting Genetic Algorithm with elite strategy,NSGA II)[12]等。其中，NSGA II算法是Deb等[13]在NSGA算法的基礎上提出的帶精英策略的非支配排序遺傳算法，是一種比較成熟和理想的Pareto尋優算法[14]。

基于以上分析，本文提出了一種物流配送車輛精細化多目標調度方法：建立了物流配送車輛精細化多目標調度模型，設計了帶精英策略的非支配排序遺傳算法(NSGA II)用于求解該模型。

2 模型構建

假設配送中心用p個車型的v車輛向n個客戶配送一種貨物，通過合理調度，使得配送任務的綜合成本最低、平均客戶滿意度最大。

2.1 綜合成本

綜合成本根據式(1)進行計算。

綜合成本=調車費+耗油費+人工費+過路費+車輛折舊費+輪胎折舊費+其他成本

(1)

2.2 平均客戶滿意度

(2)

(3)

3 NSGA II算法設計

以C#.NET為開發平臺，設計了NSGA II算法求解模型。根據算法需要，定義了圖1所示的自定義類型。其中，Chr表示種群數組，Chr(i)表示種群中的個體。

圖1 自定義類型

3.1 編碼方式

對于VSP，最直觀的編碼方式有基于車輛行駛路徑的自然數編碼[15]和基于客戶的編碼[16]，但這兩種編碼方式解決的VSP均是車輛數和車型沒有限制的問題，無法用于求解本文模型。因此，本文在基于客戶號的整數編碼方式的基礎上加以改進，采用固定長度為lens(lens=2×rp-1)的整數編碼方式。式(4)中屬性CO即為個體chr(i)的編碼，根據每一條路徑對應的總載重量約束來選擇所需車型。這種編碼方式可以很好地解決有車型限制、車數限制且實際所需車輛未知的VSP，并且在進行解碼操作時可以直觀地得到每輛車服務客戶的情況。

chr(i).CO=(0 3 4 1 0 0 1 0 5 1 1 0 0 9 2 0 0 8 6 0 0 7 0)

(4)

3.2 種群初始化

采用如下步驟對種群進行初始化操作：根據編碼ch.CO計算ch.nc、ch.f、ch.VS、ch.VM、ch.CC。若某車輛未找到合適的車型，則令ch.f=0且不再連續判斷后續車輛的可行性，返回ch；反之，若所有車輛都找到了合適的車型，則ch.f保持為1，表示該個體可行，返回ch。

3.3 解碼操作

解碼操作的任務是對個體chr(i)，分別針對chr(i).O、chr(i).tm、chr(i).toc、chr(i).vd、chr(i).tc、chr(i).rt等參數進行計算。具體解碼流程如圖2所示。

圖2 解碼操作流程

函數說明：

UCch.CO(k),at)作用是車輛在at時刻到達客戶ch.CO(k)的滿意度，由式(2)計算；F(ch.VM(i)、SDV(ch.VM(i),wh)作用是司機駕駛ch.VM(i)型車時，該車型司機工資標準為SDV(ch.VM(i))、工作時間為wh的工資；C(ch.CO(k),S,HDS(ch.CO(k),CJI(ch.CO(k),ch.CO(k+1)))作用是車輛服務客戶ch.CO(k)后，該車輛載重量為S、高速收費標準為HDS(ch.CO(k))和行駛距離為CJI(ch.CO(k),ch.CO(k+1))的過路費。

3.4 遺傳操作

遺傳操作包括交叉操作和變異操作。采用“基于客戶點順序”的交叉和變異方式來進行交叉和變異。

①交叉操作。

根據個體編碼方式的特點，交叉操作采用“兩點交叉”方式。具體方法如下：設兩個父代個體為a，b，首先，產生兩個不相等的1～lens的隨機整數c1,c2，若c2

②變異操作。

根據個體編碼的特點，變異操作采用“兩點交換變異”方式，具體如下：將父代個體P產生的兩個不相等的1～lens的隨機整數m1,m2作為變異點，對父代個體屬性CO基因座m1和m2的值進行交換變異。

4 案例分析

為驗證本文所提算法的有效性，將該算法在某物流企業的車輛調度中進行了應用測試。該物流企業共有13個客戶，現需從配送中心調貨，通過對配送車輛的合理調度，使得完成配送任務的總成本最小、平均客戶滿意度最大。

經算法獨立運行20次，均能得到基本相同且均勻的Pareto解集，表明收斂效果較好。圖3是某次進化計算得到的Pareto解集，其中，個體4的綜合成本為17424元、平均客戶滿意度為0.5、里程為3198.75公里、調車費為3630元、過路費為4012.5元、油費為2487.19元、車輛折舊費為1754.52元、輪胎折舊費為520.16元；總需車數為6輛，車型分別為C、A、B、D、A、B；每輛車載重分別為16噸、4噸、11噸、17噸、9噸、11噸；C車型服務客戶號為2、8、1的客戶，A車型服務客戶號為7的客戶，B車型服務客戶號為13、6的客戶，D車型服務客戶號為12、5、4的客戶，A車型服務客戶號為10、3、9的客戶，B車型服務客戶號為11的客戶。

圖3 Pareto解集

5 結束語

針對多車型、單配送中心車輛調度問題，提出了一種物流配送車輛精細化多目標調度方法：建立了以綜合成本最低和平均客戶滿意度最大為優化目標的物流配送車輛調度模型，設計了帶精英策略的非支配排序遺傳算法(NSGA II)。在算法中，采用以客戶號為基因值的固定長度整數編碼方式進行編碼，該編碼方式更好地解決了有車型限制、車數限制且實際所需車輛未知的VSP；在解碼中，對車輛調度過程中的成本、路徑和時間進行精細化處理，實現了總利潤和平均客戶滿意度的準確計算。