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

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

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

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

0 ?引言

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

目前，國(guó)內(nèi)外學(xué)者圍繞車輛路徑優(yōu)化問(wèn)題進(jìn)行了大量的研究工作。李瑩[1]等綜合考慮了配送距離、車輛固定成本等多種因素，建立了帶有軟時(shí)間窗的循環(huán)取貨多車型車輛路徑問(wèn)題;殷亞[2]等以車載量和硬時(shí)間窗為約束條件，建立了最小發(fā)車量和最小行駛距離為目標(biāo)的數(shù)學(xué)模型，并提出了混合蝙蝠法對(duì)模型進(jìn)行求解;陳呈頻[3]等以多車場(chǎng)、多車型車輛為研究背景，建立了配送車輛路徑優(yōu)化問(wèn)題的整數(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é)合的混合求解算法。可見，考慮碳排放的車輛路徑問(wèn)題成為現(xiàn)階段研究的熱點(diǎn)。

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

1 ?模型建立

1.1 問(wèn)題描述

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

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

通過(guò)仿真得到，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)行過(guò)程中，ACO算法收斂速度較快，搜索得到的最優(yōu)解較為理想。ABC算法收斂速度較慢，GA算法大約在第300次迭代后不在進(jìn)行尋優(yōu)，出現(xiàn)了早熟收斂現(xiàn)象，如圖2所示。

表3給出了不同算法得到的配送成本和碳排放量。顯然，ACO算法的運(yùn)行結(jié)果優(yōu)于對(duì)比算法。在配送成本方面，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í)間差別不大。通過(guò)以上實(shí)驗(yàn)仿真可以看出，ACO算法具有理想的尋優(yōu)效果，能夠在配送路徑優(yōu)化過(guò)程中尋找到使配送成本和碳排放最小的配送方案。

4 ?總結(jié)

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

參考文獻(xiàn)：

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

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

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

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

[5]劉麗姣.考慮碳排放的多車場(chǎng)多車型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.