Extracting multi-objective multigraph features for the shortest path cost prediction: Statistics-based or learning-based?
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 algorit...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-02-01
|
| Series: | Green Energy and Intelligent Transportation |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2773153723000658 |
| _version_ | 1797271257338609664 |
|---|---|
| author | Songwei Liu Xinwei Wang Michal Weiszer Jun Chen |
| author_facet | Songwei Liu Xinwei Wang Michal Weiszer Jun Chen |
| author_sort | Songwei Liu |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-07T13:59:11Z |
| format | Article |
| id | doaj.art-72aed3a2c7d44f4895b629ba0affe615 |
| institution | Directory Open Access Journal |
| issn | 2773-1537 |
| language | English |
| last_indexed | 2024-03-07T13:59:11Z |
| publishDate | 2024-02-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Green Energy and Intelligent Transportation |
| spelling | doaj.art-72aed3a2c7d44f4895b629ba0affe6152024-03-07T05:30:45ZengElsevierGreen Energy and Intelligent Transportation2773-15372024-02-0131100129Extracting multi-objective multigraph features for the shortest path cost prediction: Statistics-based or learning-based?Songwei Liu0Xinwei Wang1Michal Weiszer2Jun Chen3School of Engineering and Materials Science, Queen Mary University of London, Mile End Road, London E1 4NS, United KingdomSchool of Engineering and Materials Science, Queen Mary University of London, Mile End Road, London E1 4NS, United KingdomSchool of Engineering and Materials Science, Queen Mary University of London, Mile End Road, London E1 4NS, United KingdomCorresponding author.; School of Engineering and Materials Science, Queen Mary University of London, Mile End Road, London E1 4NS, United KingdomEfficient 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.http://www.sciencedirect.com/science/article/pii/S2773153723000658Multi-objective multigraphFeature extractionShortest path cost predictionNode patternsNode embeddingsRegression |
| spellingShingle | Songwei Liu Xinwei Wang Michal Weiszer Jun Chen Extracting multi-objective multigraph features for the shortest path cost prediction: Statistics-based or learning-based? Green Energy and Intelligent Transportation Multi-objective multigraph Feature extraction Shortest path cost prediction Node patterns Node embeddings Regression |
| title | Extracting multi-objective multigraph features for the shortest path cost prediction: Statistics-based or learning-based? |
| title_full | Extracting multi-objective multigraph features for the shortest path cost prediction: Statistics-based or learning-based? |
| title_fullStr | Extracting multi-objective multigraph features for the shortest path cost prediction: Statistics-based or learning-based? |
| title_full_unstemmed | Extracting multi-objective multigraph features for the shortest path cost prediction: Statistics-based or learning-based? |
| title_short | Extracting multi-objective multigraph features for the shortest path cost prediction: Statistics-based or learning-based? |
| title_sort | extracting multi objective multigraph features for the shortest path cost prediction statistics based or learning based |
| topic | Multi-objective multigraph Feature extraction Shortest path cost prediction Node patterns Node embeddings Regression |
| url | http://www.sciencedirect.com/science/article/pii/S2773153723000658 |
| work_keys_str_mv | AT songweiliu extractingmultiobjectivemultigraphfeaturesfortheshortestpathcostpredictionstatisticsbasedorlearningbased AT xinweiwang extractingmultiobjectivemultigraphfeaturesfortheshortestpathcostpredictionstatisticsbasedorlearningbased AT michalweiszer extractingmultiobjectivemultigraphfeaturesfortheshortestpathcostpredictionstatisticsbasedorlearningbased AT junchen extractingmultiobjectivemultigraphfeaturesfortheshortestpathcostpredictionstatisticsbasedorlearningbased |