一种求解有时间窗的车辆路径问题的优化算法

摘要

本发明公开了一种求解有时间窗的车辆路径问题的优化算法，所述求解有时间窗的车辆路径问题的优化算法将现代启发式算法中的遗传算法和人工蜂群算法有机融合起来并加以改进，开发出一种改进的人工蜂群算法用于求解VRPTW问题。

主权项

一种求解有时间窗的车辆路径问题的优化算法，所述求解有时间窗的车辆路径问题的优化算法是对油料保障VRPTW实例进行求解，所述油料保障VRPTW具体模型如下：minf(x)＝{Σ_iΣ_jΣ_kv_i，jx_i，j，Σ_jΣ_kx_0，j，k} i，j∈Z，k∈K    (1)约束条件公式为：Σ_i，j∈ZΣ_k∈Kx_i，j，k＝1    (2)${\Sigma }_{i=1}^Z{q}_i\le Q---\left(3\right)$${\Sigma }_{i=1}^Z{x}_{0,i,k}=1---\left(4\right)$Σ_i，m∈ZΣ_k∈Kx_i，m，k＝Σ_m，j∈ZΣ_k∈Kx_m，j，k    (5)${\Sigma }_{j=1}^Z{x}_{j,0,k}=1---\left(6\right)$Et_i≤Se_i≤Lt_i    (7)Et_i≤Sl_i≤Lt_i    (8)Et_j，k≤Sl_i，k+t_i，j，k+t₀≤Lt_j，k    (9)Et_j，k≤Sl_j，k≤Lt_j，k    (10)$\frac{L_k}{100}\times 23\le Q_k---\left(11\right)$x_i，j，k∈{0，1}；y_i，k∈{0，1} i，j∈Z，k∈K  (12)，上述各公式中符号的具体含义如下：其特征在于，所述油料保障VRPTW的求解步骤包括：(1)设定算法参数：种群大小coloneysize，工作蜂数量Ef(Employed)，跟随蜂数量Ff(Follower)、局部最大搜索次数limit、全局最大迭代次数Maxcycles、每次程序运行次数runtime、需加油的坦克数量tank‑number、最多能使用的加油车数量vehicle‑number、最少使用数量Min_Use_Vehicle_Num、加油车最大载重量max_load、车速speed和交叉概率cross_rate，后方油库(车场)数量1和单车使用成本140为定值；(2)初始化种群，随机排列客户序列后插入加油车，生成coloneysize/2个初始解x_i,j(i＝1,2,3，...，M；j＝1,2,3,...,N)，将其暂记为A，计算各初始解的fit(x_n)值；(3)设置全局迭代次数cycle＝1；(4)设置局部搜索次数limit＝1；(5)将A进行“动态交叉”操作，增加其种群多样性，生成新的种群B；(6)工作蜂采用改进后的动态邻域搜索策略勘探种群B的邻域，存优汰劣，得到新解v_n,j种群，将其暂记为C，计算C的fit(x_n)值；(7)若解未得到优化，令limit＝limit+1，搜索继续；若解得到更新，则重置limit后继续进行邻域搜索；(8)跟随蜂根据改进后的强制保留精英锦标赛策略和“排序法”跟随策略，对C进行跟随开采，同样存优汰劣；(9)若解未得到优化，令limit＝limit+1，搜索继续；若解得到更新，则重置limit后继续进行邻域搜索；(10)第(7)步和第(9)步中的limit达到最大限制次数后，工作蜂抛弃局部最优解转换为侦察蜂，根据设定的公式再次随机产生新解或根据改进后的初始解策略生成新解，此时完成一次全局迭代，新解产生后重复第(5)步至第(9)步；(11)记录当前已知最优解，令cycle＝cycle+1；(12)判断全局搜索迭代次数cycle，如cycle＜Maxcycles，则算法继续搜索；如cycle＞Maxcycles，算法终止迭代，记录当前最小值，minf(x)越小，意味着算法求解效果越好。