文/黃埔生 曾強(qiáng)

1.引言

車輛調(diào)度問(wèn)題（Vehicle Routing Problem,VRP）最早由學(xué)者Dantzig和Ram ser于1959年提出，其一般定義如下[1]：對(duì)一系列裝貨點(diǎn)和卸貨點(diǎn)，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過(guò)它們，在滿足一定的約束條件下，達(dá)到一定的目標(biāo)。車輛調(diào)度的優(yōu)化目標(biāo)有很多，大致可分為兩類：一類是有利于物流企業(yè)的目標(biāo)，如配送路程最短[2]、配送成本最低[3]、配送車輛最少[4]；另一類是有利于客戶的目標(biāo)，如延遲時(shí)間最短[5]、滿意度最高[6]等。其中，配送成本和客戶滿意度是兩個(gè)最根本、最重要的優(yōu)化目標(biāo)。送貨的準(zhǔn)時(shí)性是決定客戶滿意度的核心因素之一。在此背景下，帶時(shí)間窗約束的車輛調(diào)度問(wèn)題（Vehicle Routing Problem w ith Time W indow s,VRPTW）成為一個(gè)重要研究課題。多目標(biāo)車輛調(diào)度問(wèn)題屬于NP-hard問(wèn)題。常用的多目標(biāo)優(yōu)化方法有“間接法”和“直接法”兩種。間接法是將多目標(biāo)轉(zhuǎn)換為單目標(biāo)、再采用單目標(biāo)優(yōu)化法進(jìn)行求解的方法，該方法的缺點(diǎn)是受人工干擾因素較大且不能得到一個(gè)完整的Pareto解集以供決策[13]。NSGA算法于1994年被Srim ivas和Deb提出[7]，其優(yōu)點(diǎn)包括非劣最優(yōu)解均勻分布、優(yōu)化目標(biāo)數(shù)可以任意選擇[8]。文獻(xiàn)[9-10]通過(guò)對(duì)以上方法定量研究得出“NSGA算法性能優(yōu)于其他算法”的結(jié)論。2002年，Deb[11]在NSGA的基礎(chǔ)上又提出了帶精英策略的非支配排序遺傳算法（NSGA II），大大提高了NSGA算法的性能?；谝陨戏治?，本文針對(duì)一類帶可選時(shí)間窗的車輛調(diào)度問(wèn)題，提出了一種基于NSGA II算法的多目標(biāo)優(yōu)化方法。

2.問(wèn)題描述

某配送中心0服務(wù)于n個(gè)客戶，為其配送某種貨物。假設(shè)條件：①車輛完成配送后需回到配送中心；②客戶的需求時(shí)間窗為軟時(shí)間窗；③客戶的需求時(shí)間窗不唯一；④一個(gè)客戶能且只能被一輛車服務(wù)；⑤客戶的需求量已知，客戶的需求時(shí)間窗已知，配送中心與各客戶、各客戶之間的行駛路程已知，每個(gè)客戶被服務(wù)的時(shí)間、車輛從配送中心出發(fā)的時(shí)間已知；⑥車輛可24小時(shí)隨時(shí)出入配送中心；⑦同一車型耗油量不考慮載重量的影響；⑧車輛有w個(gè)車型，各車型數(shù)量不限。要求：合理安排車輛及其配送路徑，使其配送總成本最低、平均客戶滿意度最高。該問(wèn)題的優(yōu)化目標(biāo)如下：

式（1）表示配送總成本最小化；式（2）表示平均客戶滿意度最大化。

其中，客戶滿意度的度量方法如下：在軟時(shí)間窗環(huán)境下，客戶i的滿意度可用圖1所示的曲線進(jìn)行度量（以客戶i提供2個(gè)可選時(shí)間窗為例）。圖中有 4個(gè)變量，分別為 ei、ai、bi、li，滿足 ei≤ai≤bi≤li。其中，ai、bi為客戶 i滿意的最早送達(dá)時(shí)間和最晚送達(dá)時(shí)間，[ai，bi]為客戶 i的滿意服務(wù)區(qū)間；ei、li分別為客戶 i可接受的最早送達(dá)時(shí)間和最晚送達(dá)時(shí)間，[ei，li]為客戶i的可接受送達(dá)區(qū)間。設(shè)t是客戶i的貨物送達(dá)時(shí)間，則該送達(dá)時(shí)間對(duì)于客戶i的第j個(gè)時(shí)間窗的滿意度函數(shù)Sij(t)如式（3）所示?？蛻鬷的滿意度如式（4）所示。

圖1 客戶i滿意度度量

3.NSGAII算法設(shè)計(jì)

3.1 算法流程

取ps為偶數(shù)，本文算法流程如圖2所示。

圖2 算法流程

3.3 編碼方式。采用“整數(shù)”方式編碼[12]，用1～2dt-1的隨機(jī)序列表示一個(gè)個(gè)體。圖3是一個(gè)dt=13，長(zhǎng)度為25的個(gè)體的編碼。該編碼表示共用6輛車進(jìn)行配送。車輛1為客戶7、8配送，行駛路徑為0→7→8→0；車輛2為客戶4、3配送，行駛路徑為0→4→3→0；車輛 3、4、5、6同理。

圖3 編碼方式

3.5 交叉操作。采用“分段交叉”的方式進(jìn)行交叉操作[21]。以dt=13為例，交叉操作如圖4所示。隨機(jī)產(chǎn)生兩個(gè)長(zhǎng)度為2dt-1的染色體A和B，其中||部分為交叉片段，同理，染色體B操作也是如此。產(chǎn)生的子代個(gè)體需要用到函數(shù)kexing判斷其是否可行。若A’可行，則取A’，否則取A；若B’可行，則取B’，否則取B。

圖4 交叉操作

3.6 變異操作。采用“兩點(diǎn)對(duì)換變異”的方式進(jìn)行變異操作[21]。隨機(jī)產(chǎn)生兩個(gè)不相同的變異點(diǎn) m point1和 m point2，設(shè)m point1=6、m point2=17，變異前后的染色體片段如圖5所示。同樣，變異后的個(gè)體仍需要用到函數(shù)kexing進(jìn)行判斷其是否可行。若A’可行，則取A’，否則取A。

圖5 變異操作

3.7 目標(biāo)值轉(zhuǎn)化。由于NSGAII算法在計(jì)算時(shí)，要求優(yōu)化目標(biāo)均為最大化或者最小化，故需對(duì)式（2）中所構(gòu)建的目標(biāo)函數(shù)進(jìn)行處理。本文將優(yōu)化目標(biāo)中的式（2）按照式（5）進(jìn)行最小化轉(zhuǎn)換。

3.8 解碼操作。解碼操作的目的是通過(guò)個(gè)體編碼解析出配送路徑，然后求得優(yōu)化目標(biāo)：配送總成本和1-平均客戶滿意度。以圖3所示的個(gè)體為例進(jìn)行說(shuō)明：配送總成本計(jì)算方法如下：由客戶7、8所需貨物總量，選擇車輛1的車型（不低于其載重量的最小額定載重所對(duì)應(yīng)的車型），以此類推，求得此配送路線的所用車型和總車數(shù)；根據(jù)各車型調(diào)車成本和車數(shù)求得調(diào)車成本，匯總得到總調(diào)車成本；將每一車輛行駛路程、單位路程耗油量、單位耗油成本相乘得到運(yùn)輸成本，將運(yùn)輸成本匯總得到總運(yùn)輸成本；將總調(diào)車成本與總運(yùn)輸成本相加得到配送總成本。1-平均客戶滿意度的計(jì)算方法如下：通過(guò)個(gè)體編碼，求得車輛到達(dá)每個(gè)客戶的時(shí)間t，根據(jù)式（3）計(jì)算送達(dá)時(shí)間t在該客戶每個(gè)需求時(shí)間窗下的滿意度，按式（4）計(jì)算該客戶的滿意度，按式（2）計(jì)算平均客戶滿意度，按式（5）計(jì)算1-平均客戶滿意度。

4.案例分析

河南省某物流企業(yè)有一個(gè)配送中心0，服務(wù)于13個(gè)客戶?？蛻?-13為分布在13個(gè)不同城市的客戶，配送中心及客戶所在的城市如表1所示?，F(xiàn)有某種貨物需要為這13個(gè)客戶配送，配送中心與各客戶以及各客戶之間的路程矩陣如表2所示。

表1 配送中心及客戶

表2 路程矩陣（單位：km）

設(shè)置算法的種群規(guī)模ps為50，迭代次數(shù)m g為300，交叉比例cr為0.7，變異比例m r為0.3。設(shè)此物流企業(yè)有1、2、3、4四種車型：對(duì)應(yīng)的額定載重量分別為 12t、15t、18t、21t，調(diào)車成本分別為400元、500元、600元、700元，單位路程耗油量分別為1.5L/km、2 L/km、2.5 L/km、3 L/km；各客戶的貨物需求量如表3所示；各客戶提供的時(shí)間窗已知。配送車輛出發(fā)時(shí)間為2020/12/15 4:30，每個(gè)客戶的服務(wù)時(shí)間為30分鐘。

表3 客戶需求量

運(yùn)行算法多次，均能得到穩(wěn)定的Pareto解集。圖6是其中一次的輸出結(jié)果。其中，Pareto解A的參數(shù)如圖7所示。

圖6 Pareto解集

圖7 Pareto A

圖7 中,A解配送總成本為6524.3元，1-平均滿意度為0.7854，是配送總成本最低的一個(gè)配送方案。共選擇6輛車，分別為 5輛1型車、1輛2型車。其中車 1載重量為 15t(5+5+5=15)、配送客戶分別為2、4、5，選擇的是客戶2的第2個(gè)時(shí)間窗、客戶4的第2個(gè)時(shí)間窗、客戶5的第1個(gè)時(shí)間窗；車2載重量為 12t（4+6+2=12）、配送客戶分別為 7、12、9，選擇的是客戶7的第1個(gè)時(shí)間窗、客戶12的第1個(gè)時(shí)間窗、客戶9的第2個(gè)時(shí)間窗；車3載重量為12t(3+3+6=12)、配送客戶分別為10、6、8，選擇的是客戶10的第1個(gè)時(shí)間窗、客戶6的第2個(gè)時(shí)間窗、客戶8的第1個(gè)時(shí)間窗；車4載重量為9t(5+4=9)、配送客戶分別為1、3，選擇的是客戶1的第2個(gè)時(shí)間窗、客戶3的第1個(gè)時(shí)間窗；車5載重量為8t、配送客戶為13，選擇的是客戶13的第1個(gè)時(shí)間窗；車6載重量為11t、配送客戶為11，選擇的是客戶11的第1個(gè)時(shí)間窗。為了比較可選時(shí)間窗與單時(shí)間窗的不同，把客戶1-13的第一時(shí)間窗保留，其余的時(shí)間窗刪除。重新計(jì)算得到單時(shí)間窗下的Pareto解集如圖8所示。

比較圖6和圖8的Pareto解集，可以發(fā)現(xiàn)：當(dāng)配送總成本都為6780元時(shí)，帶可選時(shí)間窗的“1-平均客戶滿意度”為0.5733，對(duì)應(yīng)平均客戶滿意度為0.4267；單時(shí)間窗的“1-平均客戶滿意度”為0.7618，對(duì)應(yīng)平均客戶滿意度為0.2382；當(dāng)配送總成本都為7000元時(shí)，帶可選時(shí)間窗的“1-平均客戶滿意度”為0.5000，對(duì)應(yīng)平均客戶滿意度為0.5000；單時(shí)間窗的“1-平均客戶滿意度”為0.7141，對(duì)應(yīng)平均客戶滿意度為0.2859；當(dāng)配送總成本都為7443元時(shí)，帶可選時(shí)間窗的“1-平均客戶滿意度”為0.3330，對(duì)應(yīng)平均客戶滿意度為0.6670；單時(shí)間窗的“1-平均客戶滿意度”為0.5000，對(duì)應(yīng)平均客戶滿意度為0.5000；當(dāng)配送總成本都為8600元時(shí)，帶可選時(shí)間窗的“1-平均客戶滿意度”為0.0876，對(duì)應(yīng)平均客戶滿意度為0.9124；單時(shí)間窗的“1-平均客戶滿意度”為0.2500，對(duì)應(yīng)平均客戶滿意度為0.7500；即當(dāng)配送總成本相同或相近時(shí)，帶可選時(shí)間窗問(wèn)題的平均客戶滿意度比單時(shí)間窗問(wèn)題的平均客戶滿意度高。產(chǎn)生這種現(xiàn)象的原因是可選時(shí)間窗下可選擇性高，使得平均客戶滿意度高。

圖8 單時(shí)間窗下的Pareto解集

5.結(jié)語(yǔ)：

針對(duì)一類帶可選時(shí)間窗的車輛調(diào)度問(wèn)題,提出了一種基于NSGA II算法的多目標(biāo)優(yōu)化方法。描述了以配送總成本最低、平均客戶滿意度最高為優(yōu)化目標(biāo)的多目標(biāo)問(wèn)題，設(shè)計(jì)了帶精英策略的非支配排序遺傳算法（NSGA II）對(duì)該問(wèn)題求解。案例分析表明，當(dāng)配送總成本相同或相近時(shí)，帶可選時(shí)間窗問(wèn)題的平均客戶滿意度比單時(shí)間窗問(wèn)題的平均客戶滿意度高。本文算法收斂性較好，能夠在較短的時(shí)間內(nèi)得到Pareto解集，供調(diào)度員決策。