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

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

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

1 引言

車(chē)輛調(diào)度是物流配送的關(guān)鍵問(wèn)題之一。車(chē)輛調(diào)度直接影響著物流配送的成本、客戶滿意度、社會(huì)效益和經(jīng)濟(jì)效益。車(chē)輛調(diào)度問(wèn)題(Vehicle Scheduling Problem，VSP)最早由學(xué)者Dantzig和Ramser于1959年提出[1]，已被證實(shí)為NP-Hard難題[2-3]，近年來(lái)一直是學(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)車(chē)費(fèi)、人工成本、車(chē)輛折舊成本、輪胎消耗費(fèi)、耗油費(fèi)、高速過(guò)路費(fèi)等，而這些成本或費(fèi)用直接與裝車(chē)方案、配送路徑、配送順序有關(guān)。除此之外，現(xiàn)有研究在計(jì)算運(yùn)輸成本時(shí)未區(qū)分普通路段和高速路段[9]，這也與實(shí)際不符。實(shí)際上，高速過(guò)路費(fèi)是根據(jù)車(chē)輛自重、當(dāng)前車(chē)輛載重量和行駛里程進(jìn)行計(jì)算的，這將直接影響到運(yùn)輸成本的準(zhǔn)確性。對(duì)于客戶滿意度目標(biāo)，它主要是由物料送達(dá)時(shí)間決定的，而物料送達(dá)時(shí)間取決于車(chē)輛出發(fā)時(shí)間、行駛時(shí)間和上一個(gè)客戶的服務(wù)時(shí)間等，研究時(shí)應(yīng)詳細(xì)考慮其邏輯關(guān)系，從而更為有效地確定物料的送達(dá)時(shí)間，最終確定客戶滿意度。

在工程實(shí)踐中，考慮到各種現(xiàn)實(shí)約束，VSP變得更為復(fù)雜。現(xiàn)有關(guān)于VSP的研究多集中于單目標(biāo)、單車(chē)型優(yōu)化問(wèn)題，而對(duì)于多目標(biāo)、多車(chē)型問(wèn)題的研究很少。對(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]。

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

2 模型構(gòu)建

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

2.1 綜合成本

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

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

(1)

2.2 平均客戶滿意度

(2)

(3)

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

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

圖1 自定義類(lèi)型

3.1 編碼方式

對(duì)于VSP，最直觀的編碼方式有基于車(chē)輛行駛路徑的自然數(shù)編碼[15]和基于客戶的編碼[16]，但這兩種編碼方式解決的VSP均是車(chē)輛數(shù)和車(chē)型沒(méi)有限制的問(wèn)題，無(wú)法用于求解本文模型。因此，本文在基于客戶號(hào)的整數(shù)編碼方式的基礎(chǔ)上加以改進(jìn)，采用固定長(zhǎng)度為lens(lens=2×rp-1)的整數(shù)編碼方式。式(4)中屬性CO即為個(gè)體chr(i)的編碼，根據(jù)每一條路徑對(duì)應(yīng)的總載重量約束來(lái)選擇所需車(chē)型。這種編碼方式可以很好地解決有車(chē)型限制、車(chē)數(shù)限制且實(shí)際所需車(chē)輛未知的VSP，并且在進(jìn)行解碼操作時(shí)可以直觀地得到每輛車(chē)服務(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ē)輛未找到合適的車(chē)型，則令ch.f=0且不再連續(xù)判斷后續(xù)車(chē)輛的可行性，返回ch；反之，若所有車(chē)輛都找到了合適的車(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ù)說(shuō)明：

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

3.4 遺傳操作

遺傳操作包括交叉操作和變異操作。采用“基于客戶點(diǎn)順序”的交叉和變異方式來(lái)進(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è)的車(chē)輛調(diào)度中進(jìn)行了應(yīng)用測(cè)試。該物流企業(yè)共有13個(gè)客戶，現(xiàn)需從配送中心調(diào)貨，通過(guò)對(duì)配送車(chē)輛的合理調(diào)度，使得完成配送任務(wù)的總成本最小、平均客戶滿意度最大。

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

圖3 Pareto解集

5 結(jié)束語(yǔ)

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