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

Oded Berman, Dimitris Bertsimas and Richard C. Larson
Additional contact information
Oded Berman: University of Toronto, Toronto, Ontario, Canada
Dimitris Bertsimas: Massachusetts Institute of Technology, Cambridge, Massachusetts
Richard C. Larson: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1995, vol. 43, issue 4, 623-632

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.

Keywords: financial institutions; banks; locating automatic teller machines; networks/graphs; heuristics; locating n points to intercept max flow; transportation; models; location; maximizing flow of potential customers (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (24)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.4.623 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:43:y:1995:i:4:p:623-632

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().