2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题

胡蓉 李洋 钱斌 金怀平 向凤红

胡蓉, 李洋, 钱斌, 金怀平, 向凤红. 结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题. 自动化学报, 2020, 46(x): 1−18. doi: 10.16383/j.aas.c190872
引用本文: 胡蓉, 李洋, 钱斌, 金怀平, 向凤红. 结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题. 自动化学报, 2020, 46(x): 1−18. doi: 10.16383/j.aas.c190872
HU Rong, LI Yang, QIAN Bin, JIN Huai-Ping, XIANG Feng-Hong. An enhanced ant colony algorithm combined with clustering decomposition for solving complex green vehicle routing problem. Acta Automatica Sinica, 2020, 46(x): 1−18. doi: 10.16383/j.aas.c190872
Citation: HU Rong, LI Yang, QIAN Bin, JIN Huai-Ping, XIANG Feng-Hong. An enhanced ant colony algorithm combined with clustering decomposition for solving complex green vehicle routing problem. Acta Automatica Sinica, 2020, 46(x): 1−18. doi: 10.16383/j.aas.c190872

结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题


DOI: 10.16383/j.aas.c190872
详细信息
    作者简介:

    昆明理工大学信息工程与自动化学院副教授, 2004年获得清华大学自动化系硕士学位, 主要研究方向为调度理论与方法, 智能计算, 决策支持系统. E-mail: ronghu@vip.163.com

    昆明理工大学信息工程与自动化学院硕士研究生, 2009年获得昆明理工大学电力工程学院学士学位. 主要研究方向为调度理论与智能优化算法. E-mail: Yang.L.Liam@hotmail.com

    昆明理工大学信息工程与自动化学院副教授, 2009年获得清华大学自动化系博士学位, 主要研究方向为调度理论与方法, 以及智能优化. E-mail: bin.qian@vip.163.com

    昆明理工大学信息工程与自动化学院副教授, 2016年获得北京理工大学博士学位, 主要研究方向为智能计算和软测量方法

    昆明理工大学信息工程与自动化学院教授, 2002年获得昆明理工大学博士学位, 主要研究方向为智能优化与控制

    通讯作者: 昆明理工大学信息工程与自动化学院副教授, 2009年获得清华大学自动化系博士学位, 主要研究方向为调度理论与方法, 以及智能优化. E-mail: bin.qian@vip.163.com
  • 基金项目:  国家自然科学基金项目(61963022, 51665025); 云南省应用基础研究计划重点项目资助
  • 中图分类号: TP399

An enhanced ant colony algorithm combined with clustering decomposition for solving complex green vehicle routing problem

More Information
    Corresponding author: QIAN Bin Professor at the School of Information Engineering and Automation, Kunming University of Science and Technology. He received his Ph.D. degree from Tsinghua University in 2009. His research interests include scheduling theory and method, and intelligent optimization. Corresponding author of this paper
  • Fund Project:  Supported by National Natural Science Foundation of China (61963022,51665025) and Applied Basic Research Key Project of Yunnan Province
  • 摘要: 本文针对带时间窗的低能耗多车场多车型车辆路径问题(low-energy-consumption multi-depot heterogeneous-fleet vehicle routing problem with time windows, LMHFVPR_TW), 提出一种结合聚类分解策略的增强蚁群算法(enhanced ant colony algorithm based on clustering decomposition, EACO_CD)进行求解. 首先, 由于该问题具有强约束、大规模和NP-Hard等复杂性, 为有效控制问题的求解规模并合理引导算法在优质解区域搜索, 根据问题特点设计两种基于K-means的聚类策略, 将LMHFVPR_TW合理分解为一系列带时间窗的低能耗单车场单车型车辆路径子问题(low-energy-consumption vehicle routing problem with time windows, LVRP_TW); 其次, 本文提出一种增强蚁群算法(enhanced ant colony optimization, EACO)求解分解后的各子问题(LVRP_TW), 进而获得原问题的解. EACO不仅引入信息素挥发系数控制因子进一步动态调节信息素挥发系数, 从而有效控制信息素的挥发以提高算法的全局搜索能力, 而且设计基于4种变邻域操作的两阶段变邻域局部搜索(two-stage variable neighborhood search, TVNS)来增强算法的局部搜索能力. 最后, 在不同规模问题上的仿真和对比实验验证了所提EACO_CD的有效性.
  • 图  1  EACO_CD(EACO_IBKA_HKMA)结构

    Fig.  1  Framework of EACO_CD

    图  2  4类客户平衡移动示意图

    Fig.  2  Diagram of balanced movement for four customer groups

    图  3  三车场K-means未平衡聚类与平衡聚类比较

    Fig.  3  The comparison of unbalanced K-means cluster and balanced K-means cluster of three depots

    图  4  HKMA工作机制

    Fig.  4  The HKMA’s running mechanism

    图  5  HKMA三维聚类效果

    Fig.  5  The 3D clustering results of HKMA

    图  6  HKMA二维结果

    Fig.  6  The 2D results of HKMA

    图  7  局部搜索策略

    Fig.  7  Local search strategy

    表  1  符号及定义

    Table  1  Symbols and definitions

    符号 释义 符号 释义
    $F_1$ 运输距离费用 $H_{PM}$ 表示车场 $Ρ$ $H_{PM}$ $M$ 类型的车
    $F_2$ 车辆固定成本 $r(A)$ 完成客户子集 $A$ 中所有客户的配送需要的最少车辆数
    $F_3$ 燃油消耗费用 $N$ 总共有 $N$ 个客户
    $F_4$ 时间窗惩罚费用 $V$ $V$ 表示客户编号集合{0,1,2,···, $N$ }(0表示车场)
    $C_{M1}$ $M$ 类型车的距离费用系数 $M_t$ 表示共有 $M_t$ 种类型的车
    $C_{M2}$ $M$ 种类型车的固定发车费用系数 $x_{PMijk}$ 表示车场 $P$ 车型 $M$ 的第 $k$ 辆车从客户 $i$ 到客户 $j$ 的决策变量
    $C_{M3}$ $M$ 种类型车的燃油费用系数 $k$ 表示辆车编号 $k$
    $C_1$ 配送车辆提前到达的单位惩罚费用 $d_{ij}$ $d_{ij}$ 表示客户 $i$ 到客户 $j$ 的距离
    $C_2$ 配送车辆迟到的单位惩罚费用 ${ET}_i$ 客户 $i$ 要求的最早到达时间
    $i$ 表示客户点 $i$ ${LT}_i$ 客户 $i$ 要求的最晚到达时间
    $j$ 表示客户点 $j$ $S_i$ 客户 $i$ 要求的卸货时间
    $P_s$ 表示全部车场集合{1,2,···, $P_t$ } $q_i$ 客户i要求的货物需求量
    $P_t$ 表示总共有 $P_t$ 个车场 $t_i$ 车辆到达客户 $i$ 的时间
    $P$ 表示车场编号 $P$ $Q_M$ $M$ 种车型的最大载重量
    $M_s$ 表示全部车型集合 $\{1,2,\cdots,\ M_t\}$ $M$ 表示车型编号 $M$
    $H_{PMS}$ 表示车场 $P$ 中车型 $M$ 的全部车辆集合 $\{1,2,\cdots,\ H_{PM}\}$ ${FU}_{Mij}$ 车型为 $M$ 的车辆从客户 $i$ 到客户 $j$ 之间的耗油量
    备注: 综合燃油消耗模型中的其他相关参数设定参考文[25]
    下载: 导出CSV

    表  2  目标函数中的相关系数

    Table  2  Coefficients in the object function

    符号 数值
    $C_{M1}$ 1.5元/kM
    $C_{M2}$ 300-800元/辆
    $C_{M3}$ 7.6元/L
    $C_{1}$ 15元/H
    $C_{2}$ 20元/H
    下载: 导出CSV

    表  3  主要参数与水平

    Table  3  Main parameters and level

    主要参数 水平设置
    1 2 3 4
    $\alpha$ 1.25 1.5 1.75 2.0
    $\beta$ 10 1.5 2.0 2.5
    $P_m$ 1.1 1.2 1.3 1.4
    $W$ 500 1000 1500 2000
    下载: 导出CSV

    表  4  参数设置的正交表

    Table  4  Orthogonal table of parameter settings

    组合编号 水平设置 AVR(元)
    $\alpha$ $\beta$ $P_m$ $W$
    1 1 1 1 1 9677
    2 1 2 2 2 9625
    3 1 3 3 3 9613
    4 1 4 4 4 9541
    5 2 1 2 3 9745
    6 2 2 1 4 9624
    7 2 3 4 1 9602
    8 2 4 3 2 9593
    9 3 1 3 4 9836
    10 3 2 4 3 9703
    11 3 3 1 2 9654
    12 3 4 2 1 9612
    13 4 1 4 2 9865
    14 4 2 3 1 9689
    15 4 3 2 4 9656
    16 4 4 1 3 9672
    下载: 导出CSV

    表  5  各参数不同水平下的平均响应值和影响力

    Table  5  Average response values and influences table at different levels of each parameter

    水平 水平设置
    $\alpha$ $\beta$ $P_m$ $W$
    1 9614 9780 9656 9645
    2 9641 9660 9659 9684
    3 9701 9631 9683 9683
    4 9720 9604 9677 9664
    极差 106 176 27 39
    影响力排名 2 1 4 3
    下载: 导出CSV

    表  7  EACO_IBKA与其他算法对比结果

    Table  7  Comparison results of EACO_IBKA with other algorithms

    N_Pt EACO_IBKA EACO_KM EACO_NNA EACO1 DHACO ${{T}}({{s}})$
    best average best average best average best average best average
    96_2 17483 18155 18037 18379 16768 17675 15371 17009 16011 17559 19
    192_2 27522 28546 28457 29482 28758 29560 28379 29838 28524 30863 38
    288_2 39217 41028 40412 42363 41179 42142 41283 43164 42606 43930 58
    360_2 53748 56268 54672 57402 55251 57847 56276 58653 56965 59409 72
    96_3 16638 17278 17066 17491 15957 16821 14627 16582 15236 17186 29
    192_3 26199 27175 27090 28066 27376 28140 27016 28405 27153 29381 58
    288_3 37337 39062 38476 40333 39205 41123 39305 41096 40565 41826 86
    360_3 51176 53576 52056 54656 52608 55080 53584 55848 54240 56568 108
    96_4 16062 16943 16810 17146 15871 16425 16012 16907 16391 16991 38
    192_4 25690 26612 26528 27235 26846 27620 26443 27896 26623 28850 77
    288_4 36519 38266 37624 39493 38365 39338 38442 40278 39692 40974 115
    360_4 50480 52904 51344 53960 51904 54392 52088 55184 53584 55904 144
    平均值 33173 34651 34048 35501 34174 35514 34069 35905 34799 36620 /
    下载: 导出CSV

    表  8  HKMA与其他划分算法的对比结果

    Table  8  Comparison results of HKMA and the other dividing algorithms

    $ {{N}}\_ {{M}}_{{t}}$ EACO_ HKMA EACO_ RDA EACO_ RAA EACO_KEW EACO2 TSA_RDA $ {{T}}({{s}})$
    best average best average best average best average best average best average
    96_2 16299 16759 17570 19461 16238 17661 16754 17704 16543 17838 17746 19656 29
    192_2 24847 25998 25983 26905 26000 27201 26039 26918 26520 27745 26243 27174 57
    288_2 32225 33356 33783 34713 32740 35242 32540 35156 34050 36652 34121 35060 87
    360_2 48344 50050 50695 52088 49129 52874 48828 52743 51094 54989 51202 52609 108
    96_3 15777 15929 16704 18494 16011 16792 15932 16839 16171 16960 16871 18679 44
    192_3 23624 24718 24704 25570 24714 25850 24748 25588 25455 26626 24951 25826 87
    288_3 30621 31700 32106 32984 31111 33493 30929 33414 32667 35168 32427 33314 129
    360_3 45933 47554 48172 49502 46691 50237 47401 50118 49026 52749 48654 49997 162
    96_4 14214 14349 15047 16655 14422 15118 14346 15171 14566 15269 15197 16822 57
    192_4 21273 22251 22237 23018 22257 23268 22282 23034 22925 23966 22459 23248 116
    288_4 27563 28542 28902 29689 28012 30149 27842 30088 29413 31656 29191 29986 173
    360_4 41350 42809 43360 44558 42028 45218 41776 43111 44129 47479 43794 45004 216
    平均值 28506 29501 29939 31136 29113 31092 29118 30824 30213 32258 30238 31448 /
    下载: 导出CSV

    表  9  EACO_CD性能验证

    Table  9  EACO_ CD’s performance verification

    $ {{N}}$ _ ${{ P}}_{{t}}$ _ $ {{M}}_{{t}}$ EACO_CD (EACO_IBKA_HKMA) IACO_CD (IACO_NNA_SWA) IHGA ${{T}}({{s}})$
    best average worst SD best average worst SD best average worst SD
    96_2_2 16370 16526 16904 295 17800 18071 18381 272 15852 16011 16376 285 31
    192_2_2 23664 24760 25650 556 26040 27250 28218 576 24863 26010 26948 590 71
    288_2_2 30690 31768 32227 724 33772 34962 35457 803 35311 36550 37076 824 123
    360_2_2 39903 41303 41906 951 43907 45448 46111 1059 45507 46098 47781 1197 162
    96_3_2 16883 17869 18993 358 18568 20115 20999 343 16800 18283 19011 363 48
    192_3_2 24257 25492 26408 668 26692 28059 29065 671 26688 28052 29053 746 109
    288_3_2 30258 31572 32860 907 34814 36319 37797 1017 35414 36956 38450 1092 183
    360_3_2 39347 41061 42734 1141 43291 45187 47020 1263 47228 49291 51297 1389 243
    96_3_3 15867 17082 17860 388 17470 18911 19664 368 16514 17874 18584 478 62
    192_3_3 22816 23977 24832 631 25108 26383 27320 708 26242 27588 28567 743 145
    288_3_3 28458 29693 30892 828 32742 34157 35530 957 35582 37120 38622 1048 245
    360_3_3 37006 38610 40166 1079 40722 42474 44186 1198 47081 49427 51523 1399 288
    平均值 27127 28309 29286 711 30077 31445 32479 770 31090 32438 33607 846 /
    下载: 导出CSV

    表  6  4种不同车型相关参数设置

    Table  6  Related parameter settings for four different vehicle types

    车型列表 车型参数
    载重量(kg) 空车重量(kg) 平均速度(km/h) 固定费用(元) 最大承货物载数(件)
    Type 1 200 1600 60-80 300-400 20
    Type 2 500 2700 50-70 400-500 30
    Type 3 600 3500 40-60 500-600 40
    Type 4 800 5000 30-50 600-800 50
    下载: 导出CSV
  • [1] Dantzig G B, Ramser J H. The truck dispatching problem. Management Science, 1959, 1(6): 80−81
    [2] Anbuudayasankar S P, Ganesh K, Mohapatra S. Models for Practical Routing Problems in Logistics. Springer Press, 2014.
    [3] Li H Q, Yuan J L, LV T, et al. The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems considering carbon dioxide emissions. Transportation Research Part D, 2016, (49): 231−245
    [4] Zhao Y W, Zhang J L, Wang W L. Vehicle Routing Optimization Method for Logistics Distribution. Beijing: Science Press, 2014.
    [5] Sbihi A, Eglese R. Combinatorial optimization and green logistics. 4OR: A Quarterly Journal of Operations Research, 2007, 2(5): 97−116
    [6] Chen D S, Batson R, Dang Y. Applied integer Programming. New York: Wiley Press, 2010.
    [7] Jabir E, Panicker V V, Sridharan R. Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem. Transportation Research Part D: Transport and Environment, 2017, 57: 422−457 doi:  10.1016/j.trd.2017.09.003
    [8] Kaabachi I, Jriji D, Krichen S. An Improved Ant Colony Optimization for Green MultiDepot Vehicle Routing Problem with Time Windows. IEEE, 2017.
    [9] Xiao Y, Konak A. The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion. Transportation Research Part E: Logistics and Transportation Review, 2016, 88: 146−166 doi:  10.1016/j.tre.2016.01.011
    [10] Kwon Y J, Choi Y J, Lee D H. Heterogeneous fixed fleet vehicle routing considering carbon emission. Transportation Research Part D, 2013, 23: 81−89 doi:  10.1016/j.trd.2013.04.001
    [11] Geetha S. Metaheuristic approach for the multi-depot vehicle routing problem. Applied Artificial Intelligence: An International Journal, 2012, 26: 878−901 doi:  10.1080/08839514.2012.727344
    [12] Geetha S, Poonthalir G, Vanathi P T. Nested particle swarm optimization for multi-depot vehicle routing problem. Operational Research, 2013, 16(3): 112−128
    [13] Ho W, Ho G T S, Ji P, et al. A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, 2008, 21: 548−557 doi:  10.1016/j.engappai.2007.06.001
    [14] Wang Y, Kevin Assogba, Liu Y. Two-echelon location-routing optimization with time windows based on customer clustering. Expert System with Application, 2018, 104: 244−260 doi:  10.1016/j.eswa.2018.03.018
    [15] Dondo R, Cerdá J. A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. European Journal of Operational Research, 2007, 176: 1478−1507 doi:  10.1016/j.ejor.2004.07.077
    [16] Tang Y L, Cai Y G, Yang Q J. Improved ant colony optimization for multi-depot heterogeneous vehicle routing problem with soft time windows. Journal of Southeast University (English Edition), 2015, 31(1): 94−99
    [17] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society, 1996, 26(1): 29
    [18] 王素欣, 高利, 催小光, 曹宏美. 多需求点车辆调度模型及其群体智能混合求解. 自动化学报, 2008, 34: 102−104

    Wang Su Xin, GAO Li, CUI Xiao Guang, CAO Hong Mei. Study on multi-requirement points vehicle scheduling model and its swarm mix algorithm. ACTA AUTOMATICA SINICA, 2008, 34: 102−104
    [19] Lee C Y, Lee Z J, Lin S W, et al. An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem. Applied Intelligence, 2010, 32(1): 88−95 doi:  10.1007/s10489-008-0136-9
    [20] Yu B, Yang Z Z. An ant colony optimization model: The period vehicle routing problem with time windows. Transportation Research Part E, 2011, 47(2): 166−181 doi:  10.1016/j.tre.2010.09.010
    [21] Ding Q L, Hu X P, Sun L J, et al. An improved ant colony optimization and its application to vehicle routing problem with time windows. Neurocomputing, 2012, 98: 101−107 doi:  10.1016/j.neucom.2011.09.040
    [22] Yan F L. Autonomous vehicle routing problem solution based on artificial potential field with parallel ant colony optimization (ACO) algorithm. Pattern Recognition Letters, 2018, 116: 195−199 doi:  10.1016/j.patrec.2018.10.015
    [23] 陈希琼, 胡大伟, 杨倩倩, 等. 多目标同时取送货车辆路径问题的改进蚁群算法. 控制理论与应用, 2018, 35(09): 1347−1356

    X Chen, D Hu, Q Yang, et al. An improved ant colony algorithm for multi-objective vehicle routing problem with simultaneous pickup and delivery. Control Theory & Applications, 2018, 35(09): 1347−1356
    [24] Xu H T, Pu P, Duan F. Dynamic vehicle routing problems with enhanced ant colony optimization. Discrete Dynamics in Nature and Society, 2018: 1−13
    [25] Demir E, Bektas T, Laporte G. An adaptive large neighborhood search heuristic for the pollution-routing problem. European Journal of Operational Research, 2012, 223: 346−359 doi:  10.1016/j.ejor.2012.06.044
    [26] Bektas T, Gouveia L. Gouveia Requiem for the Miller-Tucker-Zemlin subtour elimination constraints. European Journal of Operational Research, 2014, 236: 820−832 doi:  10.1016/j.ejor.2013.07.038
    [27] Toth P, Vigo D. The Vehicle Routing Problem. Beijing: Tsinghua University Press, 2012.
    [28] Wolsey L A. Integer Programmin. New York: Wiley Press, 1998.
    [29] Schneider M, Stenger A, Goeke D. The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 2014: 1−21
    [30] Gu S S. A polynomial time solvable algorithm to linearly constrained binary quadratic programming problems with Q being a tri-diagonal matrix. Advances in Information Sciences and Service Sciences, 2011, 3(6): 65−72 doi:  10.4156/aiss.vol3.issue6.8
    [31] Meng X, Li J, Zhou M C, et al. Population-based incremental learning algorithm for a serial colored traveling salesman problem. IEEE Transactions on Systems Man & Cybernetics: Systems, 2018, 48(2): 277−288
    [32] Wang Y, Ma X L, Lao Y T, et al. A fuzzy-based customer clustering approach with hierarchical structure for logistics network optimization. Expert Systems with Applications, 2013, (07): 78−91
    [33] Wang Y, Zhang J, Kevin Assogba, et al. Collaboration and transportation resource sharing in multiple centers vehicle routing optimization with delivery and pickup. Knowledge-Based Systems, 2018, 160: 296−310 doi:  10.1016/j.knosys.2018.07.024
    [34] Wang B D, Miao Y W, Zhao H Y, et al. A biclustering-based method for market segmentation using customer pain points. Engineering Applications of Artificial Intelligence, 2015, 06: 5−14
    [35] Ji J C, Pang W, Zhou C G, et al. A fuzzy k-prototype clustering algorithm for mixed numeric and categorical data. Knowledge-Based Systems, 2012, 30: 129−135 doi:  10.1016/j.knosys.2012.01.006
    [36] Yong Wang, Xiaolei Ma, Mingwu Liu, et al. Cooperation and profit allocation in two-echelon logistics joint distribution network optimization. Applied Soft Computing, 2017, 02: 25−67
    [37] He R, Xu W, Sun J, et al. Balanced K-Means Algorithm for Partitioning Areas in Large-Scale Vehicle Routing Problem. IEEE, 2009.
    [38] 王东风, 孟丽. 粒子群优化算法的性能分析和参数选择. 自动化学报, 2016, 10: 1552−1561

    Wang D F, Li Meng. Performance analysis and parameter selection of PSO algorithms. ACTA AUTOMATICA SINICA, 2016, 10: 1552−1561
    [39] Beasley J E. Route first—Cluster second methods for vehicle routing. OMEGA, 1983, 11(4): 403−408 doi:  10.1016/0305-0483(83)90033-6
    [40] E G B, Miller Leland R. A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 1974, 22(2): 340−349 doi:  10.1287/opre.22.2.340
    [41] Yua B, Yao B. An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research, 2009, 196: 171−176 doi:  10.1016/j.ejor.2008.02.028
    [42] Mladenovic M, Hansen P. Variable neighborhood search. Computers and Operations Research, 1997, 24: 1097−1100 doi:  10.1016/S0305-0548(97)00031-2
    [43] 李进, 傅培华. 具有固定车辆数的多车型低碳路径问题及算法. 计算机集成制造系统, 2013, 06: 1351−1362

    Li J, Fu P. Heterogeneous fixed fleet low-carbon routing problem and algorithm. Computer integrated manufacturing systems, 2013, 06: 1351−1362
  • [1] 唐昊, 裴荣, 周雷, 谭琦. 基于状态聚类的多站点CSPS系统的协同控制方法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2014.00901
    [2] 王大志, 刘士新, 郭希旺. 求解总拖期时间最小化流水车间调度问题的多智能体进化算法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2014.00548
    [3] 王利, 高宪文, 王伟, 王琦. 基于模型的子空间聚类与时间段蚁群算法的合同生产批量调度方法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2014.01991
    [4] 杨培颖, 唐加福, 于洋, 裴金翔. 面向最小碳排放量的接送机场服务的车辆路径与调度[J]. 自动化学报, doi: 10.3724/SP.J.1004.2013.00424
    [5] 周林, 平西建, 徐森, 张涛. 基于谱聚类的聚类集成算法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2012.01335
    [6] 王骏, 钟富礼, 王士同, 邓赵红. 基于移相加权球面单簇聚类的周期时间序列异常检测[J]. 自动化学报, doi: 10.3724/SP.J.1004.2011.00984
    [7] 黄旭, 吕强, 钱培德. 一种用于蛋白质结构聚类的聚类中心选择算法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2011.00682
    [8] 吴聪, 李勃, 董蓉, 陈启美. 基于车型聚类的交通流参数视频检测[J]. 自动化学报, doi: 10.3724/SP.J.1004.2011.00569
    [9] 钱鹏江, 王士同, 邓赵红. 基于稀疏Parzen窗密度估计的快速自适应相似度聚类方法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2011.00179
    [10] 康一梅, 李志军, 胡江, 董吉昌. 一种低能耗层次型无线传感器网络拓扑控制算法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2010.00543
    [11] 白保存, 陈英武, 贺仁杰, 李菊芳. 基于分解优化的多星合成观测调度算法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2009.00596
    [12] 徐森, 卢志茂, 顾国昌. 解决文本聚类集成问题的两个谱算法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2009.00997
    [13] 田志波, 唐立新, 任一鸣, 赵永明, 邬成新. 基于合成邻域的蚁群算法求解无委托板坯匹配问题[J]. 自动化学报, doi: 10.3724/SP.J.1004.2009.00186
    [14] 潘天红, 薛振框, 李少远. 基于减法聚类的多模型在线辨识算法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2009.00220
    [15] 熊伟清, 魏平. 二进制蚁群进化算法[J]. 自动化学报, doi: 10.1360/aas-007-0259
    [16] 柯良军, 冯祖仁, 冯远静. 有限级信息素蚁群算法[J]. 自动化学报
    [17] 闫德勤, 迟忠先, 王军. MLVQ网络聚类算法[J]. 自动化学报
    [18] 闻育, 吴铁军. 求解复杂多阶段决策问题的动态窗口蚁群优化算法[J]. 自动化学报
    [19] 汪镭, 吴启迪. 蚁群算法在系统辨识中的应用[J]. 自动化学报
    [20] 李艳君, 吴铁军. 求解混杂生产调度问题的嵌套混合蚁群算法[J]. 自动化学报
  • 加载中
计量
  • 文章访问数:  23
  • HTML全文浏览量:  3
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-12-22
  • 录用日期:  2020-05-03

结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题

doi: 10.16383/j.aas.c190872
    基金项目:  国家自然科学基金项目(61963022, 51665025); 云南省应用基础研究计划重点项目资助
    作者简介:

    昆明理工大学信息工程与自动化学院副教授, 2004年获得清华大学自动化系硕士学位, 主要研究方向为调度理论与方法, 智能计算, 决策支持系统. E-mail: ronghu@vip.163.com

    昆明理工大学信息工程与自动化学院硕士研究生, 2009年获得昆明理工大学电力工程学院学士学位. 主要研究方向为调度理论与智能优化算法. E-mail: Yang.L.Liam@hotmail.com

    昆明理工大学信息工程与自动化学院副教授, 2009年获得清华大学自动化系博士学位, 主要研究方向为调度理论与方法, 以及智能优化. E-mail: bin.qian@vip.163.com

    昆明理工大学信息工程与自动化学院副教授, 2016年获得北京理工大学博士学位, 主要研究方向为智能计算和软测量方法

    昆明理工大学信息工程与自动化学院教授, 2002年获得昆明理工大学博士学位, 主要研究方向为智能优化与控制

    通讯作者: 昆明理工大学信息工程与自动化学院副教授, 2009年获得清华大学自动化系博士学位, 主要研究方向为调度理论与方法, 以及智能优化. E-mail: bin.qian@vip.163.com
  • 中图分类号: TP399

摘要: 本文针对带时间窗的低能耗多车场多车型车辆路径问题(low-energy-consumption multi-depot heterogeneous-fleet vehicle routing problem with time windows, LMHFVPR_TW), 提出一种结合聚类分解策略的增强蚁群算法(enhanced ant colony algorithm based on clustering decomposition, EACO_CD)进行求解. 首先, 由于该问题具有强约束、大规模和NP-Hard等复杂性, 为有效控制问题的求解规模并合理引导算法在优质解区域搜索, 根据问题特点设计两种基于K-means的聚类策略, 将LMHFVPR_TW合理分解为一系列带时间窗的低能耗单车场单车型车辆路径子问题(low-energy-consumption vehicle routing problem with time windows, LVRP_TW); 其次, 本文提出一种增强蚁群算法(enhanced ant colony optimization, EACO)求解分解后的各子问题(LVRP_TW), 进而获得原问题的解. EACO不仅引入信息素挥发系数控制因子进一步动态调节信息素挥发系数, 从而有效控制信息素的挥发以提高算法的全局搜索能力, 而且设计基于4种变邻域操作的两阶段变邻域局部搜索(two-stage variable neighborhood search, TVNS)来增强算法的局部搜索能力. 最后, 在不同规模问题上的仿真和对比实验验证了所提EACO_CD的有效性.

English Abstract

胡蓉, 李洋, 钱斌, 金怀平, 向凤红. 结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题. 自动化学报, 2020, 46(x): 1−18. doi: 10.16383/j.aas.c190872
引用本文: 胡蓉, 李洋, 钱斌, 金怀平, 向凤红. 结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题. 自动化学报, 2020, 46(x): 1−18. doi: 10.16383/j.aas.c190872
HU Rong, LI Yang, QIAN Bin, JIN Huai-Ping, XIANG Feng-Hong. An enhanced ant colony algorithm combined with clustering decomposition for solving complex green vehicle routing problem. Acta Automatica Sinica, 2020, 46(x): 1−18. doi: 10.16383/j.aas.c190872
Citation: HU Rong, LI Yang, QIAN Bin, JIN Huai-Ping, XIANG Feng-Hong. An enhanced ant colony algorithm combined with clustering decomposition for solving complex green vehicle routing problem. Acta Automatica Sinica, 2020, 46(x): 1−18. doi: 10.16383/j.aas.c190872
  • 传统的车辆路径问题(vehicle routing problem, VRP)由Dantzig和Ramser于1959年首次提出[1]. 该问题主要描述为在满足车辆载重、容积、行驶里程及客户服务要求等条件的同时, 合理调度车辆出行数量、行车路线、出行时间, 使得总运费用最优化. 随着社会经济的高速发展, 跨区域多车队联合车辆配送需求明显增加[2-4]. 同时, 当今环保要求越来越严格, 考虑燃油消耗和碳排放等因素的低能耗车辆配送已开始受到重视[5]. 此外, 日益激烈的市场竞争逼迫企业注重降低物流配送成本和提高客户满意度[6]. 在此背景下, 研究带时间窗的低能耗多车场多车型车辆路径问题(low-energy-consumption multi-depot heterogeneous-fleet vehicle routing problem with time windows, LMHFVPR_TW), 具有十分重要的现实意义. 由于VRP为NP-hard问题, 而VRP可归约为LMHFVPR_TW, 故LMHFVPR_TW也属于NP-hard问题, 对其开展研究亦具有较大理论价值.

    低能耗车辆路径问题近年已开始受到重视, 但相关研究仍较为有限. 在低能耗多车场VRP (low-energy-consumption multi-depot VRP, LMVRP)方面, Jabir等[7]在问题中考虑碳排放等因素, 利用低能耗车辆路径问题近年已开始受到重视, 但相关研究仍较为有限. 在低能耗多车场VRP (low-energy-consumption multi-depot VRP, LMVRP)方面, Jabir等[7]在问题中考虑碳排放等因素, 利用蚁群算法与变邻域搜索(Variable Neighborhood Search, VNS)相结合进行求解. 仿真实验表明该算法可有效求解小规模和大规模问题. Kaabachi等[8]在问题中考虑距离、碳排放和燃油消耗等因素, 并在蚁群算法中加入插入、交换和2-opt等邻域搜索策略以提高算法局部搜索能力, 取得良好的效果. 在低能耗多车型VRP (low-energy-consumption heterogeneous-fleet VRP, LHFVRP)方面, Xiao等[9]在问题中考虑交通拥堵和碳排放等因素, 并设计融合变邻域搜索和整数规划的迭代搜索算法进行求解. Kwon等[10]在问题中考虑碳排放交易机制(即各国之间通过碳排放交易市场相互买卖碳排放量, 以保证该国的碳排放量在其规定的配额内), 然后采用混合禁忌搜索算法进行求解. 目前尚无LMHFVPR_TW的相关研究.

    对于多车场VRP (multi-depot VRP, MVRP)、多车型VRP (heterogeneous-fleet VRP, HFVRP)和多车场多车型VRP (multi-depot heterogeneous-fleet VRP, MHFVPR)这几类复杂VRP, 智能算法已有一定的研究. 现有研究大多对问题进行整体编码和求解, 但由于这些问题比单车场单车型VRP(即传统VRP)具有更多的决策变量和约束条件, 使得解空间扩大且编码解码较为繁琐, 这时仅靠智能算法本身已难以将搜索快速引导至目标值整体较优的不同区域(即较优区域)执行, 容易导致算法实际搜索效率下降. 因此, 近年部分学者在所提算法中, 先采用某种分解策略将问题合理分解为多个相对简单的子问题, 从而将算法搜索尽量限定于解空间中部分存在优质解的较优区域之内, 然后再用智能算法等求解各子问题并获得原问题的解, 取得良好效果. 在MVRP方面, 主要考虑地理条件、客户需求和交货时间等因素, 并采用聚类算法把MVRP分解为一系列单个车场VRP, 然后采用PSO算法[11-12]、遗传算法[13]等求解. 在HFVRP方面, 主要考虑车辆载重量、车辆运输费用和客户需求等因素, 并采用路径分割法把HFVRP分解为一系列单车辆VRP(即traveling salesman problem, TSP), 进而采用禁忌搜索算法[14]等求解. 在MHFVRP方面, 由于该问题复杂度高, 为HFVRP和MVRP的综合, 故大都先采用分解策略将MHFVRP分解为一系列HFVRP(即单车场异构车辆的VRP), 然后采用路径分割法将各HFVRP进一步分解为多个TSP. 譬如, Dondo等[15]先采用一种启发式聚类算法把全部客户分成若干类, 然后利用路径分割算法分配车辆, 从而将原问题转化为多个小规模TSP后再利用混合整数规划求解器进行求解. Tang等[16]先利用最近邻方法把客户聚类到相应的车场, 然后再用扫描法对每个车场中的客户进行路径分割, 进而把原问题转化为多个TSP, 最后采用蚁群算法求解. 上述文献中的仿真实验和算法对比验证了分解策略和智能算法结合的必要性. 然而, 对于现实物流配送中大量存在且更为复杂的LMHFVPR_TW, 尚无结合分解策略的智能求解算法, 故开展相关研究意义重大.

    蚁群算法(ant colony optimization, ACO)是一种模拟蚂蚁寻找食物的群智能优化算法, 最早由Dorigo等[17]提出并首次用于求解TSP. ACO借鉴蚂蚁觅食的群体智能行为, 利用信息素浓度矩阵(以下简称信息素矩阵)学习和保留蚂蚁在各自行驶路径(即问题解)上留下的信息素浓度信息, 并基于该矩阵构建路径转移概率矩阵(以下简称概率矩阵), 然后通过对概率矩阵采样生成新种群来实现路径搜素(即解空间搜索)并引导搜索方向. ACO采用正反馈机制使得较短行驶路径(较优解)的优良信息得以更多积累, 可引导算法在较短时间内到达解空间中存在优质解的区域. 这使得算法具有较强的全局搜索能力, 从而在多种VRP上得到成功应用[7-8, 18-24]. 从ACO在VRP系列问题上的研究现状来看, 采用合理的信息素浓度计算策略可控制全局搜索的方向, 引入基于有效邻域操作的局部搜索能进一步提高算法性能, 两者是设计有效ACO的关键. 文献调研表明, ACO求解LMHFVPR_TW的研究处于空白状态.

    本文研究LMHFVPR_TW的建模与求解. 在建模方面, 给出包含经济费用、燃油消耗费用和客户满意度费用的运输总费用计算模型, 并建立以最小化运输总费用为优化目标的LMHFVPR_TW. 在求解方面, 考虑到LMHFVPR_TW这类问题的解空间庞大且整体编码解码复杂, 直接采用智能算法难以在较短时间内实现有效搜索, 故提出一种结合聚类分解的增强蚁群算法(enhanced ant colony algorithm based on clustering decomposition, EACO_CD)进行求解.

    EACO_CD的结构如图1所示(以2个车场2类车型为例). 由图1可知, EACO_CD由问题分解阶段和子问题求解阶段组成. (1)在问题分解阶段, 为确保分解后的各子问题区域尽量覆盖解空间中的优质解区域, 设计两层基于K-means的聚类算法对问题进行逐步分解. 第1层聚类算法为所提的一种改进平衡K-means聚类算法(improved balanced K-means algorithm, IBKA), 用于给每个车场分配一定数量的客户, 从而形成一系列带时间窗的低能耗单车场多车型VRP(LHFVRP with time windows, LHFVRP_TW). 第2层聚类算法为所提的一种带粒子群优化的混合K-means聚类算法(hybrid K-means clustering algorithm with PSO, HKMA), 用于给每个LHFVRP_TW中的每类车型合理分配一定数量的客户, 进而得到一系列带时间窗的低能耗VRP(low-energy-consumption VRP with time windows, LVRP_TW). 两层聚类分解算法将原问题最终分解为子问题LVRP_TW, 而不是分解为比LVRP_TW规模更小的带时间窗的低能耗TSP, 这使其子问题的解空间区域相对较大, 有利于算法对原问题解空间中更多区域进行搜索, 可望获得更好的解. (2)在子问题求解阶段, 采用所提的增强蚁群算法(enhanced ant colony algorithm, EACO)对每个分解后子问题(即LVRP_TW)的解空间区域进行搜索, 进而将子问题的解合并后得到原问题的解. 在EACO中, 采用动态的信息素浓度挥发系数(以下简称信息素挥发系数), 并进一步加入信息

    图  1  EACO_CD(EACO_IBKA_HKMA)结构

    Figure 1.  Framework of EACO_CD

    素挥发系数控制因子以调节其取值, 可避免算法过早收敛并进一步引导算法全局搜索到达更多的不同区域; 同时, 设计基于4种变邻域操作的两阶段局部搜索策略, 用于对全局搜索发现的优质解区域进行细致且高效的搜索, 以平衡全局和局部搜索并增强算法性能. 最后, 通过仿真实验和算法比较验证所提算法的有效性.

    • 本节建立LMHFVPR_TW模型并对问题特点和求解算法进行分析. LMHFVPR_TW为带软时间窗约束的多车场多车型车辆配送问题, 优化目标为最小化运输总费用(即经济费用、燃油消耗费用和客户满意度费用之和). 该问题在已知客户位置坐标、车场位置坐标、客户货物需求量、客户时间窗、各车场车型特征(表1中给出相应的符号定义)的情况下, 希望找到各车场中车辆的最佳配送路线(由1.3节问题模型中的决策变量具体取值确定), 从而使总运输费用达到最优. LMHFVPR_TW的应用场景很多, 譬如电商和连锁超市的商品配送、战区和疫区的紧急物资配送、石化企业成品油的一次和二次配送等.

      表 1  符号及定义

      Table 1.  Symbols and definitions

      符号 释义 符号 释义
      $F_1$ 运输距离费用 $H_{PM}$ 表示车场 $Ρ$有 $H_{PM}$辆 $M$类型的车
      $F_2$ 车辆固定成本 $r(A)$ 完成客户子集 $A$中所有客户的配送需要的最少车辆数
      $F_3$ 燃油消耗费用 $N$ 总共有 $N$个客户
      $F_4$ 时间窗惩罚费用 $V$ $V$表示客户编号集合{0,1,2,···, $N$}(0表示车场)
      $C_{M1}$ 第 $M$类型车的距离费用系数 $M_t$ 表示共有 $M_t$种类型的车
      $C_{M2}$ 第 $M$种类型车的固定发车费用系数 $x_{PMijk}$ 表示车场 $P$车型 $M$的第 $k$辆车从客户 $i$到客户 $j$的决策变量
      $C_{M3}$ 第 $M$种类型车的燃油费用系数 $k$ 表示辆车编号 $k$
      $C_1$ 配送车辆提前到达的单位惩罚费用 $d_{ij}$ $d_{ij}$表示客户 $i$到客户 $j$的距离
      $C_2$ 配送车辆迟到的单位惩罚费用 ${ET}_i$ 客户 $i$要求的最早到达时间
      $i$ 表示客户点 $i$ ${LT}_i$ 客户 $i$要求的最晚到达时间
      $j$ 表示客户点 $j$ $S_i$ 客户 $i$要求的卸货时间
      $P_s$ 表示全部车场集合{1,2,···, $P_t$} $q_i$ 客户i要求的货物需求量
      $P_t$ 表示总共有 $P_t$个车场 $t_i$ 车辆到达客户 $i$的时间
      $P$ 表示车场编号 $P$ $Q_M$ 第 $M$种车型的最大载重量
      $M_s$ 表示全部车型集合 $\{1,2,\cdots,\ M_t\}$ $M$ 表示车型编号 $M$
      $H_{PMS}$ 表示车场 $P$中车型 $M$的全部车辆集合 $\{1,2,\cdots,\ H_{PM}\}$ ${FU}_{Mij}$ 车型为 $M$的车辆从客户 $i$到客户 $j$之间的耗油量
      备注: 综合燃油消耗模型中的其他相关参数设定参考文[25]
    • LMHFVPR_TW满足如下假设:

      (1) 每个车场当中的每一类车型都参与配送任务.

      (2) 每个车场所含的车型种类相同.

      (3) 车辆在一次任务分配中仅进行一次配送.

      (5) 车辆从车场出发, 完成服务后需回到原车场.

      (6) 每个客户都被服务, 被服务的次数有且仅有一次.

      (7) 车辆配送中的货物需尽量在每个客户要求的到达时间段内送达. 同时, LMHFVPR_TW的相关符号定义如表1所示.

    • LMHFVPR_TW的优化目标为运输总费用 $Z_{Total} $ , 该优化目标由三部分组成: 经济费用 $ {Z}_{Emission\ cost} $ 、排放费用 $ {Z}_{Emission\ cost} $ 及客户满意度费用 $ {Z}_{Customer\ Satisfaction} $ . 其中, 经济费用由运输距离费用 $ {F}_1 $ 和车辆固定成本 $ {F}_2 $ 组成, 排放费用设定为燃油消耗费用 $F_3 $ , 客户满意度费用由软时间窗惩罚费用 $F_4 $ 构成. $ F_1 $ $ F_2 $ $ F_3 $ $ F_4 $ 的计算如下:

      $$ F_{1} = \sum\limits_{p = 1}^{P_{t}} \sum\limits_{M = 1}^{M_{t}} \sum\limits_{k = 1}^{H_{P M}} \sum\limits_{i = 0}^{N} \sum\limits_{j = 0}^{N} C_{M 1} * x_{P M i j k} * d_{i j} $$ (1)
      $$ F_{2} = \sum\limits_{p = 1}^{P_{t}} \sum\limits_{M = 1}^{M_{t}} \sum\limits_{k = 1}^{H_{P M}} C_{M 2} * x_{P M i j k} $$ (2)
      $$ F_{3} = \sum\limits_{p = 1}^{P_{t}} \sum\limits_{M = 1}^{M_{t}} \sum\limits_{k = 1}^{H_{P M}} \sum\limits_{i = 0}^{N} \sum\limits_{j = 0}^{N} C_{M 2} * F U_{M i j} * x_{P M i j k} $$ (3)
      $$ F_{4} = \sum\limits_{i = 1}^{N} \max \left\{C_{1} *\left(E T_{i}-t_{i}\right), 0, C_{2} *\left(t_{i}-L T_{i}\right)\right\} $$ (4)

      其中, 式(3)中燃油消耗量 $ {FU}_{Mij} $ 的计算基于文中[30]的综合燃油消耗模型和参数设置, 并假设各类车型的油耗参数相同, 可得到 $ {FU}_{Mij} $ 的如下计算公式:

      $$ \begin{align} {FU}_{Mij} \!=\! \left(\dfrac{\omega_1^M}{\overline{v_{ij}^M}}\!+\!{\omega_2^M}\!+\!{\omega_3^M}\ast G_{ij}^M\!+\!\overline{{v_{ij}^M}}^2\ast{\omega_4^M}\right){\ast d}_{ij\ } \end{align} $$ (5)

      式(5)中 $ G_{ij}^M $ 为车型 $ M $ 的车辆从客户 $ i $ 到客户 $ j $ 途中的车辆总重量, $ \overline{v_{ij}^M} $ 为车型 $ M $ 从客户 $ i $ 到客户 $ j $ 的平均速度, $ \omega_1^M $ $ \omega_2^M $ $ \omega_3^M $ $ \omega_4^M $ 为常量. 此外, 式(4)中车辆到达时间 $ t_j $ 的计算如下:

      $$ t_j = \ \sum\limits_{i = 0}^{N}x_{PMijk}\ast\left(t_i+\frac{d_{ij}}{\overline{{v_{ij}^M}}^2}+s_i\right) $$ (6)

      综上, 运输总费用 $Z_{Total} $ 的计算如下:

      $$ {Z}_{Total} = {F_1}+F_2+F_3+F_4 $$ (7)
    • 问题优化目标:

      $$ min\ Z_{Total} = F_1+F_2+F_3+F_4 $$ (8)

      问题约束条件:

      $$\begin{array}{l} \sum\limits_{M = 1}^{{M_t}} {\sum\limits_{j = 1}^N {\sum\limits_{k = 1}^{{H_{PM}}} {{x_{PM0jk}}} = } } \sum\limits_{M = 1}^{{M_t}} {\sum\limits_{j = 1}^N {\sum\limits_{k = 1}^{{H_{PM}}} {{x_{PMj0k}}} \;} } \\ \left( {\forall P \in {P_s}} \right) \end{array}$$ (9)
      $$ \sum\limits_{P = 1}^{P_t}\sum\limits_{M = 1}^{M_t}\sum\limits_{i = 1}^{N}\sum\limits_{k = 1}^{H_{PM}}{x_{PMijk} = \ }1\ \ (i\neq j,\forall j\ \in V \backslash\{0\}) $$ (10)
      $$ \sum\limits_{P = 1}^{P_t}\sum\limits_{M = 1}^{M_t}\sum\limits_{j = 1}^{N}{\sum\limits_{k = 1}^{H_{PM}}{x_{PMijk} = }\ }1\ (i\neq j,\forall i\ \in V \backslash\{0\}) $$ (11)
      $$ \begin{array}{l} \sum\limits_{j = 1}^N {{x_{PM0jk}}} = \sum\limits_{j = 1}^N {{x_{PMj0k}}} = 1,\\ \left( {\forall P \in {P_s},\forall M \in {M_s},\forall k \in {H_{PMS}}} \right) \end{array}$$ (12)
      $$ \begin{array}{l} \sum\limits_{P = 1}^{{P_t}} {\sum\limits_{M = 1}^{{M_t}} {\sum\limits_{k = 1}^{{H_{PM}}} {\sum\limits_{i \notin A} {\sum\limits_{j \in A} {{x_{PMijk}}} } } } } \ge r(A)\\ (\forall A \subseteq V\backslash \{ 0\} ,A \ne \emptyset) \end{array}$$ (13)
      $$ \begin{array}{l} \sum\limits_{j = 1}^{N}{\sum\limits_{i = 1}^{N}x_{PMijk}\ast q_i\le\ }Q_M, \\ \left(i\neq j,\forall k\ \epsilon\ H_{PMS},\ \forall P\in P_s,\forall M\ \in M_s\right) \end{array} $$ (14)

      决策变量:

      $$ \begin{array}{l} {x_{PMijk}} = \left\{ {\begin{array}{*{20}{c}} {1,}&\begin{array}{l} if\;vehicle\;k\;of\;type\;M\;in\;depotP\\ travels\;from\;node\;i\;to\;j \end{array}\\ {0,}&{otherwise} \end{array}} \right.\\ \left( {i \ne j,\;\left( {j,i} \right)\epsilon \;V,\forall k\;\epsilon \;{H_{PM}},\forall \;P \in {P_s},\forall M \in {M_s}} \right) \end{array}$$ (15)

      其中, 式(9)要求从某车场出发的车辆数目和回到该车场的车辆数目相等; 式(10)和式(11)要求每个客户只能被一辆车服务1次; 式(12)要求所有车辆均需参与配送, 且配送完后返回原车场式(13)要求生成的配送方案或问题解不出现不含车场的子回路; 式(14)要求车辆配送过程中不能超过其对应车型的额定载重量.

    • 由1.3节可知, 本文的LMHFVPR_TW为具有非线性和大规模约束的0-1整数规划问题. 相对于传统VRP, 式(1)至式(4)使优化目标不同且更加复杂, 同时式(4)使优化目标具有非线性; 多车场和多车型的引入, 使得决策变量由传统VRP的3维变量 $ x_{ijk} $ 变为5维变量 $ x_{PMijk} $ , 导致决策变量和约束的数量增多, 这时问题解空间更加庞大和复杂. 此外, 相对于常规0-1整数规划问题, VRP系列问题均含子回路消除约束(见式(13)), 该类约束的数量为 $ 2^{N+1}-2 $ , 这种指数级的约束数量限制了问题的求解规模. 虽然可以通过增加连续决策变量使式(13)的约束个数变为客户数N的多项式, 从而扩大问题的求解规模, 但这时原问题近似转化为同时含离散和连续决策变量的混合0-1整数规划问题, 该近似问题的求解难度并未降低[26].

    • VRP系列问题(包括本文的LMHFVPR_TW)均可建模为0-1整数或混合整数规划模型, 其求解算法分为两类. 一类为运筹学算法, 包括分支定界、分支切割、动态规划等[27]. 该类算法主要以线性代数和几何分析为基本工具, 利用问题优化目标函数和约束条件式的结构信息构造遍历或部分遍历解空间的搜索, 可在几分钟至几十分钟内求解较小规模问题(客户数小于等于20), 同时经过合适设计, 也可用于求解较大规模问题(客户数大于等于80), 但往往求解时间很长[27-29]. 不同于线性规划问题, 0-1规划问题具有非凸特性, 其内在几何结构与最优解间的关系仍属开放问题, 目前仅在无约束0-1二次规划等少数具有特殊结构的简单问题上存在有效多项式时间求解算法[6, 28, 30], 尚无通用的最优解多项式时间求解算法. 对于LMHFVPR_TW这类复杂的0-1规划问题, 采用已有的运筹学算法框架虽也可设计相应的求解算法, 但算法难以在较短时间获取较大规模问题的满意解. 另一类是智能优化算法(以下简称智能算法), 包括蚁群优化算法、遗传算法、禁忌搜索算法等[27]. 该类算法不依赖于问题结构, 而是将问题的约束条件隐式地包含在所设计的解的编码、解码规则中处理, 并利用某种拟人、拟物的机制不断生成新的可行个体或解, 从而引导算法执行搜索, 往往可在几秒或十几秒内就能获得各类VRP的满意解[6, 27, 31].

      目前, 各类文献对所提智能算法使用少量个体一般种群规模为 $ 20 \sim 100 $ )运行少量代数(一般进化代数为 $ 100 \sim 1000 $ 代)后, 为何都可获得问题的满意解, 基本都只从算法本身的机制进行解释. 这导致现有研究过于追求新方法层面的创新. 实际上, 智能算法为何有效, 是由其编码解码规则和智能算法自身机制共同决定的. 智能算法并不直接对0-1变量编码, 而是对客户序号排列进行编码解码规则的设计. 这样的排序编码解码, 容易将解中元素的取值限定在满足约束的可行范围, 从而避免繁杂的约束处理, 可明显提升算法搜索效率. 同时, 排序编码解码规则所确定的解空间极为扁平, 问题目标值的变化范围远远小于排序模型解空间的规模, 这非常有利于算法短时间内获取满意解. 具体来说, 譬如优化目标为最小化总行驶距离的单车辆VRP(即TSP), 假如有100个客户, 任意两个客户间的距离为在区间[1, 1000]上均匀分布的随机数, 且要求车辆从某个客户驻地(车场)出发, 服务完客户后返回该驻地, 则其目标值变化范围在(1, 1000000) 之内(1000000为各客户间的距离之和的上限, 实际的最大目标值小于此值), 而解空间规模为99! (车辆出发位置的客户需扣除), 平均每一个具体目标值对应约 $ 9\times10^{149} $ 个不同排列或解, 这表明数量巨大的不同解具有相同的目标值. 对于其他更为复杂的VRP(包括本文的LMHFVPR_TW), 也存在这一情况. 另外, 离散问题本身解之间没有梯度, 相邻解之间的目标值差别可能很小, 也可能较大. 排序编码解码规则所确定解空间的“极为扁平”性和“无梯度”性, 使得各种智能算法即使只用几秒(CPU为2.6 GHZ的主流PC在1秒内可搜索并评价含100个客户的传统VRP问题的数万个解)搜索解空间中极小的区域(数万相对于99! 类似于1根针或更小的面积相对于体育场), 也可能到达较广的目标值区域, 同时其内在的寻优机制可驱动算法到达目标值较优的不同区域搜索, 从而获得满意解. 智能算法这种通过对解空间极小区域的搜索来实现对目标值较广且较优区域的搜索, 是其有效的本质原因, 也是现有运筹学算法这类偏遍历或部分遍历解空间的算法难以做到的. 因此, 设计智能算法以实现对LMHFVPR_TW快速有效求解, 是合理且必要的.

      由1.4节和1.5节的分析可知, 对于LMHFVPR_TW这类非凸、非线性问题, 直接采用运筹学方法在短时间内获取满意解难度很大, 故本文设计一种智能算法(即结合聚类分解的增强蚁群算法EACO_CD)进行求解.

    • 本文所提的求解算法EACO_CD包含问题分解阶段和子问题求解阶段(见图1). 通过两层聚类分解, 原问题LMHFVPR_TW转换成为 $ P_t $ * $ M_t $ 个单车场单车型子问题LVRP_TWs, 然后采用本文设计的子问题求解算法EACO依次对每个LVRP_TW进行求解, 进而可获得原问题的解和优化目标值. 2.1节介绍EACO_CD中问题分解阶段的细节, 包含两层聚类算法的细节和复杂度分析; 2.2节介绍EACO_CD中子问题求解阶段的细节, 包含EACO的细节和复杂度分析; 2.3节介绍EACO_CD的总体框架并分析整体复杂度.

    • EACO_CD的问题分解阶段执行两层聚类算法, 第1层聚类算法为IBKA, 用于将原问题LMHFVPR_TW分解为 $ P_t $ 个单车场子问题LHFVRP_TWs; 第2层聚类算法为HKMA, 用于把每个单车场问题LHFVRP_TW进一步分解为个单车场单车型子问题LVRP_TWs(见图1). 在对数值型数据进行聚类时, 大都采用K-means、模糊聚类(fuzzy cluster)等算法[14, 32-34]. 而针对混合型数据, 可采用k-prototypes算法或先将混合型数据转换为数值型数据[35]. 由于本文问题中的客户属性数据均为值型, 不需要对数据类型进行转换, 同时K-means具有线性计算复杂度已被成功用于VRP系列问题[12, 14, 33, 36-37], 故本文在IBKA和HKMA中采用K-means作为基本分解策略.

    • 本文问题的优化目标(见式(8))由四部分组成, 其中有两部分与车辆运输距离有关. 当车辆距客户较远时, 配送所产生的燃油消耗费用和距离费用都随之增加(见1.2节模型), 故IBKA采用客户之间的欧式距离作为评价标准, 把客户聚成和车场数目相同的几类, 使得每个车场服务其中一类客户. 但是, 随着客户数量逐渐增大, 聚类后会出现每个车场服务的客户数量相差较大. 为确保每个车场的客户资源能均衡分配, 设计IBKA进行聚. 由于文献[37]提出的K-means平衡算法仅适用于2类客户之间的平衡( $ P_t $ = 2), 本节把文献[37]提出的K-means平衡算法推广客户群, 同时设计车场分配规则, 可更为合理地确定各车场服务的客户群, 进而获得 $ P_t $ 个单车场子问题LHFVRP_TWs. IBKA的步骤如下:

      步骤1:对全体客户进行K-means聚类. 初始化聚类重心为每个车场的坐标位置, 初始化聚类数量为车场数量, 以欧式距离作为评价指标, 以迭代次数作为终止条件.

      步骤2: 平衡客户群. 完成上述步骤后进行k类客户群之间的平衡计算, 具体如图2所示, 按每类客户群数目由大到小排序, 根据2类客户间的边缘算法[37]把客户较多的客户群依次向其余客户较少的客户群移动, 循环操作直到各类客户群中客户数量数目达到平衡.

      图  2  4类客户平衡移动示意图

      Figure 2.  Diagram of balanced movement for four customer groups

      步骤3: 计算每个车场到各聚类重心的距离. 列出距离矩阵 $ {{A}} $ , 设 $ {{A}} $ $ P_t $ (行)* $ P_t $ (列)的二维矩阵, 矩阵中的每一个元素表示某一车场坐标到某聚类重心的距离(详见式(16)).

      $${{A}} = \left( {\begin{array}{*{20}{c}} {d(1,1)}& \cdots &{d(1,{P_t})}\\ \vdots & \ddots & \vdots \\ {d({P_t},1)}& \cdots &{d({P_t},{P_t})} \end{array}} \right) $$ (16)

      其中, $ d(i,j) $ 为车场坐标i到聚类重心坐标 $ j $ 的欧式距离.

      步骤4: 按设计的分配规则对车场所服务的客户群进行分配. 选取矩阵 $ {{A}} $ 中不同行(车场不同)不同列(客户群重心不同)的 $ P_t $ 个元素并相加, 共有 $ P_t! $ 种不同的组合及对应的累加和 $( S_1 ,\cdots, $ $ S_{p_t!}), $ 选出其中最小的 $ S_{min} $ (见式(17)) 所对应的组合中每个元素 $ d(i,j) $ 的行、列标号即为车场 $ i $ 所服务的客户群 $ j $ . 采用 $ S_{min} $ 确定车场服务的客户群有利于整体减小车辆运输距离.

      $$ {\ S}_{min}\ = \ \min\ (S_1,\ {S}_2,\cdots,\ {S}_{l},\cdots,\ {S_{p_t!}})\ \ \ \ $$ (17)

      其中, $ S_l $ 表示矩阵 $ {{A}} $ 中对不同行不同列元素的第 $ l $ 种累加和.

      对于K-means迭代次数为 $ ge{n1}_K $ 、平衡迭代次数为 $ gen_b $ 、问题规模为 $ N $ _ $ P_t $ (客户数量_车场数量)的问题, IBKA的计算复杂度(以下简称复杂度) $ T_{IBKA} $ 分别由K-means聚类复杂度 $O(gen1_K* $ $ {P_t}*N) $ 、客户平衡复杂度 $ O(gen_b* (P_t*N)^2) $ (最坏情况)、获取方阵A的复杂度 $ O(P_t^2) $ 和获取 $ S_{min} $ 的复杂度 $ O(P_t*P_t!) $ 决定. 因此, $T_{IBKA} = O(gen1_K* $ $ P_t*N+genb*(P_t*N)^2+P_t^2+ P_t*P_t!) $ .

      针对3车场和144客户的本文问题LMHFVPR_TW, 采用IBKA进行车场划分, 列出距离矩阵 $ {{A}}_{(3\ast3)} $ , 分别列出矩阵 $ {{A}}_{(3\ast3)} $ 中不同行不同列的 $ P_t $ 个元素加和值的全部组合方式, 并计算3!次(详见式(18)), 若 $ {{\ S}_{min} = S}_1 $ , 即车场1服A类客户, 车场2服务B类客户, 车场3服务C类客户, 划分结果如图3所示, 图中上、下图分别为未采用和采用平衡聚类的结果, 从中可看出采用平衡聚类可使各车场服务的客户数量更加接近, 有利于提高各车场的整体效率和控制子问题规模.

      图  3  三车场K-means未平衡聚类与平衡聚类比较

      Figure 3.  The comparison of unbalanced K-means cluster and balanced K-means cluster of three depots

      $$ \begin{array}{l} S_{1} = d(1,1)+d(2,2)+d(3,3) \\ S_{2} = d(1,1)+d(2,3)+d(3,2) \\ \cdots \cdots \\ S_{6} = d(1,3)+d(2,2)+d(3,1) \end{array} $$ (18)
    • 客户的时间窗、客户的货物需求重量、客户与车场间的距离是影响本文问题优化目标(见式(8))的重要因素, 故HKMA将其作为客户的3类属性, 采用K-means对客户聚类后再为各类客户分配相应的车型K. means聚类时是把每个客户作为一个对象(质点), 多属性客户进行K-means聚类时, 需将各属性做加权和后才可进行. 然而, 上述3类属性对优化目标(见式(8))的影响程度无法直接确定, 故需对各属性权重系数进行优化, 从而提高子问题分解的合理性.

      HKMA为内外两层结构, 外层执行微粒群优化(particle swarm optimization, PSO)算法, 用于优化属性权重系数向量( $ {{\lambda}} $ = ( $ \lambda_1,\lambda_2{,\lambda}_3 $ )且 $\lambda_1+\lambda_2+ $ $ \lambda_3 = 1 $ ), 内层对基于每个 $ {{\lambda}}_{{i}} $ 的聚类分解效果进行评价, 并将评价值 $ f_{i}({{\lambda}}_{{i}}) $ 作为PSO种群个体的适应度值. HKMA的工作机制如图4所示, 其中PSO种群 $ P_{PSO} $ 的每个 $ {{\lambda}}_{{i}} $ ( $ i $ = $ 1,\cdots, M1 $ )表示一组权重系数取值, 基于 $ {{\lambda}}_{{i}} $ 对单车场问题LHFVRP_TW做K-means聚类可得 $ M_t $ 类客户群, 将 $ M_t $ 类车型和 $ M_t $ 类客户群逐一配对得到单车场单车型子问题LVRP_TW(记为 $ {{A}}_{i, j} $ , $ i $ $ j $ 分别为车型和客户群编号, $ i $ , $j = 1,\cdots, M_t$ ), $ f({{{A}}_{i, j}}) $ 表示对问题 $ {{{A}}_{i, j}} $ 采用3.1节的编码规则随机生成10个解的评价值(即子问题总运输费用)的平均值, $ {{F}}_{i} $ $ f({{{A}}_{i, j}}) $ 组成的方阵, $ Sum\_{ f_k} $ ( $k = 1,\cdots, M_t!$ )表示第k个由 $ {{{F}}_{i}} $ $ M_t $ 个相互不同行(车型不同)不同列(客户群不同)元素累加所得的值, $ f_{i} \_{\min}$ 取所有 $ Sum\_{f_k} $ 中的最小值并赋值给 $ f_{i}({{\lambda}}_{{i}}) $ . 由于 $ M_t $ 个车型和客户群均不同的 $ {{{A}}_{i, j}} $ 可构成一个LHFVRP_TW, 故 $ Sum\_{f_k} $ 实际上是对第k种子问题分解方式合理性的评估, 同时 $ f_{i} \_{\min}$ 用于标识相对最为合理的子问题分解方式.

      图  4  HKMA工作机制

      Figure 4.  The HKMA’s running mechanism

      $ \mathrm{Z}_{\rm {Total}}({{A}}_{i,j}) $ (见式(8))为个体 $ {{A}}_{i,j} $ 的目标函数值, $ {{\lambda}}_{{opt}} $ $ P_{PSO} $ 的历史最优个体 $ {{{sub}}} {{P}}\left({{\lambda}}_{{opt}}\right) $ $ f\left({{\lambda}}_{{opt}}\right) $ 对应的 $ M_t $ 个单车场单车型问题LVRP_TWs的集合(具体见上一段), Maxgen (PSO)为HKMA中PSO算法的运行代数, $ gen2_K $ 为HKMA中每次执行K-means算法的运行代数. HKMA的具体步骤如下:

      步骤1: 令 $ gen = 1 $ , 随机生成 $ P_{PSO} $ 中的每个 $ {{\lambda}}_{\bf{i}} $ .

      步骤2: (内层): 确定 $ P_{PSO} $ 中所有 $ {{\lambda}}_{\bf{i}} $ 的适应度值(具体见上一段).

      步骤3: (外层): 若 $ gen>1 $ , 则将当代 $ P_{PSO} $ 和父代 $ P_{PSO} $ 的个体进行冒泡排序并择优保留前 $ M1 $ 个组成 $ P_{PSO} $ . 更新 $ {{\lambda}}_{{opt}} $ $ {{sub}} {{P}}\left({{\lambda}}_{\bf{o p t}}\right) $ .

      步骤4: (外层): $ P_{PSO} $ 通过PSO算法进化后得到新的种群 $ P_{PSO} $ , 也即得到 $ M1 $ 组新的权重系数向量.

      步骤5: 令 $ gen = gen+1 $ , 若 $gen\le Maxgen (PSO)$ , 则返回步骤2, 否则输出 $ {{sub}} {{P}}\left({{\lambda}}_{{opt}}\right) $ .

      HKMA的复杂度 $ T_{HKMA} $ 由步骤2至步骤5的复杂度决定. 对于单车场问题LHFVRP_TW, 问题规模为 $ N_i $ _ $ M_t $ (客户数量_ 车型数量), 其中 $ \sum_{i = 1}^{P_t}N_i = \ N $ . 步骤2的复杂度由K-means聚类复杂度 $ O({ge{n2}_K\ast M}_t\ast N_i) $ 、获取方阵 $ { F}_{{ i}} $ 的复杂度 $ O({M_t}^2\ast N_i) $ 、获取 $ f_i \_{\min}$ 的复杂度 $ O(M_t*M_t!) $ 组成为 $ O({{{M1\!\ast\!(ge{n2}_K\ast M}_t\!\ast\! N_i\!+\!M}_t}^2{\!\ast\! N}_i\!+\! M_t\!*\!M_t!)) $ ; 步骤3的复杂度为 $ O({M1}^2) $ ; 步骤4的复杂度为 $ O(M1) $ . 因此, $T_{HKMA} = O(Maxgen\left(PSO\right)\ast(M1\ast g e{n2}_K\ast M_t\ast N_i+M1\ast M_t^2{\ast N}_i+ M1\ast M_t \ast M_t!+ {M1}^2 ))$ . 由于需采用HKMA对 $ {P}_t $ 个单车场子问题LHFVRP_TWs进行分解, 故第2层分解总的复杂度为:

      $$ \begin{align} {\rm{ total }} T_{H K M A} =& O({{\rm{Maxgen}}}(\mathrm{PSO})*\\ &\left(M 1 * g e n 2_{K} * M_{t} * N+M 1 * M_{t}^{2}\right.*\\ &\! \left. N+P_{t} * M 1 * M_t* M_{t} !+P_{t} * M 1^{2} \right) \end{align} $$

      在本文算法EACO_CD中, HKMA的参数设置为 $ M1 = 10 $ $ M2 = 10 $ $ Maxgen(PSO) $ = 10和 $ gen2_K $ $ = 20 $ , PSO中的惯性权重和加速因子的设置和文献[38]相同, 具体设置为惯性权重 $ \omega = 0.9 $ , 速度因子 $ c_1 = 1.2 $ , $ c_2 = 1.5 $ . 针对2.1节中示例问题的车场1和其服务的A类客户(即IBKA划分得到一个单车场子问题LHFVRP_TW), 采用HKMA进行车型划分, 可得如图5图6. 由图5图6可见, A类客户依据车型和客户的3类属性得以进一步划分, 从而将1个LHFVRP_TW分解为规模更小的2个单车场单车型子问题LVRP_TWs.

      图  5  HKMA三维聚类效果

      Figure 5.  The 3D clustering results of HKMA

      图  6  HKMA二维结果

      Figure 6.  The 2D results of HKMA

    • 通过上一阶段的两层聚类分解后, 原问题LMHFVPR_TW转换成为 $ {P}_t\ast M_t $ 个单车场单车型子问题LVRP_TWs, 从而本阶段可采用本文设计的子问题求解算法EACO依次对每个LVRP_TW进行求解, 进而可获得原问题的解和优化目标值(见图1). 2.2.1节至2.2.4节介绍EACO的细节, 2.2.5节给出EACO的复杂度分析.

    • EACO对各车辆服务的所有客户进行整体编码. 每只蚂蚁代表多辆车, 每只蚂蚁的行驶路径(即子问题LVRP_TW的 $ l $ 个解)为对应各车辆的总行驶路径. 譬如对于第只蚂蚁服务10个客户, 可记为: $ { \pi}_{{ a} { n}{ t}({ l})} = [1,4,9,5,10,2,3,6,7,8] $ .

      EACO采用文[39]中的方法对每只蚂蚁的行驶路径进行解码, 即逐一选择车场中的每辆车, 将 $ {{\pi}}_{{ant(l)}} $ 中客户从左往右依次加入当前车辆, 如果当前车辆的载重量大于其服务客户的总需求量, 则继续往该车辆中加入客户, 否则选择下一辆车继续依次加入剩余客户. 譬如, 对于上一段的 $ { \pi}_{{ a} { n}{ t}({ l})} $ , 假设需两辆车进行服务, 解码后可得 $ { \pi}_{{ a} { n}{ t}({ l})} = [{ \pi}_{\pmb vehicle(1)},{ \pi}_{\pmb vehicle(2)}] = [1,4,9,5],[10,2,3,6,7,8] $ .

      显然, 当采用上述编码解码规则时, 式(13)的子回路消除约束自然得到满足, 同时也不违反其他约束.

    • 首先, 利用扫描法构造1只蚂蚁的行驶路径[40], 并采用该路径对信息素浓度 $ \tau_{i j} $ 进行初始化:

      $$ {\tau _{ij}} = \left\{ {\begin{array}{*{20}{l}} {{P_m},}&{{\rm{ if}}\;i,j\;{\rm{in}}\;{\rm{the}}\;{\rm{route }}}\\ {}&{{\rm{ constructed}}\;{\rm{by}}\;SWA}\\ {1,}&{\;\;\;\;\;{\rm{ otherwise }}} \end{array}} \right.$$ (19)

      其中, $ i $ $ j $ 为客户编号, $ P_m $ 为信息素浓度值的初始值(设置为大于1的值). 为防止算法过早陷入局部最优[41], 设置信息素浓度 $ \tau_{i j} $ 的最大值和最小值为:

      $$ \tau_{i j_{-}} \min = \frac{Q_{m}}{2 \displaystyle\sum_{i = 1}^{N} d_{D i}} , 0<\tau_{i j_{-}} \min <1 $$ (20)
      $$ \tau_{i j_{-}} \max = \frac{Q_{m}}{\displaystyle\sum_{i = 1}^{N} d_{D i}} , \tau_{i j_{-}} \max >\mathrm{P}_{m} $$ (21)

      其中, $ N $ 为车场需服务的全部客户总数, $ d_{Di} $ 为车场到客户 $ i $ 的距离, $ Q_m $ 为常数( $\sum_{i = 1}^{N} d_{D i} < Q_m < $ $2 \sum_{i = 1}^{N} d_{D i}$ ).

      然后, 设置信息素浓度增量 $ \Delta \tau_{i j} = 0 $ 和种群大小 $ popsize = (2/3)*N $ .

    • EACO每代通过对当前种群中各蚂蚁行驶路径的确定来实现对问题解空间的全局搜索. 每只蚂蚁均利用式(22)确定其行驶路径.

      $$P_{iu}^l = \left\{ {\begin{array}{*{20}{c}} {\dfrac{{{{\left( {{\tau _{iu}}} \right)}^\alpha }*{{\left( {{\eta _{iu}}} \right)}^\beta }}}{{\displaystyle\sum\limits_{s \notin tabu} {\left( {{{\left( {{\tau _{is}}} \right)}^\alpha }*{{\left( {{\eta _{is}}} \right)}^\beta }} \right)} }},\;{\rm{ if}}\;u \notin tabu}\\ {0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;,\;{\rm{ otherwise }}} \end{array}} \right. $$ (22)

      其中, $ i $ 为当前客户, $ u $ 下一客户, $ P_{iu}^l $ 为第 $ l $ 只蚂蚁从 $ i $ $ u $ 的转移概率, $ s $ 为蚂蚁 $ l $ 还未服务过的客户, $ \tau_{iu}(\tau_{is}) $ $ i $ $ u(s) $ 间的信息素浓度, $ \eta_{i u}\left(\eta_{i s}\right) $ $ u(s) $ 之间距离的倒数, $ \alpha $ $ \beta $ 为重要程度权重, $ tabu $ 为蚂蚁已经搜索过的客户地点集合. 对 $ \left\{P_{i u}^{l} | u \notin t a b u\right\} $ 进行轮盘赌选择, 即可得到 $ u $ 的取值, 从而确定蚂蚁 $ l $ 从客户 $ i $ 出发需到达的下一客户.

    • EACO每代对每只蚂蚁的信息素浓度采用式(23)-(26)依次进行更新:

      $$ \gamma = \left\{ {\begin{array}{*{20}{c}} {\gamma *\left( {1 - \dfrac{{{M_a}}}{T}} \right),{\rm{ The}}\;{L_b}\;{\rm{is}}\;{\rm{unchanged }}}\\ {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{ for}}\;{M_a}\;{\rm{iterations }}}\\ {\gamma *\left( {1 + \dfrac{{{M_b}}}{T}} \right),\;{\rm{ The}}\;{L_b}\;{\rm{is}}\;{\rm{changed }}}\\ {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{ for}}\;{M_b}\;{\rm{iterations }}}\\ {\gamma \quad \;\;\;\;\;\;\;\;\;\;\;\;,\;\;\;{\rm{ otherwise }}\;\;\;\;\;\;\;\;\;\;} \end{array}} \right.$$ (23)
      $$ {\rho ^{(t + 1)}} = \left\{ {\begin{array}{*{20}{c}} {\gamma *{\rho ^{\rm{t}}},\;{\rm{if}}\;{\rho _{\min }} \le \gamma *{\rho ^{\rm{t}}} \le {\rho _{\max }}}\\ {{\rho _{\min }}\;{\rm{or}}\;{\rho _{\max }},\quad {\rm{ otherwise }}} \end{array}} \right. $$ (24)
      $$\Delta \tau _{ij}^t = \left\{ {\begin{array}{*{20}{l}} {\dfrac{W}{{{L_b}}},\;{\rm{if}}\;{\mathop{\rm edge}\nolimits} (i,j) \in {L_b}}\\ {0\;\;\;,\;{\rm{otherwise }}} \end{array}} \right.$$ (25)
      $$ \tau_{i j}^{(t+1)} = \rho^{\mathrm{t}} * \tau_{i j}^{t}+\Delta \tau_{i j}^{t}, \rho^{\mathrm{t}} \in\left[\rho_{\min }, \rho_{\max }\right] $$ (26)

      其中, $ \gamma $ 为信息素挥发系数控制因子(初始设置为1), $ M_a $ $ M_b $ 为迭代次数系数(均设置为5), $ T $ 为基准值(设置为50), $ L_b $ 为当前最好解对应的目标函数值, $ t $ 表示算法进化的第 $ t $ 代(即算法第 $ t $ 次迭代), $ \rho^t $ 为第 $ t $ 代的信息素挥发系数(初始设置为0.9), $ \rho_{min} $ $ \rho_{max} $ 分别为的最小值和最大值(分别设置为0和1), $ {{\Delta\tau}_{ij}}^t $ 为第 $ t $ 代的信息素浓度增量, $ W $ 为信息素增量常数(设置为500), $ {\tau_{ij}}^t $ 为第 $ t $ 代的信息素浓度. $ \gamma $ 根据算法每代的实际运行效果动态调整其取值, 可在运行效果好(差)时增加(减小)信息素浓度, 有利于增强算法合理引导搜索的能力.

    • 本节在基本变邻域搜索(variable neighborhood search, VNS)[42]基础上提出一种两阶段变邻域局部搜索策略TVNS(two-stage variable neighborhood search, TVNS), 对EACO每代发现的当前最好解进一步执行高效且细致的邻域搜索, 以提高解的质量.

      TVNS为在车辆间和车辆内部分别执行多种邻域操作(见图7)的两阶段局部搜索, 两个阶段中各邻域操作均在当前最好解上执行且每次执行的最大次数均设置为 $ gen_{local} = 20 $ . 首先, 第1阶段随机选择两辆车, 依次对车辆间的客户执行“Insert”和“Exchange”邻域操作, 如果在执行操作期间发现更好解, 则更新当前最好解并立刻进入第2阶段, 否则各邻域操作均执行至最大次数 $ gen_{local} $ 后进入第2阶段. 然后, 第2阶段逐一选择每辆车, 对每辆车的内部客户依次执行“2-opt”、“Insert”、“Exchange”和“Swap”邻域操作, 如果在执行操作期间发现更好解, 则更新当前最好解并立刻对下一辆车执行操作, 否则各邻域操作均执行至最大次数 $ gen_{local} $ 后再对下一辆车执行操作. 第2阶段结束后完成本次局部搜索.

      图  7  局部搜索策略

      Figure 7.  Local search strategy

    • 设定终止条件为算法的运行时间, 如果满足运行时间要求, 则输出服务所有客户的每辆车的行驶路径以及相应的行驶总费用.

    • EACO为EACO_CD中求解由聚类分解(见2.1节)得到的单车场单车型子问题LVRP_TW的算法. 令EACO种群规模为 $ {popsize}_E $ , 全局搜索运行代数为 $ gen_{global} $ , 局部搜索每代迭代次数为 $ gen_{local} $ , 局部搜索(含第1和第2阶段)执行时实际使用各邻域的平均总次数为 $ Z $ (即 $Z \leq 2 + 4 * max \ \{H_{PM}|P = 1,2,\cdots,P_t,M = 1,2,\cdots,M_t\}$ ), 第 $ i $ 个车场的LVRP_TW的客户数量为 $ N_{i,\ x} $ ,( $ \sum_{x = 1}^{M_t} N_{i,x} = \ N_i,\ \sum_{i = 1}^{P_t}\sum_{x = 1}^{M_t}N_{i,\ x} = N $ ). EACO的算法复杂度 $ T_{EACO} $ 分别由EACO的全局搜索复杂度和局部搜索复杂度构成. 在每一代中, 全局搜索复杂度由种群初始化复杂度 $ O(popsizeE*N_{i,\ x}) $ 、信息素矩阵和概率矩阵更新复杂度 $ O({N_{i,\ x}}^2) $ 、采样概率矩阵生成蚂蚁路径(即个体)的复杂度 $ O(popsize_E* {N_{i,\ x}}^2) $ 、种群评价复杂度 $ O(popsize_E*N_{i,\ x}) $ 组成, 为 $ O(popsize_E*{N_{i,\ x}}^2) $ ; 局部搜索复杂度为 $ O(gen_{local}*Z*N_{i,\ x}) $ (最坏情况). 因此, $ T_{EACO} = O(gen_{global}\!*\!(popsize_E\!*\!{N_{i,\ x}}^2\!+\!gen_{local}\!*\!Z\!*\!N_{i,\ x})) $ .由于需采用EACO对 $ {P}_t\ast M_t $ 个单车场单车型子问题LVRP_TWs进行求解, 故采用EACO求解所有LVRP_TWs总的复杂度 $ total_{T_{E A C O}} = O(\text {gen}_{\text {global}} * \left. \left(\text {popsize}_{E} *\!\right.\right. \!\sum_{i = 1}^{P_{t}} \!\sum_{x = 1}^{M_{t}} N_{i, x}^{2}\!+\!gen_{local} * Z * \sum_{i = 1}^{P_{t}} \sum_{x = 1}^{M_{t}} N_{i,\ x}) = O(g e n_{g l o b a l} *(\text {popsize}_{E}*\widetilde{\log}N * N+g e n_{\text {local}}*Z*N)) $ . 这里用 $ \widetilde{\log}N $ (而非默认以2为底数的 $ \log N $ )表示低于 $ N $ 的亚线性复杂度.

    • 整个算法EACO_CD的结构如图1所示(以2个车场2类车型为例). 由图1可知, EACO_CD对个子问题LVRP_TWs依次执行EACO进行求解, 最终将获得的各子问题解合并得到原问题的解, 同时将各子问题解的优化目标值累加得到原问题的优化目标值, 从而实现对原问题的求解.

    • EACO_CD是对本文问题LMHFVPR_TW的整体求解, 其复杂度 $ T_{EACO\_CD} $ 由分解算法IBKA的复杂度 $ T_{IBKA} $ (见2.1.1节)、分解算法HKMA总的复杂度 $ totalT_{HKMA} $ (见2.1.2节)、求解算法EACO总的复杂度 $ totalT_{EACO} $ 组成(见2.2.5节), 即 $ T_{EACO\_CD}\! =\! T_{IBKA}\!+\!totalT_{HKMA}\!+\!totalT_{EACO} $ . 虽然 $ T_{IBKA} $ $ totalT_{HKMA} $ $ totalT_{EACO} $ 中的变量较多, 但除 $ N $ (客户数量)、 $ Ρ_t $ (车场数量)、 $ M_t $ (车型数量)与问题规模相关, $ Z $ (局部搜索每次迭代搜索的邻域或个体)与具体问题相关, $ {popsize}_E $ 设置为 $ 2/3*N $ (见2.2.2.1节)以外, 其余变量均与算法相关且实际使用中都设置为常数. 因此, 可得简化的 $ T_{IBKA} = O((P_t*N)^2+P_t*P_t!) {\text{、}} {totalT}_{HKMA} = {O(M_t}^2\ast N+{P}_t\ast M_t\ast M_t!) {\text{、}} totalT_{EACO} = O(\widetilde{\log} N\ast N^2+Z\ast N) $ . 显然, 所有变量的多项式次数不超过2, 影响 $ T_{EACO\_CD} $ 的是 $ T_{IBKA} $ 中的 $ O(P_t!) $ $ {totalT}_{HKMA} $ 中的 $ O({{P}_t\ast M}_t!) $ . 然而, 实际问题中 $ P_t $ $ M_t $ 一般都不大于10, 而单计算10! 用CPU为2.6GHZ的主流PC可在1秒左右完成计算, 故EACO_CD对大多数实际问题可在较短时间内结束运算. 另外, 如果 $ P_t(M_t) $ 很大(譬如为50), 可将IBKA的步骤4(HKMA的步骤2)中穷举不同行不同列的组合改为采样 $ P_t(M_t) $ 的多项式次数的组合, 从而扩大EACO_CD求解问题的规模.

    • 本节所有算法的测试均采用: 英特尔I7处理器(3.2 GHz)、8 G内存、Win10操作系统、matlab2018a编程环境.

    • 在第1节所提出的目标函数中(式(7)), 距离费用系数设定参考文[7], 车辆固定费用参考文[9], 燃油费用系数设定参考文[43], 时间窗惩罚费用系数参考文[16], 具体取值见表2.

      表 2  目标函数中的相关系数

      Table 2.  Coefficients in the object function

      符号 数值
      $C_{M1}$ 1.5元/kM
      $C_{M2}$ 300-800元/辆
      $C_{M3}$ 7.6元/L
      $C_{1}$ 15元/H
      $C_{2}$ 20元/H

      EACO的残留信息素重要程度 $ \alpha $ , 启发信息素重要程度 $ \beta $ , 初始化信息素浓度参数 $ P_m $ , 信息素增量常数 $ W $ 为个主要的参数, 为确定合适的参数组合, 对这4个参数进行正交实验, 各参数设置水平如表3所示. 由于聚类分解后原问题LMHFVPR_TW转变为 $ P_t*M_t $ 个LVRP_TWs, 故采用Solomon标准VRPTW数据集中的问题c101(100个客户)进行测试. 每组参数组合下的EACO在c101上独立运行20次, 取20次的平均最小运输总费用值作为平均响应值ARV, 参数设置的正交表见表4, 参数的平均响应值和影响力见表5. 由表4表5可得EACO的参数设置为: $\alpha = 1.25, \beta = 2.5,$ $P_m = 1.1, W = 500$ .

      表 3  主要参数与水平

      Table 3.  Main parameters and level

      主要参数 水平设置
      1 2 3 4
      $\alpha$ 1.25 1.5 1.75 2.0
      $\beta$ 10 1.5 2.0 2.5
      $P_m$ 1.1 1.2 1.3 1.4
      $W$ 500 1000 1500 2000

      表 4  参数设置的正交表

      Table 4.  Orthogonal table of parameter settings

      组合编号 水平设置 AVR(元)
      $\alpha$ $\beta$ $P_m$ $W$
      1 1 1 1 1 9677
      2 1 2 2 2 9625
      3 1 3 3 3 9613
      4 1 4 4 4 9541
      5 2 1 2 3 9745
      6 2 2 1 4 9624
      7 2 3 4 1 9602
      8 2 4 3 2 9593
      9 3 1 3 4 9836
      10 3 2 4 3 9703
      11 3 3 1 2 9654
      12 3 4 2 1 9612
      13 4 1 4 2 9865
      14 4 2 3 1 9689
      15 4 3 2 4 9656
      16 4 4 1 3 9672

      表 5  各参数不同水平下的平均响应值和影响力

      Table 5.  Average response values and influences table at different levels of each parameter

      水平 水平设置
      $\alpha$ $\beta$ $P_m$ $W$
      1 9614 9780 9656 9645
      2 9641 9660 9659 9684
      3 9701 9631 9683 9683
      4 9720 9604 9677 9664
      极差 106 176 27 39
      影响力排名 2 1 4 3
    • EACO_CD由IBKA、HKMA和EACO组成. 为验证EACO_CD的有效性, 先将这3种算法分别与国际期刊上的相近算法进行比较, 最后再进行总体比较.

      首先, 为验证EACO的有效性, 在多车场单车型问题LMVRP_TW上, 将EACO1和国际期刊中的有效算法DHACO[37]进行对比. EACO1为EACO_CD不含两层聚类的算法, 而DHACO为不含分解且直接求解整个问题的一类蚁群算法. EACO1采用DHACO的编码. 测试结果见表7.

      表 7  EACO_IBKA与其他算法对比结果

      Table 7.  Comparison results of EACO_IBKA with other algorithms

      N_Pt EACO_IBKA EACO_KM EACO_NNA EACO1 DHACO ${{T}}({{s}})$
      best average best average best average best average best average
      96_2 17483 18155 18037 18379 16768 17675 15371 17009 16011 17559 19
      192_2 27522 28546 28457 29482 28758 29560 28379 29838 28524 30863 38
      288_2 39217 41028 40412 42363 41179 42142 41283 43164 42606 43930 58
      360_2 53748 56268 54672 57402 55251 57847 56276 58653 56965 59409 72
      96_3 16638 17278 17066 17491 15957 16821 14627 16582 15236 17186 29
      192_3 26199 27175 27090 28066 27376 28140 27016 28405 27153 29381 58
      288_3 37337 39062 38476 40333 39205 41123 39305 41096 40565 41826 86
      360_3 51176 53576 52056 54656 52608 55080 53584 55848 54240 56568 108
      96_4 16062 16943 16810 17146 15871 16425 16012 16907 16391 16991 38
      192_4 25690 26612 26528 27235 26846 27620 26443 27896 26623 28850 77
      288_4 36519 38266 37624 39493 38365 39338 38442 40278 39692 40974 115
      360_4 50480 52904 51344 53960 51904 54392 52088 55184 53584 55904 144
      平均值 33173 34651 34048 35501 34174 35514 34069 35905 34799 36620 /

      其次, 为单独验证IBKA的有效性, 在多车场单车型问题LMVRP_TW上, 将EACO_IBKA和EACO_KM、EACO_NNA进行对比. 这3种算法为在EACO1中分别加入3类第1层聚类算法(即IBKA、K-means[12, 14]、NNA[11])后得到. 测试结果见表7.

      然后, 为单独验证HKMA的有效性, 在单车场多车型问题LHFVPR_TW上, 将EACO_ HKMA和EACO_RDA、EACO_RAA、EACO_ KEW、EACO2、TSA_RDA[10]进行对比. 前4种算法为在EACO1中中分别加入4类第2层聚类算法(即HKMA、RDA[10]、RAA、KEW)后得到, 其中RDA根据客户需求量优先选择最大载重量的车型, 进而将问题分解为一系列单车辆LVRPs(即TSPs), RAA随机将客户划分给某种车型, KEW每类客户属性分配相同权重后用K-means划分车型(即简化的HKMA), RAA和KEW均将问题分解为一系列单车型LVRP_TWs; EACO2为EACO1改用多车型编码后得到, 用于直接求解整个问题; TSA_RDA为国际期刊中的有效算法, 该算法在禁忌搜索算法中加入RDA. 测试结果见表8.

      表 8  HKMA与其他划分算法的对比结果

      Table 8.  Comparison results of HKMA and the other dividing algorithms

      $ {{N}}\_ {{M}}_{{t}}$ EACO_ HKMA EACO_ RDA EACO_ RAA EACO_KEW EACO2 TSA_RDA $ {{T}}({{s}})$
      best average best average best average best average best average best average
      96_2 16299 16759 17570 19461 16238 17661 16754 17704 16543 17838 17746 19656 29
      192_2 24847 25998 25983 26905 26000 27201 26039 26918 26520 27745 26243 27174 57
      288_2 32225 33356 33783 34713 32740 35242 32540 35156 34050 36652 34121 35060 87
      360_2 48344 50050 50695 52088 49129 52874 48828 52743 51094 54989 51202 52609 108
      96_3 15777 15929 16704 18494 16011 16792 15932 16839 16171 16960 16871 18679 44
      192_3 23624 24718 24704 25570 24714 25850 24748 25588 25455 26626 24951 25826 87
      288_3 30621 31700 32106 32984 31111 33493 30929 33414 32667 35168 32427 33314 129
      360_3 45933 47554 48172 49502 46691 50237 47401 50118 49026 52749 48654 49997 162
      96_4 14214 14349 15047 16655 14422 15118 14346 15171 14566 15269 15197 16822 57
      192_4 21273 22251 22237 23018 22257 23268 22282 23034 22925 23966 22459 23248 116
      288_4 27563 28542 28902 29689 28012 30149 27842 30088 29413 31656 29191 29986 173
      360_4 41350 42809 43360 44558 42028 45218 41776 43111 44129 47479 43794 45004 216
      平均值 28506 29501 29939 31136 29113 31092 29118 30824 30213 32258 30238 31448 /

      最后, 为验证EACO_CD的有效性, 在本文问题LMHFVPR_TW上, 将EACO_CD和国际期刊中的有效算法IACO_CD[16]和IHGA[13]进行对比. IACO_CD为两层分解算法, 该算法第2层将问题分解为单车辆LVRP(即TSPs), 而IHGA通过加入车型染色体后对问题进行整体求解. 测试结果见表9.

      表 9  EACO_CD性能验证

      Table 9.  EACO_ CD’s performance verification

      $ {{N}}$_ ${{ P}}_{{t}}$_ $ {{M}}_{{t}}$ EACO_CD (EACO_IBKA_HKMA) IACO_CD (IACO_NNA_SWA) IHGA ${{T}}({{s}})$
      best average worst SD best average worst SD best average worst SD
      96_2_2 16370 16526 16904 295 17800 18071 18381 272 15852 16011 16376 285 31
      192_2_2 23664 24760 25650 556 26040 27250 28218 576 24863 26010 26948 590 71
      288_2_2 30690 31768 32227 724 33772 34962 35457 803 35311 36550 37076 824 123
      360_2_2 39903 41303 41906 951 43907 45448 46111 1059 45507 46098 47781 1197 162
      96_3_2 16883 17869 18993 358 18568 20115 20999 343 16800 18283 19011 363 48
      192_3_2 24257 25492 26408 668 26692 28059 29065 671 26688 28052 29053 746 109
      288_3_2 30258 31572 32860 907 34814 36319 37797 1017 35414 36956 38450 1092 183
      360_3_2 39347 41061 42734 1141 43291 45187 47020 1263 47228 49291 51297 1389 243
      96_3_3 15867 17082 17860 388 17470 18911 19664 368 16514 17874 18584 478 62
      192_3_3 22816 23977 24832 631 25108 26383 27320 708 26242 27588 28567 743 145
      288_3_3 28458 29693 30892 828 32742 34157 35530 957 35582 37120 38622 1048 245
      360_3_3 37006 38610 40166 1079 40722 42474 44186 1198 47081 49427 51523 1399 288
      平均值 27127 28309 29286 711 30077 31445 32479 770 31090 32438 33607 846 /
    • 本文的测试数据数据来源于网站(http://neo.lcc.uma.es/vrp/)中的MDVRP数据集(数据中不存在明显聚类特征的客户位置分布). 其中包括问题pr01(48个客户), pr02(96个客户), pr03(144个客户), pr04(192个客户), pr05(240个客户), pr06(288个客户), p22(360个客户). 由于该数据中未含有车型数据, 故在HKMA和EACO_CD的有效性验证时加入车型数据(见表6), 各比较算法在每个问题上独立运行20次, 每个算法设置相同运行时间 $ T $ (单位: s). 性能指标为各算法20次运行中的最优值best、平均值average、最差值worst和标准差SD. 各种带分解策略的比较算法每次运行时间为问题分解算法与问题求解算法运行时间的总和, 譬如EACO_CD每次运行的时间为EACO、IBKA和HKMA的运行时间总和, 表7-9中粗体为算法运行结果的较小值. 需要说明的是, 为节约空间, 表7-9中仅提供问题pr02 (96个客户), pr04 (192个客户), pr06 (288个客户), p22 (360个客户)的相关测试结果, 更多问题和性能指标下的测试结果可网上下载*. 表7-9中的测试结果和网上测试结果具有相近统计性能, 均可对各比较算法性能做出较客观判断.

      表 6  4种不同车型相关参数设置

      Table 6.  Related parameter settings for four different vehicle types

      车型列表 车型参数
      载重量(kg) 空车重量(kg) 平均速度(km/h) 固定费用(元) 最大承货物载数(件)
      Type 1 200 1600 60-80 300-400 20
      Type 2 500 2700 50-70 400-500 30
      Type 3 600 3500 40-60 500-600 40
      Type 4 800 5000 30-50 600-800 50
    • 表7可知, EACO的最优值和平均值均优于DHACO. 在算法全局搜索部分, DHACO和EACO的复杂度无明显差异, 但EACO在全局阶段引入信息素挥发系数控制因子进一步动态调节信息素挥发系数, 可有效控制信息素的挥发从而提高了算法的全局搜索能力. 在算法局部搜索部分, 相比DHACO的VNS策略, EACO的TVNS能有效搜索更多不同区域, 具有更强的局部搜索能力.

    • 表7可知, EACO_IBKA总体优于EACO_K M和EACO_NNA. 这表明IBKA通过聚类和平衡客户群, 可更合理地分配车场并较好实现子问题解耦. 同时, EACO_IBKA也总体优于不含问题分解策略的整体求解算法EACO1和DHACO. 这说明采用有效的问题分解策略为算法提前确定需搜索的较优区域, 可在一定程度上避免过多的低效搜索, 有利于增强算法性能. 此外, 测试结果显示带分解策略的算法更适用于较大规模问题, 原因在于这些问题的解空间更加庞大, 仅依靠智能算法自身进化机制难以快速引导算法发现优质解区域.

    • 表8可知, EACO_HKMA总体优于其他比较算法. 这表明HKMA综合考虑客户的3类属性并为各属性设定合适的权重, 可更合理地划分子问题. 具体而言, EACO_HKMA明显优于EACO_RDA和TSA_RDA, 这说明RDA将问题分解为更小规模的单车辆LVRPs(即TSPs)会将算法实际搜索空间限定得过小, 从而遗漏较多存在优质解的区域; EACO_HKMA明显优于EACO_RAA(除N = 96的1个较小规模问题)和EACO_KEW, 这说明RAA随机划分子问题的方式和KEW给各属性分配相同权重后再划分子问题的方式, 均无法获取真正优质的搜索区域; EACO_HKMA也明显优于整体求解算法EACO2, 这再次验证了将问题先合理分解可把算法搜索直接限定在较优搜索区域进行, 有利于提高算法效率. 此外, 与3.3.2节类似, 本节的分解策略同样对较大规模问题更有效.

    • 表9可知, EACO_CD总体优于IACO_CD和IHGA. 具体而言, EACO_CD的最优值、平均值、最差值均明显优于IACO_CD, 且标准差整体较小, 这说明IACO_CD将问题分解为更小规模的单车辆LVRPs(即TSPs)会遗漏较多存在优质解的区域, 同时IACO_CD自身算法的搜索能力有限, 从而导致该算法的性能和鲁棒性较差; EACO_CD的最优值、平均值、最差值、标准差明显优于IHGA(除N = 96的2个较小规模问题), 这表明随着车场、车型和客户的增多, 本文问题LMHFVPR_TW的可行解空间呈指数倍增加, 仅采用智能算法(如IHGA)难以在较短时间内完成大范围搜索以获得原问题的优质解, 而EACO_CD依靠合理的问题分解能将EACO的搜索限定在较优区域之内, 进而利用EACO较强的搜索能力可短时间内从较优区域中获得优质解, 从而使其性能和鲁棒性均较强.

      综上可知, 结合IBKA和KHMA的EACO_CD是求解本文问题LMHFVPR_TW的有效鲁棒算法.

    • 针对多车场多车型绿色车辆路径问题LMHFVRP_TW, 本文提出一种结合聚类分解策略的增强蚁群算法(EACO_CD) 进行求解. 这是首次采用智能优化算法求解该问题. EACO_CD包括两个阶段. 第一阶段为问题分解, 该阶段设计两种聚类分解策略IBKA和HKMA, 用于对LMHFVRP_TW进行分解, 从而有效制问题规模并快速引导算法在较优区域内搜索. 第二阶段为子问题求解, 该阶段采用EACO对每个分解后的子问题LVRP_TW进行求解. 在EACO的全局搜索中, 通过加入信息素挥发系数控制因子动态调节信息素挥发系数的取值, 可较好避免算法出现过早收敛, 进而引导算法搜索达到解空间中更多的不同区域. 同时, 为增强EACO的局部搜索能力, 设计一种两阶段变邻域搜索对全局搜索获得的优质解区域进行细致且高效的搜索. 仿真实验和算法比较验证了所提EACO_CD是求解LMHFVRP_TW的有效算法. 对于HFVRP和MHFVRP, 已有的问题分解方法大都将其最终分解为一系列最为简单的单车辆VRP(即标准TSP), 这一分解方式是否合理且唯一, 尚无人探讨. 本文所提的IBKA和HKMA把LMHFVRP_TW有效分解为一系列单车型VRP (即多车辆TSP), 使其子问题具有较大的可行解区域进而适当扩大了算法的实际搜索空间, 取得了更好的效果. 这表明合理选取子问题可在一定程度上提高算法求解性能, 也对复杂车辆路径问题如何进行分解优化设计具有借鉴意义. 后续研究将把EACO_CD和随机处理技术结合, 用于求解动态复杂车辆路径问题.

WeChat 关注分享

返回顶部

目录

    /

    返回文章
    返回