Optimal routes for electric vehicles facing uncertainty, congestion, and energy constraints
Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2013.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/84715 |
| _version_ | 1811074249441411072 |
|---|---|
| author | Fontana, Matthew William |
| author2 | Dimitris Bertsimas and Thomas Magnanti. |
| author_facet | Dimitris Bertsimas and Thomas Magnanti. Fontana, Matthew William |
| author_sort | Fontana, Matthew William |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2013. |
| first_indexed | 2024-09-23T09:46:20Z |
| format | Thesis |
| id | mit-1721.1/84715 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:46:20Z |
| publishDate | 2014 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/847152019-04-11T11:24:48Z Optimal routes for electric vehicles facing uncertainty, congestion, and energy constraints Fontana, Matthew William Dimitris Bertsimas and Thomas Magnanti. Massachusetts Institute of Technology. Operations Research Center. Massachusetts Institute of Technology. Operations Research Center. Operations Research Center. Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2013. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 165-170). 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. by Matthew William Fontana. Ph.D. 2014-02-10T13:32:45Z 2014-02-10T13:32:45Z 2013 Thesis http://hdl.handle.net/1721.1/84715 868238531 eng 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. http://dspace.mit.edu/handle/1721.1/7582 170 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Operations Research Center. Fontana, Matthew William Optimal routes for electric vehicles facing uncertainty, congestion, and energy constraints |
| title | Optimal routes for electric vehicles facing uncertainty, congestion, and energy constraints |
| title_full | Optimal routes for electric vehicles facing uncertainty, congestion, and energy constraints |
| title_fullStr | Optimal routes for electric vehicles facing uncertainty, congestion, and energy constraints |
| title_full_unstemmed | Optimal routes for electric vehicles facing uncertainty, congestion, and energy constraints |
| title_short | Optimal routes for electric vehicles facing uncertainty, congestion, and energy constraints |
| title_sort | optimal routes for electric vehicles facing uncertainty congestion and energy constraints |
| topic | Operations Research Center. |
| url | http://hdl.handle.net/1721.1/84715 |
| work_keys_str_mv | AT fontanamatthewwilliam optimalroutesforelectricvehiclesfacinguncertaintycongestionandenergyconstraints |