The multicriteria p-facility median location problem on networks

Jörg Kalcsics, Stefan Nickel, Miguel A. Pozo*, Justo Puerto, Antonio M. Rodríguez-Chía

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper we discuss the multicriteria p-facility median location problem on networks with positive and negative weights. We assume that the demand is located at the nodes and can be different for each criterion under consideration. The goal is to obtain the set of Pareto-optimal locations in the graph and the corresponding set of non-dominated objective values. To that end, we first characterize the linearity domains of the distance functions on the graph and compute the image of each linearity domain in the objective space. The lower envelope of a transformation of all these images then gives us the set of all non-dominated points in the objective space and its preimage corresponds to the set of all Pareto-optimal solutions on the graph. For the bicriteria 2-facility case we present a low order polynomial time algorithm. Also for the general case we propose an efficient algorithm, which is polynomial if the number of facilities and criteria is fixed.

Original languageEnglish
Pages (from-to)484-493
Number of pages10
JournalEuropean Journal of Operational Research
Volume235
Issue number3
DOIs
Publication statusPublished - 16 Jun 2014

Keywords

  • Multicriteria optimization
  • Network location
  • p-Facility location

Fingerprint

Dive into the research topics of 'The multicriteria p-facility median location problem on networks'. Together they form a unique fingerprint.

Cite this