Improving Traditional Dual Ascent Algorithm for the Uncapacitated Multiple Allocation Hub Location Problem: A RAMP Approach

摘要

Hub Location Problems are complex combinatorial optimization problems that raised a lot of interest in the literature and have a huge number of practical applications, going from the telecommunications, airline transportation among others. In this paper we propose a primal-dual algorithm to solve the Uncapacitated Multiple Allocation Hub Location Problem (UMAHLP). RAMP algorithm combines information of traditional Dual Ascent procedure on the dual side with an improvement method on the primal side, together with adaptive memory structures. The overall performance of the proposed algorithm was tested on standard Australian Post (AP) and Civil Aeronautics Boarding (CAB) instances, comprising 192 test instances. The effectiveness of our approach has been proven by comparing with other state-of-the-art algorithms.