Vehicle Routing Problem With Simultaneous Pickup And Delivery Based On Particle Swarm Optimization

In recent years, with the reduction of renewable resources and the growing awareness of environmental protection, people increasingly pay attention to the energy recovery and utilization. Besides, the "Saving Society" policy supported by the government makes the combination of forward logistics together with reverse logistics become a requirement of the times. Therefore, a great many of research interests have been shown on vehicle routing problem with simultaneous pickup and delivery (VRPSPD).Current research on VRPSPD is still not deep enough. Moreover, due to the large scalability in current practical problem, algorithms with less running time and relative acceptable problem-solving ability are needed in practice. With the aim of the difficulties in solving them, a customer pre-assigned two-phase heuristic algorithm is developed. We first deploy different vehicles, with algorithm used to assign customer groups to delivery vehicles, so customers are assigned to the same vehicle, the angle of which with the datum mark is only slightly different. Secondly we propose a modified particle swarm optimization to arrange customers visiting sequences for every vehicle. In process of optimization, the infeasible routes which violate the capability constraint are not abjured but adjusted before the next iteration. So the number of infeasible routes decreases through this adjustment, and it can help the particle to move forward to a more feasible solution.In order to verify the effectiveness and efficiency of the proposed algorithm, a large number of simulation experiments have been carried out. They can be divided into two parts:experiments on vehicle routing problem and vehicle routing problem with simultaneous pickup and delivery. The experimental results prove the feasibility and validity of the proposed method which can obtain the efficient solution within short time. Therefore, it can be used to solve the real-life large-scale vehicle routing problem. At last, the thesis predicts the application prospect of the improved particle swarm optimization and gives some directions of future research.