## Abstract

Given a tour in a metric space, the latency of the vertex v is the distance traveled along the tour starting from the root and arriving at v for the first time. The minimum latency problem (MLP) is to find a tour visiting all given vertices such that the total latency of these vertices is minimized. We consider an online variant in traffic networks, where as many as ℓ edges are to be blocked during the traversal, for a non-negative integer ℓ. We first prove a lower bound on the competitive ratio for any online algorithm and then propose an online algorithm GoodTreeTraversal, which is demonstrated to be near optimal if there is a good k-tree for every k in the range from 2 to n and the number of blockages is large enough. We also present a polynomial time heuristic algorithm called Detour, which is much faster than GoodTreeTraversal. The numerical experiments demonstrate the efficiency and effectiveness of our two algorithms.

Original language | English |
---|---|

Pages (from-to) | 418-429 |

Number of pages | 12 |

Journal | European Journal of Operational Research |

Volume | 273 |

Issue number | 2 |

DOIs | |

State | Published - Mar 1 2019 |

## Keywords

- Canadian traveler problem
- Competitive ratio
- Minimum latency problem
- Routing
- Traffic blockage