物流配送車輛精細(xì)化多目標(biāo)調(diào)度方法*

□ 曾 強(qiáng)，林 凱，王科峰

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

1 引言

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

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

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

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

2 模型構(gòu)建

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

2.1 綜合成本

綜合成本根據(jù)式(1)進(jìn)行計(jì)算。

綜合成本=調(diào)車費(fèi)+耗油費(fèi)+人工費(fèi)+過路費(fèi)+車輛折舊費(fèi)+輪胎折舊費(fèi)+其他成本

(1)

2.2 平均客戶滿意度

(2)

(3)

3 NSGA II算法設(shè)計(jì)

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

圖1 自定義類型

3.1 編碼方式

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

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 種群初始化

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

3.3 解碼操作

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

圖2 解碼操作流程

函數(shù)說明：

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

3.4 遺傳操作

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

①交叉操作。

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

②變異操作。

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

4 案例分析

為驗(yàn)證本文所提算法的有效性，將該算法在某物流企業(yè)的車輛調(diào)度中進(jìn)行了應(yīng)用測(cè)試。該物流企業(yè)共有13個(gè)客戶，現(xiàn)需從配送中心調(diào)貨，通過對(duì)配送車輛的合理調(diào)度，使得完成配送任務(wù)的總成本最小、平均客戶滿意度最大。

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

圖3 Pareto解集

5 結(jié)束語

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