Extracting multi-objective multigraph features for the shortest path cost prediction:Statistics-based or learning-based?  

作　　者：Songwei Liu Xinwei Wang Michal Weiszer Jun Chen 

机构地区：[1]School of Engineering and Materials Science,Queen Mary University of London,Mile End Road,London E14NS,United Kingdom

出　　处：《Green Energy and Intelligent Transportation》2024年第1期1-15,共15页新能源与智能载运（英文）

基　　金：This work was supported by the UK Engineering and Physical Sciences Research Council(grant no.EP/N029496/1,EP/N029496/2,EP/N029356/1,EP/N029577/1,and EP/N029577/2);the joint scholarship of the China Scholarship Council and Queen Mary,University of London(grant no.202006830015).

摘　　要：Efficient airport airside ground movement(AAGM)is key to successful operations of urban air mobility.Recent studies have introduced the use of multi-objective multigraphs(MOMGs)as the conceptual prototype to formulate AAGM.Swift calculation of the shortest path costs is crucial for the algorithmic heuristic search on MOMGs,however,previous work chiefly focused on single-objective simple graphs(SOSGs),treated cost enquires as search problems,and failed to keep a low level of computational time and storage complexity.This paper concentrates on the conceptual prototype MOMG,and investigates its node feature extraction,which lays the foundation for efficient prediction of shortest path costs.Two extraction methods are implemented and compared:a statistics-based method that summarises 22 node physical patterns from graph theory principles,and a learning-based method that employs node embedding technique to encode graph structures into a discriminative vector space.The former method can effectively evaluate the node physical patterns and reveals their individual importance for distance prediction,while the latter provides novel practices on processing multigraphs for node embedding algorithms that can merely handle SOSGs.Three regression models are applied to predict the shortest path costs to demonstrate the performance of each.Our experiments on randomly generated benchmark MOMGs show that(i)the statistics-based method underperforms on characterising small distance values due to severe overestimation;(ii)A subset of essential physical patterns can achieve comparable or slightly better prediction accuracy than that based on a complete set of patterns;and(iii)the learning-based method consistently outperforms the statistics-based method,while maintaining a competitive level of computational complexity.

关 键 词：Multi-objective multigraph Feature extraction Shortest path cost prediction Node patterns Node embeddings Regression 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]