Optimized Multiagent Routing for a Class of Guidepath-Based Transport Systems
Optimized Multiagent Routing for a Class of Guidepath-Based Transport Systems
复制标题
DOI：
10.1109/tase.2018.2798630
复制
发表时间：
2019-01
影响因子：
5.6
通讯作者：
G. Daugherty;S. Reveliotis;G. Mohler
中科院分区：
文献类型：
--
作者：
G. Daugherty;S. Reveliotis;G. Mohler
本文提出了一种启发式算法，用于最小化所需的最大完工时间路由一组代理居住在一个共享的引导路径网络从他们的初始位置到各自的目的地，同时遵守一组规则，以确保安全和完整的所产生的交通。从应用的角度来看，所提出的发展是由交通协调的挑战，出现在许多自动化的单位载荷材料处理系统的背景下，也在量子计算的背景下发生的电离原子的运输。从方法论的角度来看，我们的发展构成了定制的一般“本地搜索”框架的组合优化理论的交通管理问题，在本文中被认为是。因此，所提出的结果包括所考虑的问题及其解决方案空间的严格表征，详细的算法建设所需的初始解决方案和改进步骤所追求的搜索，这些算法的复杂性分析，和一组计算实验，揭示和评估所提出的算法的计算效率和所得到的解决方案的功效。最后，本文提出了一些建议，为潜在的扩展所提出的结果。从业者注意：在自动化科学和工程的许多当代应用中，许多实体或“代理”必须使用定义底层“引导路径网络”的一组链接方便地从其初始位置运输到某些目的地。此外，各种安全的考虑要求，代理必须充分分离，在这些运输，和施加的限制把相应的交通协调问题变成一个复杂的资源分配问题，其中有争议的资源是引导路径网络链接。本文提出了一套算法，可以提供高质量的时间表，从而产生的交通调度问题，在计算效率高的方式。我们的算法的这些属性是通过必要的理论分析建立的，但它们也通过一系列的数值实验证明，它们能够在不超过几秒钟的时间内为一些非常复杂的问题实例提供接近最优的解决方案。此外，我们的算法是“完整的”，即，它们将总是为本文中考虑的业务调度问题的任何实例化提供可行的调度。因此，它们可以有效地解决所考虑的应用程序的上下文中出现的“实时”交通管理的需求。
This paper presents a heuristic algorithm for minimizing the makespan required to route a set of agents inhabiting a shared guidepath network from their initial locations to their respective destinations while observing a set of regulations that seek to ensure the safety and the integrity of the generated traffic. From an application standpoint, the presented developments are motivated by the traffic coordination challenges that arise in the context of many automated unit-load material handling systems and also in the transport of the ionized atoms that takes place in the context of quantum computing. From a methodological standpoint, our developments constitute a customization of the general “local-search” framework of combinatorial optimization theory to the traffic management problem that is considered in this paper. Hence, the presented results include a rigorous characterization of the considered problem and its solution space, detailed algorithms for the construction of the necessary initial solutions and the improving step for the pursued search, a complexity analysis of these algorithms, and a set of computational experiments that reveal and assess the computational efficiency of the presented algorithms and the efficacy of the derived solutions. The paper concludes with some suggestions for potential extensions of the presented results. Note to Practitioners—In many contemporary applications of automation science and engineering, a number of entities—or “agents”—must be transported expediently from their initial locations to certain destinations using a set of links that define the underlying “guidepath network.” Furthermore, various safety considerations require that the agents must be adequately separated during these transports, and the imposed restrictions turn the corresponding traffic coordination problem into a complex resource allocation problem, where the contested resources are the guidepath-network links. This paper presents a set of algorithms that can provide high-quality schedules for the resulting traffic-scheduling problems in a computationally efficient manner. These properties of our algorithms are established through the necessary theoretical analysis, but they are also demonstrated through a series of numerical experiments where they are shown capable to provide near-optimal solutions for some very complex problem instances in no more than a few seconds. In addition, our algorithms are “complete,” i.e., they will always provide a feasible schedule for any instantiation of the traffic-scheduling problem considered in this paper. Hence, they can effectively address the needs for “real-time” traffic management that arise in the context of the considered applications.