车辆路径问题(Vehicle Routing Problem, VRP)[1]是指:给定若干具有一定需求量的客户,若干具有一定装载能力的车辆从配送中心出发,为客户进行配送服务后回到配送中心,同时使总路程最短、车辆数最少、费用最省等多个目标达到最优。Solomon[2]于1987年首次考虑了带时间窗的VRP(VRP with Time Window, VRPTW),要求提供服务的配送车辆必须在客户满意的时间范围内进行配送。
冷链物流是指货品在生产、运输、销售等环节始终处于规定的低温环境下,以保证货品质量的货物。易腐生鲜货品作为冷链物流中的一部分,其配送成本与冷链物流一样,不仅包括一般配送货品中的运输成本、固定成本等,而且包括在配送过程中为控制车厢温度而增加的制冷成本[3]。本文研究的基于易腐生鲜货品的VRP,相比一般货品的车辆路径问题,该问题的成本构成及客户满意度构成更为复杂,找到高效解决此类问题的方法已成为问题的关键。
本文研究的基于模糊时间窗的多目标车辆路径问题是对基本VRP的拓展,属于NP难题。由于智能启发式算法求解效率高且有在短时间内为大规模优化问题提供满意解的优势,所以更多学者青睐用智能启发式算法求解此类组合优化问题,如粒子群算法[4~5]、遗传算法[6~7]、蚁群算法[8~9]、禁忌搜索算法[10~11]等。Yang[12]受到蝙蝠在高维空间定位、捕猎的启发于2010年提出了蝙蝠算法(Bat Algorithm, BA), 可以应用于各种实际问题求解。Khan等[13]提出了模糊逻辑蝙蝠算法(Fuzzy Logic Bat Algrithm, FLBA)用于办公场所的人因工程研究;Lin等[14]给出了混沌蝙蝠算法(Chaotic Bat Algorithm, CBA)实现线性生态系统中的参数估计;Nakamura等[15]在蝙蝠算法基础上提出进一步研究用于解决特征选择问题的二元蝙蝠算法(Binary Bat Algorithm, BBA);Fister等[16]将蝙蝠算法用于体育训练规划。相应的研究成果表明,相比粒子群算法、遗传算法等,蝙蝠算法具有模型简单、鲁棒性强、收敛性好、适应性强的优点;但是蝙蝠算法作为一种新兴智能启发式算法,在各个领域的应用研究还不完善[17]。本文将在混合蝙蝠算法的基础上进行进一步改进,并将优化结果与基本蝙蝠算法及3种混合蝙蝠算法对比,验证了本文算法对混合蝙蝠算法的改进具有良好的效果。
1 易腐生鲜货品的车辆路径问题 1.1 问题描述基于模糊时间窗的多目标车辆路径问题是在VRP的基础上考虑了软硬时间窗的混合,且通过服务时间对客户满意程度的影响模糊量化的多目标车辆路径问题[18]。
由于本文研究的配送的货物考虑不同种类的生鲜易腐货品,所以相同的运输时间及配送过程中相同的开门次数对不同类型的货品价值,及客户满意度的影响程度不同。所以本文研究的易腐生鲜货品VRP以总客户满意度最高及总成本最低作为优化目标,并满足条件:1) 车辆从配送中心出发,完成其配送路径上的所有任务后必须返回配送中心;2) 配送途中,配送车辆的车载量不能超过配送车辆的最大载重量;3) 所有客户的需求必须得到满足,每个客户仅可以被一辆车服务一次,且一辆车可以服务多个客户;4) 车辆必须在客户允许的时间范围内提供配送服务,即车辆可以早到,但早到车辆必须等待,直到客户允许的最早服务时间才能开始服务,但车辆不可以晚到。
1.2 构建模型 1.2.1 符号定义下面对易腐生鲜货品车辆路径问题数学模型中的符号进行定义:
已知一个配送中心(配送中心用0表示)和n个客户(客户集合N={1, 2, …, n})构成配送网络中的节点集合U(U={0, 1, …, n}),设总的车辆数为K(K={1, 2, …, k});每辆车的最大载重为WE;车辆到达客户的时间ti;客户i允许服务的最早开始时间和最晚开始时间分别为ETi和LTi; 且客户i接受服务的最大容忍时间上下限分别为EETi和ELTi;客户i所需配送的载重、所需服务时间、配送车辆等待服务客户i的时间、客户i对配送服务的满意度分别为wei、Si、wi、μi;车辆的行驶速度、固定成本和单位行驶距离的单位成本分别为v、C1和C2;每吸收千卡路里消耗单位制冷剂的价格为C3;车门关闭和打开时单位时间发生的热负荷分别为Q1、Q2;车辆从客户i到客户j的距离为dij;S表示某一配送车辆的配送客户集合;|S|表示集合S中所包含的顶点个数;P表示配送货品的种类;fp为单位车门打开次数对p类易腐货品客户满意度产生的影响因数;noi表示配送车辆为客户i车门在某次配送中已打开次数;总客户满意度为CS。
决策变量为:
${x_k} = \left\{ \begin{array}{l} 1,\quad 车辆k被征用\\ 0,\quad 其他 \end{array} \right.$ |
${y_{ijk}}{\rm{ = }}\left\{ \begin{array}{l} 1,\quad 线路(i, j)由车辆k服务\\ 0,\quad 其他 \end{array} \right.$ |
本文的最小成本之和的目标建立基于易腐生鲜货品,首先通过分析各项成本,构成最终配送路径上的各项总成本之和。
1) 固定成本。
车辆的固定成本是指车辆的购置、日常的维护,以及人工费用等,且与完成此次配送任务所派出的配送车辆数成正相关。设每辆车的固定成本为C1,总车辆固定成本为TC1,则总车辆的固定成本计算公式为:
$T{C_1}{\rm{ = }}{{\rm{C}}_1}\sum\limits_{j \in N} {\sum\limits_{k \in K} {{y_{0jk}}} } \;\;\;\;$ | (1) |
2) 运输成本。
影响运输成本的因素主要是运输距离,且与运输距离呈正相关关系。假设单位路径运输成本为C2,则总的运输成本计算公式如下:
$T{C_2} = {C_2}\sum\limits_{i \in U} {\sum\limits_{j \in U} {\sum\limits_{k \in K} {{d_{ij}}{y_{ijk}}} } } $ | (2) |
3) 制冷成本。
易腐生鲜货品要求在整个物流配送环节一直处于低温环境来确保货品品质,因此,配送车辆必须通过消耗制冷剂维持低温。这种因制冷增加的成本称为制冷成本。
在整个配送过程中,制冷剂的消耗源于外部环境与配送车厢之间的热量传递,且此热消耗主要分为两种方式:车辆行驶过程中产生的热消耗和车门开启对客户进行服务时产生的热消耗,制冷成本计算公式如下:
$\begin{array}{l} T{C_3}{\rm{ = }}{C_3} \times {Q_1}\left( {\sum\limits_{k \in K} {\sum\limits_{i \in U} {\sum\limits_{j \in U} {{d_{ij}}{y_{ijk}}/v + {w_i}} } } } \right) + \\ \quad \quad \quad {C_3} \times {Q_2}\sum\limits_{i \in U} {{y_{ijk}}{S_i}} \end{array}$ | (3) |
1) 模糊时间窗对客户满意度的隶属函数。
车辆在配送途中,受到各种不确定因素,如交通顺畅度、天气等的影响,导致货物不能在规定的时间内送达客户,而在实际配送过程中,客户一般会接受货物,只是会降低客户满意度,所以硬时间窗VRP不具有一般性。本文所构建的模糊时间窗在原时间窗范围[ETi, LTi]客户的满意度最高为100;超过原时间窗且在[EETi, ELTi]时间窗范围之内, 满意度随时间呈下降趋势,但客户仍可接受服务,体现了软时间窗的特点;一旦超过时间窗最大容忍上限EETi或下限ELTi,客户不接受服务,且客户满意度为0,满足硬时间窗的条件。
对应上述描述,构建的梯形模糊时间窗的客户满意度隶属函数如图 1所示,对应计算式(4)。
${\mu _i}\left( {{t_i}} \right) = \left\{ \begin{array}{l} \frac{{{t_i} - EE{T_i}}}{{E{T_i} - EE{T_i}}} \times 100,\;\;\;\;\;\;{t_i} \in \left[ {EE{T_i},E{T_i}} \right]\\ 100,{\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_i} \in \left[ {E{T_i},L{T_i}} \right]\\ \frac{{EL{T_i} - {t_i}}}{{EL{T_i} - L{T_i}}} \times 100,\;\;\;\;\;\;{t_i} \in \left[ {L{T_i},EL{T_i}} \right]\\ 0,{\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_i} \notin \left[ {EE{T_i},EL{T_i}} \right] \end{array} \right.$ | (4) |
$C{S_1} = \sum\limits_{i \in N} {{\mu _i}} ({t_i})$ | (5) |
2) 车门打开次数对不同类型的生鲜货品的影响。
在对客户进行配送服务途中,对于不同种类的生鲜货品,每打开一次车门,对车厢中尚待配送的货品的品质影响大小不同。所以本文根据车厢门打开次数对货品产生的影响大小将待配送的生鲜货品分成p类,每种货品对应的单位车门开启次数对客户满意度产生的影响因数为fp,基于以上所述,配送途中车厢门打开次数对客户满意度的影响对应计算公式:
$C{S_2} = - \sum\limits_{i \in N} {\sum\limits_{p \in P} {{f_p} \cdot n{o_i}} } $ | (6) |
在满足约束条件下建立的基于易腐生鲜货物的带模糊时间窗的多目标车辆路径问题的数学模型如下:
$\begin{array}{l} \min {\kern 1pt} Z = {{\rm{C}}_1}\sum\limits_{j \in N} {\sum\limits_{k \in K} {{y_{0jk}}} } + {C_2}\sum\limits_{i \in U} {\sum\limits_{j \in U} {\sum\limits_{k \in K} {{d_{ij}}{y_{ijk}}} } } + \\ \quad \quad \quad {C_3} \times {Q_1}\left( {\sum\limits_{k \in K} {\sum\limits_{i \in U} {\sum\limits_{j \in U} {{d_{ij}}{y_{ijk}}/v + \sum\limits_{i \in U} {{w_i}} } } } } \right) + \\ \quad \quad \quad {C_3} \times {Q_2}\sum\limits_{i \in U} {{y_{ijk}}{S_i}} \end{array}$ | (7) |
$\max CS = \sum\limits_{i \in N} {\left( {{\mu _i} - {f_p} \cdot n{o_i}} \right)} $ | (8) |
s.t.
$\sum\limits_{k \in K} {\sum\limits_{j \in N} {{y_{ijk}}} } = 1,\forall i \in U,i \ne j,\;\;i \ne 0$ | (9) |
$\sum\limits_{j \in N} {{y_{0jk}}} = {x_k},\forall k \in K$ | (10) |
$\sum\limits_{j \in N} {{y_{j0k}}} = {x_k},\forall k \in K$ | (11) |
$\sum\limits_{j \in N} {{y_{ijk}}} - \sum\limits_{j \in N} {{y_{jik}}} = 0,\forall i \in N,\forall k \in K$ | (12) |
$\sum\limits_{i \in N} {\sum\limits_{j \in N} {{y_{ijk}}} } w{e_i} \le WE,\forall k \in K$ | (13) |
$\sum\limits_{i,j \in N} {{y_{ijk}}} \le \left| S \right| - 1,\forall k \in K$ | (14) |
$EE{T_i} \le {t_i} + {w_i} \le EL{T_i},\forall i \in N$ | (15) |
模型中,式(7)、(8) 分别表示最小化总成本和最大化客户满意度的目标函数;式(9) 保证所有客户仅被服务一次;式(10) 表示每辆车必须从配送中心出发;式(11) 则表示所有车辆结束其路径上的配送任务后必须返回配送中心;式(12) 保证配送车辆进入某一客户节点后必须从该客户节点离开;式(13) 确保每辆配送车辆服务的所有客户的需求量之和不超过该车的最大承载量;式(14) 为支路消除约束;式(15) 为客户时间窗约束。
2 车辆路径的改进混合蝙蝠算法设计 2.1 经典蝙蝠算法公式蝙蝠是一种神奇的动物,它靠一种神奇的回声定位系统来捕捉猎物,在黑暗中找到自己的栖息地[19]。经典蝙蝠算法是受蝙蝠在搜寻猎物过程中的回声定位行为启发而提出的一种群体智能启发式算法,其思想是利用蝙蝠的回声定位行为搜寻优化空间中的潜在解。
1) 经典蝙蝠的搜索过程。
经典蝙蝠算法的搜索过程实质是通过频率f实现对蝙蝠的移动步伐和范围的控制来更新蝙蝠的速度和位置。假设在t时刻将数量为m的蝙蝠种群散布到d维搜索空间,则编号为i的蝙蝠在位置xi=(xi1, xi2, …, xid)以速度vi=(vi1, vi2, …, vid)随机飞行,通过改变频率fi调整与最优解之间的距离,跟随最优解,则蝙蝠在t+1时刻的位置和速度更新公式如下:
${f_i} = {f_{\min }} + \left( {{f_{\max }} - {f_{\min }}} \right)\beta \;$ | (16) |
$v_i^{t + 1} = v_i^t + \left( {x_i^t - {x_{\rm{*}}}} \right){f_i}$ | (17) |
$x_i^{t + 1} = x_i^t + v_i^{t + 1}$ | (18) |
其中:i=1, 2, …, m;fi∈[fmin, fmax]; 当前位置最优的蝙蝠为x*;β是一个随机因子且β∈[0, 1]。
2) 经典蝙蝠的寻优过程。
另外,与其他智能启发式算法类似,可以设定蝙蝠的寻优行为,当前最优蝙蝠xold通过公式在最优位置附近随机游走产生新位置。
${x_{{\rm{new}}}} = {x_{{\rm{old}}}} + \varepsilon {A^t}$ | (19) |
其中:At表示当前代蝙蝠种群响度的平均值;ε∈[0, 1]是一个随机数。
当蝙蝠找到猎物时,脉冲音强Ai降低,同时脉冲频度ri增加,具体更新公式如下:
$A_i^{t + 1} = \alpha A_i^t$ | (20) |
$\gamma {}_i^{t + 1} = \gamma _i^0\left[ {1 - \exp \left( { - \gamma t} \right)} \right]$ | (21) |
其中,α∈[0, 1], γ>0, 两者均为常量。对于任意α和γ, 当t→∞时有Ait→0、rit→ri0。
2.2 改进混合蝙蝠算法的设计 2.2.1 经典蝙蝠算法的简化经典蝙蝠算法最初用于求解连续型函数优化,而车辆路径问题等实际应用工程问题大多都是组合优化问题,为了使蝙蝠算法在解决组合优化问题时有较好的运算效率,本文采用基于客户编号的编码方式对个体进行编码。且对蝙蝠算法中蝙蝠速度的更新方式作出简化,以编号1~8的客户为例进行编码为例,求出蝙蝠与当前最优解之间对应位不同的数量即汉明距离,作为蝙蝠下一次飞行的速度,过程如图 2所示。
蝙蝠算法对当前最佳位置扰动产生新位置完成局部搜索,这使得进化过程由单一个体引导,容易造成群体多样性不足。在求解组合优化问题时,这种缺陷体现为蝙蝠个体之间与精英个体(最优解)之间的群体智能作用表现不明显,因此,引入精英片段保留策略,以编号1~8的客户为例,基本操作为:X*为精英个体,随机截取编码序列片段A,将精英片段A接入Xit编码尾部,同时将原Xit中与A重复的客户编码删除,得到基于精英的新蝙蝠个体Xit+1,过程如图 3所示。
为了蝙蝠个体能够有效地进行邻域搜索,使得在当前蝙蝠种群的最优个体搜寻到更好的解,本文设计出单亲遗传选择性单、多点变异操作,用最优解对每个蝙蝠个体进行引导,最优个体也随着进化的进行不断更新,种群在多个精英个体领导下,可以避免陷入局部最优。同样以编号为1~8的客户为例,首先求出当前蝙蝠与最优蝙蝠之间的汉明距离:如果汉明距离大于n/2,随机选出当前蝙蝠的一对位点,交换对位点上的解完成单点变异操作;如果汉明距离小于等于n/2,随机选出当前蝙蝠解的两对位点,交换对位点上的解完成多点变异操作。选择性变异策略过程如图 4所示。
针对组合优化的特点,本文首先对基本蝙蝠算法进行简化,并采用精英片段保留策略和单亲遗传算法中的单(多)点变异策略,较好地克服了蝙蝠算法在求解类似于车辆路径这种离散型函数问题的局限性。
设计的改进混合蝙蝠算法具体步骤如下:
步骤1 初始化各参数,确定蝙蝠种群的数量m;最大迭代次数Itermax;蝙蝠种群的位置Bi(i=1, 2, …, m)。
步骤2 通过路径约束、车载量限制、服务约束等确定每只蝙蝠路径上的配送车辆和所有配送车辆的路径,根据目标函数,找出适应度值最小的函数,确定为当前最优蝙蝠。
步骤3 将当前最优解的客户排列编码视为精英个体,并将精英片段与当前所有蝙蝠个体进行交叉,删除重复客户编号,形成基于精英进化的新蝙蝠。
步骤4 排列现有所有蝙蝠(解),并更新当前最优解B*。
步骤5 计算当前蝙蝠与最优蝙蝠的汉明距离,进行局部搜索:如果((rand>ri) & (Vit>n/2))(随机数rand∈[0, 1)),在最优解周围通过单亲遗传多点变异产生新解;否则((rand>ri) & (Vit≤n/2)), 则利用单亲遗传单点变异产生新解。
步骤6 平衡局部搜索和全局搜索机制:如果((rand < Ai) & (f(Bi) < f(B*))),接受Bi这个新解,并增大ri,减小Ai。
步骤7 排列现有所有蝙蝠(解),并更新当前最优解B*。
步骤8 令Iter=Iter+1,如果Iter < Itermax,返回步骤3。
改进混合蝙蝠算法框图如图 5所示。
在实际编码过程中本文将蝙蝠的位置及位置的优劣分别与它所代表的解、目标函数的大小建立对应关系:1) 将客户编号随机排列(视为当前蝙蝠的位置);2) 按随机排列的顺序,派出车辆对第一个客户进行服务,同时更新配送车辆实时载重、当前时间、已开门次数;3) 计算当前客户满意度、当前车辆累计消耗成本;4) 对第二个客户进行配送,根据测试算例设定的车辆载重限制值,当前客户配送时间窗的最大容忍上下限值等约束条件确定该配送车辆是否适合对该客户进行配送,一旦约束条件不满足当即从配送中心重新派车对该客户进行服务;5) 下一客户同理判定是否需新增车辆进行配送,最终确定路线,并计算目标函数值(判断当前蝙蝠位置优劣)。另外,本文对多目标函数通过目标线性加权和法处理转换成单目标求最小值。
3 实验结果与分析文献[18]求解了带软、硬时间窗客户的VRP,本文也采用该实例部分数据进行实验,如表 1所示;并将本文研究的单位车门打开次数对p类易腐货品客户满意度产生的影响添加入算例,来验证本文设计的改进混合蝙蝠算法在求解VRP的有效性。
测试算例中各参数设定情况如下:车辆的最大载重量WE为30 t,行驶速度为60 km/h,车辆向15个客户提供配送服务,考虑避开交通拥堵高峰时段,设开始工作时间为早上6:00,晚18:00停止工作,所有配送车辆于18:00之前返回配送中心。此外,单位车辆派遣成本C1=200元; 单位距离每km运费C2=3元;单位制冷剂价格C3=0.2元/kCal;冷藏车车门关闭时发生的热负荷Q1=48 kCal/h;冷藏车车门开启时发生的热负荷Q2=60 kCal/h。要求合理安排路线,使得完成所有配送任务之后,总成本最少,总客户满意度最高。配送中心与客户需求点数据如表 1所示,将货品类型1~3按照随机生成类型1、2、3添加入算例。
3.2 计算结果分析为了验证本文改进过后的混合蝙蝠算法较混合蝙蝠算法及基本蝙蝠算法在求解车辆路径问题的有效性,本文利用Matlab R2010a对基本蝙蝠算法(基本)、精英遗传混合蝙蝠算法[20](精英混合)、单亲单点重组精英遗传混合蝙蝠算法[20](单点+精英)、单亲多点重组精英遗传混合蝙蝠算法[20](多点+精英)、改进混合蝙蝠算法(改进混合)等5种算法进行编程实现,5种算法在Intel Core i5-5200U 2.19 GHz(4.00 GB RAM),操作系统为Win 10的环境下进行。考虑到本文选取的算例为中小型算例,为了避免蝙蝠算法中的最大频率和初始蝙蝠响度值Qmax、A0选值不当出现算法无法收敛、收敛过快或全局部搜索不和谐等问题,本文选取文献[20]的最大声波频率值和蝙蝠音量值,且∂、γ值选取基本蝙蝠算法经验值。算法具体设置参数如下:Qmax=10,Qmin=0,∂=0.9, γ=0.9,蝙蝠的初始响度A0∈[0, 1],初始脉冲发生率r0∈[0, 1],蝙蝠种群数n=30,Itermax=500。其中,基本蝙蝠算法种群数为60,改进混合蝙蝠算法种群数为20。
表 2~3数据皆为算法随机运行10次所有解数据记录和计算得出。表 2为用本文设计的改进混合蝙蝠算法求解得到的最佳配送路径线路表;表 3为根据求解结果进行实际配送所消耗的成本和客户满意度等的数据结果。
由表 3可见,改进混合蝙蝠算法在更短的求解时间内减小了此次配送任务的总成本,同时提高了客户满意度。为进一步验证本文设计的改进混合蝙蝠算法的有效性,以本文的改进混合蝙蝠算法各结果数值为基数1,计算出该算法与其他蝙蝠算法[20]结果提高的百分比,计算提高结果如表 4所示。
由表 4可知,改进后的混合蝙蝠算法在平均客户满意度上的提高均大于1.60%,最大提高了4.20%;在平均总成本方面减小多于0.68%。所以,本文所提算法比基本蝙蝠算法、混合蝙蝠算法具有更好的搜索性能和稳定性。
易腐生鲜货品车辆路径问题的关键在于保证货品品质的的基础上节约成本,而在实际配送过程中也应充分考虑客户对不同生鲜货品的品质要求及配送服务时间要求,本文在考虑客户软、硬时间窗的同时将生鲜货品分类,最大化满足客户需求,提高客户满意度。
另外,本文算法针对组合优化特点,对原有混合蝙蝠算法速度更新算子进行精简,并将单点重组精英遗传算子和多点重组精英遗传算子进行选择性调用,提高了算法运算效率。实例对本文算法、基本蝙蝠算法及文献[20]中的3种蝙蝠算法进行测试,测试结果表明,改进混合蝙蝠算法在确保种群多样性的基础上,平衡了全局与局部搜索的能力,全面提高了混合蝙蝠算法的计算速率和计算效果,同时具有更高的稳定性。在实际应用中,易腐生鲜货品车辆路径问题有求解规模大的特点,如何进一步提高算法求解大规模算例是下一步研究的重点。
[1] | 刘云, 张惠珍. 多目标带时间窗的车辆路径问题的单亲遗传混合蚁群算法[J]. 公路交通科技, 2016, 33(6): 95-100. (LIU Y, ZHANG H Z. A partheno-gentic hybrid ant colony algorithm for solving multi-objective vehicle routing problem with time window[J]. Journal of Highway and Transportation Research and Development, 2016, 33(6): 95-100.) |
[2] | SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254-265. DOI:10.1287/opre.35.2.254 |
[3] | 马向国, 刘同娟, 杨平哲, 等. 基于随机需求的冷链物流车辆路径优化模型[J]. 系统仿真学报, 2016, 28(8): 1824-1832. (MA X G, LIU T J, YANG P Z, et al. Vehicle routing optimization model of cold chain logistic based on stochastic demand[J]. Journal of System Simulation, 2016, 28(8): 1824-1832.) |
[4] | MARINAKIS Y, MAGDALENE M. A hybrid particle swarm optimization algorithm for the open vehicle routing problem[C]//Proceedings of the 20108th International Conference on Swarm Intelligence, LNCS 7461. Berlin:Springer, 2010:180-187. |
[5] | 陈玉光, 陈志祥. 基于准时送货和最小耗油的配送车辆路径问题研究[J]. 中国管理科学, 2015, 23(S1): 156-164. (CHEN Y G, CHEN Z X. Study on the vehicle routing problem with objectives of on-time delivery and oil consumption minimization[J]. Chinese Journal of Management Science, 2015, 23(S1): 156-164.) |
[6] | URSANI Z, ESSAM D, CORNFORTH D, et al. Localized genetic algorithm for vehicle routing problem with time windows[J]. Applied Soft Computing, 2011, 11(8): 5375-5390. DOI:10.1016/j.asoc.2011.05.021 |
[7] | GHOSEIRI K, GHANNADPOUR S F. Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm[J]. Applied Soft Computing, 2010, 10(4): 1096-1107. DOI:10.1016/j.asoc.2010.04.001 |
[8] | 何小锋, 马良. 带时间窗车辆路径问题的量子蚁群算法[J]. 系统工程理论与实践, 2013, 33(5): 1255-1261. (HE X F, MA L. Quantum-inspired ant colony algorithm for the vehicle routing problem with time windows[J]. Systems Engineering-Theory & Practice, 2013, 33(5): 1255-1261. DOI:10.12011/1000-6788(2013)5-1255) |
[9] | 段征宇, 杨东援, 王上. 时间依赖型车辆路径问题的一种改进蚁群算法[J]. 控制理论与应用, 2010, 27(11): 1557-1563. (DUAN Z Y, YANG D Y, WANG S. Improved ant colony optimization algorithm for time-dependent vehicle routing problem[J]. Control Theory & Application, 2010, 27(11): 1557-1563.) |
[10] | RENAUD J, LAPORTE G, BOCTOR F F. A tabu search heuristic for the multi-depot vehicle routing problem[J]. Computers & Operations Research, 1996, 23(3): 229-235. |
[11] | 程碧荣, 赵晓波, 秦进. 考虑供应不足的应急物流车辆路径优化模型及算法[J]. 计算机应用研究, 2016, 33(6): 1682-1685. |
[12] | YANG X S. A New Metaheuristic Bat-Inspired Algorithm[M]//Nature Inspired Cooperative Strategies for Optimization. Berlin:Springer, 2010:65-74. |
[13] | KHAN K, NIKOV A, SAHAI A. A fuzzy bat clustering method for ergonomic screening of office workplaces[C]//Proceedings of the 2011 Third International Conference on Software, Services and Semantic Technologies, AINSC 101. Berlin:Springer, 2011:59-66. |
[14] | LIN J H, CHOU C W, YANG C H, et al. A chaotic levy flight bat algorithm for parameter estimation in nonlinear dynamic biological systems[J]. Journal of Computer and Information Technology, 2012, 2(2): 56-63. |
[15] | NAKAMURA R Y M, PEREIRA L A M, COSTA K A, et al. BBA:a binary bat algorithm for feature selection[C]//Proceedings of the 201225th SIBGRAPI Conference on Graphics, Patterns and Images. Piscataway, NJ:IEEE, 2012:291-297. |
[16] | FISTER I, RAUTER S, YANG X S, et al. Planning the sports training sessions with the bat algorithm[J]. Neurocomputing, 2015, 149(PB): 993-1002. |
[17] | 杨鹏, 邹浩, 徐贤浩. 带时间窗集送货需求可分车辆路径问题的改进蚁群算法[J]. 系统工程, 2015, 33(9): 58-62. (YANG P, ZOU H, XU X H. Improved ant colony algorithm for vehicle routing problem with time windows and split pickups and deliveries[J]. Systems Engineering, 2015, 33(9): 58-62.) |
[18] | 杨翔, 范厚明, 张晓楠, 等. 基于模糊时间窗的多中心开放式车辆路径问题[J]. 计算机集成制造系统, 2016, 22(7): 1768-1778. (YANG X, FAN H M, ZHANG X N, et al. Optimization of multi-deport open vehicle routing problem with fuzzy time window[J]. Computer Integrated Manufacturing Systems, 2016, 22(7): 1768-1778.) |
[19] | 李枝勇, 马良, 张惠珍. 蝙蝠算法在多目标多选择背包问题中的应用[J]. 计算机仿真, 2013, 30(10): 350-353. (LI Z Y, MA L, ZHANG H Z. Application of bat algorithm in multi-objective and multi-choice knapsack problem[J]. Computer Simulation, 2013, 30(10): 350-353. DOI:10.3969/j.issn.1006-9348.2013.10.080) |
[20] | 殷亚, 张惠珍. 求解带硬时间窗的多目标车辆路径问题的多种混合蝙蝠算法[J]. 计算机应用研究, 2017, 34(12): 1-7. (YIN Y, ZHANG H Z. Multi-hybrid bat algorithm for solving multi-objectives vehicle routing problem with hard time window[J]. Application Research of Computers, 2017, 34(12): 1-7.) |