Machine learning augmented approaches for hub location problems. (June 2023) - Li, Meng; Wandelt, Sebastian; Cai, Kaiquan; Sun, Xiaoqian
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.