Given a set of facilities and clients, and costs to open facilities, the classic facility location problem seeks to
open a set of facilities and assign each client to one open facility to minimize the cost of opening the chosen
facilities and the total distance of the clients to their assigned open facilities. Such an objective may induce an
unequal cost over certain socioeconomic groups of clients (i.e., total distance traveled by clients in such a
group). This is important when planning the location of socially relevant facilities such as emergency rooms.
In this work, we consider a fair version of the problem where we are given ๐ clients groups that partition
the set of clients, and the distance of a given group is defined as the average distance of clients in the group
to their respective open facilities. The objective is to minimize the Minkowski ๐-norm of vector of group
distances, to penalize high access costs to open facilities across ๐ groups of clients. This generalizes classic
facility location (๐ = 1) and the minimization of the maximum group distance (๐ = โ). However, in practice,
fairness criteria may not be explicit or even known to a decision maker, and it is often unclear how to select a
specific "๐" to model the cost of unfairness. To get around this, we study the notion of solution portfolios where
for a fixed problem instance, we seek a small portfolio of solutions such that for any Minkowski norm ๐, one
of these solutions is an ๐(1)-approximation. Using the geometric relationship between various ๐-norms, we
show the existence of a portfolio of cardinality ๐(log ๐), and a lower bound of (\sqrt{log r}).
There may not be common structure across different solutions in this portfolio, which can make planning
difficult if the notion of fairness changes over time or if the budget to open facilities is disbursed over time. For
example, small changes in ๐ could lead to a completely different set of open facilities in the portfolio. Inspired
by this, we introduce the notion of refinement, which is a family of solutions for each ๐-norm satisfying a
combinatorial property. This property requires that (1) the set of facilities open for a higher ๐-norm must be
a subset of the facilities open for a lower ๐-norm, and (2) all clients assigned to an open facility for a lower
๐-norm must be assigned to the same open facility for any higher ๐-norm. A refinement is ๐ผ-approximate if
the solution for each ๐-norm problem is an ๐ผ-approximation for it. We show that it is sufficient to consider
only ๐(log ๐) norms instead of all ๐-norms, ๐ โ [1, โ] to construct refinements. A natural greedy algorithm
for the problem gives a poly(๐)-approximate refinement, which we improve to poly(r^1/\sqrt{log ๐})-approximate
using a recursive algorithm. We improve this ratio to ๐(log ๐) for the special case of tree metric for uniform
facility open cost. Our recursive algorithm extends to other settings, including to a hierarchical facility location
problem that models facility location problems at several levels, such as public works departments and schools.
A full version of this paper can be found at https://arxiv.org/abs/2211.14873.
more »
« less
Online Facility Assignment
We consider the online facility assignment problem, with a set of facilities F of equal capacity l in metric space and customers arriving one by one in an online manner. We must assign customer ci to facility fj before the next customer ci+1 arrives. The cost of this assignment is the distance between ci and fj. The total number of customers is at most |F|l and each customer must be assigned to a facility. The objective is to minimize the sum of all assignment costs. We first consider the case where facilities are placed on a line so that the distance between adjacent facilities is the same and customers appear anywhere on the line. We describe a greedy algorithm with competitive ratio 4|F| and another one with competitive ratio |F|. Finally, we consider a variant in which the facilities are placed on the vertices of a graph and two algorithms in that setting.
more »
« less
- Award ID(s):
- 1712119
- NSF-PAR ID:
- 10065742
- Date Published:
- Journal Name:
- Walcom
- ISSN:
- 1374-5379
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
On-demand warehousing platforms match companies with underutilized warehouse and distribution capabilities with customers who need extra space or distribution services. These new business models have unique advantages, in terms of reduced capacity and commitment granularity, but also have different cost structures compared with traditional ways of obtaining distribution capabilities. This research is the first quantitative analysis to consider distribution network strategies given the advent of on-demand warehousing. Our multi-period facility location model โ a mixed-integer linear program โ simultaneously determines location-allocation decisions of three distribution center types (self-distribution, 3PL/lease, on-demand). A simulation model operationally evaluates the impact of the planned distribution strategy when various uncertainties can occur. Computational experiments for a company receiving products produced internationally to fulfil a set of regional customer demands illustrate that the power of on-demand warehousing is in creating hybrid network designs that more efficiently use self-distribution facilities through improved capacity utilization. However, the business case for on-demand warehousing is shown to be influenced by several factors, namely on-demand capacity availability, responsiveness requirements, and demand patterns. This work supports a firmโs use of on-demand warehousing if it has tight response requirements, for example for same-day delivery; however, if a firm has relaxed response requirements, then on-demand warehousing is only recommended if capacity availability of planned on-demand services is high. We also analyze capacity flexibility options leased by third-party logistics companies for a premium price and draw attention to the importance of them offering more granular solutions to stay competitive in the market.more » « less
-
more » « less
We study the problem of maximizing payoff generated over a period of time in a general class of closed queueing networks with a finite, fixed number of supply units that circulate in the system. Demand arrives stochastically, and serving a demand unit (customer) causes a supply unit to relocate from the โoriginโ to the โdestinationโ of the customer. The key challenge is to manage the distribution of supply in the network. We consider general controls including customer entry control, pricing, and assignment. Motivating applications include shared transportation platforms and scrip systems. Inspired by the mirror descent algorithm for optimization and the backpressure policy for network control, we introduce a rich family of mirror backpressure (MBP) control policies. The MBP policies are simple and practical and crucially do not need any statistical knowledge of the demand (customer) arrival rates (these rates are permitted to vary in time). Under mild conditions, we propose MBP policies that are provably near optimal. Specifically, our policies lose at most [Formula: see text] payoff per customer relative to the optimal policy that knows the demand arrival rates, where K is the number of supply units, T is the total number of customers over the time horizon, and ฮท is the demand processโ average rate of change per customer arrival. An adaptation of MBP is found to perform well in numerical experiments based on data from NYC Cab.
This paper was accepted by Gabriel Weintraub, revenue management and market analytics.
Funding: Y. Kanoria was supported by the National Science Foundationโs Division of Civil, Mechanical, and Manufacturing Innovation [Grant CMMI-1653477].
Supplemental Material: The data files and online appendices are available at https://doi.org/10.1287/mnsc.2023.4934 .
-
more » « less
Abstract In this paper, we present a drone-based delivery system that assumes to deal with a mixed-area, i.e., two areas, one rural and one urban, placed side-by-side. In the mixed-areas, called EM-grids, the distances are measured with two different metrics, and the shortest path between two destinations concatenates the Euclidean and Manhattan metrics. Due to payload constraints, the drone serves a single customer at a time returning back to the dispatching point (DP) after each delivery to load a new parcel for the next customer. In this paper, we present the
$$1$$ MEMP ) for EM-grids, whose goal is to determine the droneโs DP position that minimizes the sum of the distances between all the locations to be served and the point itself. We study theMEMP on two different scenarios, i.e., one in which all the customers in the area need to be served (full-grid) and another one where only a subset of these must be served (partial-grid). For the full-grid scenario we devise optimal and approximation algorithms, while for the partial-grid scenario we devise an optimal algorithm. -
We consider evacuation of a group of n โฅ 2 autonomous mobile agents (or robots) from an unknown exit on an infinite line. The agents are initially placed at the origin of the line and can move with any speed up to the maximum speed 1 in any direction they wish and they all can communicate when they are co-located. However, the agents have different wireless communication abilities: while some are fully wireless and can send and receive messages at any distance, a subset of the agents are senders, they can only transmit messages wirelessly, and the rest are receivers, they can only receive messages wirelessly. The agents start at the same time and their communication abilities are known to each other from the start. Starting at the origin of the line, the goal of the agents is to collectively find a target/exit at an unknown location on the line while minimizing the evacuation time, defined as the time when the last agent reaches the target. We investigate the impact of such a mixed communication model on evacuation time on an infinite line for a group of cooperating agents. In particular, we provide evacuation algorithms and analyze the resulting competitive ratio (CR) of the evacuation time for such a group of agents. If the group has two agents of two different types, we give an optimal evacuation algorithm with competitive ratio CR = 3+2โ2. If there is a single sender or fully wireless agent, and multiple receivers we prove that CR โ [2+โ5,5], and if there are multiple senders and a single receiver or fully wireless agent, we show that CR โ [3,5.681319]. Any group consisting of only senders or only receivers requires competitive ratio 9, and any other combination of agents has competitive ratio 3.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
