Abstract
Computers & Operations Research, Volume 136, p105509 (2021) Dynamic routing occurs when customers are not known in advance, e.g. for
real-time routing. Two heuristics are proposed that solve the balanced dynamic
multiple travelling salesmen problem (BD-mTSP). These heuristics represent
operational (tactical) tools for dynamic (online, real-time) routing. Several
types and scopes of dynamics are proposed. Particular attention is given to
sequential dynamics. The balanced dynamic closest vehicle heuristic (BD-CVH)
and the balanced dynamic assignment vehicle heuristic (BD-AVH) are applied to
this type of dynamics. The algorithms are applied to a wide range of test
instances. Taxi services and palette transfers in warehouses demonstrate how to
use the BD-mTSP algorithms in real-world scenarios. Continuous approximation
models for the BD-mTSP's are derived and serve as strategic tools for dynamic
routing. The models express route lengths using vehicles, customers, and
dynamic scopes without the need of running an algorithm. A machine learning
approach was used to obtain regression models. The mean absolute percentage
error of two of these models is below 3%.