考虑新能源车的低碳集货模型与算法研究
史雨同 尹静 王柏琳
关键词： 制造供应链; 碳排放; 新能源车; 集货模型; 路径优化; 遗传算法; 节约算法
中图分类号： TN911.1?34; F253.9 ? ? ? ? ? ? ? ? ? 文献标识码： A ? ? ? ? ? ? ? ? ? 文章编号： 1004?373X（2019）03?0101?06
Abstract： Aiming at the consolidation problem of manufacture supply chain scattered in various areas of China， the multi?object consolidation model with shorted path and lowest carbon emission is established by considering the vehicle types such as new energy electrical vehicle and traditional diesel vehicle. A two?stage heuristic algorithm was designed according to model feature to solve the model. In the first stage of the algorithm， the genetic algorithm is used to find the consolidation scheme with shortest path as the initial consolidation scheme. On the basis of first stage， the basic thought of saving algorithm is used to perform route splitting， match the limited quantity new energy vehicles， and replan the consolidation method for residue node and vehicle， so as to optimize the carbon emission. The simulation experimental results show that the proposed model and two?stage algorithm can utilize the new energy vehicle effectively， and satisfy the economic benefit and environmental benefit in consolidation process.
Keywords： manufacturing supply chain; carbon emission; new energy vehicle; consolidation model; route optimization; genetic algorithm; saving algorithm0 ?引 ?言
制造供应链中的集货运输活动由于具有节点较多且位置分散等特征，会引起物流成本上升和碳排放增多等问题，不利于我国绿色经济的发展。新能源货车尤其是纯电动车具有零排放等优势，代表了未来的发展方向。研究考虑纯电动车的集货运输活动，对于减少集货过程中的碳排放具有积极的意义。
大部分学者将集货问题归结于车辆路径问题（Vehicle Routing Problem，VRP）进行研究。文献[1]利用禁忌搜索和自适应大邻域搜索构造了一个新的启发式算法来解决容量化的车辆路径问题，文献[2]用人工蜂群算法解决交通拥堵导致车辆路径效率低下的问题。在低碳集货问题方面，文献[3]通过改进遗传算法求解考虑碳排放因素的VRP问题。文献[4]研究了具有固定车辆数的多车型低碳路径问题，实验分析表明，采用固定车辆数的多车型低碳路径问题比传统安排更加经济环保。
以往的研究大多把汽油车或柴油车作为研究对象，考虑新能源车特别是纯电动货车的研究较少。本文研究了同时具有传统柴油车和纯电动车的集货问题，并针对当今技术条件下纯电动车装载量小、续航里程短的特点，建立最短距离和最小碳排放的多目标优化模型，进而采用基于遗传算法和启发式节约算法的两阶段算法进行求解，通过纯电动车的有效利用寻找同时满足环境效益和经济效益的集货方案。1 ?问题描述与建模
1.1 ?问题描述
本文所研究的考虑新能源货车的集货模型可描述为：配送中心派遣一组车辆前往供货商处取货，然后返回配送中心，目标是找到总路径最短和碳排放量最小的集货方案。集货过程中的约束如下：
1） 配送中心约束：所有车辆由配送中心驶出，完成取货任务后返回配送中心;
2） 车辆约束：配送中心有多车型的货车，每种车型的数量和参数已知;
3） 访问唯一性约束：每个供货商只能被一辆车一次性服务;
4） 载重约束：每种类型车辆的装载量需满足该车型的容量限制;
5） 载运距离约束：每种车型车辆的行驶距离不能超过该车型的最大行驶距离;
6） 时间窗约束：供货商只能在规定的时间窗内被车辆服务，如果车辆到达的时间早于最早开始服务时间，车辆将在供货商处等待，如果车辆在最晚开始服务时间之后到达，则产生不可行解;
7） 装货时间约束：车辆到达供货商后需完成装货过程，装货时间固定且已知;
8） 速度约束：行驶过程中所有车辆以相同的速度匀速行驶。
1.2 ?符号和决策变量
[G=（V，E）]：物流配送网络;[V]表示定点，即配送中心或供货商;[E]表示弧集即顶点间的路径集合，[E=（i，j）i，j∈V，i≠j]。
[P]表示路径，[VP]表示路径[P]的点集合;[Dij]表示弧[（i，j）]的距离;[Tij]表示弧[（i，j）]的运输时间;[ST]表示系统开始的时间;[UTi]表示供貨商[i]的装货时间;[[ETi，LTi]]为供货商[i]的时间窗，[ETi]为最早开始服务时间，[LTi]为最晚开始服务时间。
[k]表示车辆集合，[Lk]表示车辆[k]的最大行驶距离;[Qijk]表示车辆[k]在从[i]发往[j]的过程中的载重。
表7中的总费用分别由式（21）和式（22）计算得到，因为所用成本系数不同，所以没有可比性。由表5和表6对比可知，在以总费用最小为目标优化集货问题时，即使针对同一问题，当费用组成中的成本系数不一致时也会得出不一样的路径方案。如今还没有公认的成本系数，大多数研究只能针对所研究的现实问题设计符合自身问题的成本系数，而成本系数的设定直接影响最终方案的产生。本文为了消除成本系数的影响，寻找更具通用性的模型和算法，采用两阶段的计算方法，首先在阶段1解决最短路径问题，然后在阶段2集货方案的基础上进行路径的拆分重组，寻找碳排放更少的集货方案。由于阶段2集货方案是在阶段1解的基础上得到的，因此阶段2的集货方案同时考虑了路径和碳排放的影响。案例中阶段2的结果相比于阶段1，距离仅增加了74 km，碳排放降低了125 kg，在最短距离方案的基础上降低碳排放量，优化环境效益是切实可行的。4 ?结 ?论
本文考虑纯电动车的多车型集货问题，将路径优化和最小碳排放量结合起来，建立统一的多目标优化模型。为了寻找具有通用性的计算方法，根据模型特征，本文设计了分阶段算法进行求解。首先用遗传算法解决最短车辆路径问题，产生初始集货方案;进而基于节约算法的基本思想对方案中的路径进行拆分和重组，通过新能源电动货车和传统柴油货车的统一调度和有效利用，得到更为低碳的集货方案。实例中拆分重组后的集货方案较之前降低了125 kg碳排放量，可以看到本文提出的模型和算法是有效的。
参考文献
[1] SENA K， HARUN R Y， EMRE T. A novel heuristic algorithm for capacitated vehicle routing problem [J]. Journal of industrial engineering international， 2017， 13（3）： 323?330.
[2] LEE C K M，WU K，WILLIAM H， et al. A multiple colonies artificial bee colony algorithm for a capacitated vehicle routing problem and re?routing strategies under time?dependent traffic congestion [J]. Computers & industrial engineering， 2017， 5（4）： 151?168.
[3] 邱雅君，宋国防.考虑碳排放因素的车辆路径问题研究[J].物流技术，2012（13）：226?229.
QIU Yajun， SONG Guofang. Study on carbon emissions consi?dered VRP [J]. Logistics technology， 2012（13）： 226?229.
[4] 李进，傅培华.具有固定车辆数的多车型低碳路径问题及算法[J].计算机集成制造系统，2013，19（6）：1351?1362.
LI Jin， FU Peihua. Heterogeneous fixed fleet low?carbon rou?ting problem and algorithm [J]. Computer integrated manufactu?ring systems， 2013， 19（6）： 1351?1362.
[5] 史春阳，赵磊.同时取送货的车辆路径问题中的低碳研究[D].北京：清华大学，2011.
SHI Chunyang， ZHAO Lei. The low carbon study of the take and delivery vehicle routing problem [D]. Beijing： Tsinghua University， 2011.
[6] 雷英杰，张善文.Matlab遗传算法工具箱及应用[M].西安：西安电子科技大学出版社，2014：82?84.
LEI Yingjie， ZHANG Shanwen. Application of Matlab genetic algorithms toolbox [M]. Xian： Xidian University Publishing House， 2014： 82?84.
[7] UBEDA S， ARCELUS F J， FANLIN J. Green logistics at Eroski： a case study [J]. International journal of production economics， 2011， 131： 44?51.
[8] 李进，傅培华，李修琳，等.低碳环境下的车辆路径问题及禁忌搜索算法研究[J].中国管理科学，2015，23（10）：98?106.
LI Jin， FU Peihua， LI Xiulin， et al. Study on vehicle routing problem and tabu search algorithm under low?carbon environment [J]. Chinese journal of management science， 2015， 23（10）： 98?106.
[9] 张津.考虑碳排放的带时间窗约束的车辆路径问题研究[D].重庆：重庆大学，2016.
ZHANG Jin. Vehicle routing problem with time windows constraint considering carbon emission [D]. Chongqing： Chongqing University， 2016.
[10] 葛显龙，许茂增，王伟鑫.多车型车辆路径问题的量子遗传算法研究[J].中国管理科学，2013，21（1）：125?133.
GE Xianlong， XU Maozeng， WANG Weixin. Study on multi?types vehicle routing problem and its quantum genetic algorithm [J]. Chinese journal of management science， 2013， 21（1）： 125?133.
关键词： 制造供应链; 碳排放; 新能源车; 集货模型; 路径优化; 遗传算法; 节约算法
中图分类号： TN911.1?34; F253.9 ? ? ? ? ? ? ? ? ? 文献标识码： A ? ? ? ? ? ? ? ? ? 文章编号： 1004?373X（2019）03?0101?06
Abstract： Aiming at the consolidation problem of manufacture supply chain scattered in various areas of China， the multi?object consolidation model with shorted path and lowest carbon emission is established by considering the vehicle types such as new energy electrical vehicle and traditional diesel vehicle. A two?stage heuristic algorithm was designed according to model feature to solve the model. In the first stage of the algorithm， the genetic algorithm is used to find the consolidation scheme with shortest path as the initial consolidation scheme. On the basis of first stage， the basic thought of saving algorithm is used to perform route splitting， match the limited quantity new energy vehicles， and replan the consolidation method for residue node and vehicle， so as to optimize the carbon emission. The simulation experimental results show that the proposed model and two?stage algorithm can utilize the new energy vehicle effectively， and satisfy the economic benefit and environmental benefit in consolidation process.
Keywords： manufacturing supply chain; carbon emission; new energy vehicle; consolidation model; route optimization; genetic algorithm; saving algorithm0 ?引 ?言
制造供应链中的集货运输活动由于具有节点较多且位置分散等特征，会引起物流成本上升和碳排放增多等问题，不利于我国绿色经济的发展。新能源货车尤其是纯电动车具有零排放等优势，代表了未来的发展方向。研究考虑纯电动车的集货运输活动，对于减少集货过程中的碳排放具有积极的意义。
大部分学者将集货问题归结于车辆路径问题（Vehicle Routing Problem，VRP）进行研究。文献[1]利用禁忌搜索和自适应大邻域搜索构造了一个新的启发式算法来解决容量化的车辆路径问题，文献[2]用人工蜂群算法解决交通拥堵导致车辆路径效率低下的问题。在低碳集货问题方面，文献[3]通过改进遗传算法求解考虑碳排放因素的VRP问题。文献[4]研究了具有固定车辆数的多车型低碳路径问题，实验分析表明，采用固定车辆数的多车型低碳路径问题比传统安排更加经济环保。
以往的研究大多把汽油车或柴油车作为研究对象，考虑新能源车特别是纯电动货车的研究较少。本文研究了同时具有传统柴油车和纯电动车的集货问题，并针对当今技术条件下纯电动车装载量小、续航里程短的特点，建立最短距离和最小碳排放的多目标优化模型，进而采用基于遗传算法和启发式节约算法的两阶段算法进行求解，通过纯电动车的有效利用寻找同时满足环境效益和经济效益的集货方案。1 ?问题描述与建模
1.1 ?问题描述
本文所研究的考虑新能源货车的集货模型可描述为：配送中心派遣一组车辆前往供货商处取货，然后返回配送中心，目标是找到总路径最短和碳排放量最小的集货方案。集货过程中的约束如下：
1） 配送中心约束：所有车辆由配送中心驶出，完成取货任务后返回配送中心;
2） 车辆约束：配送中心有多车型的货车，每种车型的数量和参数已知;
3） 访问唯一性约束：每个供货商只能被一辆车一次性服务;
4） 载重约束：每种类型车辆的装载量需满足该车型的容量限制;
5） 载运距离约束：每种车型车辆的行驶距离不能超过该车型的最大行驶距离;
6） 时间窗约束：供货商只能在规定的时间窗内被车辆服务，如果车辆到达的时间早于最早开始服务时间，车辆将在供货商处等待，如果车辆在最晚开始服务时间之后到达，则产生不可行解;
7） 装货时间约束：车辆到达供货商后需完成装货过程，装货时间固定且已知;
8） 速度约束：行驶过程中所有车辆以相同的速度匀速行驶。
1.2 ?符号和决策变量
[G=（V，E）]：物流配送网络;[V]表示定点，即配送中心或供货商;[E]表示弧集即顶点间的路径集合，[E=（i，j）i，j∈V，i≠j]。
[P]表示路径，[VP]表示路径[P]的点集合;[Dij]表示弧[（i，j）]的距离;[Tij]表示弧[（i，j）]的运输时间;[ST]表示系统开始的时间;[UTi]表示供貨商[i]的装货时间;[[ETi，LTi]]为供货商[i]的时间窗，[ETi]为最早开始服务时间，[LTi]为最晚开始服务时间。
[k]表示车辆集合，[Lk]表示车辆[k]的最大行驶距离;[Qijk]表示车辆[k]在从[i]发往[j]的过程中的载重。
表7中的总费用分别由式（21）和式（22）计算得到，因为所用成本系数不同，所以没有可比性。由表5和表6对比可知，在以总费用最小为目标优化集货问题时，即使针对同一问题，当费用组成中的成本系数不一致时也会得出不一样的路径方案。如今还没有公认的成本系数，大多数研究只能针对所研究的现实问题设计符合自身问题的成本系数，而成本系数的设定直接影响最终方案的产生。本文为了消除成本系数的影响，寻找更具通用性的模型和算法，采用两阶段的计算方法，首先在阶段1解决最短路径问题，然后在阶段2集货方案的基础上进行路径的拆分重组，寻找碳排放更少的集货方案。由于阶段2集货方案是在阶段1解的基础上得到的，因此阶段2的集货方案同时考虑了路径和碳排放的影响。案例中阶段2的结果相比于阶段1，距离仅增加了74 km，碳排放降低了125 kg，在最短距离方案的基础上降低碳排放量，优化环境效益是切实可行的。4 ?结 ?论本文考虑纯电动车的多车型集货问题，将路径优化和最小碳排放量结合起来，建立统一的多目标优化模型。为了寻找具有通用性的计算方法，根据模型特征，本文设计了分阶段算法进行求解。首先用遗传算法解决最短车辆路径问题，产生初始集货方案;进而基于节约算法的基本思想对方案中的路径进行拆分和重组，通过新能源电动货车和传统柴油货车的统一调度和有效利用，得到更为低碳的集货方案。实例中拆分重组后的集货方案较之前降低了125 kg碳排放量，可以看到本文提出的模型和算法是有效的。
参考文献
[1] SENA K， HARUN R Y， EMRE T. A novel heuristic algorithm for capacitated vehicle routing problem [J]. Journal of industrial engineering international， 2017， 13（3）： 323?330.
[2] LEE C K M，WU K，WILLIAM H， et al. A multiple colonies artificial bee colony algorithm for a capacitated vehicle routing problem and re?routing strategies under time?dependent traffic congestion [J]. Computers & industrial engineering， 2017， 5（4）： 151?168.
[3] 邱雅君，宋国防.考虑碳排放因素的车辆路径问题研究[J].物流技术，2012（13）：226?229.
QIU Yajun， SONG Guofang. Study on carbon emissions consi?dered VRP [J]. Logistics technology， 2012（13）： 226?229.
[4] 李进，傅培华.具有固定车辆数的多车型低碳路径问题及算法[J].计算机集成制造系统，2013，19（6）：1351?1362.
LI Jin， FU Peihua. Heterogeneous fixed fleet low?carbon rou?ting problem and algorithm [J]. Computer integrated manufactu?ring systems， 2013， 19（6）： 1351?1362.
[5] 史春阳，赵磊.同时取送货的车辆路径问题中的低碳研究[D].北京：清华大学，2011.
SHI Chunyang， ZHAO Lei. The low carbon study of the take and delivery vehicle routing problem [D]. Beijing： Tsinghua University， 2011.
[6] 雷英杰，张善文.Matlab遗传算法工具箱及应用[M].西安：西安电子科技大学出版社，2014：82?84.
LEI Yingjie， ZHANG Shanwen. Application of Matlab genetic algorithms toolbox [M]. Xian： Xidian University Publishing House， 2014： 82?84.
[7] UBEDA S， ARCELUS F J， FANLIN J. Green logistics at Eroski： a case study [J]. International journal of production economics， 2011， 131： 44?51.
[8] 李进，傅培华，李修琳，等.低碳环境下的车辆路径问题及禁忌搜索算法研究[J].中国管理科学，2015，23（10）：98?106.
LI Jin， FU Peihua， LI Xiulin， et al. Study on vehicle routing problem and tabu search algorithm under low?carbon environment [J]. Chinese journal of management science， 2015， 23（10）： 98?106.
[9] 张津.考虑碳排放的带时间窗约束的车辆路径问题研究[D].重庆：重庆大学，2016.
ZHANG Jin. Vehicle routing problem with time windows constraint considering carbon emission [D]. Chongqing： Chongqing University， 2016.
[10] 葛显龙，许茂增，王伟鑫.多车型车辆路径问题的量子遗传算法研究[J].中国管理科学，2013，21（1）：125?133.
GE Xianlong， XU Maozeng， WANG Weixin. Study on multi?types vehicle routing problem and its quantum genetic algorithm [J]. Chinese journal of management science， 2013， 21（1）： 125?133.
