IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v161y2022ics1366554522001065.html
   My bibliography  Save this article

A linear-time crystal-growth algorithm for discretization of continuum approximation

Author

Listed:
  • Fan, Hongqiang
  • Yun, Lifen
  • Li, Xiaopeng

Abstract

Continuous approximation is regarded as a scalable and insightful method for acquiring near-optimum solutions to various location problems. A continuous approximation solution is nonetheless only a continuous density function and a further discretization procedure is needed to obtain a discrete location solution for engineering practice. Inspired by the process of “crystal growth”, this paper proposes a constructive heuristic algorithm as an alternative to the classic meta-heuristic disk algorithm (Ouyang and Daganzo, 2006) in discretizing a continuous solution from a continuum approximation location model. The main idea of this algorithm is to rasterize the space into a set of small cells (either regular triangles or squares) and repeatedly grow a core cell into a full-service area according to a certain visiting sequence. Thus, it has only linear time complexity proportional to the number of cells in the space. Numerical examples are conducted to test the performance of the proposed algorithm. The results indicate that this algorithm can solve discrete facility locations more efficiently and exhibits robust performance compared with the disk algorithm.

Suggested Citation

  • Fan, Hongqiang & Yun, Lifen & Li, Xiaopeng, 2022. "A linear-time crystal-growth algorithm for discretization of continuum approximation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 161(C).
    • Handle: RePEc:eee:transe:v:161:y:2022:i:c:s1366554522001065
    DOI: 10.1016/j.tre.2022.102715
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554522001065
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2022.102715?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. Yun, Lifen & Wang, Xifu & Fan, Hongqiang & Li, Xiaopeng, 2020. "Reliable facility location design with round-trip transportation under imperfect information Part I: A discrete model," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    2. Yanfeng Ouyang & Carlos F. Daganzo, 2006. "Discretization and Validation of the Continuum Approximation Scheme for Terminal System Design," Transportation Science, INFORMS, vol. 40(1), pages 89-98, February.
    3. Tingting Cui & Yanfeng Ouyang & Zuo-Jun Max Shen, 2010. "Reliable Facility Location Design Under the Risk of Disruptions," Operations Research, INFORMS, vol. 58(4-part-1), pages 998-1011, August.
    4. Li, Xiaopeng & Ouyang, Yanfeng & Peng, Fan, 2013. "A supporting station model for reliable infrastructure location design under interdependent disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 60(C), pages 80-93.
    5. Wang, Xin & Lim, Michael K. & Ouyang, Yanfeng, 2015. "Infrastructure deployment under uncertainties and competition: The biofuel industry case," Transportation Research Part B: Methodological, Elsevier, vol. 78(C), pages 1-15.
    6. Li, Xiaopeng & Ouyang, Yanfeng, 2010. "A continuum approximation approach to reliable facility location design under correlated probabilistic disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 44(4), pages 535-548, May.
    7. Jiguang Wang & Yucai Wu, 2019. "A Continuous Approximation Approach Based on Regular Hexagon Partition for the Facility Location Problem under Disruptions Risk," Complexity, Hindawi, vol. 2019, pages 1-12, February.
    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. Xin Wang & Michael K. Lim & Yanfeng Ouyang, 2017. "A Continuum Approximation Approach to the Dynamic Facility Location Problem in a Growing Market," Transportation Science, INFORMS, vol. 51(1), pages 343-357, February.
    10. Ouyang, Yanfeng & Wang, Zhaodong & Yang, Hai, 2015. "Facility location design under continuous traffic equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 18-33.
    11. Ansari, Sina & Başdere, Mehmet & Li, Xiaopeng & Ouyang, Yanfeng & Smilowitz, Karen, 2018. "Advancements in continuous approximation models for logistics and transportation systems: 1996–2016," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 229-252.
    12. An, Shi & Cui, Na & Li, Xiaopeng & Ouyang, Yanfeng, 2013. "Location planning for transit-based evacuation under the risk of service disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 54(C), pages 1-16.
    13. Wang, Xin & Ouyang, Yanfeng, 2013. "A continuum approximation approach to competitive facility location design under facility disruption risks," Transportation Research Part B: Methodological, Elsevier, vol. 50(C), pages 90-103.
    14. Eiselt, H.A. & Marianov, Vladimir, 2012. "Mobile phone tower location for survival after natural disasters," European Journal of Operational Research, Elsevier, vol. 216(3), pages 563-572.
    15. Li, Xiaopeng & Ouyang, Yanfeng, 2011. "Reliable sensor deployment for network traffic surveillance," Transportation Research Part B: Methodological, Elsevier, vol. 45(1), pages 218-231, January.
    16. Chen, Qi & Li, Xiaopeng & Ouyang, Yanfeng, 2011. "Joint inventory-location problem under the risk of probabilistic facility disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 45(7), pages 991-1003, August.
    17. Cui, Tingting & Ouyang, Yanfeng & Shen, Zuo-Jun Max J, 2010. "Reliable Facility Location Design under the Risk of Disruptions," University of California Transportation Center, Working Papers qt5sh2c7pw, University of California Transportation Center.
    18. Ouyang, Yanfeng & Nourbakhsh, Seyed Mohammad & Cassidy, Michael J., 2014. "Continuum approximation approach to bus network design under spatially heterogeneous demand," Transportation Research Part B: Methodological, Elsevier, vol. 68(C), pages 333-344.
    19. Carlos F. Daganzo, 2005. "Logistics Systems Analysis," Springer Books, Springer, edition 0, number 978-3-540-27516-9, December.
    20. Yun, Lifen & Qin, Yong & Fan, Hongqiang & Ji, Changxu & Li, Xiaopeng & Jia, Limin, 2015. "A reliability model for facility location design under imperfect information," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 596-615.
    21. Peng, Peng & Snyder, Lawrence V. & Lim, Andrew & Liu, Zuli, 2011. "Reliable logistics networks design with facility disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 45(8), pages 1190-1211, September.
    22. Langevin, André & Mbaraga, Pontien & Campbell, James F., 1996. "Continuous approximation models in freight distribution: An overview," Transportation Research Part B: Methodological, Elsevier, vol. 30(3), pages 163-188, June.
    23. Lawrence V. Snyder & Mark S. Daskin, 2005. "Reliability Models for Facility Location: The Expected Failure Cost Case," Transportation Science, INFORMS, vol. 39(3), pages 400-416, August.
    24. Xiaopeng Li & Yanfeng Ouyang, 2012. "Reliable Traffic Sensor Deployment Under Probabilistic Disruptions and Generalized Surveillance Effectiveness Measures," Operations Research, INFORMS, vol. 60(5), pages 1183-1198, October.
    Full references (including those not matched with items on IDEAS)

    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. Ansari, Sina & Başdere, Mehmet & Li, Xiaopeng & Ouyang, Yanfeng & Smilowitz, Karen, 2018. "Advancements in continuous approximation models for logistics and transportation systems: 1996–2016," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 229-252.
    2. Yun, Lifen & Fan, Hongqiang & Li, Xiaopeng, 2019. "Reliable facility location design with round-trip transportation under imperfect information part II: A continuous model," Transportation Research Part B: Methodological, Elsevier, vol. 124(C), pages 44-59.
    3. An, Shi & Cui, Na & Bai, Yun & Xie, Weijun & Chen, Mingliu & Ouyang, Yanfeng, 2015. "Reliable emergency service facility location under facility disruption, en-route congestion and in-facility queuing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 82(C), pages 199-216.
    4. Cui, Jianxun & Zhao, Meng & Li, Xiaopeng & Parsafard, Mohsen & An, Shi, 2016. "Reliable design of an integrated supply chain with expedited shipments under disruption risks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 143-163.
    5. Wang, Zhaodong & Xie, Siyang & Ouyang, Yanfeng, 2022. "Planning reliable service facility location against disruption risks and last-mile congestion in a continuous space," Transportation Research Part B: Methodological, Elsevier, vol. 165(C), pages 123-140.
    6. Wang, Xin & Lim, Michael K. & Ouyang, Yanfeng, 2015. "Infrastructure deployment under uncertainties and competition: The biofuel industry case," Transportation Research Part B: Methodological, Elsevier, vol. 78(C), pages 1-15.
    7. Yun, Lifen & Wang, Xifu & Fan, Hongqiang & Li, Xiaopeng, 2020. "Reliable facility location design with round-trip transportation under imperfect information Part I: A discrete model," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    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. Yun, Lifen & Qin, Yong & Fan, Hongqiang & Ji, Changxu & Li, Xiaopeng & Jia, Limin, 2015. "A reliability model for facility location design under imperfect information," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 596-615.
    10. Zarrinpoor, Naeme & Fallahnezhad, Mohammad Saber & Pishvaee, Mir Saman, 2018. "The design of a reliable and robust hierarchical health service network using an accelerated Benders decomposition algorithm," European Journal of Operational Research, Elsevier, vol. 265(3), pages 1013-1032.
    11. An, Shi & Cui, Na & Li, Xiaopeng & Ouyang, Yanfeng, 2013. "Location planning for transit-based evacuation under the risk of service disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 54(C), pages 1-16.
    12. Li, Xiaopeng & Ouyang, Yanfeng & Peng, Fan, 2013. "A supporting station model for reliable infrastructure location design under interdependent disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 60(C), pages 80-93.
    13. Lei, Chao & Ouyang, Yanfeng, 2018. "Continuous approximation for demand balancing in solving large-scale one-commodity pickup and delivery problems," Transportation Research Part B: Methodological, Elsevier, vol. 109(C), pages 90-109.
    14. Yu, Guodong & Zhang, Jie, 2018. "Multi-dual decomposition solution for risk-averse facility location problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 70-89.
    15. Yun Bai & Xiaopeng Li & Fan Peng & Xin Wang & Yanfeng Ouyang, 2015. "Effects of Disruption Risks on Biorefinery Location Design," Energies, MDPI, vol. 8(2), pages 1-19, February.
    16. Aldrighetti, Riccardo & Battini, Daria & Ivanov, Dmitry & Zennaro, Ilenia, 2021. "Costs of resilience and disruptions in supply chain network design models: A review and future research directions," International Journal of Production Economics, Elsevier, vol. 235(C).
    17. Weijun Xie & Yanfeng Ouyang & Sze Chun Wong, 2016. "Reliable Location-Routing Design Under Probabilistic Facility Disruptions," Transportation Science, INFORMS, vol. 50(3), pages 1128-1138, August.
    18. Ouyang, Yanfeng & Wang, Zhaodong & Yang, Hai, 2015. "Facility location design under continuous traffic equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 18-33.
    19. Lifen Yun & Xifu Wang & Hongqiang Fan & Xiaopeng Li, 2017. "A reliable facility location design model with site-dependent disruption in the imperfect information context," PLOS ONE, Public Library of Science, vol. 12(5), pages 1-18, May.
    20. Xiaopeng Li & Yanfeng Ouyang, 2012. "Reliable Traffic Sensor Deployment Under Probabilistic Disruptions and Generalized Surveillance Effectiveness Measures," Operations Research, INFORMS, vol. 60(5), pages 1183-1198, October.

    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:eee:transe:v:161:y:2022:i:c:s1366554522001065. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    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.