基于节能减排的最优车辆配送路径研究

摘 要：车辆路径问题是一个典型的组合优化问题，是一个NP难题。研究的目标大多是车辆行驶里程最短、车辆按一定时间到达、运输总费用最低、使用的车辆数最少等，随着能源的日趋短缺和环境压力的不断增大，全社会节能、环保意识逐渐加强，节能减排成为了物流配送车辆路线优化的新突破。本文从节能减排的角度研究车辆路径问题（VRPRFC），并用遗传算法求解，将建设节约型社会的全新理念贯彻到物流运输发展过程中来。

关键词：车辆路径;节能减排;VRPRFC

背景

我国对车辆路径问题的研究在20世纪90年代以后才逐渐兴起，比国外相对落后。随着客户物质需求的多样化不规则性以及经济全球化趋势的发展，运输规划的重要性日益显著，近年来我国理论界逐渐开始关注车辆路径问题的解决方法，已取得了较为显著的成果。但总体来说，我国目前对车辆路径问题的理论研究仍显得不足，有待进一步的提高。随着能源的日趋短缺和环境压力的不断增大，全社会节能、环保意识逐渐加强，节能减排成为了物流配送车辆路线优化的新突破。

本文从节能减排的角度研究车辆路径问题（VRPRFC），并用遗传算法求解，将建设节约型社会的全新理念贯彻到物流运输发展过程中来。

1、VRPRFC模型的建立

1.1建立VRPRFC模型

令为客户集合（其中0代表配送中心），为可供租赁的车辆集合，为可行解的路线集合。所有的可行路径开始并结束于配送中心。令为两点（和）之间的距离。令为客户的需求，为车辆能力约束。由于点0表示配送中心，因此，。令为车辆在完成配送任务时，到达客户前车上装载的货物量。令单位行驶里程空载油耗，为单位里程单位载重附加油耗。

定义决策变量，如果点 到点路线是由车辆来完成时，，否则，。由于车辆总是在配送中心（点0）装载配送路线上的客户需求货物，因此。

基于节能减排的有能力约束的车辆路线优化问题数学描述如下：

式（1.1）表示本数学模型的优化目标为最小化油耗。约束条件（1.2）确保车辆每次配送任务量不超过其能力约束。等式（1.3）为平衡条件，确保车辆在某次配送任务中到达某需求点，则其也将在该次配送任务中离开该需求点。等式（1.4）确保某个客户仅在一次配送任务中由一辆车辆提供服务。不等式（1.5）确保实现某次配送任务的车辆只离开配送中心一次。约束条件（1.6）确保不存在不经过配送中心的回路存在。约束条件（1.7）确保当时，车辆在配送任务中，从点运往点的货物量等于该车到达点时的货物量减去在点卸货量（即用户的需求），如图1。

图1 封闭式车辆路径与的关系图

Fig.1 The relationship between andof the closed one

2、遗传算法求解

2.1编码

现用遗传算法解决VRPRFC问题，遗传算法的个体编码为一串整数，每个数字代表一个客户或者分隔不同配送路线的标志，一串没有被分隔标志分隔的客户代表一条起止点为配送中心（标记为0）的配送路线。比如，假设配送中心有10个客户，分别用1到10来表示，若估计最优配送计划的路线不会超过5条，则可以用数字11到14作为分隔标志来分隔不同的配送路径。由1到14的一个排列即表示一个配送计划（该个体编码不包含配送路径由什么车辆完成的信息，车辆指派问题利用BFD算法求解），如个体编码图2。

图2染色体编码

Fig.2 Chromosome

即可以解码为如下三条配送路线：

线路1：

线路2：

线路3：

2.2适应度函数

GA淘汰个体的原则是适应能力的强弱。个体的适应能力以适应度函数f(x)的值来判别的，这个值称为适应度值（Fitness）。

f(x)的构成与目标函数有关，往往是目标函数的变种。

适应度函数的处理有：目标函数的确定、目标函数到适应度函数的映射、适应度值调整等。目标函数与具体问题紧密相关。TSP的目标函数是通过所有不重复城市的最短路径规则归纳问题是找到覆盖所有例子集的最小数目的规则，模糊神经网络问题的目标是得到系统参数，使实际输出与期望输出达到尽可能小。个体适应度值是非负的，总是希望越大越好，而目标函数有正有负，因此，目标函数向适应度函数映射时，首先保证映射后的函数值为正，其次目标函数的优化方向对应于适应度值增大的方向[61]。

综上，建立VRPRFC模型适应度函数如下：

式中：是一个很大的数（如果公式（5.2）不满足），否则，。

2.3求解算法

基于Inver-over操作(Michalewicz Z. et al., 2000)的遗传算法的解法如下：

随机初始化种群，并计算个体适应值

3、算例分析

已知有20个客户，详细信息如下表。

表1客户数据信息

表2模型参数设置

种群规模为50，则最大迭代次数为2000，（基于Inver-over操作需求的选择概率），通过遗传算法求解，车辆数为4，总油耗是68.788。图3给出了应用遗传算法得到的一个解决方案。

图3 基于遗传算法的封闭式解决方案

Fig 3 Closed vehicle route based on genetic algorithm

4、小结

本文建立了有能力约束的VRPRFC模型，并给出求解算法，应用Inver-over操作的遗传算法给出车辆装载量限制的条件下车辆路径的选取方案。在数学模型计算过程中，车辆日行驶里程为严格约束，但在实际操作中，适当的超过日行驶里程限制导致的成本增加（日行驶里程超过上限可以理解为加班成本）往往在与租车成本降低、油耗节约的平衡中被允许，在以后的研究中，可以着眼于这类更加灵活的限制条件。

参考文献：

PENG Yong, LI Hongbo. Optimization of Vehicle Route to Reduce Fuel Consumption Based

on Genetic Algorithm[C]．International Conference on Transportation Engineering, 2009, vol.3: 1920-1925.

丁刚，杨剑炜．天线阵列综合中的遗传算法应用综述[J]．舰船电子工程，2006，154(4):26~30

周远晖，陆玉昌等．基于克服过早收敛的自适应并行遗传算法[J]．清华大学学报(自然科学版)，1998，38(3):93~95.