Home // INTERNET 2024, The Sixteenth International Conference on Evolving Internet // View article

Vehicle Routing in a Dynamic Mesh

Authors:
Ying Ying Liu
Parimala Thulasiraman

Keywords: Dynamic Mesh; Online Shortest Path; Online Greedy Algorithm; Online Dijkstra’s, Online Ant Colony Optimization.

Abstract:
We model the traffic-aware vehicle routing problem as an online problem and study online algorithms for this problem on a dynamic directed mesh. In this problem, traffic is represented as edge weights. At each time step, edge weights increase or decreases randomly. The goal of a vehicle is to find a path from the top-left corner source node S to bottom-right corner destination node T, such that the sum of edge weights on the path is minimized. We first study lower bounds on the competitive ratios for any deterministic online algorithm for the problem, and competitive analysis with bounded adversarial traffic, randomization and advice. Following the competitive analysis, we propose 9 online algorithms for the problem using deterministic, randomized and advice variants of the Greedy algorithm, Weighted Greedy algorithm, Dijkstra’s algorithm, and Ant Colony Optimization. Our experiment shows that algorithms with advice, representing traffic in the future, find the best solutions among the algorithms in comparison. Our experiment also shows that although simple randomization technique does not help the greedy algorithms in our problem setting, the more sophisticated randomization strategy used by ACO is promising. Compared to ACO, the greedy algorithms are very fast with comparable solution quality. They may be favored in practice for their speed and simplicity.

Pages: 32 to 38

Copyright: Copyright (c) IARIA, 2024

Publication date: March 10, 2024

Published in: conference

ISSN: 2308-443X

ISBN: 978-1-68558-133-6

Location: Athens, Greece

Dates: from March 10, 2024 to March 14, 2024