文/芦立华 邱煜浩 蒋涛 李恒洗

引言

近些年我国的空气质量日益恶化，据世界卫生组织调查显示，机动车尾气污染是大气环境污染的一种重要组成部分。其中，以化石燃料为能源的交通运输业是碳排放的主要来源之一，由此导致低碳经济运行模式备受关注。本文以优化快递车辆配送路径为出发点，旨在通过提高物流配送效率和减少物流配送成本，以降低机动车燃油消耗、减少碳排放，进而实现绿色低碳环保交通运输模式的理念，这对于实现可持续发展具有重要的理论价值和现实意义。

自1985年开始，国内外就有研究者提出城市运输存在空气污染的问题。2013年，针对异构车队路线规划问题进行建模，Kwon等人[1]考虑碳排放。2014年，LinC和ChoyK[2]给出碳排放问题的VRP研究综述。2014年，Konur基于碳排放约束条件下的库存控制和异型车辆的配送路径问题，并采用启发式算法进行优化求解，可以明显降低车辆运行中的碳排放量。2015年，Mohammad等[3]考虑了车辆在行驶过程中速度、距离以及道路是否堵塞等因素，建立燃料消耗模型，并用蚁群算法优化求解。2016年，YoshinoriSuzuki[4]建立以能耗最低和碳排放量最少为目标函数的车辆路径模型。考虑低碳经济的研究背景，杨涛[5]构建了一个三级的物流网络数学模型，用遗传算法求解并进行线路规划。2013年，吴丽荣等[6]从低碳的角度考虑带容量限制的VRP，建立了以最小化燃料消耗为优化目标的车辆路径模型。2014年，饶卫振等[7]考虑了道路坡度，提出了以配送车辆总能耗最小为目标的低碳车辆路径问题模型（ECM-LCVRP）。2015年，张如云等[8]在传统带时间窗VRP的基础上，建立了考虑低碳、节能和成本节约的城市车辆配送问题模型，设计改进的遗传算法进行求解。2016年，李亚男等[9]基于城市发展的理念，以碳排放为约束条件，构建冷链物流配送网络优化模型，用遗传算法得到模型的最优解，实现冷链物流企业减少碳排放和降低配送成本的双目标。

本文以快速发展的快递行业配送问题为出发点，研究了影响碳排放的主要因素——配送路径，以期通过科学选择和合理规划车辆配送路径来降低碳排放量。通过采用DP方法和蚁群算法解决该问题，分析了他们的性能。

1.问题描述

假设快递公司有n个站点，快递车辆需要经过每一个指定站点再回到起点。如果起点固定，那么从起点出发经过每一个站点再回到起点共有（n-1）种路径，如何确定这些路径中的最短路径来最大限度地减少汽车的行驶距离是需要解决的关键问题。

假设有n个站点，两个站点i和j间的距离为dij ，则目标函数如（1）所示,约束条件如（2）-（4）。

2.问题求解

文中采用状压dp方法和蚁群算法对上述模型进行求解，详细方法如下所述。

2.1 状压dp方法

状态压缩动态规划（状压dp）是一类典型的动态规划方法，常使用在小规模NP问题求解中。虽然其复杂度为指数级，但是速度快。Dp算法将每一个站点的选取与否压缩进一个二进制位里，0表示未访问，1表示已访问，S=2n用来表示所有的访问情况，v表示现在所处的站点，以此创建一个二维数组dp[S][v]来表示目前在点v回到最初节点的距离，通过计算出dp数组的每一个值来得出经过每个站点并回到起点的最小值，其伪码如下所示。

function dpslove（site_number,site_distance）

dp[0..（1<

dp[1][0]= 0

for i=1 -> （1<

if （the first site not visited） then

continue

end if

for j=1 -> site_number do

join the next site which has not been joined

compute the min dp[（1<

//“|”represents the OR operation.“<<”describes the shift operation.

end for

end for

ans = min（ans,dp[（1<

return ans

end function

2.2 蚁群算法

蚁群算法是根据仿生学理论而得出的一种仿生算法，蚂蚁走过的路线会留下与路径长度有关的信息素，路径越短释放的信息素越多，随着时间的积累，较短路径上累计的信息素浓度逐步增加，选择该路径的蚂蚁也会增加，最终可以得到优化问题的最短路径。伪码描述如下所示。

function monodomous（site_number）

ants = sqrt（site_number）

for iterative time=0 -> iterative time max do

for i=0 -> ants do

randomly assignment ant i to a city

end for

for i=0 -> site_number do

for k=0 -> ants do

choose the next site for ant k

end for

end for

compute the length of route the increment of pheromone

hold the bestsolution

for each path do

update the pheromone value

end for

end for

reutrn bestsolution

end functiondp

3.实验

3.1 数据集

采用国际学术界公认的关于NP问题测试数据的网站[10]上关于TSP问题的权威数据。不失一般性地，使用该网站上文件名为“ali535.tsp.gz”的前一百个数据。

3.2 结果分析

实验分别选取了n=15、20、50和100个城市作为快递站点来仿真运行程序。针对每个算法各运行10次，统计最短距离、最长距离和平均距离，如表1所示。根据表1可以观察，在n=15和n=20时，dp状压算法得出的最好、最差和平均距离都是相同的，均优于蚁群算法。其中蚁群算法十次运行结果中最好的距离为597.601，要高于dp算法17.361。这主要归因于dp算法是精确算法，而蚁群算法是启发式算法，后者不能保证每次都能够寻获最优解。当站点数量增大到50和100时，对于该规模的数据集，由于dp状压算法本身的局限性，已不能很好地获得结果。相反地，蚁群算法仍然适用，且误差逐渐减少，在Matlab中生成的最短路径图如图1所示。总之，在数据规模较小时，采用dp状压算法可以得到较好的结果，而当问题规模逐渐增大时，蚁群算法的性能要远远优于dp状压算法。

表1 算法结果对比

图1 蚁群算法最短路径生成图

4.总结及展望

本项目对快递车辆行驶的路径进行了研究，通过假定路径的长度和碳排放有直接的关系，即，车辆行驶路径越长碳排放量越多，反之越少。采用dp状压算法和蚁群算法分别计算快递车辆经过每一个目的地再回到起点的最短路径，从而更合理地规划车辆在站点间行驶的路径，从而削减车辆能耗，降低企业运营成本，进而减少空气污染。

尽管本文已通过车辆路径规划达到降低碳排放的目的，但是由于受dp状压算法和蚁群算法本身的局限性，仍存在一些问题未得到很好地解决。如：在建立的优化模型中，一方面没有加入某时段某路段车辆具体行驶情况，没有实现分时段的最短路径规划；另一方面未考虑道路拥堵、道路坡度等情况和碳排放量之间的关系，这都是在今后要重点研究的内容。

本项目由大学生创新创业基金支持（项目号：A1-5701-17-009-02-64）

[1]Kwon Y，Choi Y，Lee D．Heterogeneous fixed fleet vehicle routing problem considering carbon emission[J]．Transportation Research Part D：Transport and Environment，2013，16（5）：81～89

[2]Lin C，Choy K L．Survey of Green Vehicle Routing Problem：Past and Future Trends[J]．Expert Systems with Applications，2014，41（4）：1118～1138．

[3]Mohammad Reza，Jabbarpour，RafidahMd Noor．Green vehicle traffic routing system using ant ～based algorism [J]．Journal of Network and Computer Applications，2015，12（58）：294～308．

[4]Yoshinori Suzuki．A dual～objective metaheuristic approach to solve practical pollution routing problem[J]．International Journal of Production Economics，2016，6（176）：143～153．

[5]杨涛． 低碳经济下的多运输方式物流网络规划[D]． 上海：上海交通大学． 2011．

[6]吴丽荣，胡祥培，饶卫振．考虑燃料消耗率的车辆路径问题模型与求解[J]． 系统工程学报，2013，28（6）：804～811．

[7]饶卫振，金淳，王新华．考虑道路坡度因素的低碳VRP问题模型与求解策略[J]．系统工程理论与实践，2014，34（8）：2092～2105．

[8]张如云，刘清等． 考虑低碳的城市配送车辆路径优化模型研究[J]．工业工程与管理，2015，20（4）：29～34．

[9]李亚男，刘联辉等．低碳约束下城市冷链物流配送系统优化研究[J]．中国市场，2016，10（36）：36～37．

[10]http://comopt．ifi．uni-heidelberg．de/software/TSPLIB95/tsp/