基于邻域搜索的成品油多舱多目标配送路径优化算法研究

Variable neighborhood search for the multi-objective multi-compartment optimization of refined products distribution

针对成品油配送中多车型,多车舱的优化调度难题,综合考虑路径安排,舱位指派及车辆指派等决策.以配送成本最小,路径风险最小以及油品准时送达为目标,建立了成品油配送多目标路径优化模型.基于邻域搜索的基本思想,提出求解成品油配送多目标路径优化问题的MOVNS算法框架,并结合不同的可行解运行策略和比较准则,衍生出三类MOVNS算法(MOVNS-1、MOVNS-2、MOVNS-3).采用12组算例进行数值实验,结果表明,三种算法均能有效的求解配送模型,提升成品油多舱配送问题的解决效率;且MOVNS-2算法具有较强的局部搜索能力,MOVNS-3算法容易跳出局部最优:同时,考虑节点关联性的可行解构造策略和并行邻域搜索策略能够增强算法的寻优能力.

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.