Balanced dynamic multiple travelling salesmen: algorithms and continuous approximations
This provides operational and strategic tools for dynamic routing applications like taxi services and warehouse logistics, but it is incremental as it builds on existing mTSP methods.
The paper tackles the balanced dynamic multiple traveling salesmen problem (BD-mTSP) for real-time routing by proposing two heuristics (BD-CVH and BD-AVH) and deriving continuous approximation models, with the models achieving a mean absolute percentage error below 3%.
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%.