A heuristic for a hybrid fleet model

The maximal covering location problem (MCLP), the facility location equipment emplacement technique (FLEET) and the maximal expected coverage location problem (MEXCLP) have been used in the location analysis of public service facilities. The multiple-cover one-type of equipment FLEET (MOFLEET) model is an extended FLEET and MEXCLP model that involves simultaneously locating stations and allocating equipment with the objective of maximizing expected coverage. Optimal integer programming solutions to MOFLEET have demonstrated that high levels of coverage can be maintained with a given amount of equipment while reducing the number of stations. Solving the MOFLEET model utilizing linear programming with branch and bound can involve thousands of branches and hundreds of thousands of pivots resulting in relatively large computation times. A heuristic solution approach to MOFLEET is presented and computational experience on two test data sets is reported including one of Austin, Texas. Heuristic results indicate that optimal and near-optimal solutions can be generated in a fraction of the time required to find optimal integer programming solutions.