基于火花的平行适应性大邻里搜索来解决VRPTWW
Songzuo Liu1,2, Jian Sun3, Xiaohong Duan1
1Faculty of Information Engineering, Shandong Huayu University of Technology, Dezhou, 253034, China.
Scientific reports
|October 11, 2024
概括
一个新的基于Spark的平行自适应大邻里搜索 (Spark-ALNS) 算法有效地解决了使用时间窗口 (VRPTW) 的车辆路由问题. 这种先进的方法比现有的算法更快,更准确地找到最佳解决方案.
科学领域:
- 运营研究 运营研究
- 计算机科学 计算机科学
- 人工智能的人工智能
背景情况:
- 车辆路由问题与时间窗口 (VRPTW) 是一个复杂的组合优化挑战.
- 现有的算法经常在为大规模VRPTW实例有效地找到最佳解决方案时扎.
研究的目的:
- 开发一种新的,高效的,准确的算法来解决多目标的VRPTW.
- 为了提高性能,利用平行计算与自适应的大邻里搜索 (ALNS) 来提高性能.
主要方法:
- 设计了一个基于Spark的平行自适应大邻里搜索 (Spark-ALNS) 算法.
- 关键组件包括一种新的模拟回火冷却策略,CW初始化和定制的破坏/维修操作员.
- 实施了一种新的并行策略,以提高准确性和减少计算时间.
主要成果:
- 在所罗门的VRPTW实例上,Spark-ALNS算法实现了卓越的性能.
- 在56个实例中,它发现了41个已知的最佳解决方案,并在31个实例中发现了新的最佳解决方案.
- 运行时间比其他并行算法快3-5倍.
结论:
- 拟议的Spark-ALNS是解决VRPTW的一个非常有效的方法.
- 与现有的进化算法相比,它在解决方案质量和计算效率方面取得了显著的改进.
相关概念视频
Cluster Sampling Method
11.7K
Appropriate sampling methods ensure that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest.
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
11.7K
Parallel Processing
145
The brain processes sensory information rapidly due to parallel processing, which involves sending data across multiple neural pathways at the same time. This method allows the brain to manage various sensory qualities, such as shapes, colors, movements, and locations, all concurrently. For instance, when observing a forest landscape, the brain simultaneously processes the movement of leaves, the shapes of trees, the depth between them, and the various shades of green. This enables a quick and...
145
Prismatic Beams: Problem Solving
105
In the design of a supported timber beam subjected to a distributed load, both the beam's physical dimensions and the timber's characteristics, such as its grade and species, are critical. These factors determine the allowable stress values, which are crucial for calculating the necessary beam depth to ensure structural integrity and safety.
The design begins with analyzing the beam as a free body to identify moments and force balances, thereby determining support reactions. Next, the...
The design begins with analyzing the beam as a free body to identify moments and force balances, thereby determining support reactions. Next, the...
105
Area Computation by the Alternative Coordinate Method
49
The alternative coordinate method, also known as the Shoelace Formula, is a technique for determining the area of a traverse using Cartesian coordinates. This method relies on the sequential arrangement of x and y coordinates for each point of the shape, ensuring accuracy and ease of application.In this approach, each corner's x and y coordinates are listed as fractions, with the x-coordinate as the numerator and the y-coordinate as the denominator. These coordinates are arranged sequentially...
49
Random Sampling Method
11.0K
Sampling is a technique to select a portion (or subset) of the larger population and study that portion (the sample) to gain information about the population. Data are the result of sampling from a population. The sampling method ensures that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest. Among the various sampling methods used by...
11.0K
Distributed Loads: Problem Solving
628
Beams are structural elements commonly employed in engineering applications requiring different load-carrying capacities. The first step in analyzing a beam under a distributed load is to simplify the problem by dividing the load into smaller regions, which allows one to consider each region separately and calculate the magnitude of the equivalent resultant load acting on each portion of the beam. The magnitude of the equivalent resultant load for each region can be determined by calculating...
628


