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

Dominik Goeke

European Journal of Operational Research, 2019, vol. 278, issue 3, 821-836

Abstract: 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.

Keywords: Metaheuristics; Green logistics; Electric vehicle routing; Partial recharging (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719304126
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:278:y:2019:i:3:p:821-836

DOI: 10.1016/j.ejor.2019.05.010

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().