Optimization Online


Navigating Concave Regions in Continuous Facility Location Problems

Ruilin Ouyang ( ouyang.ru***at***husky.neu.edu)
Michael Beacher (michael.robert.beacher***at***gmail.com)
Ma Dinghao (ma.di***at***husky.neu.edu)
Md. Noor-E-Alam (mnalam***at***neu.edu)

Abstract: In prior literature regarding facility location problems, there has been little explicit acknowledgement of problems arising from concave (non-convex) regions. By extension, there is a distinct deficiency in existing methods to deal with them outside of problem relaxation. In this work, we present a novel algorithm for finding representative regional center-points, referred to as "Concave Interior Centers", to approximate inter-regional distances for solving optimal facility location problems. The validity of the proposed method as a means for solving these placements is tested on three theoretical "special cases", and on a humanitarian focused real-world application. We compare the performance of our algorithm to the results from using Geometric Centers in the same contexts, and show them to be comparable when the Geometric Centers are contained within their respective regions. We discuss the implications of using externally located representative centers. The context of the application involves maximizing the potential number of homeless persons in Fairfield County, Connecticut who can be housed by the construction of limited capacity night-by-night shelters given a limited budget. The test model is of a previously unstudied type. Existing well studied and utilized facility location example problems look to solve minimum cost, full covering efforts, most with uncapacitated facilities and some with capacitated ones. None, however, deal with a maximization function under both capacitated facilities and a limiting construction budget.

Keywords: Distance measurement, Facility location problem, Geometric distance, Continuous Facility Location

Category 1: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 07/28/2019
Entry Accepted: 07/28/2019
Entry Last Modified: 03/03/2020

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