IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v295y2021i1p51-65.html
   My bibliography  Save this article

Weighted online minimum latency problem with edge uncertainty

Author

Listed:
  • Akbari, Vahid
  • Shiri, Davood

Abstract

In the minimum latency problem, an undirected connected graph and a root node together with non-negative edge distances are given to an agent. The agent looks for a tour starting at the root node and visiting all the nodes to minimise the sum of the latencies of the nodes, where the latency of a node is the distance from the root node to the node at its first visit on the tour by the agent. We study an online variant of the problem, where there are k blocked edges in the graph which are not known to the agent in advance. A blocked edge is learned online when the agent arrives at one of its end-nodes. Furthermore, we investigate another online variant of the minimum latency problem involving k blocked edges where each node is associated with a weight to express its priority and the objective is to minimise the summation of the weighted latency of the nodes. In this paper, we prove that the lower bound of 2k+1 on the competitive ratio of deterministic online algorithms is tight for both weighted and non-weighted variations by introducing an optimal deterministic online algorithm which meets this lower bound. We also present a lower bound of k+1 on the expected competitive ratio of randomized online algorithms for both problems. We then develop two polynomial time heuristic algorithms to solve these online problems. We test our algorithms on real life as well as randomly generated instances that are partially adopted from the literature.

Suggested Citation

  • Akbari, Vahid & Shiri, Davood, 2021. "Weighted online minimum latency problem with edge uncertainty," European Journal of Operational Research, Elsevier, vol. 295(1), pages 51-65.
    • Handle: RePEc:eee:ejores:v:295:y:2021:i:1:p:51-65
    DOI: 10.1016/j.ejor.2021.02.038
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172100151X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.02.038?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. Luo, Zhixing & Qin, Hu & Lim, Andrew, 2014. "Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints," European Journal of Operational Research, Elsevier, vol. 234(1), pages 49-60.
    2. Patrick Jaillet & Michael R. Wagner, 2006. "Online Routing Problems: Value of Advanced Information as Improved Competitive Ratios," Transportation Science, INFORMS, vol. 40(2), pages 200-210, May.
    3. Silva, Marcos Melo & Subramanian, Anand & Vidal, Thibaut & Ochi, Luiz Satoru, 2012. "A simple and effective metaheuristic for the Minimum Latency Problem," European Journal of Operational Research, Elsevier, vol. 221(3), pages 513-520.
    4. Davood Shiri & F. Sibel Salman, 2017. "On the online multi-agent O–D k-Canadian Traveler Problem," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 453-461, August.
    5. Zhang, Huili & Tong, Weitian & Xu, Yinfeng & Lin, Guohui, 2015. "The Steiner Traveling Salesman Problem with online edge blockages," European Journal of Operational Research, Elsevier, vol. 243(1), pages 30-40.
    6. Kasaei, Maziar & Salman, F. Sibel, 2016. "Arc routing problems to restore connectivity of a road network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 177-206.
    7. Ajam, Meraj & Akbari, Vahid & Salman, F. Sibel, 2019. "Minimizing latency in post-disaster road clearance operations," European Journal of Operational Research, Elsevier, vol. 277(3), pages 1098-1112.
    8. Jean-Claude Picard & Maurice Queyranne, 1978. "The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling," Operations Research, INFORMS, vol. 26(1), pages 86-110, February.
    9. Akbari, Vahid & Salman, F. Sibel, 2017. "Multi-vehicle synchronized arc routing problem to restore post-disaster network connectivity," European Journal of Operational Research, Elsevier, vol. 257(2), pages 625-640.
    10. Marco Bender & Stephan Westphal, 2015. "An optimal randomized online algorithm for the $$k$$ k -Canadian Traveller Problem on node-disjoint paths," Journal of Combinatorial Optimization, Springer, vol. 30(1), pages 87-96, July.
    11. Davood Shiri & F. Sibel Salman, 2019. "Competitive analysis of randomized online strategies for the multi-agent k-Canadian Traveler Problem," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 848-865, April.
    12. Bock, Stefan, 2015. "Solving the traveling repairman problem on a line with general processing times and deadlines," European Journal of Operational Research, Elsevier, vol. 244(3), pages 690-703.
    13. Davood Shiri & Vahid Akbari & F. Sibel Salman, 2020. "Online routing and scheduling of search-and-rescue teams," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(3), pages 755-784, September.
    14. Sahin, Halenur & Kara, Bahar Yetis & Karasan, Oya Ekin, 2016. "Debris removal during disaster response: A case for Turkey," Socio-Economic Planning Sciences, Elsevier, vol. 53(C), pages 49-59.
    15. Moshref-Javadi, Mohammad & Lee, Seokcheon, 2016. "The Latency Location-Routing Problem," European Journal of Operational Research, Elsevier, vol. 255(2), pages 604-619.
    16. Davood Shiri & F. Sibel Salman, 2019. "On the randomized online strategies for the k-Canadian traveler problem," Journal of Combinatorial Optimization, Springer, vol. 38(1), pages 254-267, July.
    17. Huili Zhang & Yinfeng Xu & Lan Qin, 2013. "The k-Canadian Travelers Problem with communication," Journal of Combinatorial Optimization, Springer, vol. 26(2), pages 251-265, August.
    18. Özdamar, Linet & Ertem, Mustafa Alp, 2015. "Models, solutions and enabling technologies in humanitarian logistics," European Journal of Operational Research, Elsevier, vol. 244(1), pages 55-65.
    19. Zhang, Huili & Tong, Weitian & Lin, Guohui & Xu, Yinfeng, 2019. "Online minimum latency problem with edge uncertainty," European Journal of Operational Research, Elsevier, vol. 273(2), pages 418-429.
    20. Matteo Fischetti & Gilbert Laporte & Silvano Martello, 1993. "The Delivery Man Problem and Cumulative Matroids," Operations Research, INFORMS, vol. 41(6), pages 1055-1064, December.
    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. Akbari, Vahid & Shiri, Davood & Sibel Salman, F., 2021. "An online optimization approach to post-disaster road restoration," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 1-25.
    2. Tippong, Danuphon & Petrovic, Sanja & Akbari, Vahid, 2022. "A review of applications of operational research in healthcare coordination in disaster management," European Journal of Operational Research, Elsevier, vol. 301(1), pages 1-17.
    3. Vahid Akbari & İhsan Sadati & F. Sibel Salman & Davood Shiri, 2023. "Minimizing total weighted latency in home healthcare routing and scheduling with patient prioritization," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 45(3), pages 807-852, September.
    4. Davood Shiri & Hakan Tozan, 2022. "Online routing and searching on graphs with blocked edges," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1039-1059, September.

    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. Akbari, Vahid & Shiri, Davood & Sibel Salman, F., 2021. "An online optimization approach to post-disaster road restoration," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 1-25.
    2. Ajam, Meraj & Akbari, Vahid & Salman, F. Sibel, 2022. "Routing multiple work teams to minimize latency in post-disaster road network restoration," European Journal of Operational Research, Elsevier, vol. 300(1), pages 237-254.
    3. Davood Shiri & Hakan Tozan, 2022. "Online routing and searching on graphs with blocked edges," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1039-1059, September.
    4. Ajam, Meraj & Akbari, Vahid & Salman, F. Sibel, 2019. "Minimizing latency in post-disaster road clearance operations," European Journal of Operational Research, Elsevier, vol. 277(3), pages 1098-1112.
    5. Davood Shiri & Vahid Akbari, 2021. "Online Failure Diagnosis in Interdependent Networks," SN Operations Research Forum, Springer, vol. 2(1), pages 1-14, March.
    6. Souza Almeida, Luana & Goerlandt, Floris & Pelot, Ronald, 2022. "Trends and gaps in the literature of road network repair and restoration in the context of disaster response operations," Socio-Economic Planning Sciences, Elsevier, vol. 84(C).
    7. Davood Shiri & Vahid Akbari & F. Sibel Salman, 2020. "Online routing and scheduling of search-and-rescue teams," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(3), pages 755-784, September.
    8. Moreno, Alfredo & Alem, Douglas & Gendreau, Michel & Munari, Pedro, 2020. "The heterogeneous multicrew scheduling and routing problem in road restoration," Transportation Research Part B: Methodological, Elsevier, vol. 141(C), pages 24-58.
    9. Aakil M. Caunhye & Nazli Yonca Aydin & H. Sebnem Duzgun, 2020. "Robust post-disaster route restoration," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(4), pages 1055-1087, December.
    10. Farzaneh, Mohammad Amin & Rezapour, Shabnam & Baghaian, Atefe & Amini, M. Hadi, 2023. "An integrative framework for coordination of damage assessment, road restoration, and relief distribution in disasters," Omega, Elsevier, vol. 115(C).
    11. Bruni, M.E. & Khodaparasti, S. & Beraldi, P., 2020. "The selective minimum latency problem under travel time variability: An application to post-disaster assessment operations," Omega, Elsevier, vol. 92(C).
    12. Yichen Lu & Chao Yang & Jun Yang, 2022. "A multi-objective humanitarian pickup and delivery vehicle routing problem with drones," Annals of Operations Research, Springer, vol. 319(1), pages 291-353, December.
    13. Rivera, Juan Carlos & Murat Afsar, H. & Prins, Christian, 2016. "Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 249(1), pages 93-104.
    14. Zhang, Huili & Tong, Weitian & Lin, Guohui & Xu, Yinfeng, 2019. "Online minimum latency problem with edge uncertainty," European Journal of Operational Research, Elsevier, vol. 273(2), pages 418-429.
    15. F. Angel-Bello & Y. Cardona-Valdés & A. Álvarez, 2019. "Mixed integer formulations for the multiple minimum latency problem," Operational Research, Springer, vol. 19(2), pages 369-398, June.
    16. Zhang, Guowei & Zhu, Ning & Ma, Shoufeng & Xia, Jun, 2021. "Humanitarian relief network assessment using collaborative truck-and-drone system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    17. Ha-Bang Ban, 2021. "A metaheuristic for the delivery man problem with time windows," Journal of Combinatorial Optimization, Springer, vol. 41(4), pages 794-816, May.
    18. Morshedlou, Nazanin & González, Andrés D. & Barker, Kash, 2018. "Work crew routing problem for infrastructure network restoration," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 66-89.
    19. Oruc, Buse Eylul & Kara, Bahar Yetis, 2018. "Post-disaster assessment routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 76-102.
    20. Albert Einstein Fernandes Muritiba & Tibérius O. Bonates & Stênio Oliveira Da Silva & Manuel Iori, 2021. "Branch-and-Cut and Iterated Local Search for the Weighted k -Traveling Repairman Problem: An Application to the Maintenance of Speed Cameras," Transportation Science, INFORMS, vol. 55(1), pages 139-159, 1-2.

    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:ejores:v:295:y:2021:i:1:p:51-65. 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/locate/eor .

    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.