Optimization Online


Exact and heuristic approaches to the budget-constrained dynamic uncapacitated facility location-network design problem

Abdolsalam Ghaderi(ab.ghadri***at***gmail.com)
Natashia Boland(natashia.boland***at***newcastle.edu.au)
Mohammad Saeid JabalAmeli(jabal***at***iust.ac.ir)

Abstract: Facility location-network design problems seek to simultaneously determine the locations of fa- cilities and the design of the network connecting the facilities so as to best serve a set of clients accessing the facilities via the network. Here we study a dynamic (multi-period) version of the problem, subject to a budget constraint limiting the investment in new facilities and network links in each period. We consider an uncapacitated setting, in which the objective is to minimize the combined travel cost for clients and operating costs of facilities and network links. We present a mixed-integer linear programming (MIP) model generalizing related models in the literature, derive some useful properties of solutions, and show how the model can be strengthened. Three heuristics based on sequential solution of MIPs, and an efficient hybrid heuristic based on variable neighbor- hood search (VNS), are presented. The models and algorithms are compared computationally on randomly generated instances.

Keywords: facility location, network design, dynamic (multi-period), sequential heuristic, hybrid VNS algorithm

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Applications -- Science and Engineering (Facility Planning and Design )

Citation: Report C-OPT 2012/02, The University of Newcastle, Callaghan, NSW, 2308, Australia, 2012

Download: [PDF]

Entry Submitted: 02/02/2012
Entry Accepted: 02/02/2012
Entry Last Modified: 02/02/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society