Local search heuristics for the mobile facility location problem

Local search heuristics for the mobile facility location problem

0.00 Avg rating0 Votes
Article ID: iaor201527055
Volume: 62
Issue: 6
Start Page Number: 210
End Page Number: 223
Publication Date: Oct 2015
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics, heuristics: local search, programming: integer
Abstract:

In the mobile facility location problem (MFLP), one seeks to relocate (or move) a set of existing facilities and assign clients to these facilities so that the sum of facility movement costs and the client travel costs (each to its assigned facility) is minimized. This paper studies formulations and develops local search heuristics for the MFLP. First, we develop an integer programming (IP) formulation for the MFLP by observing that for a given set of facility destinations the problem may be decomposed into two polynomially solvable subproblems. This IP formulation is quite compact in terms of the number of nonzero coefficients in the constraint matrix and the number of integer variables; and allows for the solution of large‐scale MFLP instances. Using the decomposition observation, we propose two local search neighborhoods for the MFLP. We report on extensive computational tests of the new IP formulation and local search heuristics on a large range of instances. These tests demonstrate that the proposed formulation and local search heuristics significantly outperform the existing formulation and a previously developed local search heuristic for the problem.

Reviews

Required fields are marked *. Your email address will not be published.