An evolutionary-based approach for solving a capacitated hub location problem

Abstract

This paper addresses the capacitated hub location problem (CHLP), which is a variant of the classical capacitated hub problem. What is presented is a modified mixed integer linear programming (MILP) formulation for the CHLP. This modified formulation includes fewer variables and constraints compared to the existing problem formulations in the literature. We propose two evolutionary algorithms (EAs) that use binary encoding and standard genetic operators adapted to the problem. The overall performance of both EA implementations is improved by a caching technique. In order to solve large-scale instances within reasonable time, the second EA also uses a newly designed heuristic to approximate the objective function value. The presented computational study indicates that the first EA reaches optimal solutions for all smaller and medium-size problem instances. The second EA obtains high-quality solutions for larger problem dimensions and provides solutions for large-scale instances that have not been addressed in the literature so far. © 2010 Elsevier B.V. All rights reserved.