IDEAS home Printed from https://ideas.repec.org/a/spr/comgts/v14y2017i4d10.1007_s10287-017-0289-2.html
   My bibliography  Save this article

Using tropical optimization to solve constrained minimax single-facility location problems with rectilinear distance

Author

Listed:
  • Nikolai Krivulin

    (St. Petersburg State University)

Abstract

The aim of this paper is twofold: first, to extend the area of applications of tropical optimization by solving new constrained location problems, and second, to offer new closed-form solutions to general problems that are of interest to location analysis. We consider a constrained minimax single-facility location problem with addends on the plane with rectilinear distance. The solution commences with the representation of the problem in a standard form, and then in terms of tropical mathematics, as a constrained optimization problem. We use a transformation technique, which can act as a template to handle optimization problems in other application areas, and hence is of independent interest. To solve the constrained optimization problem, we apply methods and results of tropical optimization, which provide direct, explicit solutions. The results obtained serve to derive new solutions of the location problem, and of its special cases with reduced sets of constraints, in a closed form, ready for practical implementation and immediate computation. As illustrations, numerical solutions of example problems and their graphical representation are given. We conclude with an application of the results to optimal location of the central monitoring facility in an indoor video surveillance system in a multi-floor building environment.

Suggested Citation

  • Nikolai Krivulin, 2017. "Using tropical optimization to solve constrained minimax single-facility location problems with rectilinear distance," Computational Management Science, Springer, vol. 14(4), pages 493-518, October.
  • Handle: RePEc:spr:comgts:v:14:y:2017:i:4:d:10.1007_s10287-017-0289-2
    DOI: 10.1007/s10287-017-0289-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10287-017-0289-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10287-017-0289-2?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hansen, Pierre & Thisse, Jacques-Francois, 1981. "Outcomes of voting and planning : Condorcet, Weber and Rawls locations," Journal of Public Economics, Elsevier, vol. 16(1), pages 1-15, August.
    2. Jack Elzinga & Donald W. Hearn, 1972. "Geometrical Solutions for Some Minimax Location Problems," Transportation Science, INFORMS, vol. 6(4), pages 379-394, November.
    3. Jack Elzinga & Donald W. Hearn, 1973. "Letter to the Editor---A Note on a Minimax Location Problem," Transportation Science, INFORMS, vol. 7(1), pages 100-103, February.
    4. Francis, Richard L. & McGinnis, Leon F. & White, John A., 1983. "Locational analysis," European Journal of Operational Research, Elsevier, vol. 12(3), pages 220-252, March.
    5. P. M. Dearing & R. L. Francis, 1974. "A Minimax Location Problem on a Network," Transportation Science, INFORMS, vol. 8(4), pages 333-343, November.
    6. Nikolai Krivulin, 2017. "Direct solution to constrained tropical optimization problems with application to project scheduling," Computational Management Science, Springer, vol. 14(1), pages 91-113, January.
    7. ReVelle, C. S. & Eiselt, H. A., 2005. "Location analysis: A synthesis and survey," European Journal of Operational Research, Elsevier, vol. 165(1), pages 1-19, August.
    8. P. M. Dearing & R. L. Francis, 1974. "A Network Flow Solution to a Multifacility Minimax Location Problem Involving Rectilinear Distances," Transportation Science, INFORMS, vol. 8(2), pages 126-141, May.
    9. Margaret L. Brandeau & Samuel S. Chiu, 1989. "An Overview of Representative Problems in Location Research," Management Science, INFORMS, vol. 35(6), pages 645-674, June.
    10. George O. Wesolowsky, 1972. "Rectangular Distance Location under the Minimax Optimality Criterion," Transportation Science, INFORMS, vol. 6(2), pages 103-113, May.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Nikolai Krivulin, 2021. "Algebraic Solution of Tropical Polynomial Optimization Problems," Mathematics, MDPI, vol. 9(19), pages 1-18, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Alan Murray, 2010. "Advances in location modeling: GIS linkages and contributions," Journal of Geographical Systems, Springer, vol. 12(3), pages 335-354, September.
    2. Kress, Dominik & Pesch, Erwin, 2012. "Sequential competitive location on networks," European Journal of Operational Research, Elsevier, vol. 217(3), pages 483-499.
    3. Polten, Lukas & Emde, Simon, 2022. "Multi-shuttle crane scheduling in automated storage and retrieval systems," European Journal of Operational Research, Elsevier, vol. 302(3), pages 892-908.
    4. Pokutta, Sebastian & Schmaltz, Christian, 2011. "Managing liquidity: Optimal degree of centralization," Journal of Banking & Finance, Elsevier, vol. 35(3), pages 627-638, March.
    5. Gaigné, C. & Hovelaque, V. & Mechouar, Y., 2020. "Carbon tax and sustainable facility location: The role of production technology," International Journal of Production Economics, Elsevier, vol. 224(C).
    6. Xu, Jianhua & Johnson, Michael P. & Fischbeck, Paul S. & Small, Mitchell J. & VanBriesen, Jeanne M., 2010. "Robust placement of sensors in dynamic water distribution systems," European Journal of Operational Research, Elsevier, vol. 202(3), pages 707-716, May.
    7. Ting L. Lei & Richard L. Church, 2014. "Vector Assignment Ordered Median Problem," International Regional Science Review, , vol. 37(2), pages 194-224, April.
    8. Pablo Santibáñez & Georgia Bekiou & Kenneth Yip, 2009. "Fraser Health Uses Mathematical Programming to Plan Its Inpatient Hospital Network," Interfaces, INFORMS, vol. 39(3), pages 196-208, June.
    9. Abhishek Bhatnagar & Nomesh B. Bolia, 2023. "A sustainable decision‐making framework for school consolidation policy," Regional Science Policy & Practice, Wiley Blackwell, vol. 15(5), pages 1037-1063, June.
    10. Türker Tanergüçlü & Hakan Maraş & Cevriye Gencer & Haluk Aygüneş, 2012. "A decision support system for locating weapon and radar positions in stationary point air defence," Information Systems Frontiers, Springer, vol. 14(2), pages 423-444, April.
    11. Maksim Barketau & Erwin Pesch, 2016. "An approximation algorithm for a special case of the asymmetric travelling salesman problem," International Journal of Production Research, Taylor & Francis Journals, vol. 54(14), pages 4205-4212, July.
    12. Kazuo Yamaguchi, 2022. "Spatial bargaining in rectilinear facility location problem," Theory and Decision, Springer, vol. 93(1), pages 69-104, July.
    13. Khachatryan, Hayk & Jessup, Eric & Casavant, Kenneth, 2010. "A GIS-based Estimation of Regional Biomass Supply and Transportation Costs for Biofuel Plant Least-Cost Location Decisions," 51st Annual Transportation Research Forum, Arlington, Virginia, March 11-13, 2010 207816, Transportation Research Forum.
    14. Amiri, Ali, 2006. "Designing a distribution network in a supply chain system: Formulation and efficient solution procedure," European Journal of Operational Research, Elsevier, vol. 171(2), pages 567-576, June.
    15. Owen, Susan Hesse & Daskin, Mark S., 1998. "Strategic facility location: A review," European Journal of Operational Research, Elsevier, vol. 111(3), pages 423-447, December.
    16. Batta, Rajan & Lejeune, Miguel & Prasad, Srinivas, 2014. "Public facility location using dispersion, population, and equity criteria," European Journal of Operational Research, Elsevier, vol. 234(3), pages 819-829.
    17. Christian Haket & Bo van der Rhee & Jacques de Swart, 2020. "Saving Time and Money and Reducing Carbon Dioxide Emissions by Efficiently Allocating Customers," Interfaces, INFORMS, vol. 50(3), pages 153-165, May.
    18. Erdemir, Elif Tokar & Batta, Rajan & Spielman, Seth & Rogerson, Peter A. & Blatt, Alan & Flanigan, Marie, 2008. "Location coverage models with demand originating from nodes and paths: Application to cellular network design," European Journal of Operational Research, Elsevier, vol. 190(3), pages 610-632, November.
    19. Derya Celik Turkoglu & Mujde Erol Genevois, 2020. "A comparative survey of service facility location problems," Annals of Operations Research, Springer, vol. 292(1), pages 399-468, September.
    20. Myung, Young-Soo & Kim, Hu-gon & Tcha, Dong-wan, 1997. "A bi-objective uncapacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 100(3), pages 608-616, August.

    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:spr:comgts:v:14:y:2017:i:4:d:10.1007_s10287-017-0289-2. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.