Dynamic multi-period vehicle routing with touting
研究了在动态多周期车辆路径问题中，通过主动招揽尚未下单的客户来优化路线，提出了基于客户特征和当前计划的招揽策略，并在真实垃圾收集场景中验证了其减少行驶距离的效果。
This paper introduces a dynamic multi-period vehicle routing problem with touting as demand management technique, where customers that have not yet placed an order can be actively encouraged to order a service sooner. Touting the right customers, such as those located nearby customers who already placed orders, allows for more efficient routes over time. However, it also increases the frequency of visits at such touted customers as they are serviced before they would normally require, which leads to smaller demand volumes per visit. To tackle this trade-off, we propose several strategies to decide which customers to tout and when, using the characteristics of the customers as well as the current plan at the time of touting. Specifically, using the demand and the location information, we approach the ones which are close to the current tour, relatively far from the depot and not likely to easily be covered in the near future. This information is then used as a part of different touting strategies, which are further embedded in a rolling-time horizon vehicle routing algorithm to address the multi-period nature of the problem. These different strategies are empirically compared in a simulation based on a real-world waste collection problem. We demonstrate that touting indeed allows to significantly reduce the travel distance in a dynamic vehicle routing problem.