Pareto Improver: Learning Improvement Heuristics for Multi-Objective Route Planning

As a research hotspot across logistics, operations research, and artificial intelligence, route planning has become a key technology for intelligent transportation systems. Recently, data-driven machine learning heuristics, including learning construction methods and learning improvement methods, have achieved remarkable success in solving single-objective route planning problems. However, many practical route planning scenarios must simultaneously consider multiple conflict objectives. For example, modern logistics companies often need to simultaneously minimize time budget, transportation cost, and vehicle pollution. Several learning construction methods are proposed for solving classical multi-objective route planning (MORP) problems, yet no learning improvement heuristics have been developed so far, even though they are acknowledged to be more efficient in narrowing the optimality gap. To fill this gap, this paper proposes a learning improvement MORP method, Pareto Improver (PI). PI employs a population-based mechanism to approximate the Pareto front with a single deep reinforcement learning model. The experimental results on various MORP problems show that PI can significantly outperform other state-of-the-art methods.