Application Research on Vehicle Routing Problem With Time Windows Based on Dynamic Ant Algorithm

Abstract

Ant algorithm is a newly emerged stochastic searching optimization algorithm in recent years. It has been paid much attention to since the successful application in the famous traveling salesman problem. This paper further extends the idea of this new biological optimization strategy to vehicle routing problem with time windows in logistic management and designs a new kind of dynamic ant algorithm. The ability of optimization of this new ant algorithm is tested through numerical computation which gives encouraging results.

Content

《1 引言》

1 引言

蚁群算法 (ant algorithm) 是一种源于大自然中生物世界的新的仿生类算法 ^[1], 诞生至今只有短短的十几年时间。作为通用型随机优化算法, 它吸收了昆虫王国中蚂蚁的行为特性, 通过其内在的搜索机制, 在一系列困难的组合优化问题求解中取得了成效。由于模拟仿真中使用的是人工蚂蚁概念, 因此有时亦称为蚂蚁系统。

据昆虫学家的观察和研究, 发现生物世界中的蚂蚁有能力在没有任何可见提示下找出从其窝巢至食物源的最短路径, 并且能随环境的变化而变化, 适应性地搜索新的路径, 产生新的选择。作为昆虫的蚂蚁在寻找食物源时, 能在其走过的路径上释放一种蚂蚁特有的分泌物——信息激素 (pheromone) , 使得一定范围内的其他蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径上通过的蚂蚁越来越多时, 其留下的信息素轨迹 (trail) 也越来越多, 以致信息素强度增大 (当然, 随时间的推移会逐渐减弱) , 后来蚂蚁选择该路径的概率也越高, 从而更增加了该路径的信息素强度, 这种选择过程被称为蚂蚁的自催化行为 (autocatalytic behavior) 。由于其原理是一种正反馈机制, 因此, 也可将蚂蚁王国 (ant colony) 理解成所谓的增强型学习系统 (reinforcement learning system) 。

自从蚁群算法在著名的旅行商问题 ^[2] 上取得成效以来, 已陆续渗透到其他问题的求解上。笔者将这种新型的生物优化思想扩展到物流管理中的带时间窗车辆路径问题, 从数值计算上探索了蚁群算法的优化能力, 获得了满意的效果。

《2 基本蚁群算法原理》

2 基本蚁群算法原理

用于优化领域的人工蚁群算法, 其基本原理吸收了生物界中蚂蚁群体行为的某些显著特征:a. 能察觉小范围区域内的状况并判断出是否有食物或其他同类的信息素轨迹;b. 能释放自己的信息素;c. 所遗留的信息素数量会随时间而逐步减少。由于自然界中的蚂蚁基本没有视觉, 既不知向何处去寻找和获取食物, 也不知发现食物后如何返回自己的巢穴, 因此它们仅仅依赖于同类散发在周围环境中的特殊物质——信息素的轨迹, 来决定自己何去何从。有趣的是, 尽管没有任何先验知识, 但蚂蚁们还是有能力找到从其巢穴到食物源的最佳路径, 甚至在该路线上放置障碍物之后, 它们仍然能很快重新找到新的最佳路线。这里, 用一个形象化的图示来说明蚂蚁群体的路径搜索原理和机制 ^[3]:

假定障碍物的周围有两条道路可从蚂蚁的巢穴到达食物源 (见图1) :Nest—ABD—Food和Nest—ACD—Food, 分别具有长度4和6。蚂蚁在单位时间内可移动一个单位长度的距离。开始时所有道路上都未留有任何信息素。

《图1》

图1 蚂蚁从巢穴移至食物源

Fig.1 Ants move to food resource from nest

在t=0时刻, 20只蚂蚁从巢穴出发移动到A。它们以相同概率选择左侧或右侧道路, 因此平均有10只蚂蚁走左侧, 10只走右侧。

在t=4时刻, 第一组到达食物源的蚂蚁将折回。

在t=5时刻, 两组蚂蚁将在D点相遇。此时BD上的信息素数量与CD上的相同, 因为各有10只蚂蚁选择了相应的道路。从而有5只返回的蚂蚁将选择BD而另5只将选择CD。

在t=8时刻, 前5只蚂蚁又返回巢穴, 而AC, CD和BD上各有5只蚂蚁。

在t=9时刻, 前5只蚂蚁又回到A并且再次面对往左还是往右的选择。

这时, AB上的轨迹数是20而AC上是15, 因此增强了该路线的信息素。随着该过程的继续, 两条道路上信息素数量的差距将越来越大, 直至绝大多数蚂蚁都选择了最短的路线。正是由于一条道路要比另一条道路短, 因此, 在相同的时间区间内, 短的路线会有更多的机会被选择。记:

m为蚂蚁个数

η_ij为边弧 (i, j) 的能见度 (visibility) , 即1/d_ij;

τ_ij为边弧 (i, j) 的轨迹强度 (intensity) ;

Δτ $_{i j}^{k}$ $_{i j}^{k}$ 为蚂蚁k于边弧 (i, j) 上留下的单位长度轨迹信息素数量;

P $_{i j}^{k}$ $_{i j}^{k}$ 为蚂蚁k的转移概率, 与τ $_{i j}^{α}$ $_{i j}^{α}$ ·η $_{i j}^{β}$ $_{i j}^{β}$ 成正比, j是尚未访问节点。

轨迹强度的更新方程为

$τ_{i j}^{n e w} = ρ τ_{i j}^{o l d} + \sum_{k} Δ τ_{i j}^{k} (1)$ $τ_{i j}^{n e w} = ρ τ_{i j}^{o l d} + \sum_{k} Δ τ_{i j}^{k} (1)$

其中各参数的含义为:

α为轨迹的相对重要性 (α≥0) ;

β为能见度的相对重要性 (β≥0) ;

ρ为轨迹的持久性 (0≤ρ<1) , 1-ρ理解为轨迹衰减度 (evaporation) 。

算法中的参数设定目前尚无理论上的依据, 已公布的试验结果都是针对特定问题而言的。针对车辆路径问题 (VRP) 本身的特点, 可定义如下形式的转移概率 ^[3]:

$Ρ_{i j} = \frac{τ_{i j}^{α} η_{i j}^{β} μ_{i j}^{γ} Κ_{i j}^{λ}}{\sum_{h} τ_{i h}^{α} η_{i h}^{β} μ_{i h}^{γ} Κ_{i h}^{λ}} (2)$ $Ρ_{i j} = \frac{τ_{i j}^{α} η_{i j}^{β} μ_{i j}^{γ} Κ_{i j}^{λ}}{\sum_{h} τ_{i h}^{α} η_{i h}^{β} μ_{i h}^{γ} Κ_{i h}^{λ}} (2)$

其中μ_ij=d_i0+d_j0-d_ij, k_ij= (Q_i+q_j) /Q, Q为体现蚂蚁所留轨迹数量的一个常数。

采用人工蚂蚁方法进行求解的主要步骤如下:

Step 1 n_c←0 (n_c为迭代步数或搜索次数) , 各τ_ij和Δτ_ij初始化, 将m个蚂蚁置于n个顶点上;

Step 2 将各蚂蚁的初始出发点置于当前解集中, 对每个蚂蚁k (k=1, 2, …, m) , 按概率P $_{i j}^{k}$ $_{i j}^{k}$ 移至下一顶点j, 将顶点j置于当前解集中;

Step 3 计算各蚂蚁的目标函数值Z_k (k=1, 2, …, m) , 记录当前的最好解;

Step 4 按更新方程修改轨迹强度;

Step 5 对各边弧 (i, j) , 置Δτ_ij←0, n_c←n_c+1;

Step 6 若n_c小于预定的迭代次数且无退化行为 (即找到的都是相同解) , 则转Step 2。

算法的时间复杂度为0 (n_cmn²) 。

《3 动态蚁群算法》

3 动态蚁群算法

动态蚁群算法相对于基本蚁群算法, 主要改进有以下几点。基本蚁群算法依据信息素和启发函数选择目标城市。如何依据这两个因子选择城市对算法的性能是非常关键的。动态蚂蚁在迭代过程中, 在选择目标城市的标准时, 不是使用一个固定的标准, 使之有利于减小进化停滞现象。在基本蚁群算法中, 对信息素的强度没有限制, 因而易陷入局部最优点。动态蚁群算法对信息素的强度给予一定的限制, 从而大大改善了算法的性能。动态蚁群算法中挥发因子是动态变化, 信息素浓度越高挥发因子越大, 浓度越低挥发因子越小, 这样对信息素浓度也进行限制, 使信息素不可能无限增大, 也不可能为零。基本蚁群算法中仅有最好蚂蚁所走路径上的信息素进行全局更新, 如果能对更多路径上的信息素进行更新, 则有可能加快演化的速度。

基本蚁群算法依据[τ (r, s) ]^α [η (r, s) ]^β来选择下一个转移城市, α, β 是常数。在自然界中生物随着时间的推移对环境适应之后, 不再对环境敏感。基于此原理, 可认为蚂蚁随着时间的推移对信息素慢慢变得不敏感。在算法中体现为, [τ (r, s) ]^α随着时间相对于 [η (r, s) ]^β减小, 这样信息素的影响减小了, 而启发函数的影响相对加大, 这样, α, β 由常数就变为与时间有关的函数。在旅行商问题 (TSP) 中η (r, s) =1/d_rs, d_rs是城市r和城市s之间的距离。为简化计算, 置α=1, 而β按迭代次数进行如下变化。

1～mn/3次迭代β=5;mn/3～mn/2次迭代β=4;mn/2～2mn/3次迭代β=3;2mn/3～mn次β=2;mn是总的迭代次数。循环次数固定为10 000次。

在基本蚁群算法中, 挥发因子是一个常数。而在真实世界中, 信息素浓度越高, 挥发越快, 信息素浓度越低, 挥发越慢, 这样可以防止信息浓度无限制地增长, 或者变为零, 减小陷入局部最优的可能。在这种情况下挥发因子由常数变成以τ (r, s) 为变量的函数。

局部信息素更新规则变为

$\begin{array}{l} τ (r, s) \leftarrow (1 - ρ (τ (r, s)) τ (r, s) + \\ c o e (τ (r, s)) Δ τ (3) \end{array}$ $\begin{array}{l} τ (r, s) \leftarrow (1 - ρ (τ (r, s)) τ (r, s) + \\ c o e (τ (r, s)) Δ τ (3) \end{array}$

挥发函数对算法的性能有直接的影响, 在实验中曾试过如图2所示4种类型函数 (X轴为浓度, Y轴为挥发因子) , 实验表明图2d所对应的挥发函数的效果比较好。

基本蚁群算法仅对最好路径上的信息素进行全局更新, 仅有一只蚂蚁对全局信息素的更新产生影响。如果有多只蚂蚁对全局信息素的更新产生影响, 则可加速演化过程。更新规则如下:

$\begin{array}{l} τ (r, s) \leftarrow (1 - α (τ (r, s)) τ (r, s) + \\ c o e (τ (r, s)) Δ τ (r, s) (4) \end{array}$ $\begin{array}{l} τ (r, s) \leftarrow (1 - α (τ (r, s)) τ (r, s) + \\ c o e (τ (r, s)) Δ τ (r, s) (4) \end{array}$

《图2》

图2 信息素浓度与挥发系数函数关系

Fig.2 Function relationship between pheromone density and volatility coefficient

对两只蚂蚁所走路径上的信息素进行更新, 即对最好路径及最差路径上的信息素进行全局更新, 则参数

$c o e = {\begin{matrix} C & (r, s) \in g l o b a l - b e s t - t o u r \\ - C & (r, s) \in g l o b a l - b e s t - t o u r \\ 0 & (r, s) \in t h e - o t h e r \end{matrix} (5)$ $c o e = {\begin{matrix} C & (r, s) \in g l o b a l - b e s t - t o u r \\ - C & (r, s) \in g l o b a l - b e s t - t o u r \\ 0 & (r, s) \in t h e - o t h e r \end{matrix} (5)$

式 (4) 变为

$\begin{array}{l} τ (r, s) \leftarrow (1 - α (τ (r, s)) τ (r, s) + \\ C Δ τ (r, s) ∶ b e s t (6) \\ τ (r, s) \leftarrow (1 - α (τ (r, s)) τ (r, s) + \\ C Δ τ (r, s) ∶ w o r s t (7) \end{array}$ $\begin{array}{l} τ (r, s) \leftarrow (1 - α (τ (r, s)) τ (r, s) + \\ C Δ τ (r, s) ∶ b e s t (6) \\ τ (r, s) \leftarrow (1 - α (τ (r, s)) τ (r, s) + \\ C Δ τ (r, s) ∶ w o r s t (7) \end{array}$

其中

$Δ τ (r, s) = {\begin{cases} (L_{g b})^{- 1} ‚ i f (r, s) \in g l o b a l - b e s t - t o u r \\ (L_{g w})^{- 1} ‚ i f (r, s) \in g l o b a l - w o r s t - t o u r \end{cases} (8)$ $Δ τ (r, s) = {\begin{cases} (L_{g b})^{- 1} ‚ i f (r, s) \in g l o b a l - b e s t - t o u r \\ (L_{g w})^{- 1} ‚ i f (r, s) \in g l o b a l - w o r s t - t o u r \end{cases} (8)$

L_gb是最好蚂蚁所走路径长度, L_gw是最差蚂蚁所走路径长度, α (τ (r, s) ) 是全局信息素挥发因子。

《4 带时间窗车辆路径问题》

4 带时间窗车辆路径问题

在许多物流配送系统中, 管理者们需要采取有效的配送策略以提高服务水平、降低货运费用。其中车辆路径问题是亟待解决的一个重要问题, 此问题可描述如下:有一个货物需求点 (或称顾客) , 已知每个需求点的需求量及位置, 至多用K辆汽车从中心仓库 (或配送中心) 到达这批需求点, 每辆汽车载重量一定, 安排汽车路线使运距最短且满足每条路线不超过汽车载重量和每个需求点的需求量必须且只能由一辆汽车来满足的约束条件。车辆路径问题是一个NP完全问题, 只有在需求点数和路段数较少时才有可能寻求其精确解。带时间窗车辆路径问题 (VRPTW, vehicle routing problem with time windows) 是在车辆路径问题上加了客户要求访问的时间窗口。由于在现实生活中许多问题都可以归结为VRPTW来处理, 但处理的好坏将直接影响到一个企业的效益和顾客的服务质量, 所以对它的研究越来越受到人们的重视, 目前对它的求解主要集中在启发式算法上。

20世纪90年代后, 遗传算法、禁忌搜索算法、模拟退火算法和人工神经网络算法等启发式算法的出现, 为求解VRPTW提供了新的工具。文献[4,5,6]用遗传算法求解了VRPTW;文献[7,8,9]用网络启发式算法、分派启发式算法和C-W算法求解了VRPTW;文献[10]用一种修正的最近距离搜索启发式算法求解了VRPTW。但是, 遗传算法存在“早熟性收敛”问题, 其他算法也存在一些不尽人意的地方。如何针对带时间窗车辆路径问题的特点, 构造运算简单、寻优性能优异的启发式算法, 这不仅对于物流配送系统而且对于许多可转化为带时间窗车辆路径问题求解的优化组合问题均具有十分重要的意义。笔者运用蚁群算法求解带时间窗车辆路径问题, 并对其运算过程和结果进行分析。实际数据表明蚁群算法行之有效, 不失为一种求解带时间窗车辆路径问题的性能优越的启发式算法。

带时间窗车辆路径问题可描述如下:给定车辆集合V, 分店集合C和有向图G。此有向图有|C|+2个顶点, 顶点1, 2, …, n表示分店, 顶点0表示离开时的中心仓库, 顶点n +1表示返回时的中心仓库, 把顶点0, 1, …, n +1记作集合N。分店之间以及分店与中心仓库之间的弧记作集合A, 并且没有弧开始于n+1顶点, 也没有弧终止于0顶点, 每条弧 (i, j) 对应一个物耗值c_ij和一个时间值t_ij。每辆车有一个容量q, 每个分店i有一个需求d_i和一个时间窗口[a_i, b_i], 这个时间窗口说明车辆必须在b_i之前到达分店i, 在a_i之前车辆虽然可以到达分店i, 但是车辆必须等待而不能马上为分店服务。中心仓库也有一个时间窗口[a₀, b₀], 这个时间窗口说明车辆在a₀之前不能离开中心仓库, 并且必须在b₀或之前返回中心仓库。在这里, 假设q, a_i, b_i, d_i 和c_ij是非负整数, t_ij是正整数。

对于每条弧 (i, j) (i≠j, i≠n+1, j≠0) 和车辆k定义变量x_ijk:

$x_{i j k} = {\begin{cases} 0 如果车辆 k 没有从节点 i 到达节点 j ‚ \\ 1 如果车辆 k 从节点 i 到达节点 j 。 \end{cases}$ $x_{i j k} = {\begin{cases} 0 如果车辆 k 没有从节点 i 到达节点 j ‚ \\ 1 如果车辆 k 从节点 i 到达节点 j 。 \end{cases}$

对于每个分店i和车辆k定义变量s_ik, 它表示车辆k在s_ik开始对分店i进行访问, 如果车辆k不访问分店i, 则s_ik不表示任何意义。假设a₀=0, 这样对于所有的车辆k, s_0k=0。对于每辆车, 设计一条费用最小的路径, 此路径开始于顶点0, 终止于顶点n+1, 同时还要保证每个分店被精确地访问一次, 但不能违背各时间窗口和车辆的能力约束。

经上述描述, VRPTW的数学模型可以表示为:

$\min \sum_{k \in V} \sum_{i \in Ν} \sum_{j \in Ν} c_{i j} x_{i j k} (9)$ $\min \sum_{k \in V} \sum_{i \in Ν} \sum_{j \in Ν} c_{i j} x_{i j k} (9)$

$\begin{array}{l} s . t . ∶ \sum_{k \in V} \sum_{j \in Ν} x_{i j k} = 1 ‚ \forall i \in Ν (10) \\ \sum_{i \in Ν} d_{i} \sum_{j \in Ν} x_{i j k} \leq q, \forall k \in Κ (11) \\ \sum_{j \in Ν} x_{0 j k} = 1 ‚ \forall k \in V (12) \\ \sum_{i \in Ν} x_{i h k} - \sum_{j \in Ν} x_{h j k} = 0 ‚ \forall k \in V, \forall h \in C (13) \\ \sum_{i \in Ν} x_{i, n + 1, k} = 1, \forall k \in V (14) \\ s_{i k} + t_{i j} - Κ (1 - x_{i j k}) \leq s_{j k}, \\ \forall k \in V, \forall i, j \in Ν (15) \\ a_{i} \leq s_{i k} \leq b_{i}, \forall k \in V, \forall i \in Ν (16) \\ x_{i j k} \in {0, 1}, \forall k \in V, \forall i, j \in Ν (17) \end{array}$ $\begin{array}{l} s . t . ∶ \sum_{k \in V} \sum_{j \in Ν} x_{i j k} = 1 ‚ \forall i \in Ν (10) \\ \sum_{i \in Ν} d_{i} \sum_{j \in Ν} x_{i j k} \leq q, \forall k \in Κ (11) \\ \sum_{j \in Ν} x_{0 j k} = 1 ‚ \forall k \in V (12) \\ \sum_{i \in Ν} x_{i h k} - \sum_{j \in Ν} x_{h j k} = 0 ‚ \forall k \in V, \forall h \in C (13) \\ \sum_{i \in Ν} x_{i, n + 1, k} = 1, \forall k \in V (14) \\ s_{i k} + t_{i j} - Κ (1 - x_{i j k}) \leq s_{j k}, \\ \forall k \in V, \forall i, j \in Ν (15) \\ a_{i} \leq s_{i k} \leq b_{i}, \forall k \in V, \forall i \in Ν (16) \\ x_{i j k} \in {0, 1}, \forall k \in V, \forall i, j \in Ν (17) \end{array}$

在上述表达式中, 约束条件式 (10) 表达了每个分店仅能被访问一次;式 (11) 表达了被调用的车辆都满足能力约束条件;式 (12) 和式 (13) 保证了每辆车始于中心仓库, 访问分店后, 最终回到中心仓库;不等式 (15) 表达了车辆k在从i分店向j分店行驶的过程中, 在s_ij + t_ij之前不能到达分店j, 其中k 是一个较大的标量;约束条件式 (16) 表达了在车辆的行驶过程中, 要满足时间窗的约束;条件式 (17) 是整数化的约束。

这个模型通用性很强, 经过参数的不同设定, 可以将其转换为其他组合优化问题的数学模型。如果设a_i=0, b_i=M (M是一个很大的数) , 则可以把时间约束式 (15) 和式 (16) 去掉, 这样, VRPTW模型就变成了普通的VRP模型;如果仅有一辆车被利用, 则该问题就变成了旅行商问题;如果有多辆车被利用, 并且附加条件c_0j=1, j∈C和c_ij=0, 就得到了装箱问题的数学模型。如果去掉能力约束式 (11) , 则该模型就变成了m-TSPTW模型;如果仅有一辆车被利用, 又变成了TSPTW模型;如果去掉约束式 (10) , 则模型变成了基本的有时间窗和能力约束的最短路径问题, 由于所有的车辆均相同, 所以每辆车的最短路径也是相同的。

《5 数值计算结果》

5 数值计算结果

在实验中选择的参数如下:

m=10, coe (τ (r, s) ) =0.1, C=0.1, a=l, α (τ (r, s) ) =0, δ=0.5, 迭代次数mn=10 000, 挥发函数选择如图2d所示函数。

有8个分店和1个配送中心, 各分店的需求量为d_ij (i=1, 2, …, 8) (t) , 装货 (卸货) 时间T_i (h) 以及分店要求的服务时间范围[a_i, b_i]由表1给出。这些分店由容量为8 t的车辆完成配送, 配送中心与各分店的距离 (km) 由表2给出。要求合理安排车辆的行驶路线, 使总的运距最短。

表1 任务的特征及需求 ^[4]

Table 1 Christeristics and demand of task

《表1》

分店	1	2	3	4	5	6	7	8
需求/t	2	1.5	4.5	3	1.5	4	2.5	3
时间T/h	1	2	1	3	2	2.5	3	0.8
时间窗/h	[1, 4]	[4, 6]	[1, 2]	[4, 7]	[3, 5]	[2, 5]	[5, 8]	[1, 5]

表2 分店间及分店与配送中心的距离 ^[4]

Table 2 Distance among branches & distance between distributive center and branches km

《表2》

分店	0	1	2	3	4	5	6	7	8
0	0	40	60	75	90	200	100	160	80
1	40	0	65	40	100	50	75	110	100
2	60	65	0	75	100	100	75	75	75
3	75	40	75	0	100	50	90	90	150
4	90	100	100	100	0	100	75	75	100
5	200	50	100	50	100	0	70	90	75
6	100	75	75	90	75	70	0	70	100
7	160	110	75	90	75	90	70	0	100
8	80	100	75	150	100	75	100	100	0

计算结果见表3, 可见, 运用动态蚁群算法求解的结果优于节约法、分派算法和遗传算法, 不失为带时间窗车辆路径问题一个较优的满意解, 不难看到蚁群算法在大多数情况下比其他算法具有较好的寻优效果。

表3 优化结果比较

Table 3 Comparison of Optimization Results

《表3》

算法	优化解 /km	车数 /辆	对应路径
算法	优化解 /km	车数 /辆	1	2	3
节约算法	910	3	0-8-5-7-0	0-6-4-0	0-3-1-2-0
分派算法	1 020	3	0-3-1-5-0	0-6-4-0	0-8-2-7-0
遗传算法	805	3	0-6-7-2-0	0-3-1-0	0-8-5-4-0
蚁群算法	780	3	0-2-7-4-0	0-3-1-0	0-8-5-6-0

《6 结语》

6 结语

车辆路径问题已广泛用于生产, 生活的各个方面, 如报纸投递及线路的优化, 牛奶配送及送达线路的优化, 电话预订货物的车辆载货和线路设计, 垃圾车的线路优化及垃圾站选址优化, 连锁商店的送货及线路优化等等。目前, 研究水平已有很大发展, 其理论成果除在汽车运输领域外, 在水运、航空、通信、电力、工业管理、计算机应用等领域也有一定的应用, 还用于航空乘务员轮班安排, 轮船公司运送货物经过港口与货物安排的优化设计, 交通车线路安排, 生产系统中的计划与控制等多种组合优化问题。物流配送车辆路径问题, 是物流配送优化中关键的一环, 也是电子商务活动不可缺少的内容。对货运车辆进行优化调度, 可以提高物流经济效益、实现物流科学化。对货运车辆优化调度理论与方法进行系统研究是物流集约化发展、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。

在物流配送系统中, 合理安排车辆路线是减少浪费提高经济效益的重要手段, 然而由于问题的NP完全性质, 精确求解非常困难, 研究启发式算法不失为一种可行的方向。通过对带时间窗车辆路径问题的分析, 笔者建立了基于蚁群算法的带时间窗车辆路径问题的启发式算法, 设计了一种新型动态蚁群算法, 试验证明该算法性能较好, 可以较快地找到问题的优化解或近似优化解, 是求解带时间窗车辆路径问题的一个较好的方案。

Show More