Parallel genetic algorithm on GPU for the robust uncapacitated single allocation p-hub median problem with discrete scenarios

In recent years, the Hub location problems (HLPs) have been expanded to handle uncertain data, giving rise to Robust HLPs. In a Robust HLP with discrete scenarios, the unique set of requests is replaced by a set of discrete scenarios. For example, a scenario can be the collection of requests observed between nodes at given periods of the year. In a robust optimization approach, making appropriate decisions for all scenarios is time-consuming, especially for large size HLP instances. The purpose of this study is to show that such problems can be solved in a reasonable computing time and with high quality solutions, using the computing power of the GPU graphics card. So, we present a GPU-based approach for solving large Robust HLP with discrete senarios. The proposed parallel genetic algorithm returns a robust solution based on the min-max lexicographic criterion that minimizes the worst cost on all scenarios. Due to the performance of our GPU implementation we solve instances up to 4000 nodes in a few seconds on an Nvidia Quadro P6000 (3840 cores).