以降低油耗为目标的车辆路径问题研究

蔡 虹,吴 斌，殷南晨

(南京工业大学 经济与管理学院，南京 210009)

以降低油耗为目标的车辆路径问题研究

蔡 虹,吴 斌，殷南晨

(南京工业大学 经济与管理学院，南京 210009)

车辆路径问题是物流及供应链管理优化的核心环节。为实现低碳运输，文中综合考虑运输车辆的载重、车速及行驶距离等因素，以降低车辆在运输过程中的油耗成本和单位车辆的固定成本为目标优化车辆路径, 建立数学模型并创新交叉算子设计改进遗传算法，并通过仿真实验对算法的效果进行验证。仿真结果表明，所提出的算法简洁、有效。

降低油耗；车辆路径问题；改进遗传算法 ；Matlab软件

以节能减排为目标的车辆路径问题是经典车辆路径问题(vehicle routing problem，VRP)的一个新方向，它不再以传统的总运输成本为目标，而是将降低油耗作为关键目标。近年来，低碳、环保、节约能源已经成为世界各国的关键词，对于迫切要求经济增长方式转型的中国，这方面的研究意义重大，对于物流企业、零售企业均具有较强的实用价值。

国内外已有学者在车辆路径问题的研究中考虑车辆的能耗和排放问题。Miguel Figliozzi[1]以运输车辆二氧化碳的排放量为优化目标开展研究，用车程和车速计算运输车辆的二氧化碳排放量，并建立有时间窗的车辆路径问题模型，用迭代路线算法进行优化计算；Miguel Figliozzi等[2]在运输车辆选择的经济性和环境影响方面做了研究，通过综合比较不同车型的购买、维护、运行、折旧、排放费用等，选出最经济环保的运输车辆；李进，傅培华[3]对多车型低碳路径问题的研究则以降低碳排放为目标，综合考虑运量和车速来计算油耗，并运用禁忌搜索算法进行优化计算；邱雅军，宋国防[4]用车辆所行驶的路程来量化车辆路径问题中的碳排放，并运用改进的遗传算法进行优化计算。综上所述，已知文献的研究中很少考虑车辆的载重量对车辆排放的影响；针对该问题所设计的遗传算法优化效果有限，算子的设计有待改进。

本文综合运输车辆的载重、车速及行驶路程来计算运输任务中的油耗，参考文献[5-6]建立油耗计算公式，考虑油耗的经济成本和单位车辆的固定成本设定目标函数并建立模型；设计了遗传算法算子用于计算；通过仿真实验对算法的效果进行验证。仿真结果表明，经过优化的调度方案的总油耗大幅降低，从而达到节能环保的目标。

1 问题描述

2 建立降低油耗为目标的车辆路径模型

(1)

约束条件：

(2)

(3)

(4)

(5)

(6)

式(2)保证了每个所需经过的路段都有且仅有一辆车经过，保证每个客户有且仅有一辆车为他服务；式(3)保证了每个客户站点有同一辆车到达和离开；式(4)表明车辆出发后直到完成所有任务，中间不再回到车站；式(5)保证每辆车都由车站出发，并保证了每辆车都会回到车站；式(6)保证了每辆车都不会超重。

3 改进遗传算法设计

3.1 编码及染色体适应度的计算

将车站v以及所有的客户C={v1,v2，…，vn}用整数进行编码。其中车站的编码为“0”，其余客户编码依次为“1”“2”“3”…“n”。一条染色体拥有L+K+1个基因(L为客户数，K为参加运输的车辆数)，其中包括L个客户的唯一的编码，并在其中穿插了K+1个车站编码“0”以区别客户对应的车辆。

3.2 变异算子

本文以基本位变异法为基础，根据实际需要做出改进，以一定的变异概率分别对染色体的每一个基因位进行变异操作，具体步骤如下：

Step1：设变量i为从左到右基因的编号，初始值i=1，xi表示染色体R内基因；

Step2：若xi=0，则i=i+1，回到Step1；

Step3：随机取一个除xi以外的基因yi≠0，交换xi和yi的位置，得到新染色体R′；

Step4：如果R″不满足载重要求或者适应度小于R，则放弃该次变异操作，变回原染色体R；

Step5：如果i

4 仿真实验

本文用如下实例测试上述遗传算法并由Matlab实现，共有6辆同型号车辆供运输使用，需要完成16位客户的运输任务，要求总成本尽可能低。具体参数分别见表1和表2。

表1 基本数据

续 表

表2 每个客户的货物重量

4.1 实验结果

针对前述实例，交叉改进前后的线路优化结果分别如图1和图2所示。

图1 交叉改进前的优化结果

图2 交叉改进后的优化结果

在两个优化结果中都只有四条运输线路，说明6辆运输车辆中只有4辆参与了运输任务，其余两辆闲置。

利用本文的遗传算法，计算前述实例，结果见表3。

表3 实验结果

5 结束语

本文将降低运输过程中的油耗经济成本和单位车辆的固定成本作为车辆路径问题的目标，通过创新交叉算子设计改进遗传算法。通过仿真实验可以看出，优化后的调度方案的总经济成本大幅降低，并且算法简单、有效。下一步可以将服务的时间窗考虑进来，将更具实践意义。

[1]MiguelFigliozzi.Vehicleroutingproblemforemissionsminimization[J].TransportationResearchBoard，2010，2197：1-7.

[2]MiguelAFigliozzi，JesseABoudart，WeiFeng.Economicandenvironmentaloptimizationofvehiclefleets：acasestudyoftheimpactsofpolicy，market，utilization，andtechnologicalfactors[J].TransportationResearchBoard，2011，2252:1-6.

[3] 李进，傅培华. 具有固定车辆数的多车型低碳路径问题及算法[R].浙江：浙江工商大学计算机与信息工程学院，2012.

[4] 邱雅君，宋国防. 考虑碳排放因素的车辆路径问题研究[J].技术与方法，2012，36(7)：227-229.

[5] 庄志华，何仁，李丽. 运行参数对客车燃料经济性影响的参数灵敏度分析[J].轻型汽车技术，2007(2)：4-7.

[6] 何仁.汽车动力性燃料经济性模拟计算方法及 应 用[M].北京：机械工业出版社，1996:18-21.

Research on Vehicle Routing Problem for Fuel Consumption Reduction

CAI Hong, WU Bin,YIN Nanchen

(College of Economics Management,Nanjing University of Technology,Nanjing 210009,China)

Vehicle routing problem is the core of optimization on logistics and supply chain management. According to the requirement of low-carbon transportation, the paper takes vehicle weight, vehicle velocity and distance into consideration, and optimizes the vehicle routing problem by setting the fuel consumption economics cost and fixed-cost of vehicle as objective function. Then the improved genetic algorithm is proposed, applying new crossover operator. Simulation results show that the designed algorithm is simple and effective.

fuel consumption reduction; vehicle routing problem; improved genetic algorithm; Matlab software

2014-05-25；修改日期: 2014-06-21

江苏省自然科学基金资助项目(BK2010555)；江苏省高教改革基金资助项目(2011JSJG182);江苏省高等学校大学生实践创新训练计划基金资助项目(2012JSSPITP0903)。

蔡 虹(1978-),女，博士研究生，讲师，研究方向：物流系统建模与优化，收益管理。

U

Adoi:10.3969/j.issn.1672-4550.2015.03.005