軟時間窗車輛路徑優(yōu)化懲罰函數(shù)研究綜述

摘 要：軟時間窗車輛路徑問題作為車輛路徑問題中的一部分，對于提高配送滿意度至關重要，直接影響企業(yè)的發(fā)展。文章總結國內外研究的一些軟時間窗懲罰函數(shù)類型、對相關研究人員研究的模型以及求解算法進行總結，并在此的基礎上，對今后軟時間窗的類型以及適用范圍進行相應的展望。

關鍵詞：軟時間窗;懲罰函數(shù);車輛路徑問題

隨著社會的進步和信息技術的發(fā)展，人們對于生活水平的要求也有所提高，對于服務質量要求也有所提高，關注的方面也逐步上升到服務的速度方面。而運輸速度的體現(xiàn)的標準之一就是到達客戶點的時間，因此，時間窗便成為了運輸業(yè)需要考慮的一個方面。對于服務行業(yè)而言，顧客滿意度也是制約企業(yè)發(fā)展的重要因素。對于運輸行業(yè)而言，運輸成本最低是獲利的有效途徑，而運輸成本的高低衡量的標準是車輛路徑的長短。因此，時間窗也就隨之和車輛路徑優(yōu)化相結合在一起，對于運輸行業(yè)而言，運輸?shù)囊蟛粌H僅在于將貨物運輸?shù)筋櫩褪种?，還要在顧客所限制的時間范圍內，對此，這類問題的研究就顯得尤為重要。

1 軟時間窗車輛路徑懲罰函數(shù)類型

依據(jù)懲罰函數(shù)的形狀可以分為線性軟時間窗和非線性軟時間窗，依據(jù)時間窗的圖形的類型可以分為全軟時間窗和半軟時間窗。目前，國內研究的軟時間窗類型多集中于線性全軟時間窗。圖1為原先開始研究的懲罰函數(shù)圖形，隨著研究的深入，于2004年左右，對于原始圖的最低點有所上升，形成圖2所示的圖形。到2015年左右，考慮到：服務車輛早到，客戶沒有損失;服務車輛晚到，降低客戶滿意度，帶來的影響比較大，因此設置的懲罰系數(shù)較大。因此，形成了圖3所示的圖形。此外，也存在只考慮到達時間較晚的懲罰，而允許等待較早到達而不需要任何代價。再次基礎之上形成了相應的懲罰函數(shù)圖形，見圖4。至2018年，有研究人員在原始的基礎之上提出軟時間窗的折線懲罰函數(shù)，見圖5。

針對軟時間窗的懲罰函數(shù)國內也有非線性，尤其是針對生鮮冷鏈物流運輸問題。最常見的一種類型是指數(shù)類型的，主要考慮的因素是顧客的需求和滿意度，一般而言，消費者在購買生鮮產品時，會傾向于購買距保質期限較長的產品，生鮮產品被銷售出的概率隨著到達銷售端時所剩下的保質時間的長度而遞減，并且遞減的速度隨著接近保存期限的程度而增加。因此選擇指數(shù)類型的懲罰函數(shù)進行表示，見圖6。此外，也有研究者認為：線性函數(shù)并不能反映實際情況，早到對于顧客沒有損失，但是對于企業(yè)會有其他方面損失，晚到有必要體現(xiàn)客戶被服務的體驗。因此，形成了圖7的懲罰函數(shù)類型。還有針對醫(yī)藥物流的運輸問題，所提出的兩種非線性懲罰函數(shù)。

國外對于軟時間窗車輛路徑的懲罰函數(shù)主要研究都集中于線性軟時間窗，對于研究其創(chuàng)新的方面主要集中于算法方面，主要是分為六種類型，見圖10-圖11。

2 軟時間窗車輛路徑優(yōu)化模型

國內軟時間窗車輛路徑問題構建的模型大致分為兩種：一種是將時間窗加入約束條件，目標函數(shù)以路徑最短，另外一種是將時間窗加入目標函數(shù)之中，有文獻是將其作為二級目標函數(shù)，以違反時間窗約束的時間最短，也有結合相應的懲罰成本，只構建一個目標函數(shù)。約束條件方面所考慮的因素是：每一個客戶只被服務一次，避免車輛路徑的迂回，進出客戶點的車輛數(shù)相等等。與原始的車輛路徑模型方面存在差異的部分在于目標函數(shù)，以及約束中要加入時間窗約束。解決這類問題的算法和車輛路徑問題所使用的算法一致，目前，仍以啟發(fā)式算法居多，精確算法的研究較少一些。

3 結論和展望

針對軟時間窗車輛路徑優(yōu)化的研究，目前國內國外的非線性研究比較少一些，對于線性時間窗車輛路徑的研究居多，模型上的改變多數(shù)集中于軟時間窗的懲罰函數(shù)的變化，算法上的改進也是占據(jù)主流的一部分。懲罰函數(shù)的主要出發(fā)角度在于顧客的滿意度，對于不同的行業(yè)而言，軟時間窗的類型應該是不一樣的，對于這個方面，目前看來生鮮冷鏈物流上面有具體試用的軟時間窗，其他類型的物流是沒有的。因此，這個問題可以作為研究軟時間窗車輛路徑問題的一個角度。此外，很明顯線性軟時間窗是簡化了現(xiàn)實情況下因素而形成的，非線性軟時間窗更加貼合實際，因此，非線性軟時間窗應該也可以作為一個研究的角度。

參考文獻：

[1]趙冰潔.配送中心配送方案優(yōu)化研究[D].西南交通大學，2004.

[2]葛顯龍，辜羽潔，譚柏川.基于第三方帶軟時間窗約束的車輛路徑問題研究[J].計算機應用研究，2015，32（03）：689-693.

[3]Ali Gul Qureshi，Eiichi Taniguchi，Tadashi Yamada.Exact solution for the vehicle routing problem with semi soft time windows and its application[J].Procedia -Social and Behavioral Sciences，2010，2（3）.

[4]韓亞娟，彭運芳，魏航，史保莉.超啟發(fā)式遺傳算法求解帶軟時間窗的車輛路徑問題[J/OL].計算機集成制造系統(tǒng)，1-16[2019-03-29].

[5]李澤華.帶時間窗約束的生鮮產品配送車輛路徑優(yōu)化問題研究[D].大連海事大學，2009.

[6]賀小涵.帶軟時間窗的動態(tài)車輛路徑規(guī)劃問題研究與實現(xiàn)[D].哈爾濱工業(yè)大學，2017.

[7]武佳佳.時間窗約束下醫(yī)藥物流配送路徑優(yōu)化研究[D].山東師范大學，2018.

[8]Fu Z，Eglese R，Li L Y O.A unified tabu search algorithm for vehicle routing problems with soft time windows[J].Journal of the Operational Research Society，2008，59（5）：663-673.

作者簡介：陳婷（1995-），女，漢族，江蘇人，研究生在讀，研究方向：時間窗車輛路徑優(yōu)化問題。