超启发式遗传算法求解带软时间窗的车辆路径问题

Hyper-heuristic genetic algorithm for vehicle routing problem with soft time windows

针对车辆路径问题中传统软时间窗惩罚函数过于线性的问题,考虑客户容忍水平,提出一种折线型软时间窗,并构造出相应的惩罚函数。在此基础上,以运输配送总成本最小为目标,构造出一种带折线型软时间窗的车辆路径问题通用数学模型。同时,提出一种具有一定通用性的超启发式遗传算法,该算法以遗传算法作为上层搜索算法,以3种启发式算法——CW节约法、MJ插入法和Kilby插入法作为底层搜索规则,并通过预排序、局部搜索和全局优化来优化算法。最后,通过Solomon标准题库中的R101算例分析并验证了所提算法的可行性和有效性。

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.