IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v43y1995i4p623-632.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Oded Berman & Dimitris Bertsimas & Richard C. Larson, 1995. "Locating Discretionary Service Facilities, II: Maximizing Market Size, Minimizing Inconvenience," Operations Research, INFORMS, vol. 43(4), pages 623-632, August.
    • Handle: RePEc:inm:oropre:v:43:y:1995:i:4:p:623-632
    DOI: 10.1287/opre.43.4.623
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.43.4.623
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.43.4.623?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Lin, Cheng-Chang & Lin, Chuan-Chih, 2018. "The p-center flow-refueling facility location problem," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 124-142.
    2. Wu, Tai-Hsi & Lin, Jen-Nan, 2003. "Solving the competitive discretionary service facility location problem," European Journal of Operational Research, Elsevier, vol. 144(2), pages 366-378, January.
    3. Ho-Yin Mak & Ying Rong & Zuo-Jun Max Shen, 2013. "Infrastructure Planning for Electric Vehicles with Battery Swapping," Management Science, INFORMS, vol. 59(7), pages 1557-1575, July.
    4. Hernandez, Adrian & Ng, Max & Durango-Cohen, Pablo L. & Mahmassani, Hani S., 2024. "Optimizing service networks to support freight rail decarbonization: Flow selection, facility location, and energy sourcing," European Journal of Operational Research, Elsevier, vol. 317(3), pages 906-920.
    5. Barros, Lilian & Riley, Michael, 2001. "A combinatorial approach to level of repair analysis," European Journal of Operational Research, Elsevier, vol. 129(2), pages 242-251, March.
    6. Yongxi Huang & Shengyin Li & Zhen Qian, 2015. "Optimal Deployment of Alternative Fueling Stations on Transportation Networks Considering Deviation Paths," Networks and Spatial Economics, Springer, vol. 15(1), pages 183-204, March.
    7. Miyagawa, Masashi, 2010. "Distributions of rectilinear deviation distance to visit a facility," European Journal of Operational Research, Elsevier, vol. 205(1), pages 106-112, August.
    8. Li, Xiaopeng & Ma, Jiaqi & Cui, Jianxun & Ghiasi, Amir & Zhou, Fang, 2016. "Design framework of large-scale one-way electric vehicle sharing systems: A continuum approximation model," Transportation Research Part B: Methodological, Elsevier, vol. 88(C), pages 21-45.
    9. Weiping Zeng & Ignacio Castillo & M. Hodgson, 2010. "A Generalized Model for Locating Facilities on a Network with Flow-Based Demand," Networks and Spatial Economics, Springer, vol. 10(4), pages 579-611, December.
    10. Ivan Contreras & Elena Fernández, 2014. "Hub Location as the Minimization of a Supermodular Set Function," Operations Research, INFORMS, vol. 62(3), pages 557-570, June.
    11. Wu, Shanhua & Yang, Zhongzhen, 2018. "Locating manufacturing industries by flow-capturing location model – Case of Chinese steel industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 112(C), pages 1-11.
    12. Yang, Woosuk, 2018. "A user-choice model for locating congested fast charging stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 110(C), pages 189-213.
    13. Yudai Honma & Daisuke Hasegawa & Katsuhiro Hata & Takashi Oguchi, 2024. "Locational Analysis of In-motion Wireless Power Transfer System for Long-distance Trips by Electric Vehicles: Optimal Locations and Economic Rationality in Japanese Expressway Network," Networks and Spatial Economics, Springer, vol. 24(1), pages 261-290, March.
    14. Acar, Müge & Kaya, Onur, 2019. "A healthcare network design model with mobile hospitals for disaster preparedness: A case study for Istanbul earthquake," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 273-292.
    15. Li, Shengyin & Huang, Yongxi, 2014. "Heuristic approaches for the flow-based set covering problem with deviation paths," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 144-158.
    16. Tong, Daoqin & Ren, Fang & Mack, James, 2012. "Locating farmers’ markets with an incorporation of spatio-temporal variation," Socio-Economic Planning Sciences, Elsevier, vol. 46(2), pages 149-156.
    17. Capar, Ismail & Kuby, Michael & Leon, V. Jorge & Tsai, Yu-Jiun, 2013. "An arc cover–path-cover formulation and strategic analysis of alternative-fuel station locations," European Journal of Operational Research, Elsevier, vol. 227(1), pages 142-151.
    18. Taymaz, S. & Iyigun, C. & Bayindir, Z.P. & Dellaert, N.P., 2020. "A healthcare facility location problem for a multi-disease, multi-service environment under risk aversion," Socio-Economic Planning Sciences, Elsevier, vol. 71(C).
    19. Tanaka, Ken-ichi & Furuta, Takehiro & Toriumi, Shigeki, 2019. "Railway flow interception location model: Model development and case study of Tokyo metropolitan railway network," Operations Research Perspectives, Elsevier, vol. 6(C).
    20. Timothy C. Matisziw, 2019. "Maximizing Expected Coverage of Flow and Opportunity for Diversion in Networked Systems," Networks and Spatial Economics, Springer, vol. 19(1), pages 199-218, March.
    21. Bogyrbayeva, Aigerim & Kwon, Changhyun, 2021. "Pessimistic evasive flow capturing problems," European Journal of Operational Research, Elsevier, vol. 293(1), pages 133-148.
    22. Guo, Fang & Yang, Jun & Lu, Jianyi, 2018. "The battery charging station location problem: Impact of users’ range anxiety and distance convenience," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 1-18.
    23. Marković, Nikola & Ryzhov, Ilya O. & Schonfeld, Paul, 2017. "Evasive flow capture: A multi-period stochastic facility location problem with independent demand," European Journal of Operational Research, Elsevier, vol. 257(2), pages 687-703.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:43:y:1995:i:4:p:623-632. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.