基于碳排放的車輛路徑優(yōu)化和速度優(yōu)化

孫金枝

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

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

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

O引言

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

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

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

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

本文在配送成本中考慮車輛油耗成本和車輛使用成本，以路徑優(yōu)化和速度優(yōu)化為決策變量建立了數(shù)學(xué)模型，并設(shè)計(jì)了一個(gè)兩階段算法來解決該問題，第一階段假設(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è)計(jì)

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

3算例分析

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

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

3.2算法有效性驗(yàn)證

原模型是非線性混合整數(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固定速度和本文算法計(jì)算結(jié)果比較

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

4結(jié)束語

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