The capacitated electric vehicle (EV) routing problem is a challenging nondeterministic polynomial hard (NP-hard) problem consisting of two interdependent subproblems, the routing optimization problem and the charging decision problem. The routing optimization for EVs with a limited driving range is dependent on the available charging stations, while the charging decision is based on the charging demand that is estimated on the fixed route in return. Considering this coupling relationship, this article proposes a dual-population-based co-evolutionary algorithm (DPCA) that uses two evolution populations to collaboratively optimize these two subproblems. In the routing population, the charging station is regarded as a kind of customer with no demand, and an improved ant colony optimization (ACO) algorithm is designed to generate routes that involve the position information of charging stations. In the charging population, a binary genetic algorithm (GA) is used to generate a population of charging schemes whose qualities are evaluated based on the best ant obtained from the routing population, and then the resultant solution by inserting the best charging scheme is used to update the pheromone for the routing generation. Through the information interaction during the evolution, these two populations collaboratively search for the optimal solution to the problem. Experimental results demonstrate that the proposed algorithm can be able to avoid falling into the local optimum and have a reduction of about 4% in route distance averaged over two test suites. In addition, it also has a high computational efficiency, which is faster than the advanced ACO method by about two times.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A Dual-Population-Based Co-Evolutionary Algorithm for Capacitated Electric Vehicle Routing Problems


    Contributors:
    Wang, Chao (author) / Qin, Fang (author) / Xiang, Xiaoshu (author) / Jiang, Hao (author) / Zhang, Xingyi (author)


    Publication date :

    2024-06-01


    Size :

    1917784 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Advanced Phasmatodea Population Evolution Algorithm for Capacitated Vehicle Routing Problem

    Jiawen Zhuang / Shu-Chuan Chu / Chia-Cheng Hu et al. | DOAJ | 2022

    Free access


    An evolutionary algorithm for the electric vehicle routing problem with battery degradation and capacitated charging stations

    Futalef, Juan Pablo / Muñoz-Carpintero, Diego / Rozas, Heraldo | TIBKAT | 2020

    Free access

    Improved Genetic Algorithm for Capacitated Vehicle Routing Problem

    Ren, C.Y. | British Library Conference Proceedings | 2013


    Improved Genetic Algorithm for Capacitated Vehicle Routing Problem

    Ren, C.Y. | British Library Conference Proceedings | 2013