关键词: 车辆路径问题, 软时间窗, 容忍水平, 遗传算法, 超启发式

Abstract: The penalty function of traditional soft time window is too linear in Vehicle Routing Problem(VRP).To solve this problem,a new kind of broken line soft time window was proposed by taking the customer tolerance level into consideration,and the corresponding penalty function was constructed.On this basis,a general mathematical model of VRP with broken line soft time window was constructed with the objective of minimizing the total cost of transportation and distribution.Meanwhile,a commonality hyper-heuristicgenetic algorithm was presented.Within the hyper-heuristic framework,the genetic algorithm was used as the upper level search algorithm,and three heuristic algorithms (clarke-wright algorithm,mole-jameson insert algorithm and kilby insert algorithm) were used as the underlying search rules.The algorithm was optimized by pre-sorting,local search and global optimization.The example of R101 in Solomon benchmark problems was conducted to validate the feasibility and effectiveness of the proposed algorithm.

Key words: vehicle routing problem, soft time windows, tolerance level, genetic algorithms, hyper-heuristic