Vehicle Routing Problem for Electric Vehicles

How can we generate efficient routes for a large fleets of vehicles that have to make many thousands of deliveries a day while taking into account breaks, shift patterns and traffic conditions? Now let's make those vehicles electric and we need to take into account vehicle battery charge level, recharging station locations and anticipated energy efficiency. It's a challenging problem!

Vehicle Routing Problem (VRP) is the optimisation problem that describes all manifested delivery operations. It provides an optimal way of sorting deliveries onto multiple vehicles and providing each vehicle with an optimal sequence for delivery. The problem is NP-hard and suffers from a combinatorial explosion of solutions as the number of vehicles and deliveries increases.

We speak to Merve Keskin of the Warwick Business School about extending VRP as an area of optimisation to electric vehicles with a number of interesting developments:

• Keeping track of battery level en route and inserting possible stops at nearby compatible recharging points
• Allowing delay for possible queues at recharge points
• Potential for inflight negotiation on charge point booking so as to minimise contention for resource and wait times on long journeys.

With interview guest Dr. Merve Keskin, Warwick Business School and KTP fellow.
https://www.wbs.ac.uk/about/person/merve-keskin/

Further reading

• Merve Keskin's publication list (via Google Scholar)
• Paper: A matheuristic method for the electric vehicle routing problem with time windows and fast chargers (summary via ScienceDirect)
• Paper: Electric vehicle routing problem with time-dependent waiting times at recharging stations (pdf via researchgate)
• Paper: Partial recharge strategies for the electric vehicle routing problem with time windows (summary via ScienceDirect)
• Overview: A concise guide to existing and emerging vehicle routing problem variants (pdf via arXiv)

Some links above may require payment or login. We are not endorsing them or receiving any payment for mentioning them. They are provided as is. Often free versions of papers are available and we would encourage you to investigate.

Recording date: 28 Feb. 2020
Interview date: 12 Feb. 2020

Thanks for joining us in the DataCafé. You can follow us on twitter @DataCafePodcast and feel free to contact us about anything you've heard here or think would be an interesting topic in the future.