車輛路徑調(diào)度問(wèn)題的回顧

摘要：調(diào)度在車輛路徑選擇中常常扮演著重要的角色。本文描述了作者感興趣的幾個(gè)方向，包括路徑問(wèn)題中的速度優(yōu)化問(wèn)題，污染路徑問(wèn)題，并且作者提出了一些設(shè)想和展望。

關(guān)鍵詞：車輛路徑調(diào)度；時(shí)間窗口；速度優(yōu)化

一、引言

本文的目的是描述幾種時(shí)間和調(diào)度起著重要作用的路徑問(wèn)題。這種問(wèn)題出現(xiàn)的次數(shù)很多。我們的目的不是要對(duì)所有可能的案例進(jìn)行詳盡的調(diào)查或分類，而是要描述近年來(lái)的有趣的問(wèn)題。大多數(shù)車輛路徑研究都是基于對(duì)傳統(tǒng)車輛路徑問(wèn)題（VRP）的研究，該問(wèn)題包括通過(guò)一組地理上分散的客戶來(lái)確定車輛路線，且受到各種方面的限制。標(biāo)準(zhǔn)目標(biāo)是距離（或成本）最小化。這個(gè)問(wèn)題是由Dantzig和Ramser提出的，其研究從此演變成了一個(gè)豐富的研究領(lǐng)域。VRP中最常見(jiàn)的目標(biāo)是距離最小化。當(dāng)給路線持續(xù)時(shí)間施加上限時(shí)，通常將距離等同于旅行時(shí)間。但是，還有幾種情況需要分開(kāi)處理距離和時(shí)間。例如，在帶時(shí)間窗的車輛路徑問(wèn)題（VRPTW）中，必須在給定的任意位置開(kāi)始服務(wù)的時(shí)間間隔。如果車輛在時(shí)間窗口開(kāi)始之前到達(dá)某個(gè)位置，則必須等待。在這種情況下，旅行的距離和路線的持續(xù)時(shí)間顯然不相同。本文的其余部分安排如下。第2節(jié)至第3節(jié)分別討論了如下話題：路徑問(wèn)題中的速度優(yōu)化，污染路徑問(wèn)題。第5節(jié)中總結(jié)了本文的內(nèi)容。

二、路徑問(wèn)題的速度優(yōu)化

速度在路徑和調(diào)度問(wèn)題中很少出現(xiàn)作為決策變量。最近有關(guān)速度控制的研究主張減速作為降低成本和二氧化碳排放量的手段。這在當(dāng)今的經(jīng)濟(jì)和環(huán)境背景下尤為重要。海運(yùn)是減速可以產(chǎn)生可觀節(jié)省的運(yùn)輸活動(dòng)。為了說(shuō)明這種影響，據(jù)估計(jì)，在450美元/噸的燃料價(jià)格下，全世界燃油消耗量減少1%，將使成本降低12億美元以上，二氧化碳排放量減少1050萬(wàn)噸。由Norstad等人進(jìn)行的計(jì)算研究已經(jīng)表明，在合理的假設(shè)下，優(yōu)化航線的速度可以減少多達(dá)14%的油耗。Fagerholt等人的論文提出了一些海上運(yùn)輸?shù)乃俣瓤刂颇Ｐ秃退惴?。?jiǎn)而言之，二氧化碳排放量與燃料消耗量成正比，在某些領(lǐng)域，二氧化碳排放量是一個(gè)凸增速度函數(shù)。由于成本凸性，在具有時(shí)間窗的路線上，這意味著如果在時(shí)間窗開(kāi)始之前到達(dá)頂點(diǎn)，則高速航行是不理想的。航行速度最好慢一點(diǎn)，這樣可以不必等待。本文認(rèn)為一個(gè)固定的路線（v0，...，vn），其中在每個(gè)頂點(diǎn)vi的服務(wù)時(shí)間的開(kāi)始處施加時(shí)間窗[ai， bi ]?？偮窂匠掷m(xù)時(shí)間是給定的，即a0 = b0和an = bn。使用時(shí)間離散化，這個(gè)問(wèn)題可以很容易地轉(zhuǎn)化為有向無(wú)環(huán)圖上的最短路徑問(wèn)題。在一項(xiàng)后續(xù)研究中，Hvattum等人提出了一個(gè)精確的O（n2） 算法來(lái)解決這個(gè)問(wèn)題。只要旅行費(fèi)用是速度的凸函數(shù)，它就是有效的，它適用于海運(yùn)或地面運(yùn)輸。最初，該算法計(jì)算在時(shí)間an時(shí)到達(dá)vn所需的速度。然后確定路徑（v0， . . . ， vn）上的最大時(shí)間窗違規(guī)。例如，假設(shè)這個(gè)最大違規(guī)相當(dāng)于延遲到達(dá)頂點(diǎn)vi（ti>bi）。然后該算法以bi為到達(dá)時(shí)間在子路徑（v0， . . . ， vi）上重新計(jì)算更高的速度，并以bi為出發(fā)時(shí)間在子路徑（vi， . . . ， vn）上的較慢的速度。它在每個(gè)子路徑上以同樣的方式重復(fù)，直到不存在任何時(shí)間窗違規(guī)。在第3節(jié)，我們展示了如何使用速度優(yōu)化作為減少貨車卡車在或與運(yùn)輸中二氧化碳排放的工具。

三、污染路線問(wèn)題

在大多數(shù)國(guó)家，貨運(yùn)占二氧化碳排放量的很大一部分。舉例來(lái)說(shuō)，據(jù)估計(jì)，在英國(guó)貨運(yùn)占運(yùn)輸部門排放量的21%，占排放總量的6%。Bektas和Laporte的論文是首先研究車輛路線中二氧化碳排放量的文章之一。根據(jù)Barth等人和Barth和Boriboonsomsin的文章，一個(gè)給定類型的車輛在平坦的路段上消耗的能量可以近似為公式

A和B是正的常數(shù)。這兩個(gè)常數(shù)包括允許以能量單位（kWh）來(lái)衡量這兩個(gè)術(shù)語(yǔ)的技術(shù)因素。假定速度超過(guò)約40公里/小時(shí)的特定閾值，因?yàn)橥ǔ５陀谶@個(gè)速度駕駛商用車的效率會(huì)降低（參見(jiàn)Bektas和Laporte 2011）。行駛車輛產(chǎn)生的二氧化碳排放量或多或少與其消耗的能量成正比。Bektas和Laporte（2011）通過(guò)數(shù)學(xué)模型和各種示例的發(fā)展，闡述了車輛路線解決方案之間的各種相互作用。這些例子是以恒定的速度構(gòu)建的，沒(méi)有時(shí)間窗口。當(dāng)在頂點(diǎn)到達(dá)時(shí)間施加時(shí)間窗口時(shí)，應(yīng)用第2節(jié)中Hvattum等人的算法在給定路線上優(yōu)化速度是很容易的。后一個(gè)例子清楚地說(shuō)明了貨運(yùn)中速度和時(shí)間安排對(duì)二氧化碳排放量最小化的影響。設(shè)計(jì)數(shù)學(xué)模型是相對(duì)簡(jiǎn)單的，這種模型可以在時(shí)間窗存在的情況下，將一個(gè)或幾個(gè)車輛的能耗降至最低，并具有目標(biāo)函數(shù)（如（1））。但是，對(duì)于中等大小的實(shí)例，即使對(duì)于單個(gè)車輛，也無(wú)法準(zhǔn)確解決這些模型。Demir等人最近設(shè)計(jì)并測(cè)試了自適應(yīng)大鄰域搜索啟發(fā)式算法，該算法適用于大小符合實(shí)際的例子。在實(shí)踐中，要使運(yùn)營(yíng)商在能耗最小化目標(biāo)下設(shè)計(jì)路線可能是困難的，如果這樣做比在成本最小化目標(biāo)下獲得的解決方案成本更高。通常情況下，通過(guò)緩慢駕駛來(lái)減少燃料消耗，這對(duì)駕駛時(shí)間和工資會(huì)產(chǎn)生不利影響。Bektas和Laporte通過(guò)一些計(jì)算實(shí)驗(yàn)表明，考慮到二氧化碳成本和燃料成本（甚至急劇增加），這一結(jié)論仍然成立，因?yàn)轳{駛員成本往往占據(jù)整體解決方案成本的主導(dǎo)地位。例如Demir等人的文章，說(shuō)明可以通過(guò)自適應(yīng)大鄰域搜索算法來(lái)最小化結(jié)合運(yùn)營(yíng)成本和CO2排放的全局函數(shù)。

四、總結(jié)

我們已經(jīng)描述了幾個(gè)路徑問(wèn)題，其中調(diào)度起著重要的作用。對(duì)于調(diào)度的需求通常是由時(shí)間窗的存在引起的，調(diào)度也與速度控制有關(guān)，這通常被用作減少二氧化碳排放的手段。我們提供了兩個(gè)速度控制的例子，一個(gè)是遠(yuǎn)洋航運(yùn)，另一個(gè)是車輛路線。最后，有一些問(wèn)題需要幾輛車的同步，例如我們所描述的兩個(gè)弧路徑問(wèn)題。本文提供的例子反映了作者最近的研究興趣。它們顯然不代表調(diào)度在其中發(fā)揮重要作用的所有問(wèn)題。潛在的應(yīng)用數(shù)量非常大，我們希望這會(huì)吸引其他研究人員的興趣。在組合路由和調(diào)度方面存在一些有前景的研究途徑。第一個(gè)挑戰(zhàn)是將交通堵塞和速度的可變性納入最佳車輛路徑和時(shí)間表的計(jì)算中。第二個(gè)有趣的研究課題是在供應(yīng)鏈的不同層面上運(yùn)行的車輛的同步，例如在轉(zhuǎn)運(yùn)和跨接操作的情況下。最后，例如關(guān)于擁塞的實(shí)時(shí)信息的可用性的增加，這就要求開(kāi)發(fā)能夠有效地處理在線信息和動(dòng)態(tài)更新解決方案的算法。（作者單位：重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院）

作者簡(jiǎn)介：劉天鶴，1993年生，男，滿族，研究生，研究方向：物流工程。

參考文獻(xiàn)

[1]Baldacci R， Mingozzi A， Roberti R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints[J]. European Journal of Operational Research， 2012（218）：1–6.

[2]Barth M， Boriboonsomsin K. Energy and emissions impacts of a freeway-based dynamic ecodriving system[J]. Transportation Research. Part D， 2009（14）： 400–410.

[3]Bektas T，Laporte G.The pollution-routing problem. Transportation Research[J].Part B， 2011（45）：1232–1250.

[4]Demir E， Bektas T， Laporte G. An adaptive large neighborhood search heuristic for thepollution-routing problem[J]. European Journal of Operational Research， 2012（223）：346–359.

[5]Drexl M.Synchronization in vehicle routing—a survey of VRPs with multiple synchronization constraints[J]. Transportation Science，2012（46）：297–316.