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

Abstract

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

KEYWORDS:

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

Acknowledgment

This research was financinsally supported by Dutch Research Council (NWO), Social Sciences and Humanities: grant number 040.11.7421.

Data availability statement

Two classes of data have been used in this study: randomly generated instances and benchmarks. This first class is simply generated by a C# language code and the second class, which is mentioned in Table 7, is freely available at the following website and references. http://sweet.ua.pt/sbarreto/_private/SergioBarretoHomePage.htm; Baldacci et al., 2011; Harks et al., 2013.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Mansoor Davoodi

Mansoor Davoodi is an expert in modeling real-world problems, optimization algorithms and operations research. He is an assistant professor and currently, he is a senior researcher at the Center for Advanced Systems Understanding, Helmholtz-Zentrum Dresden Rossendorf (HZDR), Germany.

Jafar Rezaei

Jafar Rezaei is an associate professor of operations and supply chain management at Delft University of Technology, The Netherlands, where he obtained his Ph.D. in 2012. His main research interests are in the areas of logistics and supply chain management, and decision science.