1. Optimization of Multi-Depot Heterogeneous Incident Vehicle Routing Problem with Soft Time Windows Based on an Improved Ant Colony Optimization
- Author
-
Qi Jiang Yang, Yan Guang Cai, and Ya Lian Tang
- Subjects
Engineering ,Mathematical optimization ,Mutation probability ,business.industry ,Ant colony optimization algorithms ,Convergence (routing) ,Crossover ,Vehicle routing problem ,General Engineering ,Soft time windows ,Local search (optimization) ,business - Abstract
Aiming at vehicle routing problem (VRP) with many extended features is widely used in actual life, multi-depot heterogeneous vehicle routing problem with soft time windows (MDHIVRPSTW) mathematical model is established. An improved ant colony optimization (IACO) is proposed for solving this model. Firstly, MDHIVRPSTW was transferred into different groups according to nearest depot method, then constructing the initial route by scanning algorithm (SA). Secondly, genetic operators were introduced, and then adjusting crossover probability and mutation probability adaptively in order to improve the global search ability of the algorithm. Moreover, smooth mechanism was used to improve the performance of ant colony optimization (ACO). Finally, 3-opt strategy was used to improve the local search ability. The proposed IACO has been tested on a 32-customer instance which was generated randomly. The experimental results show that IACO is superior to other three algorithms in terms of convergence speed and solution quality, thus the proposed method is effective and feasible, and the proposed model is better than conventional model.
- Published
- 2014