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

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

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

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

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

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

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

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

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

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

3 結(jié)論和展望

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

參考文獻(xiàn)：

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

[2]葛顯龍，辜羽潔，譚柏川.基于第三方帶軟時(shí)間窗約束的車輛路徑問題研究[J].計(jì)算機(jī)應(yīng)用研究，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]韓亞娟，彭運(yùn)芳，魏航，史保莉.超啟發(fā)式遺傳算法求解帶軟時(shí)間窗的車輛路徑問題[J/OL].計(jì)算機(jī)集成制造系統(tǒng)，1-16[2019-03-29].

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

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

[7]武佳佳.時(shí)間窗約束下醫(yī)藥物流配送路徑優(yōu)化研究[D].山東師范大學(xué)，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.

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