A Bilevel Ant Colony Optimization Algorithm for Capacitated Electric Vehicle Routing Problem

The development of electric vehicle (EV) techniques has led to a new vehicle routing problem (VRP) called the capacitated EV routing problem (CEVRP). Because of the limited number of charging stations and the limited cruising range of EVs, not only the service order of customers but also the recharg...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on cybernetics 2022-10, Vol.52 (10), p.10855-10868
Main Authors: Jia, Ya-Hui, Mei, Yi, Zhang, Mengjie
Format: Article
Language:English
Subjects:
Algorithms
Ant colony optimization
Ant colony optimization (ACO)
Batteries
capacitated vehicle routing problem (VRP)
Charging stations
combinatorial optimization
Customers
electric vehicle (EV) routing problem
Electric vehicle charging
Electric vehicles
Electricity
Optimization
Optimization algorithms
Route planning
Routing
Schedules
Urban areas
vehicle charging problem
Vehicle routing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The development of electric vehicle (EV) techniques has led to a new vehicle routing problem (VRP) called the capacitated EV routing problem (CEVRP). Because of the limited number of charging stations and the limited cruising range of EVs, not only the service order of customers but also the recharging schedules of EVs should be considered. However, solving these two aspects of the problem together is very difficult. To address the above issue, we treat CEVRP as a bilevel optimization problem and propose a novel bilevel ant colony optimization algorithm in this article, which divides CEVRP into two levels of subproblem: 1) capacitated VRP and 2) fixed route vehicle charging problem. For the upper level subproblem, the electricity constraint is ignored and an order-first split-second max-min ant system algorithm is designed to generate routes that fulfill the demands of customers. For the lower level subproblem, a new effective heuristic is designed to decide the charging schedule in the generated routes to satisfy the electricity constraint. The objective values of the resultant solutions are used to update the pheromone information for the ant system algorithm in the upper level. Through good orchestration of the two components, the proposed algorithm can significantly outperform state-of-the-art algorithms on a wide range of benchmark instances.
ISSN:2168-2267
2168-2275
DOI:10.1109/TCYB.2021.3069942