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

李雪陽，魏曉波，趙 凱

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 結(jié)論

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

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