“双成本”视阈下双向物流车辆路径选择问题研究

刘 跃，付世敏

（重庆邮电大学，重庆 400065）

“双成本”视阈下双向物流车辆路径选择问题研究

刘 跃，付世敏

（重庆邮电大学，重庆 400065）

在运输中汽车尾气造成的环境污染越来越严重，在传统路径研究中由于正逆向物流分离，其路径优化结果不能满足低碳化社会的需要。在传统路径研究的基础上，增加“同时取送”、“环境成本”约束条件，建立“双成本”视阈下双向物流车辆路径选择模型并设计相应的遗传算法，通过案例证明模型和算法的有效性和可行性。结果分析表明，综合考虑环境成本和运输成本的车辆路径问题在有效降低物流成本的同时，能实现绿色物流。

双成本；同时取送货；物流车辆；路径选择；运输费用；CO2排放；遗传算法

1 引言

物流被认为是获取利润的“第三源泉”。中国物流与采购联合会发布的2017年1-5月社会物流总费用为4.6万亿元，运输费用为2.4万亿元，占物流总费用的一半；而在交通运输中产生的大量的CO2排放严重污染环境，企业在减少经济成本的同时也要兼顾着社会责任，因而减少环境成本成为物流配送路径选择问题中的目标。

车辆路径问题（VRP）是Dantzig和Ramser[1]在1959年提出的，之后的学者也进行了大量研究，产生了很多重要的研究成果，大多集中在单向物流方面。而在实际情形中，同时取送货的顾客很常见，因此，研究同时取送货车辆路径问题（VRP-SDP）更加接近实际的配送管理。VRP-SDP的概念首次是由Min[2]在1989年提出的，研究了车辆数量限制和装载能力限制情况下如何处理1个配送中心和22个客户点之间图书的配送和回收问题，采用先分组后排序的算法，把各个组群当作一个独立的旅行商问题进行路径求解；张建勇、李军[3]设计了一种混合遗传算法求解具有同时配送和回收需求的车辆路径问题；刘晴[4]对随机需求的同时取送货车辆路径问题进行了研究；王超，穆东[5]以一种主从式并行模拟退火算法代替传统的串行模拟退火算法研究物流配送和废旧产品回收的VRPSDP问题；一些学者认为[6]，扩展车辆路径问题的目标，路径安排不应该只考虑经济成本，更应该考虑对社会和环境的影响，以减少碳排放量。Demir[7]等提出以减少环境污染为目标，综合考虑经济成本及社会环境成本的PRP模型；钟聪儿[8]等在配送路径优化中综合考虑碳排放和运输费用并以其费用最小为目标函数；侯跃[9]等提出碳交易环境下固定车辆数的多车型车辆配送路径优化问题，考虑碳交易市场机制对运输企业收益成本的影响；朱长征[10]等在经典的车辆路径优化模型的基础上考虑碳排量，建立了碳排量最小的车辆路径优化模型；张立毅[11]等针对物流配送中碳排放的度量方法，以碳排放成本为目标函数，建立了低碳物流配送路径优化模型；葛显龙[12]等在分析现有文献中多车型车辆路径问题中车辆使用优先原则的基础上，将车辆使用费用分为固定费用和油耗费用。以上文献虽然探讨了如何降低企业的经济成本和环境成本，但大多只是假设配送中心具有同种车型，然而每种车型的装载能力、碳排放能力等都不同，这与实际情况不相符；此外，以上文献并没有把“双成本”和双向物流综合联系起来。基于此，本文在双向物流路径选择问题研究中，结合实际情况将不同车型考虑到CO2排放量的计算过程中，并结合运输成本建立以总成本最小为目标的车辆路径选择问题，合理调配车辆、优化路线，不仅提高企业的经济效益也避免了运输车辆的空载和重复运输等，减少了CO2排放量。

2 碳排放计算模型

根据不同的精确度要求和所采集的数据种类，二氧化碳排放量的计算可以选取不同的计算方法，参考文献[13]有：

其中F为货物运输过程中的燃油消耗；G为地形坡度因子；D为车辆的行驶距离；L为载货重量；a、b为燃油消耗参数（该参数随车型的变化而变化，并忽略驾驶情况、交通路况的影响）。直接的二氧化碳排放量=燃油消耗量×燃油转换系数，设燃油转换系数为π，则二氧化碳排放量为:

由式（2）可知，二氧化碳排放量与燃油消耗成正比例关系；而燃油消耗与行驶距离成正比例关系，与装载量成正线性相关。为模型求解方便，令地形坡度因子G为1，根据实际问题可以得出：

3 考虑运输成本和环境成本的同时取送货车辆路径选择模型

3.1 问题描述

假设一个配送中心有L辆K种不同类型的车辆服务于多个客户，任务完成后最终返回配送中心，已知配送中心和每个顾客的位置，且顾客的需求量和回收量已知。要求合理安排车辆路线，使得运输成本和环境成本之和最小，并满足以下条件：（1）在顾客节点可以同时完成取货和送货任务，每个顾客的需求只能被一辆车服务且服务一次；（2）每一条路径上车辆的装载量不能超过车辆的最大载重量；（3）每一条路径的长度不能超过车辆行驶的最大距离；（4）每种车型的车辆数固定，且具有不同的载重量和燃油消耗（与计算碳排放量有关）。

为了描述方便，定义以下使用的符号和决策变量：

（1）现有一个有向图 G=(V,E)，其中 V=（0，1，2，…，n）有n+1个顶点，0表示配送中心，剩余的集合表示顾客点；E为弧集，则E＝｛(i,j)/i,j∈V，i≠j｝；

（2）yi为节点i的配送需求量，i∈V；

（3）zi为节点i的回收量，i∈V；

（4）Dij为节点i到节点j之间的距离；

（5）π表示燃油转换系数；

（6）L为配送中心的汽车数量；

（7）K表示车型种数，mk为车型k的数量，满足

（9）Qk为车型k的装载能力，同种车型装载能力相同；

决策变量：

3.2 模型的建立

综合考虑运输成本和环境成本的同时取送货路径选择模型如下：

约束条件：

目标函数式（4）表示总成本最小，包括运输成本和环境成本两部分；约束条件式（5）表示离开配送中心的数量和回到配送中心的数量相等，即车辆从配送中心出发，任务完成后返回配送中心；式（6）表示每个顾客只能被车辆服务一次；式（7）表示每种车型的数量限制；式（8）表示车的装载量不大于它的最大装载能力；式（9）和式（10）表示送货需求和取货需求被满足；式（11）为决策变量的约束。

4 VRPSDP问题的遗传算法设计

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，它广泛应用于各种学科。本文所研究的是组合优化问题，其问题规模较大，搜索空间也急剧扩大，要寻找到一种能以有限的代价来解决最优化问题的通用方法仍是一个难题。而遗传算法却为我们解决这类问题提供了一个有效的途径和通用框架，开创了一种新的全局优化搜索算法。

遗传算法的特点：（1）可以直接以目标函数作为搜索信息。传统的算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向。（2）可以同时使用多个搜索点的搜索信息。由很多个体所组成的一个初始群体开始最优解的搜索过程，而不是从单一的个体开始搜索，这也是遗传算法所持有的一种隐含并行性。

遗传算法的求解步骤：（1）选择能够直观反映问题的编码方式，并设置相应的参数；（2）随机产生初始种群；（3）对群体中的每一个个体进行适应度评价；（4）对种群进行选择操作；（5）对种群进行交叉操作；（6）对种群进行变异操作；（7）判断是否满足本论文选择的终止条件的标准，若不满足继续执行（3）、（4）、（5），如果满足则输出结果。

4.1 编码

为了便于直观反映车辆的路径，本文采用自然数编码策略，同时需要相应调整遗传操作策略。自然数编码方式也存在着三种不同的编码方法，为避免计算机存储量较大，将采用顾客直接排列的编码方式，即用1～n自然数表示顾客，这些自然数的任意排列就是一个解，按照问题的约束条件，依次将解的每个顾客纳入车辆的配送路径中。如123456789，首先将顾客1纳入第一条配送路径中，看是否满足约束条件，若满足则构成配送路径0-1-0，再将2纳入这条配送路径中，判断是否满足约束条件，若满足则构成配送路径0-1-2-0，接着将3纳入这条配送路径中，若不能满足问题的约束条件，则顾客3不能由这条路径配送，要重新开始一条新的配送路径即0-3-0；重复上述过程，直到把每个顾客都纳入到配送路径中。

4.2 适应度函数

遗传算法中使用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。为了遗传操作的简单进行，适应度函数可以基于目标函数式（4）进行构建。

4.3 遗传算子

4.3.1 选择算子。选择操作建立在对个体的适应度进行评价的基础上，选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。

由于选择、交叉、变异等遗传操作的随机性，它们也有可能破坏掉当前群体中适应度最好的个体，降低群体的平均适应度，对遗传算法的运行效率、收敛性有不利的影响，所以我们希望适应度最好的个体要尽可能的保留到下一代群体中。为达到这个目的，将采用轮盘赌选择法并结合最优保留策略进化模型来进行优胜劣汰操作。

4.3.2 交叉算子。从遗传算法运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力。本文采用了适用于整数编码问题的部分匹配交叉法。其优点是能够保证即使两个相同的个体进行交叉依然能产生新的个体，从而摆脱了传统交叉算子对群体多样性的要求，同时避免了早熟现象，降低了局部最优解的可能。在一定程度上保持了种群的多样性，避免陷入局部最优解。假设随机选择两个父代P1：123|456|78和P2:437|816|52，随机产生两个交叉点，交叉点中间的区域部分称为匹配区域，交换P1和P2的两个匹配区域，从而获得匹配关系：8和4；1和5；6和6交换映射基因码，得到两个子代C1:52381674和C2:83745612。

4.3.3 变异算子。从遗传算法运算过程中产生新个体的能力方面来说，变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力。变异算子的目的是增强种群的多样性，本文针对所研究问题的特征，采用倒位变异算子。以一定的变异概率从种群中随机选取其中的一个个体并产生两个变异点，将变异点中间的元素进行逆转操作。如一个个体为12|3456|789，“3”和“6”是两个变异点，将变异段进行逆转得新个体12|6543|789。

5 算例分析

5.1 实例计算

假设某一配送中心为27个顾客同时配送货物和取货，配送中心和顾客的坐标及配送量与回收量见表1，配送中心有2种车型且每种车型的数量已知，每种车型的参数见表2，参考文献[13]设置燃油转化系数为2.68（千克CO2/升）。求解如何合理地安排车辆的行驶路线，使得企业的运输成本和环境成本最小。

表1 客户节点坐标及取送货需求量统计表

表2 配送车辆信息

遗传算法参数的设定：

遗传算法中需要选择的运行参数主要有群体大小M、交叉概率Pc、变异概率Pm、终止代数T等。这些参数对遗传算法的运行性能影响较大，须认真选取。

（1）群体大小M。群体大小M表示群体中所含个体的数量。M取值较小时，可提高遗传算法的运算速度，却降低了群体的多样性，有可能引起遗传算法的早熟现象；若M取值较大时，又会使得遗传算法的运行效率降低。一般取值范围为20～100，本文M取值为100。

（2）交叉概率Pc。交叉操作是遗传算法中产生新个体的主要方法。Pc若取值过大，会破快群体中的优良模式，对进化运算产生不利影响；Pc若取值过小，产生新个体的速度较慢，一般建议的取值范围是0.4～0.99，本文Pc取值为0.9。

（3）变异概率Pm。Pm取值较大虽然能产生较多的新个体，但可能破快掉很多较好的模式，使得遗传算法的性能近似于随机搜索算法的性能；若Pm取值太小，则变异操作产生新个体的能力和抑制早熟现象的能力就会较差。一般建议的取值范围为0.000 1-0.1，本文Pm取值为0.01。

（4）终止代数T。其有两个判定标准：①设定遗传算法运行结束条件的一个参数，当遗传算法运行到指定的进化代数之后就停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。一般建议的取值范围是100～1 000。②当群体已经进化成熟且不再有进化趋势时就可终止算法的运行过程，本文选择第2个标准终止代数，在进化到后五次后收敛性趋于稳定。

5.2 求解结果分析

根据以上数据，利用遗传算法在计算机上运用C#进行算法编程，求解本文所建立的VRPSDP模型，得到最优目标函数值及相对应的最优车辆路径可行解，算法运行10次的结果见表3。

表3 算法运行10次取得的同时取送货结果

从10次运行结果来看，通过对比分析，本文选取总成本最小的最优路径即方案7，其具体的车辆安排及行驶路线见表4。

表4 最优结果

车辆路径示意图如图1所示。

图1 车辆路径示意图

根据算例结果，本文所建立的模型和设计的算法较好地解决了既考虑运输成本又考虑环境成本的同时取送货的车辆路径选择问题。结果分析：（1）从10次运行的结果来看，总里程短的并不一定总成本最低，说明影响成本的因素有很多，不能片面追求里程最优；（2）环境成本在总成本中所占的比例较小，考虑环境成本对企业的总成本影响并不大，但对二氧化碳排放的减少有很好的效果，所以企业在考虑减少经济成本时兼顾环境成本，更能履行好企业的社会责任；（3）不同的车型其装载能力和碳排放量不同，所花费的运输成本和环境成本也不同，应根据装载量等要求进行合理的安排车辆。

6 结论与展望

6.1 结论

（1）建立“双成本”视阈下双向物流车辆路径选择模型，通过使用遗传算法求得总成本最少的最终路径。通过实验证明，该算法计算效率高，能得到较满意的解，结果稳定，表明该算法在求解该问题的有效性。

（2）研究结果为快递企业在减少运输成本时也能履行社会责任提供了合理的方案及决策支持，具有一定的参考价值和建议。

（3）车辆的碳排放是产生全球碳排放的主要因素，影响车辆碳排放的因素很多，例如：道路状况、车速、距离、载重等。本文在研究过程中做了简化，只研究了车型、距离、载重对碳排放的影响，这与实际运作情况存在一定的差异。

6.2 展望

（1）路径优化问题在实际情况中更加复杂，本文的研究是一种相对理想的状态，模型中的参数获取比较理想化，后续应该进行大量的实验，寻找更加精准的参数值。

（2）本文只考虑了一个配送中心，在实际中可能有多个配送中心；而且当前顾客需求趋于多样性和及时性，也要求企业在时间上有特殊的要求，所以未来的研究应该更加贴近现实。

[1]Dantzig G,Ranser J.The truck dispathing problem[J].Management Science,1959,6(1):80-91.

[2]Min H.The multiple vehicle routing problems with simultaneous delivery and pick-up points[J].Transportation Research,1989,23(5):377-386.

[3]张建勇,李军.具有同时配送和回收需求的车辆路径问题的混合遗传算法[J].中国公路学报,2006,(4):118-122.

[4]刘晴.随机需求同时取送货车辆路径问题建模及优化研究[D].南京:南京航空航天大学,2012.

[5]王超,穆东.物料配送和废旧产品回收的VRPSDP问题的并行模拟退火算法[J].北京交通大学学报,2014,(6):19-26.

[6]Sbihi A,Eglese R W.Combinatorial optimization and green logistics[J].Annals of Operations Research,2010,175(1):159-175.

[7]Demir E,Bektas T,Laporte G.The bi-objective Pollution-Routing Problem[J].European Journal of Operational Research,2014,232(3):464-478.

[8]钟聪儿,邱荣祖.综合考虑碳排放与运输费用的配送路径优化[J].数学的实践与认识,2016,(21):89-94.

[9]侯跃,杨斌,许波桅,等.考虑碳交易的多车型运输车辆配送路径优化[J].辽宁工程技术大学学报(自然科学版),2015,(5):647-652.

[10]朱长征,李艳玲.碳排量最小的车辆路径优化问题研究[J].计算机工程与应用,2013,(22):15-18.

[11]张立毅,王迎,费腾,等.混沌扰动模拟退火蚁群算法低碳物流路径优化[J].计算机工程与应用,2017,(1):63-68,102.

[12]葛显龙,许茂增,王伟鑫.多车型车辆路径问题的量子遗传算法研究[J].中国管理科学,2013,(1):125-133.

[13]史春阳.同时取送货的车辆路径问题中的低碳研究[D].北京:清华大学,2011.

A Duo-cost Perspective on Logistics Vehicle Two-way Route Selection Problem

Liu Yue,Fu Shimin
(Chongqing University of Posts&Telecommunications,Chongqing 400065,China)

In this paper,on the basis of traditional researches on the routing problem,we added in such constraints as"simultaneous pick-up and delivery"and"environment cost",built the logistics vehicle two-way route selection model from the duo-cost perspective,and designed the suitable genetic algorithm for its solution.Next,through a case study,we demonstrated the validity and feasibility of the model and algorithm.

duo-cost;simultaneous pick-up and delivery;logistics vehicle;route selection;transportation fee;CO2discharge;genetic algorithm

F252.14;F253.7

A

1005-152X(2017)10-0069-06

10.3969/j.issn.1005-152X.2017.10.015

2017-08-19

国家邮政局委托研究项目（E2016-84）

刘跃（1958-），男，四川内江人，重庆邮电大学经济管理学院副院长，教授，硕士，研究方向：电子商务；付世敏（1989-），通讯作者，女，河南商丘人，重庆邮电大学经济管理学院硕士研究生，研究方向：物流规划与设计。