Granular tabu search for the pickup and delivery problem with time windows and electric vehicles

Nowadays, electric vehicles are considered a viable option for goods distribution, especially in urban areas that are heavily burdened by local emissions. The call for environmentally-friendly vehicles has been heard by car manufacturers and they have begun to introduce electric commercial vehicles, suitable for logistics tasks, into the market. This trend has also motivated the development of algorithms to plan delivery routes that take the characteristics of electric vehicles into account. In the literature, problems have been studied that consider the distribution of goods with electric vehicles from a central depot. However, many real-world applications have a pickup and delivery structure. In these applications, one needs to plan routes in order to satisfy requests; each request requires that a commodity is transported from a pickup to a delivery location. Here, we study the pickup and delivery problem with time windows and electric vehicles (PDPTW-EV). In the PDPTW-EV, access to locations is restricted by time windows. Electric vehicles, that are constrained by capacities for energy and commodities, serve the routes. Energy can be recharged when stopping at dedicated stations. We develop a granular tabu search (GTS) with a policy to determine the amount of energy recharged. In numerical studies, we validate our approach on small-sized instances, and compare it to the results obtained with a commercial solver. On larger-sized instances, we demonstrate that GTS can handle the partial recharging strategy by comparing it to full recharging. Finally, we show that our algorithm is competitive on benchmark instances of the pickup and delivery problem with time windows.