2. 北京邮电大学 计算机学院, 北京 100876
在分析电动汽车加电站运营模式的基础上, 根据电动汽车加电站需求动态变化的特点, 建立了加电站电池配送路径问题的动态车辆调度模型.利用自适应准则改进遗传算法, 构造了自适应遗传算法; 针对动态车辆调度问题实时性强的特点, 设计了"初始化路径制定+实时动态调度"的两阶段求解策略, 通过信息更新插入动态需求加电站, 对已产生的计划路径进行局部优化调整, 仿真计算结果验证了模型和算法的有效性.
2. School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
On the basis of analyzing electric vehicle power station operation mode and aiming at the dynamic changes of power station requirements, a two-phase mathematic programming model based on power station center is presented for dynamic vehicle routing problem. And a new adaptive genetic algorithm is designed for dynamic vehicle routing problem. Aiming at the real time of dynamic vehicle scheduling problem, the two-phase solution of "initial path stage" and "real-time dynamic scheduling stage" are established, which optimizes sub-routes through continuously updating information and inserting the dynamic needs power stations. Simulation validates the effectiveness of the model and the algorithm.
近来，大气污染给人们的生产生活造成了严重的影响，发展电动汽车是解决大气污染的有效途径，电动汽车加电站运营面临巨大的机遇与挑战.由于电动汽车完成一次充电需要1~2 h，在一定程度上阻碍了电动汽车的快速推广.换电模式作为一种新的电动汽车加电模式，可以将加电时间缩短到5~10 min，将成为未来非常重要的电动汽车加电模式.为了支持电动汽车换电的需求，电动汽车加电运营商需要根据不同情况向各加电站配送不同型号的电动汽车电池.目前的电池配送存在车辆使用多、装载率低、临时电池需求无法快速满足等问题.制定合理的加电站电池配送策略将直接影响加电站的服务质量和经济效益.
加电站电池配送路径优化是电池配送策略的核心问题，是动态车辆调度问题(DVRP，dynamic vehicle routing problem)[1-4]的一种实际应用，具有建模困难、计算复杂、对算法的实时性要求高等特点.自适应遗传算法已被广泛应用于优化计算、机器学习等领域[5-6].笔者提出了一种改进的自适应遗传算法，对交叉概率和变异概率的动态调整及编码方式、选择、交叉和变异算子均进行了一定的改进，并将这种方法首次应用于电动汽车加电站电池配送路径优化算法中.
1 加电站动态需求车辆路径问题描述及其数学模型本研究的加电站电池配送路径问题描述为：一个电池配送中心拥有容量为q的车辆K辆，负责对L个加电站进行多种型号的电池配送工作，电池型号共有B种.加电站i对第b型电池的理想需求量为hib，加电站i对第b种电池的最低需求量为lib，并且lib≤hib.每个加电站仅被一辆车服务一次，每辆车完成任务后返回原配送中心.配送车辆行驶的平均速度已知且确定, 行驶的路程与车辆行驶时间成正比.
在电池配送过程中，当有新的加电站提出需求计划时，配送中心调度系统需要根据各加电站对不同电池的需求量，在至少满足各加电站对不同电池最低需求量的情况下，改变原先路径或重新开辟路径以对动态需求做出及时处理.
问题的目标是寻找一种合适的车辆调度方案，满足加电站的实时需求，并使车辆总的运输距离最短.根据以上描述，笔者建立以下初始化路径制定阶段模型和实时动态调度阶段模型.
1.1 初始化路径制定模型初始化路径制定模型的建立如下：配送中心和各加电站均用点i，j表示；配送中心的编号为0，加电站编号为1, 2, …, L；车辆用k表示，编号为1, 2, …, K；电池种类用b表示，编号为1, 2, …, B；从i地到j地的距离cij，i, j∈{0, 1, 2, …, L}.
定义决策变量：
|
则初始化路径制定阶段的数学模型表示如下.
目标函数：
|
(1) |
|
(2) |
|
(3) |
|
(4) |
|
(5) |
|
(6) |
|
(7) |
上述模型中，式(2) 保证负责配送的车辆数目不能超过配送中心的所有车辆数；式(3) 保证车辆都是从配送中心出发，最后再回到中心；式(4) 保证每辆车的能力约束；式(5) 保证每个加电站都能被服务；式(6) 和式(7) 保证每个加电站仅被一辆车服务.
1.2 实时动态调度模型在实时动态调度阶段调度的开始时刻，初始化路径制定阶段的车辆已向部分加电站提供服务，车辆上各类型电池的数量有所减少，并且车辆位于最后服务的加电站处.在车辆上的电池能满足加电站需求的前提下，将新增加电站加入到已有路径中，否则需要安排新的车辆服务.
实时动态调度阶段模型的建立如下：假设第一阶段配送车辆剩余电池量为qk(k=1, 2, …, K)，N为第一阶段未服务加电站和实时动态调度阶段新增加电站的总数量，配送中心新派T辆车.第一阶段配送中心驶出的车辆分别处在K个加电站位置，编号为N+1, N+2, …, N+K，原配送中心编号为N+K+1.
目标函数：
|
(8) |
|
(9) |
|
(10) |
|
(11) |
|
(12) |
上述模型中，式(9) 保证实时动态调度阶段车辆的能力约束；式(10) 保证每个加电站都被服务；式(11) 和式(12) 保证每个加电站仅被一辆车服务.
2 加电站电池配送路径算法设计2.1 两阶段求解策略根据第2章建立数学规划模型，采用“预优化路径制定+实时动态调度”的两阶段求解策略，具体步骤如图 1所示.
|
图 1 电池配送路径问题求解策略流程图 |
1) 编码
根据电池配送路径优化问题的特点，为了在编码中反映车辆配送的路径，笔者采用了一种基于自然数的编码方法.配送中心用0表示，各个加电站用1, 2, …, L表示.由于在配送中心有K辆汽车，则最多存在K条配送路径，分别用L+1, L+2, …, L+K-1表示这K辆汽车.例如，对于一个有7个加电站，用2辆汽车完成配送任务的问题，则编码21768345表示第1条配送路径为：0-2-1-7-6-8(0)，第2条配送路径为:8(0)-3-4-5.
2) 适应度评估
在满足配送约束条件的前提下，需要计算个体的目标值来判定个体的优劣程度.对于某个个体j，设其目标函数值为Zj，则该个体的适应度Fj可用式(13) 表示.
|
(13) |
式中
3) 自适应参数
在遗传算法中，为了避免陷于局部最优，种群中的个体在整个遗传过程中，需要保持解的多样性[7].交叉概率Pc和变异概率Pm选择不当会影响算法的行为和性能. Pc和Pm越大，个体适应度波动越大，使得优良的个体被破坏的概率也相应增大；反之，Pc和Pm越小，个体适应度波动越小，使得形成新的个体的概率也相应减小.鉴于标准遗传算法采用固定的Pc和Pm限制了算法的搜索效果，自适应遗传算法引入了如式(14)、式(15) 所示的自适应选择函数，使得自适应遗传概率Pc和Pm在种群进化过程中可以自动调整.
同时，对于适应度值高于群体平均值的个体，对应于较低的Pc和Pm，使该个体得以保护从而进入下一代；而低于群体平均值的个体，对应于较高的Pc和Pm，使该个体被淘汰掉.因此，自适应遗传算法在保持群体多样性的同时，保证了遗传算法的收敛性.自适应参数公式如下：
|
(14) |
|
(15) |
其中：f表示每代群体的平均适应度值，fmax表示群体中最大的适应度值，f′表示要交叉的2个个体中较大的适应度值；f表示要变异个体的适应度值.取pc1=0.9，pc2=0.6，pm1=0.1，pm2=0.01.
4) 选择操作
笔者采用最优染色体保留法与赌轮选择法相结合的选择策略：将父代适应度最高的染色体直接保留进入下一代，并利用赌轮选择法产生其余染色体.
5) 交叉操作
交叉规则采用PMX(部分匹配交叉)法，除排在第一位的最优个体外，对其余个体要按交叉概率Pc进行配对交叉，产生新的种群.交叉概率Pc计算如式(14) 所示.
6) 变异操作
为保持群体内个体的多样化，采用两点交换作为自适应遗传算法的变异算子，随机选取染色体上的两个基因位，交换这两个位置上的相应基因，形成新个体.变异操作是以概率Pm发生的，一旦变异操作发生，则用随机方法产生2个交换位.变异概率Pm计算如式(15) 所示.
3 算例分析采用Java程序对一个由计算机随机产生的电动汽车电池动态配送网络进行计算仿真.配送区域为边长50 km的正方形，随机产生30个预优化阶段加电站和10个实时优化阶段加电站，其中配送中心位置为O(25 km，25 km)，配送中心车辆的载重体积均为60 t，电池类型共有3种.加电站位置及电池需求量如表 1所示.
|
表 1 初始化路径制定阶段加电站电池需求量 |
首先对第1阶段加电站配送路径进行求解，结果如表 2所示.
|
|
表 2 初始化调度路径 |
在时刻t=30更新加电站需求信息，此时有10个新加电站提出电池配送需求，其位置坐标和电池需求量如表 3所示.
|
|
表 3 新增加电站电池需求量 |
由计算结果知，此时配送中心已发出4辆车，分别位于加电站2、6、30、27和21.在实时动态调度阶段，未服务加电站和新增加电站共31个，根据已知信息对配送网络的车辆进行实时动态调度，运用自适应遗传算法对时刻t=30的配送网络进行求解，并输出时刻t=30的调度计划，计算结果如表 4所示.
|
|
表 4 实时动态调度路径 |
由此可见，两阶段求解策略能够较好地解决动态车辆调度问题的实时性要求，取得较好的结果.
4 结束语针对加电站电池配送过程中加电站需求动态变化的情况，建立了动态车辆调度数学规划模型，制定了相应的“初始化路径制定+实时动态调度”的两阶段求解策略，并设计了改进的自适应遗传算法.实验结果表明，该方法能有效地求解动态车辆路径问题，满足调度的实时性要求.
| [1] |
蔡焕芹, 王丽亚, 高薛文. 遗传算法在预拌混凝土配送中的应用[J]. 上海交通大学学报, 2007, 41(8): 1388–1392.
Cai Huanqin, Wang Liya, Gao Xuewen. Optimizing the scheduling of dispatching ready mixed concret trucks through genetic algorithm[J].Journal of Shanghai Jiaotong University, 2007, 41(8): 1388–1392. |
| [2] |
侯玲娟, 周泓, 梁春华. 不确定需求和旅行时间下的车辆路径问题[J]. 计算机集成制造系统, 2011, 17(1): 101–108.
Hou Lingjuan, Zhou Hong, Liang Chunhuan. Vehicle routing problem with uncertain demand and travel time[J].Computer Integrated Manufacturing Systems, 2011, 17(1): 101–108. |
| [3] |
张飞舟, 耿嘉洲, 程鹏. 基于云遗传算法的公交车辆智能调度[J]. 武汉大学学报:信息科学版, 2010, 35(8): 905–908.
Zhang Feizhou, Geng Jiazhou, Cheng Peng. Intelligent dispatching of public vehicles based on cloud genetic algorithms[J].Geomatics and Information Science of Wuhan University, 2010, 35(8): 905–908. |
| [4] | Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Trans on Systems, Man and Cybernetics, 1994, 24(4): 656–667. doi: 10.1109/21.286385 |
| [5] |
李剑, 景博. 自适应遗传算法在多边多议题协商中的应用[J]. 北京邮电大学学报, 2008, 31(6): 67–69.
Li Jiang, Jing Bo. Adaptive genetic algorithm and its application in multi-lateral multi-issue negotiation[J].Journal of Beijing University of Posts and Telecommunication, 2008, 31(6): 67–69. |
| [6] |
庄家俊, 刘琼. 自适应遗传优化BP网络的研究与应用[J]. 北京邮电大学学报, 2012, 35(5): 41–45.
Zhuang Jiajun, Liu Qiong. Research and application of an optimized BP neural network based on adaptive genetic algorithm[J].Journal of Beijing University of Posts and Telecommunication, 2012, 35(5): 41–45. |
| [7] |
郑岩, 黄荣怀, 战晓苏, 等. 基于遗传算法的动态模糊聚类[J]. 北京邮电大学学报, 2005, 28(1): 75–78.
Zheng Yan, Huang Ronghuai, Zhan Xiaosu, et al. Dynamic fuzzy clustering method based on genetic algorithm[J].Journal of Beijing University of Posts and Telecommunications, 2005, 28(1): 75–78. |