Bi-sided facility location problems: an efficient algorithm for k-centre, k-median, and travelling salesman problems

Mansoor Davoodi*, Jafar Rezaei

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review


This study introduces a general framework, called Bi-sided facility location, for a wide range of problems in the area of combined facility location and routing problems such as locating test centres and designing the network of supermarkets. It is based on a multi-objective optimisation model to enhance the service quality which the clients received, called client-side, and enhance the interconnection quality and eligibility among the centres, called center-side. Well-known problems such as k-median and k-centre for the client-side and the travelling salesman problem for the centre-side are taken into account in this paper. After discussing the complexity of this kind of combination, we propose a heuristic approximation algorithm to find approximation Pareto-optimal solutions for the problem. The algorithm is an efficient local search utilising geometric objects such as the Voronoi diagram and Delaunay triangulation as well as algorithms for computing approximation travelling salesman tour. In addition to the comprehensive theoretical analysis of the proposed models and algorithm, we apply the algorithm to different instances and benchmarks, and compare it with NSGA-II based on set coverage and spacing metrics. The results confirm the efficiency of the algorithm in terms of running time and providing a diverse set of efficient trade-off solutions. Highlights: Introducing a general bi-side location model considering centres and clients’ utilities Discussing and proving the NP-hardness of the model in the general framework Considering two instances; k-centre and k-median for client-side and TSP for centre-side Proposing an efficient geometric-based algorithm for solving the problems Implementing, testing, and comparing the proposed algorithm on several benchmarks.
Original languageEnglish
Article number2235814
JournalInternational Journal of Systems Science: Operations and Logistics
Issue number1
Publication statusPublished - 2023

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.


  • approximation
  • connected facility location
  • Facilities planning
  • local search
  • routing
  • travelling salesman problem

Cite this