杜宾斯的启发式和学习模型 MinMax 旅行销售员问题
Abhishek Nayak1, Sivakumar Rathinam1
1Mechanical Engineering, Texas A&M University, College Station, TX 77843, USA.
Sensors (Basel, Switzerland)
|July 29, 2023
概括
这项研究解决了Dubins机器人任务的多个旅行销售员问题 (mTSP). 可变社区搜索启发式在较大的问题上表现出色,而基于学习的方法在较小的实例上表现良好.
科学领域:
- 运营研究 运营研究
- 机器人技术 机器人技术 机器人技术
- 人工智能的人工智能
背景情况:
- 杜宾斯的多个旅行销售员问题 (mTSP) 对于无人驾驶汽车和地面机器人的任务规划至关重要.
- 一个特定的变体,即一组中的Dubins mTSP (MD-GmTSP),需要高效的路由解决方案.
研究的目的:
- 为了制定和解决MD-GmTSP.
- 为了比较这种路由问题的启发式和基于学习的方法的有效性.
主要方法:
- 制定MD-GmTSP作为一个混合整数线性程序 (MILP).
- 开发基于启发式的搜索方法,使用旅游构造和可变社区搜索 (VNS).
- 探索图形神经网络与强化学习用于政策学习.
主要成果:
- 基于启发式的VNS方法有效地解决了较大的MD-GmTSP实例.
- 基于学习的方法,利用图形神经网络,在较小的实例上表现出强的性能.
- 在修改后的TSPLIB实例上验证了算法性能.
结论:
- 基于VNS的启发式和基于学习的方法都为MD-GmTSP提供了可行的解决方案.
- 算法的选择取决于问题的规模.
- 这项研究有助于优化自主系统的任务规划.
更多相关视频
相关概念视频
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
81
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
81
Heuristics
111
Heuristics are problem-solving strategies that use mental shortcuts to simplify decision-making. Unlike algorithms, which must be followed precisely to achieve a correct result, heuristics offer a general problem-solving framework. They save time and energy but can sometimes lead to less rational decisions.
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...
111
The Availability Heuristic
6.0K
A heuristic is a general problem-solving framework (Tversky & Kahneman, 1974). You can think of these as mental shortcuts that are used to solve problems. Different types of heuristics are used in different types of situations, and the impulse to use a heuristic occurs when one of five conditions is met (Pratkanis, 1989):
6.0K
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
3.1K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
3.1K
The Anchoring-and-Adjustment Heuristic
7.3K
In order to make good decisions, we use our knowledge and our reasoning. Often, this knowledge and reasoning is sound and solid. However, sometimes, we are swayed by biases or by others manipulating a situation. For example, let’s say you and three friends wanted to rent a house and had a combined target budget of $1,600. The realtor shows you only very run-down houses for $1,600 and then shows you a very nice house for $2,000. Might you ask each person to pay more in rent to get the...
7.3K
Theorems of Pappus and Guldinus: Problem Solving
765
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
765


