带时间窗装卸货问题的改进多策略分组编码遗传算法

通过研究求解PDPTW的分组编码遗传算法(GGA)及多策略分组编码遗传算法(MSGGA),改进了GGA中的交叉算子及MSGGA中的路径调整策略,提出了易位组合交叉算子、单车路径重排策略及需求对换策略。求解了400个客户点的标准算例集,其中4个算例lc2₄₃、lrc1₄₁、lrc2₄₂和lrc2₄₃的行驶总路程有所减少。

Improved Multi-Strategy Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows

The Pickup and Delivery Problem with Time Windows (PDPTW) is a generalization of the Vehicle Routing Problem with Time Windows (VRPTW). Since the Pickup and Delivery Problem with Time Windows is an NP-hard problem, it is difficult to obtain an optimal solution. PDPTW refers to arranging service paths for a given fleet of vehicles to meet the customers' loading and unloading needs. Each demand task consists of two demand points (customer points):one pickup location (origin) and one delivery location (destination). For each pickup and delivery location, the size of the load has to be transported from the origin to the destination by exactly one vehicle. Each demand point has a time window, that is, the earliest start time and the latest start time for loading or unloading at the point. There are enough vehicles, each with the same maximum loading capacity. Each vehicle starts from the depot and returns to the depot after completing the distribution task.Firstly, the mathematical model of the PDPTW is established. Then, by comparing the optimal solution obtained from the test with the sub-optimal solution, it is found that the vehicle routing is more or less the same, only the location of some customers in a single vehicle needs to be adjusted, or the requests in two paths need to be changed. In order to improve the Multi-Strategy Grouping Genetic Algorithm for solving the PDPTW, a translocation combination crossover operator and two path adjustment strategies are presented:single-vehicle path rearrangement strategy and requests exchange strategy. Compared with the combination crossover operator presented by Pankratz G, the translocation combination crossover operator can accelerate the optimization of the number of vehicles used. The single-vehicle path rearrangement strategy is based on the full arrangement of some customer points selected. Requests exchange strategy refers to exchanging the requests of two paths in an individual.The algorithm is tested by using Li & Lim's Pickup and Delivery Benchmark 400-Customer Problems. There are 60 examples in the case set, each of which has at least 400 customer points. In comparison to the best results published, the best results of the IMSGGA are better with respect to total travel distance in 4 cases and the same in 14 cases. Finding the appropriate path adjustment strategy will further optimize the algorithm.