Details

Autor(en) / Beteiligte

• Markarian, Christine
• Khallouf, Peter
• Madani, Kurosh
• Smirnov, Alexander
• Panetto, Hervé

Titel

Online Facility Location Problems Inspired by the COVID-19 Pandemic

Ist Teil von

• Innovative Intelligent Industrial Production and Logistics, 2023, p.110-123

Ort / Verlag

Cham: Springer Nature Switzerland

Erscheinungsjahr

2023

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• The COVID-19 pandemic has challenged countries to take immediate measures to contain the disease and minimize its spread. Most, if not all, communities faced unprecedented healthcare resource shortages and limitations in hospital capacities. Consequently, leasing facilities and transforming them into health-care service providers were among the common actions taken. Inspired by this situation and the attempt to make wise leasing choices amidst these challenging times, we address in this paper a variant of the well-known Facility Location problem, one of the most well-studied optimization problems in computer science, operations research, and combinatorics. Given a collection of facilities, clients, services, and a positive integer d≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d \ge 2$$\end{document}. Services can be leased for different durations and prices at each facility location. Each service at each facility location is associated with a dormant fee that needs to be paid each time the service is not leased at the facility for d days. In each step, a subset of the clients arrives, each requesting a number of the services. The goal is to connect each client to one or more facility locations jointly offering its requested services. Connecting a client to a facility incurs a connecting cost equal to the distance between the client and facility. The aim is to decide which services to lease, when, and for how long, in order to serve all clients as soon as they appear with minimum costs of leasing, connecting, and dormant fees. This variant is referred to as the Online Facility Service Leasing with Duration-Specific Dormant Fees (d-OFSL). In this paper, we design online algorithms for the metric and non-metric variants of d-OFSL. In the metric variant, facilities and clients are assumed to reside in the metric space. We measure the performance of our algorithms in the competitive analysis framework in which the online algorithm is measured against the optimal offline solution constructed by knowing all the input sequence in advance. The latter is the standard to evaluate online algorithms.