李雪陽，魏曉波，趙 凱

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 時間窗特點及應用場景

本文對帶有硬時間窗、軟時間窗、模糊時間窗的文獻進行了研究，三種時間窗的特點和應用場景見表1。

表1 時間窗特點及應用場景

2 結論

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

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