1. An Improved Genetic Algorithm for Multi-Depot Heterogeneous Vehicle Routing Problem with Simultaneous Pickup and Delivery Time Windows
- Author
-
Qi Jiang Yang, Yan Guang Cai, and Ya Lian Tang
- Subjects
Engineering ,Mathematical optimization ,Branch and bound ,Time windows ,business.industry ,Vehicle routing problem ,Neighborhood search ,Inversion (meteorology) ,Pickup ,General Medicine ,business ,Algorithm ,Merge (version control) - Abstract
Multi-depot heterogeneous vehicle routing problem with simultaneous pickup and delivery and time windows (MDHVRPSPDTW) is an extension of vehicle routing problem (VRP), MDHVRPSPDTW mathematical model was established. The improved genetic algorithm (IGA) is proposed for solving the model. Firstly, MDHVRPSPDTW is transferred into different groups by the seed customer selecting method and scanning algorithm (SA).Secondly, IGA based on elite selection and inversion operator is used to solve the model, and then cutting merge strategy based on greedy thought and three kinds of neighborhood search methods is applied to optimize the feasible solutions further. Finally, 3-opt local search is applied to adjust the solution. The proposed IGA has been test on a random new numerical example.The computational results show that IGA is superior to branch and bound algorithm (BBD) by Lingo 9.0 in terms of optimum speed and solution quality, and the model and the proposed approach is effective and feasible.
- Published
- 2015