孫金枝

摘要：近年來，環(huán)境和能源問題成為人們關(guān)注的一個焦點。交通運輸業(yè)是一個高能耗的行業(yè)，該行業(yè)實現(xiàn)節(jié)能減排是有必要的。文章以降低車輛碳排放為目標(biāo)進(jìn)行車輛路徑構(gòu)建和速度優(yōu)化，從而實現(xiàn)交通運輸業(yè)的節(jié)能減排。在考慮配送節(jié)點約束、車輛速度約束、容量約束、時間窗約束的情況下，構(gòu)建了一個非線性數(shù)學(xué)模型，并設(shè)計了一個兩階段算法：第一階段假設(shè)網(wǎng)絡(luò)速度相同進(jìn)行路徑優(yōu)化，第二階段在已知路徑的情況下進(jìn)行速度優(yōu)化。最后通過算例驗證了算法的可行性和有效性。

關(guān)鍵詞：帶時間窗的車輛路徑問題;速度優(yōu)化;碳排放

中圖分類號：U116.2文獻(xiàn)標(biāo)識碼：A

O引言

隨著環(huán)境污染、能源枯竭問題越來越突出，人們也更加關(guān)注環(huán)境和能源問題。交通運輸業(yè)是一個高能耗的行業(yè)，《公路水路交通節(jié)能中長期規(guī)劃綱要》、《“十三五”現(xiàn)代綜合交通運輸體系發(fā)展規(guī)劃》等都指出要降低能源消耗，減少污染氣體的排放。除了構(gòu)建合理的交通運輸系統(tǒng)、研發(fā)新能源汽車等措施外，交通運輸企業(yè)可以通過構(gòu)建合理的車輛行駛路徑、車輛行駛速度等措施來降低能源消耗?；诖舜_定了本文的研究主題——基于碳排放的車輛路徑優(yōu)化和速度優(yōu)化。

關(guān)于路徑優(yōu)化（VRP）的文章很多，研究也相對成熟。本文主要關(guān)注了帶時間窗的車輛路徑問題（VRFTW），該類問題屬于典型的NP-hard問題，求解方式包括精確算法和啟發(fā)式算法。精確算法有分支定界、列生成等，Desrochers等用分支定界算法解決列生成中的子問題，該算法可以求得VRPTW的最優(yōu)解。Choi等采用列生成算法求解整數(shù)規(guī)劃問題，并針對VRPTW提出了兩種動態(tài)規(guī)劃算法。啟發(fā)式算法有禁忌搜索、蟻群算法等，Pisinger等提出了大規(guī)模領(lǐng)域搜索算法框架來解決VRPTW的問題。張金金（2012）設(shè)計了兩階段的啟發(fā)式算法，何小鋒，馬良（2013）通過將量子計算和蟻群算法相結(jié)合提出了量子蟻群算法。

速度優(yōu)化問題最先出現(xiàn)在航海路徑減排問題上。Fagerholt等證明了速度優(yōu)化問題為非線性凸規(guī)化問題。Norstad等提出了一個遞歸算法來求解固定路徑上的速度優(yōu)化問題，被Hvattum等證明該算法是精確算法。

目前，考慮碳排放的路徑優(yōu)化問題還比較少。BektaS等提出了污染路徑問題并建立了一個非線性數(shù)學(xué)模型，然后通過離散化速度，將非線性模型轉(zhuǎn)化為線性模型進(jìn)行求解。Fukasawa等構(gòu)建混合整數(shù)規(guī)劃算法解決PRP問題。Demir等建立了一個ALNP算法解決污染路徑問題。李進(jìn)等以旅行時間、碳排放和油耗的總費用最小化為目標(biāo)函數(shù)，設(shè)計了兩階段啟發(fā)式算法。

本文在配送成本中考慮車輛油耗成本和車輛使用成本，以路徑優(yōu)化和速度優(yōu)化為決策變量建立了數(shù)學(xué)模型，并設(shè)計了一個兩階段算法來解決該問題，第一階段假設(shè)網(wǎng)絡(luò)速度相同采用二分法求解可能路徑，第二階段在已知的路徑集合中進(jìn)行速度優(yōu)化，從而輸出最優(yōu)解。

1問題描述與模型構(gòu)建

1.1問題描述

根據(jù)1.2.1，該目標(biāo)函數(shù)為凸函數(shù)，約束式（13）為非線性約束，該問題為非線性凸規(guī)劃問題，速度決策可以借助MAT-LAB的fmincon命令求解。

2.2算法設(shè)計

本算法設(shè)計整體思路分為兩個階段，第一階段是假定網(wǎng)絡(luò)速度相同的情況下，對網(wǎng)絡(luò)進(jìn)行路徑優(yōu)化;第二階段是在獲得路徑之后，對路徑上的速度進(jìn)行速度優(yōu)化。由于給定的網(wǎng)絡(luò)速度會影響求解結(jié)果。本文在第一階段用二分法求出所有可能路徑，之后在第二階段對所有路徑進(jìn)行速度優(yōu)化，從而輸出最優(yōu)解。具體算法流程如圖1、圖2所示。

3算例分析

3.1參數(shù)設(shè)置

現(xiàn)有一個配送中心和15個客戶，所有節(jié)點的經(jīng)緯度、客戶需求（單位kg）、需要的服務(wù)時間（單位s）如表1所示。此外，配送中心有載重量為3.5t的車輛10輛，采用的油耗成本如1.2.2中所示，車輛最高限速為120km/h，最低限速為20km/h，最優(yōu)速度υ_opt為63.39km/h。單位里程的油耗成本C₁=7.5，車輛使用成本C₂=100。對于不同的測試實例，生成不同寬度的時間窗。

3.2算法有效性驗證

原模型是非線性混合整數(shù)規(guī)劃，不容易求得最優(yōu)解。為此，需要尋找原問題最優(yōu)解的下界。假設(shè)（x，y）是原問題P1的最優(yōu)解，問題P2仍然按照該路徑和速度行駛，也可以滿足所有約束，因此（x，y）也是問題P2的可行解。則P2的最優(yōu)值小于等于P1的最優(yōu)值，因此問題P2的最優(yōu)值可以作為問題P1最優(yōu)值的下界。

3.3固定速度和本文算法計算結(jié)果比較

為了進(jìn)一步說明對車輛進(jìn)行速度優(yōu)化的必要性，將網(wǎng)絡(luò)速度固定為使單位里程油耗最小的速度υ_opt=63.39km/h，計算了在此情況下的配送成本、車輛使用數(shù)量，如表3所示。計算結(jié)果表明，對車輛進(jìn)行速度優(yōu)化，平均可以節(jié)省11.98%的費用，因此對車輛進(jìn)行速度優(yōu)化是有必要的。

4結(jié)束語

本文以車輛油耗成本和使用成本為目標(biāo)函數(shù)，建立了以路徑和速度同為決策變量的數(shù)學(xué)模型，并針對模型設(shè)計了算法，通過算例驗證了模型和算法的可行性和有效性。但是本文選用cplex進(jìn)行路徑優(yōu)化，僅適用于客戶規(guī)模較小的情況，在后續(xù)研究中將針對大規(guī)?？蛻暨M(jìn)行研究。