A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 6 Issue 2
Mar.  2019

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2019  >  6(2): 516-526
Ling Wang and Jiawen Lu, "A Memetic Algorithm With Competition for the Capacitated Green Vehicle Routing Problem," IEEE/CAA J. Autom. Sinica, vol. 6, no. 2, pp. 516-526, Mar. 2019. doi: 10.1109/JAS.2019.1911405
Citation: Ling Wang and Jiawen Lu, "A Memetic Algorithm With Competition for the Capacitated Green Vehicle Routing Problem," IEEE/CAA J. Autom. Sinica, vol. 6, no. 2, pp. 516-526, Mar. 2019. doi: 10.1109/JAS.2019.1911405
shu

A Memetic Algorithm With Competition for the Capacitated Green Vehicle Routing Problem

doi: 10.1109/JAS.2019.1911405

  • Department of Automation, Tsinghua University, Beijing 100084, China

Funds:

the National Science Fund for Distinguished Young Scholars of China 61525304

the National Natural Science Foundation of China 61873328

More Information
    Abstract
  • In this paper, a memetic algorithm with competition (MAC) is proposed to solve the capacitated green vehicle routing problem (CGVRP). Firstly, the permutation array called traveling salesman problem (TSP) route is used to encode the solution, and an effective decoding method to construct the CGVRP route is presented accordingly. Secondly, the k-nearest neighbor (kNN) based initialization is presented to take use of the location information of the customers. Thirdly, according to the characteristics of the CGVRP, the search operators in the variable neighborhood search (VNS) framework and the simulated annealing (SA) strategy are executed on the TSP route for all solutions. Moreover, the customer adjustment operator and the alternative fuel station (AFS) adjustment operator on the CGVRP route are executed for the elite solutions after competition. In addition, the crossover operator is employed to share information among different solutions. The effect of parameter setting is investigated using the Taguchi method of design-of-experiment to suggest suitable values. Via numerical tests, it demonstrates the effectiveness of both the competitive search and the decoding method. Moreover, extensive comparative results show that the proposed algorithm is more effective and efficient than the existing methods in solving the CGVRP.

     

    • FullText(HTML)
  • loading
    • References(29)
  • [1]
    IEA, "CO2 emissions from fuel combustion highlights 2016, " Paris: International Energy Agency, pp. 9-12, 2016.
    [2]
    China State Council, "Made in China 2025, "[Online], available: http://www.gov.cn/zhengce, 2015.
    [3]
    C. H. Lin, C. K. L. Choy, G. T. S. Ho, S. H. Chung, and H. Y. Lam, "Survey of green vehicle routing problem: past and future trends, " Expert Systems with Applications, vol. 41, no. 4, pp. 1118-1138, 2014. http://www.sciencedirect.com/science/article/pii/S095741741300609X
    [4]
    S. Erdoǧan and E. Miller-Hooks, "A green vehicle routing problem, " Transportation Research Part E: Logistics and Transportation Review, vol. 48, no. 1, pp. 100-114, 2012. doi: 10.1016/j.tre.2011.08.001
    [5]
    P. Moscato, "On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms, " Caltech Concurrent Computation Program, C3P Report, pp. 826, 1989.
    [6]
    A. El Fallahi, C. Prins, and R. W. Calvo, "A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem, " Computers Operations Research, vol. 35, no. 5, pp. 1725-1741, 2008. doi: 10.1016/j.cor.2006.10.006
    [7]
    M. Boudia and C. Prins, "A memetic algorithm with dynamic population management for an integrated production-distribution problem, " European Journal of Operational Research, vol. 195, no. 3, pp. 703-715, 2009. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=1a33ed0595b4709618016fc3576f1a00
    [8]
    H. Zhao and R. Jiang, "The Memetic algorithm for the optimization of urban transit network, " Expert Systems with Applications, vol. 42, no. 7, pp. 3760-3773, 2015. doi: 10.1016/j.eswa.2014.11.056
    [9]
    B. Liu, L. Wang, and Y. H. Jin, "An effective PSO-based memetic algorithm for flow shop scheduling, " IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 37, no. 1, pp. 18-27, 2007. doi: 10.1109/TSMCB.2006.883272
    [10]
    L. Wang, S. Y. Wang, and X. L. Zheng, "A hybrid estimation of distribution algorithm for unrelated parallel machine scheduling with sequence-dependent setup times, " IEEE/CAA J. Autom. Sinica, vol. 3, no. 3, pp. 235-246, 2016. doi: 10.1109/JAS.2016.7508797
    [11]
    T. Bektaş and G. Laporte, "The pollution-routing problem, " Transportation Research Part B: Methodological, vol. 45, no. 8, pp. 1232-1250, 2011. doi: 10.1016/j.trb.2011.02.004
    [12]
    T. Bektaş, E. Demir, and G. Laporte, "Green vehicle routing, " Green Transportation Logistics, pp. 243-265, 2016. http://d.old.wanfangdata.com.cn/Periodical/gygcygl201701006
    [13]
    A. Palmer, "The development of an integrated routing and carbon dioxide emissions model for goods vehicles, " Cranfield University, pp. 1-151, 2007. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.444555
    [14]
    Y. Xiao, Q. Zhao, I. Kaku, and Y. Xu, "Development of a fuel consumption optimization model for the capacitated vehicle routing problem, " Computers Operations Research, vol. 39, no. 7, pp. 1419-1431, 2012. doi: 10.1016/j.cor.2011.08.013
    [15]
    C. F. Hsueh, "A vehicle routing problem with consideration of green transportation, " Journal of Management and Sustainability, vol. 7, no. 4, pp. 89-97, 2017. doi: 10.5539/jms.v7n4p89
    [16]
    G. Poonthalir and R. Nadarajan, "A fuel efficient green vehicle routing problem with varying speed constraint (F-GVRP), " Expert Systems with Applications, vol. 100, pp. 131-144, 2018. doi: 10.1016/j.eswa.2018.01.052
    [17]
    A. D. Jovanović, D. S. Pamučar, and S. Pejčić-Tarle, "Green vehicle routing in urban zones — a neuro-fuzzy approach, " Expert Systems with Applications, vol. 41, no. 7, pp. 3189-3203, 2014. doi: 10.1016/j.eswa.2013.11.015
    [18]
    G. Ćirović, D. Pamučar, and D. Božanić, "Green logistic vehicle routing problem: Routing light delivery vehicles in urban areas using a neuro-fuzzy model, " Expert Systems with Applications, vol. 41, no. 9, pp. 4245-4258, 2014. doi: 10.1016/j.eswa.2014.01.005
    [19]
    R. Eglese and T. Bektaş, "Green vehicle routing. In vehicle routing: problems, methods, and applications, " Society for Industrial and Applied Mathematics, pp. 437-458, 2014.
    [20]
    J. Andelmin and E. Bartolini, "An exact algorithm for the green vehicle routing problem, " Transportation Science, vol. 51, no. 4, pp. 1288- 1303, 2017.
    [21]
    M. Schneider, A. Stenger, and D. Goeke, "The electric vehicle-routing problem with time windows and recharging stations, " Transportation Science, vol. 48, no. 4, pp. 500-520, 2014. http://d.old.wanfangdata.com.cn/Conference/WFHYXW632573
    [22]
    Á. Felipe, M. T. Ortuño, G. Righini, and G. Tirado, "A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges, " Transportation Research Part E: Logistics and Transportation Review, vol. 71, pp. 111-128, 2014. doi: 10.1016/j.tre.2014.09.003
    [23]
    S. Zhang, Y. Gajpal, and S. S. Appadoo, "A meta-heuristic for capacitated green vehicle routing problem, " Annals of Operations Research, vol. 269, no. 1-2, pp. 753-771, 2018. doi: 10.1007/s10479-017-2567-3
    [24]
    Y. S. Ong, M. H. Lim, and X. Chen, "Memetic computation-past, present future, " IEEE Computational Intelligence Magazine, vol. 5, no. 2, pp. 24-31, 2010. http://dl.acm.org/citation.cfm?id=1821395&cfid=360992805&cftoken=92968035
    [25]
    N. Mladenović and P. Hansen, "Variable neighborhood search, " Computers Operations Research, vol. 24, no. 11, pp. 1097-1100, 1997. doi: 10.1016/S0305-0548(97)00031-2
    [26]
    M. Hasegawa, T. Ikeguchi, and K. Aihara, "Combination of chaotic neurodynamics with the 2-opt algorithm to solve traveling salesman problems, " Physical Review Letters, vol. 79, no. 12, pp. 2344, 1997. doi: 10.1103/PhysRevLett.79.2344
    [27]
    L. Wang, "Intelligent optimization algorithms with applications, " Tsinghua University Springer Press, Beijing, 2001.
    [28]
    D. C. Montgomery, Design and Analysis of Experiments, John Wiley Sons, 2017.
    [29]
    E. Osaba, X. S. Yang, F. Diaz, E. Onieva, A. D. Masegosa, and A. Perallos, "A discrete firefly algorithm to solve a rich vehicle routing problem modelling a newspaper distribution system with recycling policy, " Soft Computing, vol. 21, no. 18, pp. 5295-5308, 2017. doi: 10.1007/s00500-016-2114-1
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(12)  / Tables(7)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1481) PDF downloads(75) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return