For Libraries For Publication Open Access Downloads About Us Contact Us
Paper Titles
Sybil Node Discovery Based on Group Location Information
p.1088
The Research on the Axis-Symmetric Development and Verification for the Positive Scheme Numerical Method
p.1096
The Upper Bound of Primitive Exponent of a Class of Special Nonnegative Matrix Pairs
p.1100
Ubiquitous Library Service System Architecture Research Based on Cloud Computing
p.1104
Optimization of Multi-Depot Heterogeneous Incident Vehicle Routing Problem with Soft Time Windows Based on an Improved Ant Colony Optimization
p.1108
Watermarking Scheme Resilient to Geometrical Attacks Base Normalized Feature Area
p.1118
A Study on Static Water Resistance Prediction of Offshore Wind Turbine Installation Vessel
p.1124
Contrastive Analysis on Parameter Identification of Unmanned Gliding-Hydrofoil Craft’s Maneuverability Based on GA and PSO
p.1129
Grillage Structural Optimization Based on Genetic Algorithm and Mechanical Direct Calculation
p.1135

Optimization of Multi-Depot Heterogeneous Incident Vehicle Routing Problem with Soft Time Windows Based on an Improved Ant Colony Optimization

Article Preview

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.

You might also be interested in these eBooks
Research in Materials and Manufacturing Technologies IV View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 1061-1062)

Pages:

1108-1117

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.1061-1062.1108

Citation:

Cite this paper

Online since:

December 2014

Authors:

Ya Lian Tang*, Yan Guang Cai, Qi Jiang Yang

Keywords:

3-Opt Strategy, GA, IACO, MDHIVRPSTW, Smooth Mechanism

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

© 2015 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

* - Corresponding Author

References

[1] Gulczynski D, Golden B, Wasil E. the multi-depot split delivery vehicle routing problem: An integer programming-based heuristic, new test problems, and computational results. Computers & Industrial Engineering, (2011), 61(3): 794-804.

DOI: 10.1016/j.cie.2011.05.012

Google Scholar

[2] Rahimi-Vahed A, Crainic T G, Gendreau M, Rei W. A path relinking algorithm for a multi-depot periodic vehicle routing problem. Journal of Heuristics, (2013), 19(3): 497-524.

DOI: 10.1007/s10732-013-9221-2

Google Scholar

[3] Ho W, Ho G T S, Ji P, Lau H C W. A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, (2008), 21(4): 548-557.

DOI: 10.1016/j.engappai.2007.06.001

Google Scholar

[4] Tu W, Fang Z, Li Q, Shaw S L, Chen B Y. A bi-level Voronoi diagram-based metaheuristic for a large-scale multi-depot vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, (2014), 61: 84-97.

DOI: 10.1016/j.tre.2013.11.003

Google Scholar

[5] Yu B, Ma N, Cai W J, Li T, Yuan X T, Yao B Z et al. Improved ant colony optimisation for the dynamic multi-depot vehicle routing problem. International Journal of Logistics Research and Applications, (2013), 16(2): 144-157.

DOI: 10.1080/13675567.2013.810712

Google Scholar

[6] Mirabi M. A hybrid electromagnetism algorithm for multi-depot periodic vehicle routing problem. The International Journal of Advanced Manufacturing Technology, (2014): 509-518.

DOI: 10.1007/s00170-013-5501-0

Google Scholar

[7] Geetha S, Poonthalir G, Vanathi P T. Nested particle swarm optimisation for multi–depot vehicle routing problem. International Journal of Operational Research, (2013), 16(3): 329-348.

DOI: 10.1504/ijor.2013.052336

Google Scholar

[8] LIU J, MA Z. Multi-depot open vehicle routing problem with time windows based on vehicle leasing and sharing. Systems Engineering-Theory & Practice, (2013), 3: 015.

Google Scholar

[9] Mirabi M, Fatemi Ghomi S M T, Jolai F. Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem. Robotics and Computer-Integrated Manufacturing, (2010), 26(6): 564-569.

DOI: 10.1016/j.rcim.2010.06.023

Google Scholar

[10] Yu B, Yang Z Z, Xie J X. A parallel improved ant colony optimization for multi-depot vehicle routing problem. Journal of the Operational Research Society, (2011), 62(1): 183-188.

DOI: 10.1057/jors.2009.161

Google Scholar

[11] Kuo Y, Wang C C. A variable neighborhood search for the multi-depot vehicle routing problem with loading cost. Expert Systems with Applications, (2012), 39(8): 6949-6954.

DOI: 10.1016/j.eswa.2012.01.024

Google Scholar

[12] Bettinelli A, Ceselli A, Righini G. A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies, (2011), 19(5): 723-740.

DOI: 10.1016/j.trc.2010.07.008

Google Scholar

[13] Surekha P, Sumathi S. Solution To Multi-Depot Vehicle Routing Problem Using Genetic Algorithms. World Applied Programming, (2011), 1(3): 118-131.

Google Scholar

[14] Yao B, Hu P, Zhang M, et al. Artificial bee colony algorithm with scanning strategy for the periodic vehicle routing problem. Simulation, (2013), 89(6): 762-770.

DOI: 10.1177/0037549713481503

Google Scholar

[15] Tsai C C, Huang H C, Chan C K. Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation. Industrial Electronics, IEEE Transactions on, (2011), 58(10): 4813-4821.

DOI: 10.1109/tie.2011.2109332

Google Scholar

[16] Saeheaw T, Charoenchai N, Chattinnawat W. Application of Ant colony optimization for Multi-objective Production Problems. World Academy of Science, Engineering and Technology, (2009), 60: 654-659.

Google Scholar

[17] Qu D P, Tu H, Fan T S. Performance Analysis of Local Optimization Algorithms in Traveling Salesman Problem. Advanced Materials Research, (2014), 846: 1364-1367.

DOI: 10.4028/www.scientific.net/amr.846-847.1364

Google Scholar

© 2025 Trans Tech Publications Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies. For open access content, terms of the Creative Commons licensing CC-BY are applied.
Scientific.Net is a registered trademark of Trans Tech Publications Ltd.