A hybrid metaheuristic to optimize electric first-mile feeder services with charging synchronization constraints and customer rejections

• Published in: Transportation research. Part E, Logistics and transportation review Logistics and transportation review, 2024-05, Vol.185, p.103505, Article 103505
• Main Authors: Ma, Tai-Yu, Fang, Yumeng, Connors, Richard D., Viti, Francesco, Nakao, Haruko
• Format: Article
• Language: English
• Subjects: Demand responsive transport; Electric vehicle; Meeting point; Metaheuristic; Synchronization constraint mixed integer linear programming
• ISSN: 1366-5545; 1878-5794
• DOI: 10.1016/j.tre.2024.103505

•A meeting-point-based electric feeder service model with charging synchronization.•Layered graph structure to reduce the problem size.•A hybrid metaheuristic algorithm is proposed to solve the problem efficiently.•Algorithm tested in the Arlon-Luxembourg cross-border area with 1000 requests. This paper addresses the on-demand meeting-point-based feeder electric bus routing and charging scheduling problem under charging synchronization constraints. The problem considered exhibits the structure of the location routing problem, which is more difficult to solve than many electric vehicle routing problems with capacitated charging stations. We propose to model the problem using a mixed-integer linear programming approach based on a layered graph structure. An efficient hybrid metaheuristic solution algorithm is proposed. A mixture of random and greedy partial charging scheduling strategies is used to find feasible charging schedules under the synchronization constraints. The algorithm is tested on instances with up to 100 customers and 49 bus stops/meeting points. The results show that the proposed algorithm provides near-optimal solutions within less one minute on average compared with the best solutions found by a mixed-integer linear programming solver set with a 4-hour computation time limit. A case study on a larger sized case with 1000 customers and 111 meeting points shows the proposed method is applicable to real-world situations.