Optimal routes for electric vehicles facing uncertainty, congestion, and energy constraints

There are many benefits of owning a battery electric vehicle, including zero tailpipe emissions, potential independence from oil, lower fuel costs, and the option to recharge the battery at home. However, a significant concern about owning a battery electric vehicle is range anxiety: the fear that the battery will run out of charge before the driver reaches his or her destination. We address range anxiety by providing a robust optimization framework to give drivers confidence that they can reach their destinations in a reasonable amount of time with enough energy in the battery, even when there is uncertainty in travel time and energy consumption on the roads. The robust optimization appropriately incorporates uncertainty without significantly increasing the complexity of the problem. This thesis describes that optimization framework and how to use it on real-world examples to find appropriate routes, with a central part being the application of robust optimization to the problem. We develop an energy model, an optimization-based formulation using robust optimization, and algorithms to quickly find good routes for battery electric vehicles. The combination of using robust optimization, the A-Star algorithm to find shortest paths, and Lagrangian relaxation allows us to solve the problem in seconds or less. For one example start and destination, our algorithms required less than 2 seconds for each instance (energy consumption limit). In addition, for example trips, we compute a Pareto frontier to illustrate the time-energy tradeoff from driving different routes. We use Lagrangian relaxation to provide lower bounds and estimates that suggest that our algorithms produce near-optimal solutions. We apply our methodology to example trips in Massachusetts and Michigan to demonstrate its practicality and its potential for real-world use. Future work could continue to improve the modeling accuracy and include algorithmic enhancements to further improve running time, especially for larger networks.

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2013

Author dc:creator

• Fontana, Matthew William

Advisor dc:contributor.advisor

• Dimitris Bertsimas and Thomas Magnanti.

• Operations Research Center.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/84715

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/84715