Machine learning augmented approaches for hub location problems. (June 2023)

• Record Type: Journal Article
• Authors: Li, Meng; Wandelt, Sebastian; Cai, Kaiquan; Sun, Xiaoqian
• Is Part Of: Computers & operations research. Volume 154(2023)
• Publication Date: 2023-06
• Subjects: Hub location problem -- Machine learning -- Multi-graph -- Graph neural network -- Node ranking; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2023.106188
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: Hub location problems are widely analyzed in fields of logistic and transportation industry for cost reduction. In this paper, a novel algorithm framework based on machine learning is proposed to improve solution quality of hub location problems for large-scale instances. First, a deep-learning based probabilistic hub-ranker (DLHr) is developed to determine the priority of nodes to be selected as hubs. Next, two node-ranking based approaches DL-CBS and DL-GVNS are developed to augment the DLHr for single allocation hub location problems. DL-CBS is an augment algorithm embedding DLHr-ranking into clustering-based potential hub sets algorithm (CBS) while DL-GVNS embeds DLHr-ranking into general variable neighborhood search (GVNS). The numerical results evidence that DLHr outperforms baselines on the node-ranking task and helps to identify potential hubs. Evaluation on a wide range of experiments shows that DL-CBS and DL-GVNS improve solution quality of single allocation hub location problems compared with vanilla CBS and GVNS, revealing DLHr ranking helps to boost the performance of traditional heuristics. Highlights: A novel learning-based algorithm framework to solve hub location problems. A deep learning-based ranker is to predict hubs in single allocation problems. The gated recurrent unit-based graph convolutional networks. Design the multi-graphs and multi-type features mechanism. Compare with variable neighborhood search, genetic algorithm and tabu search.