Distance approximation to support customer selection in vehicle routing problems
本文用简单回归模型和少量特征预测旅行商问题和车辆路径问题的总距离，帮助快速选择客户或分配任务，在虚构和真实案例中均比启发式方法节省距离。
Abstract Estimating the solution value of transportation problems can be useful to assign customers to days for multi-period vehicle routing problems, or to make customer selection decisions very fast (e.g., within an online environment). In this paper, we apply several regression methods to predict the total distance of the traveling salesman problem (TSP) and vehicle routing problem (VRP). We show that distance can be estimated fairly accurate using simple regression models and only a limited number of features. Besides using features found in the scientific literature, we also introduce new classes of spatial features. The model is validated on a fictional case with different spatial instances considering both a backordering and lost sales configuration, and on a realistic case that involves dynamic waste collection in the city of Amsterdam, The Netherlands. For the fictional case, we show differences in performance per instance type and configuration, and we show that our model can save up to $$25.3\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>25.3</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> in distance compared with a heuristic approximation. For the waste collection case, we introduce a cost function that combines the travel distance and service level, and show that our model can reduce distances up to 17% compared to a well-known heuristic approximation while maintaining the same service level. Furthermore, we show the benefits of using approximations for combining offline learning with online or frequent optimization.