時間窗罰函數(shù)在物流優(yōu)化計(jì)算中的作用研究

李雪陽，魏曉波，趙 凱

（沈陽工業(yè)大學(xué)，遼寧 遼陽 111000）

0 引言

帶時間窗的車輛路徑問題（Vehicle Routing Problems with Time Windows，VRPTW）由車輛路徑問題（Vehicle Routing Problems，VRP）添加時間窗約束演變而來，一般是指：組織一定的運(yùn)輸車輛以適當(dāng)?shù)男熊嚶肪€，在規(guī)定的時間窗口范圍內(nèi)，把貨物送達(dá)給一系列不同需求的客戶，并以配送成本最低或路徑里程最短，或時間耗費(fèi)最少等一個方向或多個方向?yàn)閮?yōu)化目標(biāo)。時間窗約束是VRPTW 研究中不可回避的問題，也是多數(shù)優(yōu)化問題需要考慮的充分必要條件，研究帶時間窗的物流配送的最優(yōu)化問題，符合社會生活實(shí)際。物流學(xué)者研究的VRPTW 優(yōu)化問題，時間窗呈現(xiàn)不同的表現(xiàn)形式。從時間窗邊界來劃分，時間窗類型基本可分為硬時間窗、軟時間窗、模糊時間窗，本文從時間窗罰函數(shù)的角度出發(fā)，研究不同時間窗的性質(zhì)和應(yīng)用場景。

1 時間窗與罰函數(shù)

VRPTW 問題本質(zhì)上屬于有約束的離散變量的尋優(yōu)問題，一般使用遺傳算法、蟻群算法、模擬退火算法、列表搜索算法等啟發(fā)式算法編程計(jì)算。而啟發(fā)式算法都是從一個或一組初始解出發(fā)，在算法程序的控制下產(chǎn)生若干鄰域解，這些鄰域解中必然包含大量的不可行解，消除這些不可行解的最常用的辦法就是構(gòu)造罰函數(shù)，在程序運(yùn)行迭代過程中從不可行解域移動到可行解域，逐漸淘汰罰函數(shù)值較大的個體，實(shí)現(xiàn)目標(biāo)函數(shù)值收斂，從而達(dá)到尋優(yōu)目的。

1.1 硬時間窗及其罰函數(shù)

硬時間窗是一種剛性時間約束，是客戶最早至最晚可接受車輛配送服務(wù)的時間區(qū)間，客戶只在此窗口期接受服務(wù)，早到需等待，遲到則不接受服務(wù)。常見硬時間窗如圖1 所示，客戶只在［ET，EL］時間段接受服務(wù)，此區(qū)間罰函數(shù)值為0，區(qū)間外罰函數(shù)值為，是個足夠大的正數(shù)。

圖1 硬時間窗罰函數(shù)

車輛在時刻到達(dá)客戶，罰函數(shù)公式如下：

由硬時間窗構(gòu)造的罰函數(shù)較為簡單，使有約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題，簡化了程序處理過程。但硬時間窗罰函數(shù)值由于非0 即的函數(shù)特性，不能細(xì)化函數(shù)值，不便于構(gòu)造滿意度函數(shù)；同時，由于硬時間窗要求的嚴(yán)苛性，在優(yōu)化計(jì)算中可能存在不可行解，導(dǎo)致優(yōu)化失敗。

1.2 軟時間窗及其罰函數(shù)

軟時間窗是一種彈性時間窗，包含客戶的期望服務(wù)時間和可接受服務(wù)時間。如果把本文上一節(jié)提到的硬時間窗看作是客戶的期望服務(wù)時間，那么軟時間窗就是客戶的可接受服務(wù)時間，可以把軟時間窗看作是硬時間窗的有限外延。服務(wù)應(yīng)盡可能在硬時間窗內(nèi)開始，如有提前或延誤也不能超出軟時間窗，如圖2 所示，［ET，LT］區(qū)間為原來的硬時間窗，［EET，ET］和［LT，ELT］區(qū)間就是軟時間窗?？蛻粼谡麄€［EET，ELT］時間區(qū)間內(nèi)均可接受服務(wù)，配送服務(wù)早于EET 和晚于ELT 則客戶不接受服務(wù)。

圖2 軟時間窗罰函數(shù)

車輛在時刻到達(dá)客戶，罰函數(shù)公式如下：

一些學(xué)者認(rèn)為，軟時間窗總是存在可行解，在硬時間窗基礎(chǔ)上擴(kuò)展時間段形成軟時間窗，則可通過罰函數(shù)實(shí)現(xiàn)與硬時間窗一樣的評價(jià)。另外，軟時間窗分段函數(shù)可以在［EET，ELT］范圍內(nèi)量化函數(shù)值，越偏離［ET，LT］時間窗罰函數(shù)值越高，軟時間窗可以約束服務(wù)者的送貨準(zhǔn)時率，提高服務(wù)水平。

部分學(xué)者認(rèn)為軟時間窗的線型分段函數(shù)，不足以反映時間的緊迫性要求，構(gòu)建了指數(shù)函數(shù)形式的分段函數(shù)，如圖3 所示，越接近最早和最晚的軟時間窗上下限，函數(shù)圖形越陡峭，函數(shù)值變化越快；也有學(xué)者認(rèn)為早到只是未達(dá)到客戶期望，罰函數(shù)值較小，構(gòu)建了圖4所示的分段函數(shù)，另有學(xué)者認(rèn)為早到對于客戶并無損失，構(gòu)建了如圖5 所示的分段函數(shù)；還有部分學(xué)者考慮了車輛早到等待成本問題，構(gòu)造了更加復(fù)雜的分段函數(shù)，如圖6 所示。另外，還有其他類型的一些軟時間窗罰函數(shù)。

圖3 軟時間窗罰函數(shù)類型一

圖4 軟時間窗罰函數(shù)類型二

圖5 軟時間窗罰函數(shù)類型三

圖6 軟時間窗罰函數(shù)類型四

物流配送的及時與否是反映用戶滿意度的重要指標(biāo)，考慮加入其他影響滿意度的因素，即可構(gòu)建軟時間窗滿意度函數(shù)，貨品越接近客戶的期望時間窗送達(dá)，客戶滿意度就越高。

1.3 模糊時間窗及其罰函數(shù)

模糊時間窗是學(xué)者根據(jù)模糊理論，通過建立模糊隸屬度函數(shù)在硬時間窗的基礎(chǔ)上構(gòu)建的虛時間窗，目的是引入滿意度函數(shù)，在犧牲部分客戶滿意度的情況下，進(jìn)一步壓縮物流企業(yè)配送成本。多數(shù)學(xué)者采取定值擴(kuò)大或隨機(jī)擴(kuò)大原有時間窗的方法，理論上對原有時間窗進(jìn)行模糊化處理，在程序?qū)嶋H運(yùn)行中再進(jìn)行去模糊化處理，擴(kuò)大了可行解范圍。兩種類型的模糊時間窗罰函數(shù)分別如圖7、圖8 所示，［ET，LT］為原有的硬時間窗，［FET，ET］和［LT，F(xiàn)LT］即為擴(kuò)展后的模糊時間窗（Fuzzy Windows），模糊時間窗罰函數(shù)和軟時間窗類似，本文認(rèn)為模糊時間窗罰函數(shù)與軟時間窗并無本質(zhì)區(qū)別。

圖7 模糊時間窗罰函數(shù)類型一

圖8 模糊時間窗罰函數(shù)類型二

車輛在時刻到達(dá)客戶，模糊時間窗罰函數(shù)轉(zhuǎn)化的滿意度函數(shù)如下：

式中為客戶的時間敏感度，也可取值為1，變成線性分段函數(shù)。

模糊時間窗的確立，構(gòu)建了客戶滿意度函數(shù)，在優(yōu)化計(jì)算中可以在客戶滿意度和運(yùn)營成本之間權(quán)衡考慮，降低局部客戶滿意度，達(dá)到運(yùn)營成本最優(yōu)的目的。

1.4 時間窗特點(diǎn)及應(yīng)用場景

本文對帶有硬時間窗、軟時間窗、模糊時間窗的文獻(xiàn)進(jìn)行了研究，三種時間窗的特點(diǎn)和應(yīng)用場景見表1。

表1 時間窗特點(diǎn)及應(yīng)用場景

2 結(jié)論

在國家加快構(gòu)建國內(nèi)統(tǒng)一大市場的背景下，物流行業(yè)必將迎來新的發(fā)展機(jī)遇，優(yōu)化資源配置、降低企業(yè)成本成為不容忽視的問題。物流成本優(yōu)化越來越凸顯其重要性，而時間窗是優(yōu)化計(jì)算中必須考慮的因素。大量研究者提供的優(yōu)化應(yīng)用與實(shí)踐使得各類時間窗體系框架日臻成熟，硬時間窗、軟時間窗、模糊時間窗在VRPTW 優(yōu)化計(jì)算中，由于側(cè)重點(diǎn)和優(yōu)化場景的不同，分別扮演了不同角色。

從優(yōu)化場景的角度看，優(yōu)化計(jì)算中時間窗的設(shè)定應(yīng)貼近實(shí)際情況，在滿足客戶需求的同時，優(yōu)化物流企業(yè)運(yùn)營成本。從計(jì)算過程角度看，硬時間窗優(yōu)化計(jì)算步驟相對簡單，易于實(shí)現(xiàn)；軟時間窗更能適應(yīng)復(fù)雜多變的現(xiàn)實(shí)環(huán)境，需要考慮的變量也更加龐雜，計(jì)算過程也變得更為復(fù)雜；模糊時間窗則能在面對寬松時間窗需求的客戶時，利用模糊理論在計(jì)算中進(jìn)行模糊—清晰化處理，把物流企業(yè)的成本降低到一個新的水平。