Capacitated Single Allocation p-Hub Location Problem: Hyperheuristic Approaches with different Selection Methods

Session : SS1-1 / SS1 : Challenging Mixed-Integer Problems in Network Optimization
Mercredi 10 février 15:00 - 16:00 Salle : CI2-06
Kassem Danach, Shahin Gelareh, Frédéric Semet, Rahimeh N. Monemi et Wissam Khalil

Hub Location Routing Problems (HLRP), which deal with the design of hubs and spokes networks, have a wide range of applications in such domains such as transportation, telecommunication, etc. It decides on the nodes that will be considered as hubs, as well as on the spoke nodes and their allocations. This variant of HLRP that we deal with here was first proposed in the literature and is made up of: 1) Single allocation problem where each spoke is allocated to one and only one hub, 2) Feeder networks are cyclic, which means that the spokes are connected via edges in a cyclic form (for each feeder network), 3) Number of spokes for each feeder network are bounded, and 4) The objective function is minimizing of the total transportation cost. In this study, we will design and implement several hyperheuristic methods that have same low-level-heuristics and different heuristic selection schemes. Selection methods, in the literature, are classified as: 1) Random selection methods, 2) Peckish method, 3) Choice Function method, 4) Reinforcement Learning methods, and 5) metaheuristic to choose heuristics methods. We analyze the performance of each method by comparing the different proposed methods, which are classified in the above mentioned mentioned schemes. We show that the proposed hyperheuristics are efficient in producing high quality solutions in reasonable amount of CPU time.

Mots clés : Hub location problem, Hyper-Heuristic, Meta-Heuristic, Reinforcement Learning