论文标题
平衡的动态多重旅行推销员：算法和连续近似
Balanced dynamic multiple travelling salesmen: algorithms and continuous approximations
论文作者
论文摘要
当客户未提前知道时，就会发生动态路由，例如用于实时路由。提出了两个启发式方法，可以解决平衡的动态多重旅行人员问题（BD-MTSP）。这些启发式方法代表了动态（在线，实时）路由的操作（战术）工具。提出了几种类型和动力学范围。特别注意顺序动力学。平衡的动态最接近的车辆启发式（BD-CVH）和平衡的动态分配车辆启发式（BD-AVH）被应用于这种类型的动力学。将算法应用于广泛的测试实例。仓库中的出租车服务和调色板转移演示了如何在实际情况下使用BD-MTSP算法。 BD-MTSP的连续近似模型被得出，并用作动态路由的战略工具。模型使用车辆，客户和动态范围表示路线长度，而无需运行算法。使用机器学习方法来获得回归模型。这两个模型的平均绝对百分比误差低于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%.
