Locating Discretionary Service Facilities, II: Maximizing Market Size, Minimizing Inconvenience

Oded Berman · Dimitris Bertsimas · Richard Charles Larson

105 citations0/0 files storedOperations Research

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Facility Location and Emergency Management Complexity and Algorithms in Graphs Vehicle Routing Optimization Methods

Abstract

Discretionary service facilities are providers of products and/or services that are purchased by customers who are traveling on otherwise preplanned trips such as the daily commute. Optimum location of such facilities requires them to be at or near points in the transportation network having sizable flows of different potential customers. N. Fouska (Fouska, N. 1988. Optimal Location of Discretionary Service Facilities. MS Thesis, Operations Research Center, MIT, Cambridge, Mass.) and O. Berman, R. Larson and N. Fouska (BLF [Berman, O., R. C. Larson, N. Fouska. 1992. Optimal location of discretionary service facilities. Trans. Sci. 26(3) 201–211.]) formulate a first version of this problem, assuming that customers would make no deviations, no matter how small, from the preplanned route to visit a discretionary service facility. Here the model is generalized in a number of directions, all sharing the property that the customer may deviate from the preplanned route to visit a discretionary service facility. Three different generalizations are offered, two of which can be solved approximately by greedy heuristics and the third by any approximate or exact method used to solve the p-median problem. We show for those formulations yielding to a greedy heuristic approximate solution, including the formulation in BLF, that the problems are examples of optimizing submodular functions for which the G. Nemhauser, L. Wolsey and M. Fisher (Nemhauser, G. L., L. A. Wolsey, M. L. Fisher. 1978. An analysis of approximations for maximizing sub-modular set functions, I. Math. Prog. 14 265–294.) bound on the performance of a greedy algorithm holds. In particular, the greedy solution is always within 37% of optimal, and for one of the formulations we prove that the bound is tight.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 105 citations exist upstream.

References

1964Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph 1991Discrete location theory 1990A Flow‐Capturing Location‐Allocation Model 1992Optimal Location of Discretionary Service Facilities

Cited by

2013Networks and Spatial Economics 2008A Generalized Model for Locating Facilities on a Network with Flow-Based Demand 2014Heuristic approaches for the flow-based set covering problem with deviation paths 2019A healthcare network design model with mobile hospitals for disaster preparedness: A case study for Istanbul earthquake 2002Solving the competitive discretionary service facility location problem 2017Deviation-flow refueling location problem with capacitated facilities: Model and algorithm 2019Node-based vs. path-based location models for urban hydrogen refueling stations: Comparing convenience and coverage abilities 1996Locating flow-capturing units on a network with multi-counting and diminishing returns to scale

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.