DataCafé

Vehicle Routing Problem for Electric Vehicles

DataCafé Season 1 Episode 3

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

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.