关键词: 车辆路径问题, 模糊时间窗, 动态规划, 多目标禁忌搜索, Pareto最优

Abstract: The Vehicle Routing Problem with Fuzzy Time Windows is addressed. A multi-objective mathematical model is designed with the objectives of logistics cost and average customer satisfaction. Based on Pareto dominance theory, a multi-objective tabu search algorithm is proposed to solve multi-objective optimization problems. Moreover, a dynamic programming method is embedded in the algorithm to optimize the customer satisfaction, which simplifies the original problem into tight path optimization sub-problems with the use of phasing. While fuzzy time windows are in piecewise linear and nonlinear convex membership function forms, customer beginning service time is optimized by proposed limited iteration subgradient algorithm and median iteration subgradient algorithm, respectively. Computational experiments on Solomon’s benchmark not only verify that the dynamic programming is more effective than projected subgradient methods to optimize the service level, but also show the advantages of the proposed multi-objective tabu search approach when compared with the well-known NSGA-II method.

Key words: vehicle routing problem, fuzzy time windows, dynamic programming, multi-objective tabu search, Pareto optimization