IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v47y2024i3d10.1007_s10878-024-01113-1.html
   My bibliography  Save this article

Minimizing the expense transmission time from the source node to demand nodes

Author

Listed:
  • Mehdi Ghiyasvand

    (Bu-Ali Sina University)

  • Iman Keshtkar

    (Bu-Ali Sina University)

Abstract

An undirected graph $$G=(V,A)$$ G = ( V , A ) by a set V of n nodes, a set A of m edges, and two sets $$S,\ D\subseteq V$$ S , D ⊆ V consists of source and demand nodes are given. This paper presents two new versions of location problems which are called the $$f(\sigma )$$ f ( σ ) -location and $$g(\sigma )$$ g ( σ ) -location problems. We define an $$f(\sigma )$$ f ( σ ) -location of the network N as a node $$s\in S$$ s ∈ S with the property that the maximum expense transmission time from the node s to the destinations of D is as cheap as possible. The $$f(\sigma )$$ f ( σ ) -location problem divides the range $$(0,\infty )$$ ( 0 , ∞ ) into intervals $$\displaystyle \cup _{i}{(a_i,b_i)}$$ ∪ i ( a i , b i ) and finds a source $$s_i\in S$$ s i ∈ S , for each interval $$(a_i,b_i)$$ ( a i , b i ) , such that $$s_i$$ s i is a $$f(\sigma )$$ f ( σ ) -location for each $$\sigma \in (a_i,b_i)$$ σ ∈ ( a i , b i ) . Also, define a $$g(\sigma )$$ g ( σ ) -location as a node s of S with the property that the sum of expense transmission times from the node s to all destinations of D is as cheap as possible. The $$g(\sigma )$$ g ( σ ) -location problem divides the range $$(0,\infty )$$ ( 0 , ∞ ) into intervals $$\displaystyle \cup _{i}{(a_i,b_i)}$$ ∪ i ( a i , b i ) and finds a source $$s_i\in S$$ s i ∈ S , for each interval $$(a_i,b_i)$$ ( a i , b i ) , such that $$s_i$$ s i is a $$g(\sigma )$$ g ( σ ) -location for each $$\sigma \in (a_i,b_i)$$ σ ∈ ( a i , b i ) . This paper presents two strongly polynomial time algorithms to solve $$f(\sigma )$$ f ( σ ) -location and $$g(\sigma )$$ g ( σ ) -location problems.

Suggested Citation

  • Mehdi Ghiyasvand & Iman Keshtkar, 2024. "Minimizing the expense transmission time from the source node to demand nodes," Journal of Combinatorial Optimization, Springer, vol. 47(3), pages 1-18, April.
  • Handle: RePEc:spr:jcomop:v:47:y:2024:i:3:d:10.1007_s10878-024-01113-1
    DOI: 10.1007/s10878-024-01113-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-024-01113-1
    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/s10878-024-01113-1?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. Kien Nguyen & Lam Anh, 2015. "Inverse $$k$$ k -centrum problem on trees with variable vertex weights," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 82(1), pages 19-30, August.
    2. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    3. Gilbert Laporte & Stefan Nickel & Francisco Saldanha Gama, 2015. "Introduction to Location Science," Springer Books, in: Gilbert Laporte & Stefan Nickel & Francisco Saldanha da Gama (ed.), Location Science, edition 127, chapter 0, pages 1-18, Springer.
    4. A. J. Goldman, 1971. "Optimal Center Location in Simple Networks," Transportation Science, INFORMS, vol. 5(2), pages 212-221, May.
    5. Kien Trung Nguyen & Huong Nguyen-Thu & Nguyen Thanh Hung, 2018. "On the complexity of inverse convex ordered 1-median problem on the plane and on tree networks," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 88(2), pages 147-159, October.
    6. G. Y. Handler, 1973. "Minimax Location of a Facility in an Undirected Tree Graph," Transportation Science, INFORMS, vol. 7(3), pages 287-293, August.
    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. Esmaeil Afrashteh & Behrooz Alizadeh & Fahimeh Baroughi, 2020. "Optimal approaches for upgrading selective obnoxious p-median location problems on tree networks," Annals of Operations Research, Springer, vol. 289(2), pages 153-172, June.
    2. Chunsong Bai & Jun Du, 2024. "The Constrained 2-Maxian Problem on Cycles," Mathematics, MDPI, vol. 12(6), pages 1-9, March.
    3. Igor Averbakh & Wei Yu, 2020. "Multi-depot traveling salesmen location problems on networks with special structure," Annals of Operations Research, Springer, vol. 286(1), pages 635-648, March.
    4. Mulder, H.M. & Pelsmajer, M.J. & Reid, K.B., 2006. "Generalized centrality in trees," Econometric Institute Research Papers EI 2006-16, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    5. Musolino, Giuseppe & Rindone, Corrado & Polimeni, Antonio & Vitetta, Antonino, 2019. "Planning urban distribution center location with variable restocking demand scenarios: General methodology and testing in a medium-size town," Transport Policy, Elsevier, vol. 80(C), pages 157-166.
    6. Le Xuan Dai & Kien Trung Nguyen & Le Phuong Thao & Pham Thi Vui, 2024. "Some robust inverse median problems on trees with interval costs," Computational Management Science, Springer, vol. 21(2), pages 1-25, December.
    7. Van Huy Pham & Nguyen Chi Tam, 2019. "A combinatorial algorithm for the ordered 1-median problem on cactus graphs," OPSEARCH, Springer;Operational Research Society of India, vol. 56(3), pages 780-789, September.
    8. Wei Ding & Ke Qiu, 2018. "A quadratic time exact algorithm for continuous connected 2-facility location problem in trees," Journal of Combinatorial Optimization, Springer, vol. 36(4), pages 1262-1298, November.
    9. Kien Trung Nguyen & Nguyen Thanh Hung, 2020. "The inverse connected p-median problem on block graphs under various cost functions," Annals of Operations Research, Springer, vol. 292(1), pages 97-112, September.
    10. Esmaeil Afrashteh & Behrooz Alizadeh & Fahimeh Baroughi & Kien Trung Nguyen, 2018. "Linear Time Optimal Approaches for Max-Profit Inverse 1-Median Location Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(05), pages 1-22, October.
    11. Trung Kien Nguyen & Nguyen Thanh Hung & Huong Nguyen-Thu, 2020. "A linear time algorithm for the p-maxian problem on trees with distance constraint," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 1030-1043, November.
    12. 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.
    13. Rainer E. Burkard & Johannes Hatzl, 2010. "Median problems with positive and negative weights on cycles and cacti," Journal of Combinatorial Optimization, Springer, vol. 20(1), pages 27-46, July.
    14. Lee, Chungmok & Han, Jinil, 2017. "Benders-and-Price approach for electric vehicle charging station location problem under probabilistic travel range," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 130-152.
    15. Shuihua Han & Yudi Mo & Linlin Chen & Zongwei Luo & Cyril R. H. Foropon & H. M. Belal, 2025. "A multi-period closed-loop supply chain network design with circular route planning," Annals of Operations Research, Springer, vol. 348(3), pages 1195-1233, May.
    16. A. Anaya-Arenas & J. Renaud & A. Ruiz, 2014. "Relief distribution networks: a systematic review," Annals of Operations Research, Springer, vol. 223(1), pages 53-79, December.
    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. Arthur Mahéo & Diego Gabriel Rossit & Philip Kilby, 2023. "Solving the integrated bin allocation and collection routing problem for municipal solid waste: a Benders decomposition approach," Annals of Operations Research, Springer, vol. 322(1), pages 441-465, March.
    19. Liu, Yubin & Ye, Qiming & Escribano-Macias, Jose & Feng, Yuxiang & Candela, Eduardo & Angeloudis, Panagiotis, 2023. "Route planning for last-mile deliveries using mobile parcel lockers: A hybrid q-learning network approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    20. Burcin Bozkaya & Seda Yanik & Selim Balcisoy, 2010. "A GIS-Based Optimization Framework for Competitive Multi-Facility Location-Routing Problem," Networks and Spatial Economics, Springer, vol. 10(3), pages 297-320, September.

    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:jcomop:v:47:y:2024:i:3:d:10.1007_s10878-024-01113-1. 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.