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

潘 帥 陳鈺成 高 元 李文霞

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

0 引 言

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

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

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

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

1 帶軟時間窗的多種服務(wù)需求車輛調(diào)度問題數(shù)學(xué)模型

1.1 問題描述

貨物到達(dá)當(dāng)?shù)匚锪鲌@后，根據(jù)物流信息，電商企業(yè)物流中心通知該貨主隸屬的區(qū)域服務(wù)中心安排車輛和技工進(jìn)行上門服務(wù).僅有配送需求的貨主，區(qū)域負(fù)責(zé)人只需安排一輛配送車完成配送任務(wù)；有配送和安裝需求的貨主，區(qū)域負(fù)責(zé)人需安排一輛配送車和一輛安裝車分別完成配送和安裝任務(wù)，安裝車應(yīng)在配送車完成配送任務(wù)后的60 min內(nèi)到達(dá)貨主處提供安裝服務(wù)，過早或者過晚的到達(dá)貨主處，均會產(chǎn)生懲罰成本.即已知區(qū)域服務(wù)中心和貨主處的位置、貨物體積、服務(wù)需求、配送服務(wù)時間窗、配送車輛車廂裝載體積等信息.目標(biāo)是在滿足各個貨主的服務(wù)需求條件下，如何調(diào)度配送車和安裝車，使得整個服務(wù)過程的總成本最小.圖1為多種服務(wù)需求車輛調(diào)度問題示意圖.

圖1 多種服務(wù)需求車輛調(diào)度問題示意圖

1.2 模型假設(shè)

1) 物流園與電商企業(yè)區(qū)域服務(wù)中心的距離可以忽略不計.

2) 全部車輛從電商企業(yè)區(qū)域服務(wù)中心出發(fā)，完成任務(wù)后回到出發(fā)地.

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

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

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

1.3 模型符號定義

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

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

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

?i,j∈N,s∈S

(1)

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

?i,j∈N,k∈K

(2)

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

(3)

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

(4)

1.4 模型數(shù)學(xué)表達(dá)

基于對上述問題的分析，建立帶軟時間窗的多種服務(wù)需求車輛調(diào)度問題數(shù)學(xué)模型，為

(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)

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

2 帶軟時間窗的多種服務(wù)需求車輛調(diào)度問題的禁忌搜索算法

2.1 算法簡介

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

圖2 禁忌搜索算法常規(guī)流程圖

2.2 算法改進(jìn)

2.2.1解的結(jié)構(gòu)

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

2.2.2鄰域變換規(guī)則

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

圖3 鄰域變換規(guī)則示意圖

2.2.3禁忌表

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

2.2.4禁忌對象

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

2.2.5禁忌長度

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

3 算例研究及其分析

3.1 數(shù)據(jù)生成及處理

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

表1 電商企業(yè)區(qū)域服務(wù)中心數(shù)據(jù)信息

表2 貨主數(shù)據(jù)信息

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

圖4 算例中各個節(jié)點分布圖

3.2 算例結(jié)果及分析

3.2.1禁忌搜索算法及近似解

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

表3 近似求得服務(wù)車輛的調(diào)度方案

圖5 近似求得的服務(wù)車輛調(diào)度路線圖

3.2.2Lingo及精確解

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

表4 精確求得服務(wù)車輛的調(diào)度方案

圖6 精確求得的服務(wù)車輛調(diào)度路線圖

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

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

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

圖7 隨機生成案例的服務(wù)車輛調(diào)度路線圖

4 結(jié) 束 語

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

文中建立的模型與算法可以在短時間內(nèi)得到帶軟時間窗的多種服務(wù)需求車輛調(diào)度問題的較優(yōu)可行解，在未來研究中，可同時考慮兩類子問題，進(jìn)一步優(yōu)化禁忌搜索算法，解決多種服務(wù)需求車輛調(diào)度問題.