Refined products distribution is an extension of the multi-compartment vehicle routing problem, which has to simultaneously consider the vehicle routing, the assignment of heterogonous trucks and loading policies of multi-compartment. An optimum model is developed with the objectives of minimizing the transport cost, the transport risk, and the time penalty cost. This article proposes a multi-objective variable neighborhood search (MOVNS) framework based on neighborhood search, which derive three MOVNS algorithms (MOVNS-1, MOVNS-2, MOVNS-3) when combined with different searching strategies and comparison criteria of feasible solutions. And extensive computational tests on 12 instances confirm the efficiency of the proposed algorithms. MOVNS-2 is equipped with stronger local search ability, and MOVNS-3 could avoid the poor local optimum effectively. Moreover, the route construction with relation degree between vertexes and the parallel search strategy can enhance the search ability of the algorithm. © 2019, Editorial Board of Journal of Systems Engineering Society of China. All right reserved.
