﻿ 基于鲸鱼群优化算法的带Sigmoid满意度应急车辆调度问题
 计算机系统应用  2018, Vol. 27 Issue (8): 180-186 PDF

Scheduling Problem with Sigmoid Satisfaction Emergency Vehicle Based on Whale Swarm Algorithm
FAN Xiang, YE Chun-Ming, CAO Lei
Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
Foundation item: National Natural Science Foundation of China (71271138); Project for First-class Discipline Construction of Shanghai (S1201YLXK); High-land Project of Shanghai (GYXK1201); Science and Technology Development Project of University of Shanghai for Science and Technology (16KJFZ028)
Abstract: Considering the different levels of large-scale urgent disaster, Sigmoid time satisfaction function is proposed to evaluate the rescue effect. It builds the shortest rescue path and maximum satisfaction of average time vehicle scheduling model. Chaotic Whale Swarm Algorithm is designed based on Chaos sequence search operator. the improved algorithm is applied to optimize three groups of experimental cases of different sizes, and the results are compared with those of the simulated annealing algorithm and original Whale Swarm Algorithm. Results show that there is little difference in performance when the handling smaller scale of vehicle scheduling, while the improved algorithm gain more advantage over the simulated annealing algorithm and original algorithm as the handling scale getting larger. Chaotic Whale Swarm Algorithm is effective method to deal with emergency vehicle scheduling problem.
Key words: emergency management     vehicle scheduling     Whale Swarm algorithm     time satisfaction

1 应急情景描述与数学模型 1.1 情景描述

 $C(t) = \left\{ \begin{gathered} 1{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} t \leqslant EL \hfill \\ \frac{{2{e^{ - \beta (t - EL)}}}}{{1 + {e^{ - \beta (t - EL)}}}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} t > EL \hfill \\ \end{gathered} \right.$ (1)

1.2 模型建立

 图 1 Sigmoid时间满意度函数示意图

 $\max \;\;\;{z_1} = \frac{{\sum\limits_{i = 1}^N {C({t_i})} }}{N}$ (2)
 $\min \;\;\;{z_2} = \sum\limits_{i = 0}^N {\sum\limits_{i = 0}^N {\sum\limits_{k = 1}^M {{d_{ij}}{x_{ijk}}} } }$ (3)

s.t.

 $\sum\limits_{k = 1}^M {{y_{ik}}} = 1,\;\;i = 1,2, \cdots ,N$ (4)
 $\sum\limits_{j = 0,i \ne j}^N {{x_{ijk}}} = {y_{ik}},\;\;i = 0,1,2, \cdots ,N,k = 1,2, \cdots ,M$ (5)
 $\sum\limits_{i = 0,i \ne j}^N {{x_{ijk}}} = {y_{jk}},\;\;j = 1,2, \cdots ,N,k = 1,2, \cdots ,M$ (6)
 ${s_j} = {s_i} + {t_i} + {t_{ij}},\;\;i,j = 0,1, \cdots N,i \ne j$ (7)
 $\begin{split}& {x_{ijk}}({x_{ijk}} - 1) = 0,\;\; i = 0,1, \cdots ,N, \\& j = 1,2, \cdots ,N,k = 1,2, \cdots ,M \end{split}$ (8)
 ${x_{ik}}({x_{ik}} - 1) = 0,\;\; i = 1, \cdots ,N,k = 1,2, \cdots ,M$ (9)
 ${s_0} = 0,$ (10)
 ${C_{}}({s_i}) = \left\{ \begin{gathered} 1\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \;{s_i}_{}\; \leqslant E{L_{}} \hfill \\ \frac{{2{e^{ - {\beta _i}({s_i} - E{L_{}})}}}}{{1 + {e^{^{ - {\beta _i}({s_i} - EL)}}}}}\;\;\;\;{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \;{s_i}_{}\; > E{L_{}}\; \hfill \\ \end{gathered} \right.\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ (11)

2 基于鲸鱼群算法的应急调度算法 2.1 标准鲸鱼群算法

 $\rho = {\rho _0} \cdot {e^{ - \eta \cdot d}}$ (12)

 $x_i^{t + 1} = x_i^t + rand(0,{\rho _0} \cdot {e^{ - \eta \cdot {d_{x,y}}}}) * \left( {y_i^t - x_i^t} \right)$ (13)

 图 2 鲸鱼群算法流程

2.2 混沌鲸鱼群优化算法 2.2.1 算法原理

 ${L_{n{\rm{ + 1}},d}} = 1 - 2{L^2}_{n,d},\;\;n = 1,2, \cdots ,\infty ;{L_{n,d}} \in ( - 1,1)$ (14)

 ${L_{id}} = 2 \times \frac{{{y_{id}} - {a_{id}}}}{{{b_{id}} - {a_{id}}}} - 1,d = 1,2, \cdots D$ (15)
 $x{'_{id}} = \frac{1}{2} \times ({b_{id}} - {a_{id}}) \times {L_{id}} + \frac{1}{2} \times ({b_{id}} + {a_{id}}),d = 1,2, \cdots D$ (16)

 ${x_{\min ,j}} = \max \{ {x_{\min ,j}},{x_{g,j}} - \varphi \times ({x_{\max ,j}} - {x_{\min ,j}})\}$
 ${x_{\max ,j}} = \min \{ {x_{\max ,j}},{x_{g,j}} + \varphi \times ({x_{\max ,j}} - {x_{\min ,j}})\}$ (17)

 $\varphi \left( t \right) = 1 - \frac{1}{{1 + \exp (4 - 0.04t)}}$ (18)
2.2.2 基于问题的鲸鱼编码与译码

 图 3 鲸鱼群算法编码及解码过程

2.3 适应度值计算

 $fitness{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} z = \lambda \cdot \frac{1}{{{z_2} + \varepsilon }} + (1 - \lambda ) \cdot \frac{1}{{{z_2} + \varepsilon }} \cdot {z_1}$ (19)

2.4 算法步骤

Step 1. 初始化算法基本参数: 设置鲸鱼数目Q, 衰减系数 $\eta$ , 精英群体比例 $n\%$ , 混沌搜索迭代次数H, 最大搜索次数Iter_MAX或搜索精度.

Step 2. 在搜索区域内随机初始化鲸鱼的空间位置, 根据所处位置计算鲸鱼的目标函数值, 将其作为各自的最大超声波强度 ${\rho _0}$ .

Step 3. 根据式(12)计算群体中鲸鱼的相对超声波 $\rho$ , 根据式(13)更新鲸鱼的空间位置.

Step 4. 对鲸鱼个体进行评估, 选取性能最好的 $n\%$ 的个体作为精英, 采用混沌优化策略进行优化; 选取性能最差的 $n\%$ 的个体, 重新随机产生新的鲸鱼个体予以替代.

Step 5. 根据式(17)动态收缩搜索区域.

Step 6. 根据移动后的鲸鱼位置, 重新计算各鲸鱼的最大超声波强度.

Step 7. 当满足最大搜索次数或达到搜索精度时, 转至Step 8, 否则转Step 3, 进行下一次搜索.

Step 8. 输出全局最优个体与全局极值点, 算法结束.

3 实验仿真及分析

3.1 算例设计

3.2 实验结果及分析

 图 4 CWSA救援车辆最优行驶路径

 图 5 SA救援车辆最优行驶路径

 图 6 WSA救援车辆最优行驶路径

 图 7 迭代对比(8×3)

 图 8 迭代对比(14×4)

 图 9 迭代对比(25×5)

4 结束语

 [1] 喻德旷, 杨谊. 多受灾点应急救援车辆调度的优化遗传算法. 计算机系统应用, 2016, 25(11): 201-207. [2] 陈森, 姜江, 陈英武, 等. 未定路网结构情况下应急物资车辆配送问题模型与应用. 系统工程理论与实践, 2011, 31(5): 907-913. DOI:10.12011/1000-6788(2011)5-907 [3] 王旭坪, 马超, 阮俊虎. 运力受限的应急物资动态调度模型及算法. 系统工程理论与实践, 2013, 33(6): 1492-1500. DOI:10.12011/1000-6788(2013)6-1492 [4] Qin J, Ye Y, Cheng BR, et al. The emergency vehicle routing problem with uncertain demand under sustainability environments. Sustainability, 2017, 9(2): 288. DOI:10.3390/su9020288 [5] 王付宇, 王涛, 叶春明. 基于萤火虫算法的应急救援车辆调度. 计算机系统应用, 2017, 26(9): 188-194. DOI:10.15888/j.cnki.csa.005975 [6] Zeng B, Gao L, Li XY. Whale swarm algorithm for function optimization. International Conference on Intelligent Computing. Springer, Cham. 2017. 624–639. [7] Fiedrich F, Gehbauer F, Rickers U. Optimized resource allocation for emergency response after earthquake disasters. Safety Science, 2000, 35(1-3): 41-57. DOI:10.1016/S0925-7535(00)00021-7 [8] 曹磊, 叶春明. 杂草-蚁群算法在应急管理中的应用. 微电子学与计算机, 2016, 33(9): 150-154. [9] Yu V F, Redi AANP, Hidayat YA, et al. A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing, 2017, 53: 119-132. DOI:10.1016/j.asoc.2016.12.027 [10] 穆东, 王超, 王胜春, 等. 基于并行模拟退火算法求解时间依赖型车辆路径问题. 计算机集成制造系统, 2015, 21(6): 1626-1636.