Optimizing Task Waiting Times in Dynamic Vehicle Routing

Journal article (2023)

Authors

Alexander Botros University of Waterloo
Barry Gilhuly University of Waterloo
N. Wilde Learning & Autonomous Control - Mechanical, Maritime and Materials Engineering
Armin Sadeghi University of Waterloo
J. Alonso-Mora Learning & Autonomous Control - Mechanical, Maritime and Materials Engineering
Stephen L. Smith University of Waterloo
Research Group
Learning & Autonomous Control (Mechanical, Maritime and Materials Engineering) (TU Delft)
Copyright: © 2023 Alexander Botros, Barry Gilhuly, N. Wilde, Armin Sadeghi, J. Alonso-Mora, Stephen L. Smith
DOI: https://doi.org/10.1109/LRA.2023.3295251
Cost function Robots Vehicle dynamics Vehicle routing Costs Task analysis Robot kinematics Path Planning for Multiple Mobile Robots or Agents Planning, Scheduling and Coordination Task Planning
More Info
expand_more

Published Date

2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Mechanical, Maritime and Materials Engineering

Department

Cognitive Robotics

Research Group

Learning & Autonomous Control

Abstract

We study the problem of deploying a fleet of mobile robots to service tasks that arrive stochastically over time and at random locations in an environment. This is known as the Dynamic Vehicle Routing Problem (DVRP) and requires robots to allocate incoming tasks among themselves and find an optimal sequence for each robot. State-of-the-art approaches only consider average wait times and focus on high-load scenarios where the arrival rate of tasks approaches the limit of what can be handled by the robots while keeping the queue of unserviced tasks bounded, i.e., stable. To ensure stability, these approaches repeatedly compute minimum distance tours over a set of newly arrived tasks. This letter is aimed at addressing the missing policies for moderate-load scenarios, where quality of service can be improved by prioritizing long-waiting tasks. We introduce a novel DVRP policy based on a cost function that takes the p-norm over accumulated wait times and show it guarantees stability even in high-load scenarios. We demonstrate that the proposed policy outperforms the state-of-the-art in both mean and 95th percentile wait times in moderate-load scenarios through simulation experiments in the Euclidean plane as well as using real-world data for city scale service requests.