英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems
Paul Shaw
Department of Computer Science,
University of Strathclyde, Glasgow.
April 1998
利用约束规划和局部搜索方法解决车辆路径问题。
保罗·肖
计算机科学部门,
斯特拉思克莱德大学,格拉斯哥。
1998年4月
Abstract
We use a local search method we term Large Neighbourhood Search (LNS) for solving vehicle routing problems. LNS meshes well with constraint programming technology and is analogous to the shuffling technique of job-shop scheduling. The technique explores a large neighbourhood of the current solution by selecting a number of customer visits to remove from the routing plan, and re-inserting these visits using a constraint-based tree search. We analyse the performance of LNS on a number of vehicle routing benchmark problems. Unlike related methods, we use Limited Discrepancy Search during the tree search to re-insert visits. We also maintain diversity during search by dynamically altering the number of visits to be removed, and by using a randomised choice method for selecting visits to remove. We analyse the performance of our method for various parameter settings controlling the discrepancy limit, the dynamicity of the size of the removal set, and the randomness of the choice. We demonstrate that results produced by our technique are very competitive with Operations Research meta-heuristic methods, indicating that constraint programming technology is directly applicable to vehicle routing problems.
摘要
我们使用本地搜索方法，我们称之为大型社区搜索(LNS)来解决车辆路径问题。LNS与约束编程技术相吻合，类似于作业车间调度的变换技术。该技术通过选择多个客户访问来从路由计划中删除，并使用基于约束的树搜索重新插入这些访问，从而探索当前解决方案的一个大范围。我们分析了LNS在许多车辆路径基准问题上的性能。与相关的方法不同，我们在树搜索中使用有限的差异搜索来重新插入访问。在搜索过程中，我们也通过动态改变访问次数来保持多样性，并使用随机选择的方法来选择访问删除。我们分析了各种参数设置方法的性能，控制了差异的限制，消除集的大小的动态性，以及选择的随机性。我们证明了我们的技术所产生的结果与操作研究的元启发式方法非常具有竞争性，表明约束编程技术直接适用于车辆路径问题。
1 Introduction
The vehicle routing problem (VRP) is one of visiting a set of customers using a fleet of vehicles, respecting constraints on the vehicles, customers, drivers, and so on. The goal is to minimize the costs of operation, which normally involves reducing a combination of the number of vehicles and the total distance travelled or time taken. Because of the size of routing problems that need to be routinely solved in industry, local search techniques (sometimes combined with meta-heuristics) are generally used to produce solutions to routing problems. These methods scale well and can produce reliably good solutions.
- 介绍
车辆路径问题(VRP)是一种使用车队的车辆，尊重车辆、顾客、司机等的约束。目标是尽量减少操作的费用，这通常包括减少车辆数目和总行驶距离或时间。由于在工业中需要经常解决的路由问题的大小，本地搜索技术(有时与元启发式相结合)通常用于生成路由问题的解决方案。这些方法可以很好地扩展，并能产生可靠的解决方案。
Constraint programming (CP) appears to be good technology to apply to VRPs because of the ubiquity of side constraints in real-world problems. A natural conclusion is that if one can use constraint programming technology within a local search framework, one should have a tech-nique that will work well for real-world vehicle routing problems. Unfortunately, the traditional view of local search does not integrate well with the tree-based view of search within constraint programming. The challenge is to try to get the best of both of these methods: exploration of a neighbourhood from local search, and the power of propagation and heuristics from constraint programming.
约束编程(CP)似乎是适用于VRPs的一种很好的技术，因为在现实世界的问题中存在着无所不在的约束。一个自然的结论是，如果一个人可以在本地搜索框架中使用约束编程技术，那么就应该有一个技术上的技术，这样就能很好地解决现实中的车辆路径问题。不幸的是，传统的本地搜索视图与约束编程中的基于树的搜索视图并不很好地集成。我们面临的挑战是如何在这两种方法中得到最好的结果:从局部搜索中探索一个邻域，以及从约束编程中获取传播和启发式的能力。
In this paper we use a technique we refer to as Large Neighbourhood Search (LNS) which makes moves like local search, but uses a tree-based search with constraint propagation to evaluate the cost and legality of the move. As a “heavyweight” technique such as constraint programming is used to evaluate the move, many less moves per second can be evaluated than is normally the case for local search. However, these moves can be more powerful, moving the search further at each step. When such far reaching moves are possible there are normally many more of them available than would be the case if the moves were very localized: hence the name Large Neighbourhood Search.
在本文中，我们使用了一种称为“大邻居搜索”(LNS)的技术，它使得移动像本地搜索一样，但是使用基于树的搜索和约束传播来评估移动的成本和合法性。作为一种“重量级”技术，例如约束编程，用于评估移动，比通常情况下的本地搜索更少每秒的移动。然而，这些动作可能更强大，在每一步中进一步移动搜索。如果这些移动的移动都是非常本地化的，那么它们的可用性就会比实际情况要多得多:因此，这个名字就叫做“大型社区搜索”。
LNS is applied to the vehicle routing problem by defining a move to be the removal and re-insertion of a set of customer visits. The set of customer visits chosen for removal and re-insertion defines the move. We define a “relatedness” measure between customer visits and use this as a basis for choosing the set . We use Limited Discrepancy Search to re-insert the customer visits into the routing plan. The size of the set is increased over time, stepping up when the search is deemed to have stagnated at the current size of set .
LNS被应用于车辆路径问题，通过定义一个移动，以删除和重新插入一组客户访问。选择移除和重新插入的客户访问集定义了迁移。我们定义了客户访问之间的“关联性”度量，并以此作为选择集合的基础。我们使用有限差异搜索重新插入客户访问到路由计划。随着时间的推移，设置的大小会增加，当搜索被认为在当前设置的大小上停滞时，就会增加。
Experiments are carried out on a number of classic benchmark problems from the literature, with and without time windows. We analyse the quality of solutions produced by LNS over a range of parameter settings by comparison to the best published solutions. Despite its simplicity in comparison with Operations Research techniques, LNS is shown to have excellent average performance and produces many new best solutions to these benchmark problems.
实验是在一些经典的基准问题上进行的，从文献，有和没有时间窗。我们通过与最佳发布的解决方案进行比较，分析了LNS在一系列参数设置上产生的解决方案的质量。尽管LNS与操作研究技术比较简单，但它的平均性能很好，并为这些基准问题提供了许多新的最佳解决方案。
The paper is organized as follows: Section 2 describes LNS as applied to the vehicle routing problem. The method is then compare
全文共57599字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11800]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
