Abstract: 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.

Key words: pickup and delivery problem with time windows, Genetic Algorithm, path adjustment strategy