帶二維裝載約束的車輛調度問題建模及優化

王增臣，周 良

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 210016)

0 引 言

物流配送中的車輛調度問題(vehicle scheduling problem，VSP)是由Dantzig和Ramser[1]在1959年提出的，是物流配送中的一個重要步驟，一般可以描述為：對一系列裝貨點和(或)卸貨點，在一定條件(如指定交貨時間、車輛載重量、貨物的需求量等限制)的約束下，組織適當的車輛路線，達到預定的目的，如行駛時間較少、車輛行駛路程較短、花費成本較少等[2]。

近幾十年來，車輛調度問題逐漸成為運籌學和組合優化領域的研究熱點，其研究重點也從單因素向多因素協同考慮，各國學者進行了大量和深入的研究工作。馬祥麗等[3]針對車輛調度問題，結合蝙蝠算法的原理，重新設計了BA的操作算子并采用罰函數方式對目標函數進行了簡化，取得了較好的求解性能。吳聰等[4]將車輛與車輛路徑編碼成粒子，通過粒子之間的協作找到最優物流配送車輛調度優化方案，并對粒子群算法存在的不足進行了相應的改進，提高了算法性能。Marinakis等[5]提出了一種蜜蜂交配優化算法，并對局部尋優方法進行改進，使算法解決組合優化問題效果更佳，對開放式車輛路徑問題也取得了令人滿意的結果。Zhang等[6]考慮客戶滿意度，建立了多目標車輛路徑問題模型，提出了一種自適應網格的多目標量子進化算法，利用一種改進的模糊時間窗來反映客戶滿意程度。鄧麗君[7]通過對影響客戶滿意度的一些影響因素進行分析，構建了一種測度客戶滿意度的模糊隸屬度函數，利用線性加權將多目標函數轉化成單目標函數并設計一種改進的遺傳算法對單目標函數進行優化求解。以上文獻都對車輛調度問題進行研究并取得了一定成果，但在二維裝載約束方面研究甚少。劉海明等[8]通過改進最低水平線方法與基于分階段遺傳算子的遺傳算法相結合,求解矩形件排樣問題，有效改善了排樣效果,提高了材料利用率。Sarwono等[9]融合了物流配送中的兩個最重要問題，提出了一種最鄰近法求解車輛路徑問題，并提出了裝載啟發式算法解決貨物裝載問題。王征等[10]針對二維裝載約束的車輛調度問題建立了數學模型,提出了Memetic算法,對算法中的幾個關鍵算子:深度優先的啟發式裝箱方法、染色體的編碼方式及其路徑分割程序等,進行了詳細的闡述和改進。

針對近年來實際應用領域中出現的帶二維裝載約束的車輛調度新問題，文中綜合考慮時間窗、二維裝載約束、載重量、成本和客戶滿意度，建立了帶時間窗和二維裝載約束的開放式車輛路徑問題模型(open vehicle routing problem with time windows and two-dimensional loading constraints，2L-OVRPTW),提出了一種結合多目標蟻群優化算法和最低水平線搜索算法的車輛路徑優化算法，并通過實驗對模型的可解性及算法的有效性進行驗證。

1 車輛調度問題建模

1.1 問題描述

2L-OVRPTW問題是融合二維裝箱問題(two-dimensional bin packing problem，2BPP)和帶時間窗約束的開放式車輛路徑問題(open vehicle routing problem with time windows，OVRPTW)之后的一個變種問題[11]。2BPP問題同樣屬于NP難題，貨物能否裝載、貨物如何擺放等因素都對配送車輛的調度以及服務線路的安排產生很大的影響，因此這兩個問題的融合產生了新的問題，有別于一般的車輛路徑問題，使得新問題的模型會發生很大的變化，而對新問題進行求解也有較大的挑戰[12]。

2L-OVRPTW問題可描述為：一組相同的車輛由配送中心出發，負責給N個客戶進行貨物配送。每輛車均有一個長為L寬為W的長方形裝載空間，且所載貨物的總重量不能超過車輛最大載重量Q。每個客戶都有隨機數量和重量的貨物需求，每件貨物有特定的長度和寬度[13]。貨物裝載時，遵守有向有序條件，即同一客戶的所有貨物必須裝載在一輛車上，貨物不可旋轉，不能相互疊放，并且不同客戶的貨物之間不能產生阻擋。另外，每個客戶都有一個服務時間長度和理想的服務軟時間窗[14]。配送中心派送各個車輛并安排行車路線，使得每個客戶都能被服務到，每輛車完成任務后不需要返回原配送中心。在這些約束下尋求最佳的車輛調度配送方案[15]。

1.2 2L-OVRPTW模型定義

根據車輛路徑問題描述，在建模階段建立了2L-OVRPTW模型框架，如圖1所示。

圖1 2L-OVRPTW模型框架

2L-OVRPTW模型主要由四個方面組成：基礎信息包括客戶及配送中心的位置坐標、車輛基礎參數和貨物基礎參數；客戶需求是客戶的預定訂單和臨時訂單信息；約束條件有軟時間窗區間、車輛載重量約束和二維裝載約束；調度優化主要是要達到運輸成本最小和客戶滿意度最大的目標。

因此得到模型問題編碼：(1)位置：配送中心和客戶由N+1個坐標節點表示，0代表配送中心的標號，其他數字表示要被服務的客戶標號。標號i到標號j的距離為dij，單位距離的成本為cij。(2)配送中心：有K輛相同的車輛提供運輸配送服務，每輛車的額定載重量為Qk(k=1,2,…,K)，承載貨物的車廂為一個面積A=W×L的矩形，每輛車的固定發車成本為FK。(3)客戶：i=1,2,…,N，客戶i所需求的貨物為一個集合ITi，包含mi個矩形物品，ITi中所有物品的總面積為ai，總重量為qi，第m個物品Iim有一個具體的寬度wim和長度lim(m=1,2,…,mi)。設置車廂承載面俯視圖的左下角為原點，水平向右為橫坐標，垂直向上為縱坐標，則有物品Iim的坐標(vim,him)，vim,him分別代表到坐標原點的水平距離和垂直距離。車輛到達客戶進行服務的時間為ti，令每個客戶的服務軟時間窗為[Ei,Li]，客戶滿意度ui(ti)表示為：

客戶i固有的服務時間表示為si，當車輛提前到達客戶i處時，則需等待，產生等待時間wi(ti)。等待的單位時間成本為cwait，客戶i的等待成本則表示為wi(ti)×cwait。定義決策變量如下：

2L-OVRPTW模型可表示如下：

目標函數為：

(1)

(2)

約束條件為：

(3)

(4)

(5)

(6)

(7)

xijk=0或1，?i,j,k

(8)

yik=0或1，?i,k

(9)

0≤vimk≤W-wimk,?i∈{1,2,…,N},m∈

{1,2,…,mi},k∈K

(10)

0≤himk≤L-limk,?i∈{1,2,…,N},m∈{1,

2,…,mi},k∈K

(11)

vimk+wimk≤vi'm'k,?i,i'∈{1,2,…,N},m∈{1,

2,…,mi},m'∈{1,2,…,N},k∈K,i≠i'

(12)

himk+limk≤hi′m′k,?i,i'∈{1,2,…,N},m∈{1,

2,…,mi},m'∈{1,2,…,N},k∈K,i≠i'

(13)

vimk≥vi′m′k,?i,i'∈{1,2,…,N},m∈{1,2,…,mi},m'∈{1,2,…,N},k∈K,i≠i'

(14)

himk+limk≥hi'm'k,?i,i'∈{1,2,…,N},m∈{1,

2,…,mi},m'∈{1,2,…,N},k∈K,i≠i'

(15)

hi'm'k+li'm'k≥himk,?i,i'∈{1,2,…,N},m∈{1,2,…,mi},m'∈{1,2,…,N},k∈K,i≠i'

(16)

(17)

wi(ti)=max{0,Ei-ti}

(18)

其中，式1～3為目標函數，式1表示運輸成本最小化，式2表示平均客戶滿意度最大化。約束3限制每輛車的最大載重量；約束4保證每個客戶都能被服務到；約束5和6保證一個客戶有且僅有一輛車進行服務；約束7是消除子回路；約束8、約束9表示變量的取值范圍；約束10、約束11保證在每條路徑上貨物以固定方向都能放置于車上；約束12、約束13表示貨物相互之間不可以疊放；約束14～約束16保證貨物能在裝入方向直線移進移出并不受其他貨物阻擋；約束17計算車輛的到達時間；約束18計算車輛的等待時間。

2 車輛調度問題優化

2L-OVRPTW是屬于NP-hard難題，啟發式算法成為解決該問題的首選[16]。針對上述問題模型，文中設計了一種啟發式算法。該算法是以改進的蟻群算法為算法大體框架，并融入了基于BLF的裝載策略以確保滿足二維裝載約束。針對2L-OVRPTW模型設計的調度優化總體流程如圖2所示。

圖2 調度優化總體流程

2.1 二維裝載策略

在裝載階段，結合啟發式經驗知識，設計了基于最低水平線搜索算法的二維裝載策略，將各個客戶的矩形貨物有序裝入矩形車廂，提高車輛裝載率。

2.1.1 啟發式經驗知識

一般情況下,對于二維裝載問題很難直接構造出一個最優解或者滿意解,尤其當貨物數量比較多時,盲目搜索或者遍歷就變得更加困難,甚至根本不可行。因此,利用一些人工經驗和結構特征來構造出一些啟發式規則,并按照該規則指導采用的啟發式算法,由該算法可以求得問題的滿意解。

對于二維裝載約束,有以下幾個經驗和特征可以參考利用:

(1)物品裝入車廂可行區域的邊角處，產生的零碎區域更少，車廂的裝載率更高；

(2)先裝大塊物品，后裝小塊物品。面積較大的矩形物品裝入后產生的區域可以裝入面積較小的矩形貨品，由人工裝箱經驗可知，通常先裝大塊的物品，后裝小塊的物品；

(3)裝載過程中產生的剩余區域整體水平線越平整,即組成水平線的數量越少,高度越一致，就越有利于后期矩形的裝入。

基于上述三種啟發式經驗知識，對現有的最低水平線搜索算法進行指導改進，一個客戶的全部物品能且只能由一輛車進行運輸服務，在裝載之前對該客戶貨物總面積和車廂剩余面積進行比較；對一個客戶的物品按照寬度和面積進行倒序排序，減少不可行區域的產生，同時提高向后搜索匹配的效率；物品放置于可裝入的最低水平線的左下方。

2.1.2 裝載策略主要步驟

步驟1：將待裝載的指定客戶i的物品總面積ai與當前車廂剩余面積A剩進行比較：如果ai>A剩，則不可裝入，結束；否則對該客戶的物品按照寬度和面積進行倒序排序，然后執行步驟2。

步驟2：每當裝入客戶i的下一待裝物品Iim時，比較水平線集中各個水平線高度，選擇高度最低的一段水平線，若存在多段水平線段高度相同并且同為最低，則選取位置處于最左邊的一段水平線，作為最低水平線Wlow。

步驟3：比較最低水平線段和待裝物品Iim的寬度wim：

(1)如果Wlow≥wim，則將Iim放置于最低水平線的左下方，并更新水平線集的條數和高度。

(2)如果Wlow

步驟4：重復步驟3，直至能裝入客戶i物品Iim，并更新此時的水平線集。

步驟5：重復步驟4，直至客戶i的物品全部裝入，得到最終的水平線集。

步驟6：選取水平線集中的高度最大值Hmax，與車廂長度L進行比較：如果Hmax>L，客戶i的貨品不可裝入，水平線集更新到客戶i的貨品未裝入前狀態，結束；如果Hmax

2.2 車輛調度優化

蟻群算法(ant colony optimization，ACO)是一種新興的優化技術，是一種模擬進化算法。ACO是一種啟發式仿生進化系統，通過模擬螞蟻群體在自然生活中的覓食行為而得出，其搜索過程是分布式并行計算方式，能夠提高算法的計算能力和運行效率，并采用啟發式正反饋機制，能夠使算法獲得全局最優解。

2.2.1 算法的具體改進

由于2L-OVRPTW模型同時優化兩個目標，文中設計出多目標蟻群優化算法，在改進的蟻群優化算法基礎上，采用Pareto最優解來進行多目標優化[17]。在2L-OVRPTW模型中選擇下一客戶時,在滿足車輛容量和時間窗約束的前提下,還需要考慮時間先后的擇優性,其啟發式因子由路徑距離和客戶的時間窗寬度等因素綜合決定，因此對狀態轉移的概率計算和信息素的更新等進行改進。

改進的多目標蟻群算法既可以在迭代運行過程中保持螞蟻種群的多樣性，也能夠保持Pareto解集的多樣性。

(19)

其中，τij(t)為t時刻客戶i或者倉庫到客戶j路徑上的信息素濃度；ηij(t)=1/dij為距離啟發式函數；θij(t)=1/twidthj為時間啟發式函數。

啟發式函數表示t時刻客戶i或者倉庫到客戶j的轉移期望程度；allowk為螞蟻k待訪問的客戶集合。

在螞蟻狀態轉移過程中引入偽隨機概率規則，以克服螞蟻狀態轉移速度慢的不足，規則如下：

j=

其中，r為在[0,1]上服從均勻分布的隨機變量；參數r0為用來控制轉移規則的概率。若r≤r0，則從待服務的客戶中找出概率最大的客戶為下一服務客戶；否則就根據式19并運用輪盤賭法按概率選擇出下一個服務客戶。

為了避免路徑上的信息素濃度差異過大，引入信息素最低閾值τmin,避免算法過早陷入局部最優。當螞蟻完成一次循環后，路徑上的信息素會揮發，螞蟻也會留下信息素，需要對各個路徑上的信息素進行更新，規則如下：

τij(t+1)=max(ρ·τij(t)+Δτij,τmin)

(21)

(22)

(23)

2.2.2 算法主要步驟

步驟1：編碼采用整數編碼方式并初始化參數。

步驟2：配送中心為螞蟻的當前起點，將所有客戶納入待服務集合表allow中，清空禁忌表Tabu。

步驟3：螞蟻在當前位置根據狀態轉移規則(式20)從集合表allow中選擇下一服務客戶j，并用二維裝載策略對客戶j的貨品進行裝載。

(1)如無法裝入或超重，則放棄服務客戶j，將螞蟻位置更新到配送中心，并分配新車輛，轉步驟3。

(2)如果裝入成功并且不超重，則更新螞蟻位置到客戶j，將客戶j從集合表allow轉移到禁忌表Tabu中，并重復步驟3直至所有客戶全部被服務到。

步驟4：計算種群中每只螞蟻所走路徑的總長度、路線和目標值等信息，并根據各個螞蟻之間的支配關系構建和更新非劣解集Nset。

步驟5：根據式21～23更新螞蟻種群的信息素濃度表τ。

步驟6：若迭代次數NC未達到最大迭代次數NCmax,則迭代次數NC=NC+1,并轉到步驟2；否則，輸出非劣解集Nset，結束。

3 實驗結果及分析

文中所有程序采用MATLAB編寫，在Inter 酷睿 I7-7500U CPU 3.5 GHz、內存4.0 GB的計算機上運行。目前2L-OVRPTW問題尚且沒有標準的測試數據庫，因此通過對已有的測試實例庫進行改造并設計了一個實例來進行算法分析。

為了比較提出的調度優化方法的性能，分別采用遺傳算法(A)、混合粒子群算法(B)與提出的調度優化方法(C)，對標準Solomon實例庫的三個不同類別實例C101、R101和RC101進行改造，多次運行并取平均結果，得到的運行情況如表1所示。通過比較可以看出，用車數量和算法運行時間基本一樣，而行駛距離有大幅減少，客戶滿意度也略有提高。總體而言，文中算法明顯優于其他兩種算法。

表1 算法比較

將文中算法用于求解某國際物流公司的車輛調度問題的一個實例。在該實例中，物流公司有1個配送中心，為33個客戶進行貨物配送，每個客戶位于不同的坐標上，并有不同種類貨物的需求。

在求解過程中，種群大小為50，迭代次數為200，得到Pareto最優解集為(2 413.9，0.57)，(2 429.1，0.60)，(2 478.3，0.64)，(2 544.0，0.72)，(2 682.1，0.76)，(2 835.9，0.79)，如圖3所示。分別選取2個目標向量的調度線路，如表2所示。

表2 優化調度線路

4 結束語

一般的車輛調度方法都是滿足在客戶的需求下，僅從經濟因素的角度出發，追求最短的行駛距離或者最低的成本。而在當前激烈的市場競爭環境下，現代物流企業需要綜合考慮時間窗、二維裝載約束和客戶滿意度等情況，提高企業競爭力。結合實際情況，文中描述了2L-OVRPTW問題并建立相應模型，以多目標蟻群優化算法為大體框架，并融合改進的最低水平線搜索算法，對模型進行求解，同時優化貨物裝載和配送路線。實驗結果表明，該方法可以在較短的時間內獲得模型問題的滿意解，滿足車輛調度的實時性需求，并具有較高客戶滿意度和較短的行駛路程。文中設計的模型和車輛調度方法對于現代物流企業科學并合理地開展物流調度工作有一定的理論指導和借鑒意義。