Electric vehicle routing problem with non-linear charging and load-dependent discharging. (1st December 2020)

• Record Type: Journal Article
• Authors: Kancharla, Surendra Reddy; Ramadurai, Gitakrishnan
• Is Part Of: Expert systems with applications. Volume 160(2020)
• Publication Date: 2020-12-01
• Subjects: Adaptive large neighborhood search -- Electric vehicle routing problem -- Non-linear charging -- Partial charging -- Load-dependent discharging; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2020.113714
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: E-VRP with load-dependent discharge and non-linear charging is introduced. The proposed E-VRP MILP model allows multiple visits to a CS, yet performs better. The proposed ALNS algorithm found 75 new solutions out of 120 instances tested. Abstract: We propose a three-index formulation for E-VRP with Non-Linear charging and Load-Dependent discharging (E-VRP-NL-LD), and an Adaptive Large Neighborhood Search (ALNS) algorithm to solve the E-VRP-NL- LD and E-VRP-NL-LD with Capacitated Charging Stations (E-VRP-NL-LD-CCS). Existing implementations of EVRP duplicate charging station nodes which enables the modelling of EVRP using extended VRP formulations. Two limitations of such an approach are: (i) the number of such duplications is not known a priori, and (ii) the size of the problem increases. In our formulation, we allow multiple visits to a charging station without duplicating nodes. We propose five new operators for ALNS which are tested on 120 instances each of E-VRP-NL and E-VRP-NL-LD, and 80 instances of E-VRP-NL-LD-CCS. Results show that our ALNS outperforms the existing algorithms improving the solution in 63% of the instances and matching the best known solution in 31% of the instances. Results also show that considering load-dependent discharge is critical to optimally solve E-VRP.