A multi-start route improving matheuristic for the production routeing problem
提出一种新的数学启发式算法求解多车辆生产路径问题，在1218个基准实例中改进或找到632个最优解，剩余实例偏差小于2.5%，尤其擅长大规模实例。
This paper considers the multi-vehicle production routeing problem with a maximum-level replenishment policy. This is a well-established problem within vendor managed inventory where production, inventory and routeing decisions are made simultaneously. We present a novel method to solve the problem that outperforms existing methods both in terms of solution gaps and the number of best-known solutions. The proposed matheuristic is tested on three different sets of benchmark instances consisting of 1218 instances and finds or improves the best-known solution for 632 of them. For the remaining instances, the matheuristic is less than 2.5% from the best-known solutions. The method is particularly proficient on large instances and is also efficient for the inventory routeing problem. The success of the method is largely due to its improvement phase where a novel path-flow-inspired mathematical model is introduced. Here, a route set obtained from the current solution is used and retailers can be simultaneously inserted and removed from a route, making the method flexible even when a small route set is used. In addition, we introduce a new production subproblem that approximates the costs of using a vehicle instead of approximating the costs of visiting a retailer, making it very fast to solve.