英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料

附录A 译文

一种新的求解车辆路径问题的启发式算法

摘要 考虑了容量约束条件下的车辆路径问题，采用传统的优化方法求解车辆路径问题是很困难的对于大规模问题的计算复杂度高。因此，新的启发式或启发式的方法已被开发来解决这个问题。在本文中，我们构造了一个新的启发式基于禁忌搜索算法和自适应大邻域搜索算法（ALNs）与几个专门运营特点解决车辆路径问题（CVRP）的。说明基准问题所提出的算法的有效性。算法提供了更好的性能和规模情况下的CPU时间，获得了优势。在添加此外，我们解决了一个现实生活中的问题使用该算法和与公司现状中发现了令人鼓舞的结果比较。

关键词 带能力约束的车辆路径问题（CVRP）·禁忌搜索·自适应大邻域搜索（ALNs）

1引言

容量约束的车辆路径问题是物流活动中最重要的问题之一，车辆路径问题的主要目标是设计最少的车辆路径问题。一个车队的车辆从一个仓库到一组点的成本路线。车辆属于一个舰队，位于中央仓库，并且有一个容量。每个客户，都有一个点要访问，有需求量，成本取决于距离，每条路线从中央仓库开始，并在中央仓库完成，车辆容量不得超载。

有几项研究对CVRP的文献在过去十年的启发式，启发式或混合方法研究无比。Mazzeo和Loiseau（2004）开发了一个蚁群算法.他们恢复的主要特点，并尝试了几种替代方案的每个组件的算法。该算法与文献中的其他启发式算法进行了比较不同的设置和算法的有效性问题进行了说明。Fukasawa等人（2006）提出了一种基于分支定界割和传统拉格朗日松弛的Q算法路线。该算法是在一百以上的情况下进行测试。Mester和brasys（2007）提出了积极引导的进化策略算法的适应。我所提出的启发式方法的结合，引导本地搜索和进化策略算法。它进行了一组的情况下，结果示出所提出的方法是高度竞争的。林（2009）提出了一种结合模拟退火和禁忌搜索的混合算法。该算法包括经典大型CVRP实例验证效果性。AI和kachitvichyanukul（2009）提出（n＋2m）和（3M）与N的客户和M车辆尺寸的粒子群优化算法。（n＋2m）从粒子到关注的转变客户安全进入名单的路线和优先矩阵，3m开始转变粒子到车辆的定位点和车辆覆盖半径。计算结果说明（3M）维粒子群算法优于其他。Yurtkuran和爱弥儿（2010）提出了一个electromagnetismlike算法与局部搜索方法杂交。他们说E算法简单易用、高效的CVRP。司徒等人（2011）提出了一种人工蜂群算法和文献中的其他方法相比。他们断言所提出的算法是一种替代解决CVRP。纳齐夫和李（2012）提出了一种基于遗传算法优化的交叉算子，显示了该算法的有效性基准实例。崔等人（2013）开发了一种新的改进的量子进化算法与混合本地搜索过程，并说明了该算法在不同的情况下的有效性。考和陈（2013）开发了一种双级混合算法，综合离散粒子群优化算法和模拟退火算法。该算法可以减少计算时间的结果消除不可行解的个数的影响。金等人（2014）提出的协同并行算法，包括多个并行禁忌搜索线程异步交流合作发现的最好的解决方案通过一个普通的溶液池。他们比较了算法与其他文献中的计算结果说明了该算法的有效性和竞争力。林辉和罗（2014）提出一种新的融合算法，是一个动态的自适应免疫遗传算法的自动免疫监视功能。他们证明了该算法的小型测试成功问题.盖等人（2016）专注于提高本地搜索算法的能力。在这样的背景下，他们比较了六种不同的元启发式算法：模拟退火算法、随机仿真爬山、蚁群、禁忌搜索、粒子群优化、遗传算法等，提出了一种改进的遗传算法，该算法采用蚁群算法作为初始种群创建操作人员。叶等人（2016）提出了一种基于随机变量邻居下降的两阶段迭代局部搜索策略，并从迭代局部搜索。（2016）开发的与蚁群优化算法相结合的大邻域搜索算法求解机制。他们表明，算法在不具有令人满意的结果。

例如，由于问题的NP结构对启发式算法和启发式方法解决大型CVRP问题研究。在本文中，我们开发了一个新的他基于禁忌搜索算法和ALNS。我们的算法启发是罗普克和Pisinger（2006）从ALNS给我们带来了三个重要的理论贡献，达到去效率为我们的问题。首先是具体的破坏/维修运营商的设计，既考虑路线的顺序和车辆容量。第二个修改是关于搜索服务的工作群集服务点。第三个是一个多元化的技术依赖于集群的设计。该算法进行了测试知名的差异不同情况下。计算结果表明，我们的启发式算法与其他算法求解CVRP竞争。

本文的其余部分组织如下。在下一节中，车辆路径问题的简要概述，然后由一个新的建议算法解释。在后来的部分处理基准问题的计算结果。在现实生活中的例子，提出的算法比较的数值调查的结果最后一节。最后，结论。

2车辆路径问题

车辆路径问题（VRP）的问题，其中一组路线的车辆在一个或多个仓库的基础上，必须确定一些地理分散的城市或客户。经典VRP的目的是找到一组路线以最低的成本（找到最短路径，最大限度地减少车辆的数量等）开始并结束在仓库的路线，使已知的所有节点的需求得到满足。在文献中，VRP通常定义为能力约束下，所以VRP一般具有和CVRP相同的含义。对大量的数学公式所示：

A 每辆车的容量

V 最大车辆数

F_ij 从节点i到j的核心流量

Z 运输总成本

d_i 节点需求

c_ij i和j节点的节点之间的距离

X_ij = 1,如果车辆从节点i移动到j

0,其它

N 节点数

目标函数可以写成如下：

Min Z = (1)

模型约束条件：

=1 (2)

=1 (3)

(4)

(5)

(6)

, (7)

gt;1 (8)

, (9)

, (10)

该模型的目标函数（1）是尽量减少总行驶距离。的约束（2）和（3）状态，有一个完全背离节点I约束（4）规定不超过车辆总数。约束（5）在给定节点的传入和传出弧之间提供平衡。约束（6）消除了从节点i到节点i，约束（7）是微不足道的。约束（8）、（9）及（10）在节点总流入和流出之间提供平衡。

该数学模型可以用于小型CVRP只因为它是曲由于大规模问题计算复杂度高，用传统的优化方法难以达到最优解。出于这个原因，我们构建了一个新的启发式在本研究中针对算法。

3结论

在本文中，我们考虑了车辆路径问题。有各种研究和测试这个问题。这些研究非常成功地研究这个NP难题问题。禁忌搜索和建立提供成功的一些特点：允许不可行解，弹性参数，破坏/修复算子，多元化战略，强化策略和自适应存储器。

在这方面，我们提出了一个基于CVRP问题的禁忌和建立新的启发式算法。我们测试所提出的算法和算法提供兼容结果。对于三的基准情况下，该算法产生更好的解决方案相比，在文献中最好的知名的解决方案。在前11个基准的情况下，我们算法找到最优解。然而，它收敛到最佳的解决方案与0.01%的差异近似的情况下，不找到最佳的解决方案。最后，当我们应用该算法在现实生活中的问题的结果我们很满意的效果和效率，使用该算法取代目前的方法提供了优势的公司，因为结果优于目前的方法和CPU时间是允许的。

附录B 原文

A novel heuristic algorithm for capacitated vehicle routing problem

Abstract The vehicle routing problem with the capacity constraints was considered in this paper.It is quite difficult to achieve an optimal solution with traditional optimization methods by reason of the high computational complexity for large-scale problems.Consequently,new heuristic or metaheuristic approaches have been developed to solve this problem.In this paper,we constructed a new heuristic algorithm based on the tabu search and adaptive large neighborhood search (ALNS) with several specifically designed operators and features to solve the capacitated vehicle routing problem (CVRP).The effectiveness of the proposed algorithm was illustrated on the benchmark problems.The algorithm provides a better performance on largescaled instances and gained advantage in terms of CPU time.In addition,we solved a real-life CVRP using the proposed algorithm and found the encouraging results by comparison with the current situation that the company is in.

Keywords Capacitated vehicle routing problem (CVRP)·Tabu search·Adaptive large neighborhood search (ALNS)

1 Introduction

The vehicle routing problem with capacity constraints is one of the most important subjects for logistic activities.The main objective of vehicle routing problem is to design the least cost routes for a fleet of vehicles from one depot to a set of points.Vehicles belong to a fleet and located to the central depot and have a capacity.Each customer,which located a point to visit,has amount of demand.The cost depends on the distance.Each route starts from the central depot and finish at the central depot and the vehicle capacity must not be overloaded.

There are several studies about CVRP in the literature over the past decade and heuristic, metaheuristic or hybrid methods were studied overwhelmingly. Mazzeo and Loiseau(2004) developed an ant colony algorithm. They resumed the main characteristics and tried several alternatives for each component of the algorithm. The proposed algorithm was compared with other heuristics on the literature in a different set of problems and the effectiveness of the algorithm was illustrated.Fukasawa et al. (2006) proposed an algorithm based on branch and bound cut and traditional Lagrangian relaxation over q

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[612641]，资料为PDF文档或Word文档，PDF文档可免费转换为Word