帶可選時間窗的車輛調(diào)度多目標(biāo)優(yōu)化方法

文/黃埔生 曾強

1.引言

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

2.問題描述

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

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

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

圖1 客戶i滿意度度量

3.NSGAII算法設(shè)計

3.1 算法流程

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

圖2 算法流程

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

圖3 編碼方式

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

圖4 交叉操作

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

圖5 變異操作

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

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

4.案例分析

河南省某物流企業(yè)有一個配送中心0，服務(wù)于13個客戶?？蛻?-13為分布在13個不同城市的客戶，配送中心及客戶所在的城市如表1所示?，F(xiàn)有某種貨物需要為這13個客戶配送，配送中心與各客戶以及各客戶之間的路程矩陣如表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四種車型：對應(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所示；各客戶提供的時間窗已知。配送車輛出發(fā)時間為2020/12/15 4:30，每個客戶的服務(wù)時間為30分鐘。

表3 客戶需求量

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

圖6 Pareto解集

圖7 Pareto A

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

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

圖8 單時間窗下的Pareto解集

5.結(jié)語：

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