Optimization Algorithm for the Hybrid Pickup and Delivery Problem with Time Windows for Electric Vehicles and Automatic Delivery Robots

Abstract

This paper presents the vehicle routing problem with simultaneous pickup and delivery and time windows for hybrid delivery of electric vehicles and automatic delivery robots (VRPPDTW-HEADR). Automatic delivery robots are deployed at service stations to assist electric vehicles for customer service. Electric vehicles considering charging en-route can service customers directly or handle goods at the service station to the automatic delivery robot. Simultaneous pickup and delivery services of customer-to-customer and depot-to-customer-to-depot are meticulously addressed. The problem is formulated as a mixed-integer programming model that minimizes the total cost to serve all customers. A novel hybrid metaheuristic algorithm is proposed to solve VRPPDTW-HEADR. Local search operators that fit the characteristics of the problem are customized. The performance of the proposed algorithm is tested on different scale instances. The numerical results show that it can obtain high quality solutions for all instances within a remarkably short runtime.