基于低碳排放的多車型車輛路徑優(yōu)化問題研究

王恒 王俊超 劉文美 王振鋒 王銀河 徐亞星

摘要：針對物流配送過程中，如何合理安排配送路線，提高配送效率、降低配送成本和碳排放量的問題，分析了車輛載重量、行駛速度、行車距離、交通狀態(tài)等因素對車輛油耗的影響，建立了以最小化配送成本和碳排放量為優(yōu)化目標(biāo)的多車型車輛配送路徑模型。同時(shí)，結(jié)合蟻群算法對該優(yōu)化問題進(jìn)行求解。仿真結(jié)果驗(yàn)證了算法能夠有效的降低配送成本和碳排放量。

Abstract： In the urban logistics distribution， reasonable distribution of distribution routes can effectively improve the efficiency of distribution， reduce the cost of distribution and carbon emissions. The influence of vehicle load， speed， distance and traffic condition on vehicle fuel consumption is analyzed. At the same time， an optimization model of heterogeneous vehicle distribution routes is constructed based on minimizing the cost of distribution and carbon emissions. Finally， an colony optimization algorithm is used to solve this problem. Finally， the feasibility and effectiveness of the constructed model and the proposed algorithm are verified by simulation experiments.

關(guān)鍵詞：車輛路徑優(yōu)化;多車型;碳排放;蟻群算法

Key words： vehicle routing optimization;heterogeneous fleet vehicle;carbon emissions;ant colony optimization algorithm

中圖分類號：F259.23 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1006-4311（2019）12-0080-03

0 ?引言

如何減少配送過程中的油耗成本一直是各個(gè)物流企業(yè)關(guān)注的問題之一。其原因主要有以下兩個(gè)方面：一、企業(yè)希望通過降低配送過程中的車輛油耗進(jìn)一步壓縮成本，增加企業(yè)利潤;二、企業(yè)通過控制油耗，從而降低配送過程中的碳排放量，承擔(dān)節(jié)約資源、保護(hù)環(huán)境的社會(huì)責(zé)任。因此，如何從低碳角度安排配送路線，是物流企業(yè)在配送環(huán)節(jié)中面臨的重要問題之一。

目前，國內(nèi)外學(xué)者圍繞車輛路徑優(yōu)化問題進(jìn)行了大量的研究工作。李瑩[1]等綜合考慮了配送距離、車輛固定成本等多種因素，建立了帶有軟時(shí)間窗的循環(huán)取貨多車型車輛路徑問題;殷亞[2]等以車載量和硬時(shí)間窗為約束條件，建立了最小發(fā)車量和最小行駛距離為目標(biāo)的數(shù)學(xué)模型，并提出了混合蝙蝠法對模型進(jìn)行求解;陳呈頻[3]等以多車場、多車型車輛為研究背景，建立了配送車輛路徑優(yōu)化問題的整數(shù)規(guī)劃模型，提出了多染色體遺傳算法。張傳琪[4]等以配送成本最小為目標(biāo)函數(shù)，構(gòu)建了考慮服務(wù)途中動(dòng)態(tài)擁擠的多車型車輛路徑模型，設(shè)計(jì)了求解該模型的改進(jìn)遺傳算法。劉麗姣[5]等提出了單循環(huán)結(jié)構(gòu)的細(xì)菌覓食優(yōu)化算法與改進(jìn)的綜合學(xué)習(xí)粒子群算法相結(jié)合的混合求解算法?？梢?，考慮碳排放的車輛路徑問題成為現(xiàn)階段研究的熱點(diǎn)。

鑒于此，本文分析了車速、載重，距離等因素對車輛油耗的影響。以最小化配送成本和碳排放為優(yōu)化目標(biāo)，構(gòu)建了多車型車輛配送路徑優(yōu)化模型。最后，提出了一種改進(jìn)的蟻群算法對該優(yōu)化問題進(jìn)行求解。

1 ?模型建立

1.1 問題描述

本文研究的多車型車輛路徑優(yōu)化問題具體描述如下：配送中心擁有若干不同額定載重的配送車輛，配送中心根據(jù)各個(gè)配送點(diǎn)需求，安排車輛進(jìn)行配送。車輛從配送中心出發(fā)，按照擬定的行車路線進(jìn)行逐一配送，完成配送任務(wù)后，返回配送中心。在此配送過程中，每個(gè)配送點(diǎn)由一輛車配送，配送線路上各個(gè)配送點(diǎn)的需求量總量不超過單車的最大裝載量。

3.2 仿真結(jié)果與分析

通過仿真得到，ACO算法的最優(yōu)配送方案為：額定載重15噸的配送車輛路徑為：0-18-19-11-23-25-26-14-16-28-6-30-4-2-17-29-0;0-13-5-20-9-24-27-10-15-3-8-1-0;額定載重5噸的配送車輛路徑為：0-21-22-12-7-0。ABC算法的最優(yōu)配送方案為：額定載重15噸的配送車輛路徑為：0-28-8-13-10-26-7-6-16-9-5-1-17-0;0-19-22-12-2-14-21-30-18-11-24-3-20-29-0;額定載重5噸的配送車輛路徑為：0-15-4-27-25-23-0。GA算法的最優(yōu)配送方案為：額定載重15噸的配送車輛路徑為：0-15-29-24-1-25-4-11-10-27-13-23-20-0;0-9-5-21-19-14-22-12-7-0;0-3-17-28-6-16-8-2-26-30-18-0。在算法運(yùn)行過程中，ACO算法收斂速度較快，搜索得到的最優(yōu)解較為理想。ABC算法收斂速度較慢，GA算法大約在第300次迭代后不在進(jìn)行尋優(yōu)，出現(xiàn)了早熟收斂現(xiàn)象，如圖2所示。

表3給出了不同算法得到的配送成本和碳排放量。顯然，ACO算法的運(yùn)行結(jié)果優(yōu)于對比算法。在配送成本方面，ACO算法的配送路線所需的配送成本為1268.92元，碳排放為198.21千克。與ABC和GA算法相比，分別能夠節(jié)省3.8%，11.4%的配送成本，減少2.1%和9.1%;顯然，依照ACO算法得到的配送路線進(jìn)行配送，具有較低的配送成本和碳排放量。在運(yùn)行時(shí)間方面，三個(gè)算法運(yùn)行時(shí)間差別不大。通過以上實(shí)驗(yàn)仿真可以看出，ACO算法具有理想的尋優(yōu)效果，能夠在配送路徑優(yōu)化過程中尋找到使配送成本和碳排放最小的配送方案。

4 ?總結(jié)

本文針對多車型車輛路徑優(yōu)化問題進(jìn)行了研究。首先，本文分析了車速、載重、距離等因素對車輛油耗的影響。然后，以最小化配送成本和碳排放為優(yōu)化目標(biāo)，構(gòu)建了多車型車輛配送路徑優(yōu)化模型。最后，通過蟻群算法對該優(yōu)化問題進(jìn)行求解。通過仿真驗(yàn)證模型和算法的有效性，結(jié)果表明本文構(gòu)建的模型可以有效的減少配送成本和碳排放，所提出的算法也取得了良好的效果。

參考文獻(xiàn)：

[1]李瑩.帶軟時(shí)間窗的循環(huán)取貨多車型車輛路徑問題研究[D].長安大學(xué)，2016.

[2]殷亞，張惠珍.求解帶硬時(shí)間窗的多目標(biāo)車輛路徑問題的多種混合蝙蝠算法[J].計(jì)算機(jī)應(yīng)用研究，2017（12）：118-122.

[3]陳呈頻，韓勝軍，魯建廈，等.多車場與多車型車輛路徑問題的多染色體遺傳算法[J].中國機(jī)械工程，2018，29（482）：96-101.

[4]張傳琪，張楊.動(dòng)態(tài)路網(wǎng)下多車型車輛路徑問題研究[J].交通運(yùn)輸工程與信息學(xué)報(bào)，2017，2（15）：112-118.

[5]劉麗姣.考慮碳排放的多車場多車型VRP模型及算法研究[D].深圳大學(xué)，2017.

[6]王恒，徐亞星，王振鋒，等.基于道路狀況的生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化[J].系統(tǒng)仿真學(xué)報(bào)，2019，31（1）：126-135.

[7]Bekta■ T， Laporte G. The Pollution-Routing Problem [J]. Transportation Research Part B Methodological， 2011， 45（8）： 1232-1250.

[8]Mao W W， Yu S P. Ant Colony Algorithm for VRP with Time Windows [J]. Energy Procedia， 2011， 13： 2168-2173.

[9]蔡浩原，潘郁.基于人工蜂群算法的鮮活農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化[J].江蘇農(nóng)業(yè)科學(xué)，2017，45（15）：318-321.

[10]Michalewicz Z， Janikow C Z， Krawczyk J B. A modified genetic algorithm for optimal control problems [J]. Computers & Mathematics with Applications （S0898-1221）， 1992， 23（12）： 83-94.