帶軟時間窗的多種服務需求車輛調度問題及其禁忌搜索算法研究

潘 帥 陳鈺成 高 元 李文霞

(九江職業技術學院汽車工程學院1) 九江 332007) (蘭州交通大學交通運輸學院2) 蘭州 730070)

0 引 言

對于需要專業安裝的大件貨物，絕大多數的電商企業將配送服務與安裝服務獨立分開，而貨主則希望在收到貨物后可以盡快獲得安裝服務.因此，電商企業在權衡服務質量與配送成本的同時，既要提高貨主購物滿意度，又要盡可能的降低配裝總成本，實現總利潤最大化[1].文中針對配送服務與安裝服務獨立分開的工作模式，研究帶軟時間窗的多種服務需求車輛調度問題(multi-demand vehicle routing problem with soft time window，MVRPSTW)，更符合實際工作情況.

單一服務需求的車輛調度問題研究主要集中在對經典車輛調度問題加入不同約束條件或是改進求解算法等方面.謝九勇等[2]以啟動車輛數、運行費用和非時間窗內服務產生的懲罰成本之和最小為目標函數，設計求解該問題的禁忌搜索算法.李陽等[3]針對模糊需求車輛路徑問題，提出一種新的兩階段變鄰域禁忌搜索算法，對預優化方案進行調整.李明燏等[4]構建了帶軟時間窗約束的異構車輛路徑數學模型，在傳統禁忌搜索算法的基礎上加入了車輛排序準則和等級成本結構原則，設計一種新的解決車輛路徑問題的算法，彌補了傳統禁忌搜索算法的劣勢.

多種服務需求的車輛調度是近幾年才提出的熱點問題.Bae等[5]研究了一種變形的車輛調度問題，即將商品的配送與安裝步驟分離，安裝車輛必須在配送車輛訪問貨主后的規定時間內到達，提高服務質量.Polat等[6]研究了取送混合車輛路徑問題，即每個客戶處的取送貨物可以一次完成訪問，也可以分兩次進行送貨任務與取貨任務，建立了取送混合車輛路徑問題的數學模型.

貨物多種服務需求數學模型可看作是不同種類車輛調度問題的組合[7]，即第一階段是配送車輛調度問題；第二階段是安裝車輛調度問題.由于該數學模型的復雜程度遠大于經典車輛調度問題，Kim[8]引入“分階段”概念將該變形的車輛調度問題轉化為多個子問題的組合，降低求解難度.龐海軍等[9]建立以配送、安裝時間最小為目標的數學模型，采用“分階段”思想，改進遺傳算法對問題進行求解.文章基于既有研究，在貨物多種服務需求車輛調度模型中，加入配送車輛超時工作的折損成本、軟時間窗約束、車廂裝載體積約束，沿用“分階段”的思想，將帶軟時間窗的多種服務需求車輛調度問題看作是兩類子問題的組合：第一階段是配送車輛調度問題；第二階段是安裝車輛調度問題.算例求解時，為增強求解性能，改進禁忌搜索算法，對當前解采用兩種領域變換規則，即0-1變換、0-2變換.將改進算法的解與Lingo所得解比較，證明文章模型與算法的有效性.最后，隨機生成多個案例，證明文章模型與算法可以有效處理此類問題.

1 帶軟時間窗的多種服務需求車輛調度問題數學模型

1.1 問題描述

貨物到達當地物流園后，根據物流信息，電商企業物流中心通知該貨主隸屬的區域服務中心安排車輛和技工進行上門服務.僅有配送需求的貨主，區域負責人只需安排一輛配送車完成配送任務；有配送和安裝需求的貨主，區域負責人需安排一輛配送車和一輛安裝車分別完成配送和安裝任務，安裝車應在配送車完成配送任務后的60 min內到達貨主處提供安裝服務，過早或者過晚的到達貨主處，均會產生懲罰成本.即已知區域服務中心和貨主處的位置、貨物體積、服務需求、配送服務時間窗、配送車輛車廂裝載體積等信息.目標是在滿足各個貨主的服務需求條件下，如何調度配送車和安裝車，使得整個服務過程的總成本最小.圖1為多種服務需求車輛調度問題示意圖.

圖1 多種服務需求車輛調度問題示意圖

1.2 模型假設

1) 物流園與電商企業區域服務中心的距離可以忽略不計.

2) 全部車輛從電商企業區域服務中心出發，完成任務后回到出發地.

3) 區域服務中心有足夠多的可用配送車和可用安裝車.

4) 配送車在貨主處提供的配送服務時間可忽略不計，文章認為是連續工作，因此存在正常工作的最大時常.

5) 所有車輛在工作過程中運行速度相同，各貨主處與區域服務中心直線連接.

1.3 模型符號定義

為建立帶軟時間窗的多種服務需求車輛調度問題數學模型，設M={0}為區域服務中心；s為配送車輛；k為安裝車輛；E={1,2,…,n}為所有貨主的集合，其中，每一個貨主均有配送需求；A為有安裝需求的貨主集合，A?E；N為所有貨主E和區域服務中心M的節點集合，N=E∪M；I為區域服務中心M和有安裝需求的貨主的集合，I=A∪M.

定義以下參數：qs為配送車輛s的車輛車廂裝載體積，m3；W1為配送車s行駛的單位時間費用,元/h；W2為安裝車k行駛的單位時間費用,元/h；Cs為啟動配送車輛s產生的費用,元/輛；Ck為啟動安裝車輛k產生的費用,元/輛；tij為車輛從貨主i到貨主j的行駛時間，min；tki為安裝車k為貨主i提供安裝服務的時間,min；ei為貨主i允許配送車s到達的最早時間,min；li為貨主i允許配送車s到達的最晚時間,min；Ts為配送車s正常工作的最大時常，min；di為貨主i的貨物體積，m3；Qt為電商企業的服務水平，即貨主i的配送時間與安裝時間允許的最大間隔時間，min；S1為配送車s早到達貨主處所產生的時間等待成本,元/h；S2為配送車s晚到達貨主處所產生的時間懲罰成本,元/h；ais為配送車s到達貨主i的時間，min；bia為安裝車a到達貨主i的時間，min；Ei為配送車s早到達貨主i處的等待時間，min；Li為配送車s晚到達貨主i處的延誤時間，min；δ為配送車s超時工作的車輛單位損耗成本，元/h.

定義0-1輔助決策變量vijs，為配送車s的服務順序.

?i,j∈N,s∈S

(1)

定義0-1輔助決策變量uijk，為安裝車k的服務順序.

?i,j∈N,k∈K

(2)

定義0-1輔助決策變量ys，為是否啟動配送車s.

(3)

定義0-1輔助決策變量xk，為是否啟動安裝車k.

(4)

1.4 模型數學表達

基于對上述問題的分析，建立帶軟時間窗的多種服務需求車輛調度問題數學模型，為

(5)

s.t.

(6)

(7)

(8)

(9)

ajs≥ais+Ei+tij,?i,j∈N,s∈S

(10)

bjk≥bik+Li+tij,?i,j∈I,k∈K

(11)

(12)

ais+Qt≥bik≥ais+Ei,

?i∈A,k∈K,s∈S

(13)

ei≤ais+Ei-Li≤li,?i,j∈I,s∈S(14)

vijs∈{0，1} ?i,j∈N,s∈S

(15)

uijk∈{0，1} ?i,j∈I,k∈K

(16)

ys∈{0，1} ?s∈S

(17)

xk∈{0，1} ?k∈K

(18)

目標函數(5)為配送、安裝成本最小化，其中包括配送車和安裝車的啟動成本、運行成本、配送車未在規定時間內提供服務產生的懲罰成本、配送車超時工作的折損成本.約束條件：式(6)～式(7)為全部的配送、安裝車均從區域服務中心出發.式(8)為每一位有配送需求的貨主均有一輛配送車提供服務.式(9)為每一位有安裝需求的貨主均有一輛安裝車提供服務.式(10)為配送車到達貨主處完成配送任務后再進行下一個配送任務的順序關系.式(11)為安裝車到達貨主處完成安裝任務后再進行下一個安裝任務的順序關系.式(12)為配送車所載貨物的體積不超過車輛車廂裝載體積.式(13)為安裝車應在配送車完成配送任務后的有效服務時間內到達貨主處提供安裝服務.式(14)為配送車在貨主規定的時間窗限制內完成配送任務.

2 帶軟時間窗的多種服務需求車輛調度問題的禁忌搜索算法

2.1 算法簡介

禁忌搜索算法(tabu search,TS)是一種亞啟發式(meta-heuristic)隨機搜索算法，通過模擬人的思維，利用短期記憶或者長期記憶保證算法實現全局最優解[10-11].常規流程見圖2.

圖2 禁忌搜索算法常規流程圖

2.2 算法改進

2.2.1解的結構

算法中，使用一條鏈帶來表示可行解中的一條路徑順序，每條鏈帶中存放的數字就是路徑順序中的貨主編號.文章不采用特殊的算法產生初始解，但是初始解中每條路徑順序上都有一個編號為0的地點，即電商企業區域服務中心.

2.2.2鄰域變換規則

鄰域變換規則(neighborhoods changed rules，NCR)可以很大程度的影響算法跳出區域局部解的能力，決定著算法的爬山能力.為增強禁忌搜索算法的求解性能，文章對當前解采用兩種鄰域變換規則：0-1變換、0-2變換.其中：0-1變換為在第2條路徑順序中任意選擇一個編號到第1條路徑順序中去；0-2變換為在第2條路徑順序中任意選擇兩個編號到第1條路徑順序中去.圖3為鄰域變換規則示意圖.

圖3 鄰域變換規則示意圖

2.2.3禁忌表

禁忌表(tabu list)是為了確保禁忌搜索算法在搜索過程中不會出現循環現象，它可以記錄之前服務的貨主編號、服務順序、或目標函數值[12].將此禁忌表設置為先入先出隊列(first in first out，FIFO)，即最初在禁忌表中的貨主編號，在禁忌表長度超過設定值后，先被引退.

2.2.4禁忌對象

禁忌對象(tabu object)是指在禁忌表中不能發生變化的對象，文章將有序數對(ordered pair)作為禁忌對象.如有序數對(2,5)為貨主編號為2與5，保證編號2的數值不大于編號5.在算法搜索過程中,若找到了最優的鄰域可行解,則設可行解中兩個貨主編號置為2與5,將禁忌對象(2,5)存儲在禁忌表里.

2.2.5禁忌長度

禁忌長度(tabu length)對禁忌搜索算法的求解效率高低與解的質量優劣有重要影響.文章將禁忌長度設置為一個定值常數.

3 算例研究及其分析

3.1 數據生成及處理

假設D為F市的物流園區，日常負責F市及周圍區域的貨物集散、倉儲管理、商貿展覽、增值加工等工作.某大型電商企業區域服務中心緊鄰物流園區D，負責該企業在F市及周圍區域貨主的配送與安裝工作.已知配送車啟動成本為40元/輛，安裝車啟動成本為30元/輛，配送車與安裝車在啟動后以30 km/h的恒定速度運行(忽略加速與減速時間)，單位運輸成本均為5元/km.配送車的有效裝載體積為45 m3，每天的有效服務時長為5 h，車輛超時工作產生的折損成本為80元/h.配送車早到達貨主規定時間產生的時間等待成本為200元/h,晚到達貨主規定時間造成的時間懲罰成本為300元/h.安裝車及安裝技師在貨主處提供服務的時間均為20 min，早到不產生等待成本，晚于到達貨主規定時間產生的時間懲罰成本為400元/h.根據已知的時間要求，服務中心安排車輛對25個貨主提供配送與安裝服務，使得服務成本最小化.服務中心與25個貨主的信息見表1～2.

表1 電商企業區域服務中心數據信息

表2 貨主數據信息

算例中的物流園區D與25個貨主點的分布見圖4.其中，“■”為區域服務中心.

圖4 算例中各個節點分布圖

3.2 算例結果及分析

3.2.1禁忌搜索算法及近似解

設算法的最大迭代次數為1 000，禁忌時長為100.算例的結果是需要8臺配送車為25個貨主提供配送服務，隨后，需要5臺安裝車為9個貨主提供安裝服務.表3為近似解求得服務車輛調度方案，圖5為服務車輛調度路線圖.由表3可知，本次服務總成本最小為8 158.357元.在這8條配送路徑中，均是在貨主規定的時間內完成配送任務，并且這8輛車均在有效工作時長內工作；5臺安裝車也均是在配送車離開后的60 min內到達貨主處進行安裝作業.其中，配送車4的運行時間是最長的，為286.846 min；安裝車5的運行時間是最長的，為291.567 min.

表3 近似求得服務車輛的調度方案

圖5 近似求得的服務車輛調度路線圖

3.2.2Lingo及精確解

表4為精確求得服務車輛的調度方案，由表4可知，配送與安裝的總成本最小為7 053.738元.圖6為精確求得的服務車輛調度路線圖.在這7條配送路徑中，均是在貨主規定的時間內完成配送任務，并且這7輛車均在有效工作時長內工作；3輛安裝車也均是在配送車離開后的60 min內到達貨主處進行安裝作業.其中，配送車5的運行時間是最長的，為286.644 min；安裝車2的運行時間是最長的，為308.528 min.

表4 精確求得服務車輛的調度方案

圖6 精確求得的服務車輛調度路線圖

3.2.3近似解與精確解的分析比較

通過使用Lingo11求解算例，需要經過367.812 s.使用禁忌搜索算法，第一階段問題求解需要27.732 s，第二階段問題求解需要9.376 s.引用“分階段”概念對帶軟時間窗的多種服務需求車輛調度問題進行分級考慮，將它看成是兩類子問題的組合，使用禁忌搜索算法對算例進行近似求解；再使用Lingo對算例進行精確求解.由表3～4可知，禁忌搜索算法得到的近似解雖沒有比Lingo得到的精確解好，但可以在較短時間內得到可行解.

Lingo對于計算規模較小的問題，可以精確計算，但是對于較大規模的問題，程序運行時間較長.在實際工作中，信息數據可能會更多，因此Lingo不適用于實際工作中.禁忌搜索算法可以在較短的時間內，求得一個較優的可行解，更加適用在實際工作情景中.文章為更好的對“分階段”近似求解方法進行有效性分析，隨機生成多個規模不同的案例.其中，圖7為其中一個案例的服務車輛調度路線圖，可以看出“分階段”的近似求解方法可在較短時間內找到問題的可行解.

圖7 隨機生成案例的服務車輛調度路線圖

4 結 束 語

文中研究帶軟時間窗的多種服務需求車輛調度問題，建立以配送費與安裝費之和最小為目標函數的混合整數規劃模型.將求解模型采用分層方法處理，簡化原問題的復雜度，改進禁忌搜索算法對算例近似求解.將近似解與Lingo所得的精確解比較可知，配送車調度路徑直接影響安裝車調度路徑；要保證整個服務過程中總成本最小，配送車調度路徑最優解未必是整個問題的最優解；求得精確解所消耗的時間遠多于近似解時間，且不能大幅降低服務總成本；在實際工作中，數據量可能更大，使用改進的禁忌搜索算法求解，可以提高服務效率，降低服務成本.

文中建立的模型與算法可以在短時間內得到帶軟時間窗的多種服務需求車輛調度問題的較優可行解，在未來研究中，可同時考慮兩類子問題，進一步優化禁忌搜索算法，解決多種服務需求車輛調度問題.