Search graph structure and its implications for multi-graph constrained routing and scheduling problems.
Search graph structure and its implications for multi-graph constrained routing and scheduling problems.
复制标题
DOI：
10.1038/s41598-022-18026-w
复制
发表时间：
2022-09-01
影响因子：
4.6
通讯作者：
Chen, Jun
中科院分区：
文献类型：
--
作者：
Weiszer, Michal;Burke, Edmund K.;Chen, Jun
多个边连接一对节点的多图是许多现实世界优化问题的重要建模方法。多图结构通常基于基础设施和节点之间的可用连接。在本研究中，我们对一种特殊类型的受限路由和调度问题进行了案例研究。以机场地面移动问题为例，分析了多图结构中平行边的数量及其代价对路由算法解的质量的影响。结果表明，并行边的数量不仅影响计算复杂度，而且影响折衷解的数量和找到的解的质量。在此基础上，进一步提出了一个指标，用于估计多图何时能从更多的平行边中获益。此外，我们还表明，在存在时间窗约束的情况下，在多图中包含成本占主导的边也可以改善结果。这些发现为基于多图的类似问题的多图创建的知情方法铺平了道路。
Multi-graphs where several edges connect a pair of nodes are an important modelling approach for many real-world optimisation problems. The multi-graph structure is often based on infrastructure and available connections between nodes. In this study, we conduct case studies for a special type of constrained routing and scheduling problems. Using the airport ground movement problem as an example, we analyse how the number of parallel edges and their costs in multi-graph structure influence the quality of obtained solutions found by the routing algorithm. The results show that the number of parallel edges not only affects the computational complexity but also the number of trade-off solutions and the quality of the found solutions. An indicator is further proposed which can estimate when the multi-graph would benefit from a higher number of parallel edges. Furthermore, we show that including edges with dominated costs in the multi-graph can also improve the results in the presence of time window constraints. The findings pave the way to an informed approach to multi-graph creation for similar problems based on multi-graphs.
登录
查看更多内容
影响因子：
8.5
作者：
Abbaspour, Rahim A.;Samadzadegan, Farhad
通讯作者：
Samadzadegan, Farhad
影响因子：
6.4
作者：
Ehmke, Jan Fabian;Campbell, Ann Melissa;Thomas, Barrett W.
通讯作者：
Thomas, Barrett W.
影响因子：
2.4
作者：
Androutsopoulos, Konstantinos N.;Zografos, Konstantinos G.
通讯作者：
Zografos, Konstantinos G.
影响因子：
11.2
作者：
Weiszer, Michal;Chen, Jun;Locatelli, Giorgio
通讯作者：
Locatelli, Giorgio
DOI：
10.1016/j.trc.2020.102734
发表时间：
2020-10-01
影响因子：
8.3
作者：
Weiszer, Michal;Burke, Edmund K.;Chen, Jun
通讯作者：
Chen, Jun