This is our group’s submission for Problem D in 2018 MCM/ICM, and it earned Meritorious Winner at last. I was responsible for the data scraping, cleaning and modeling.
Background
Problem D: Out of Gas and Driving on E (for electric, not empty)
For both environmental and economic reasons, there is global interest in reducing the use of fossil fuels, including gasoline for cars. Whether motivated by the environment or by the economics, consumers are starting to migrate to electric vehicles. Several countries are seeing early signs of the potential for rapid growth in the adoption of electric vehicles. In the US and other countries, the release of the more affordable all-electric Tesla Model 3 has resulted in record numbers of pre-orders and long wait lists. To further accelerate the switch to electric vehicles, some countries, including China, have announced that they will ban gasoline and diesel cars in the coming years.
Eventually, when a ban goes into effect, there needs to be a sufficient number of vehicle charging stations in all the right places so that people can use their vehicles for their daily business, as well as make occasional long-distance trips. The migration from gasoline and diesel cars to electric vehicles, however, is not simple and can’t happen overnight. In a fantasy world, we would wake up one day with every gas vehicle replaced by an electric one, and every gas station replaced with a charging station. In reality, there are limited resources, and it will take time for consumers to make the switch. In fact, the location and convenience of charging stations is critical as early adopters and eventually mainstream consumers volunteer to switch.
As nations plan this transition, they need to consider the final network of charging stations (the number of stations, where they will be located, the number of chargers at the stations, and the differences in the needs of rural areas, suburban areas, and urban areas), as well as the growth and evolution of the network of charging stations over time. For example, what should the network look like when electric vehicles represent 10% of all cars, 30% of all cars, 50% of all cars, and 90% of all cars?
As nations seek to develop policies that promote the migration towards electric vehicles, they will need to design a plan that works best for their individual country. Before they can begin, they would like your team’s help in determining the final architecture of the charging network to support the full adoption of all-electric vehicles. Additionally, they would like you to identify the key factors that will be important as they plan their timeline for an eventual ban or dramatic reduction of gasoline and diesel vehicles.
To help your team manage the scope of this problem, we ask that you focus only on personal passenger vehicles (i.e. cars, vans, and light trucks used for passengers). At the end of your report, you may briefly comment on the relevance of your findings and conclusions on commercial vehicles to include heavy trucks and busses.
Your tasks are the following:
Task1: Explore the current and growing network of Tesla charging stations in the United States. Tesla currently offers two types of charging stations: (1) destination charging designed for charging for several hours at a time or even overnight (https://www.tesla.com/destination-charging); and (2) supercharging designed for longer road trips to provide up to 170 miles of range in as little as 30 minutes of charging (https://www.tesla.com/supercharger). These stations are in addition to at-home charging used by many Tesla owners who have a personal garage or a driveway with power. Is Tesla on track to allow a complete switch to all-electric in the US? If everyone switched to all-electric personal passenger vehicles in the US, how many charging stations would be needed, and how should they be distributed between urban, suburban, and rural areas?
Task2: Select one of the following nations (South Korea, Ireland, or Uruguay).
2a.Determine the optimal number, placement, and distribution of charging stations if your country could migrate all their personal passenger vehicles to all-electric vehicles instantaneously (no transition time required). What are the key factors that shaped the development of your plan?
2b.While these countries have already started installing chargers, you get to start with a clean slate. Present a proposal for evolving the charging network of your chosen country from zero chargers to a full electric-vehicle system. How do you propose the country invest in chargers? Should the country build all city-based chargers first, or all rural chargers, or a mix of both?Will you build the chargers first and hope people buy the cars, or will you build chargers in response to car purchases? What are the key factors that shaped your proposed charging station plan?
2c.Based on your growth plan, what is the timeline you propose for the full evolution to electric vehicles in your country? To get started, you may wish to consider how long it will take for there to be 10% electric vehicles, 30%electric vehicles, 50% electric vehicles, or 100% electric vehicles on your selected country’s roads. What are the key factors that shaped your proposed growth plan timeline?
Task3: Now consider countries with very different geographies, population density distributions, and wealth distributions, such as Australia, China, Indonesia, Saudi Arabia, and Singapore. Would your proposed plan for growing and evolving the network of chargers still apply to each of these countries? What are the key factors that trigger the selection of different approaches to growing the network? Discuss the feasibility of creating a classification system that would help a nation determine the general growth model they should follow in order for them to successfully migrate away from gasoline and diesel vehicles to all electric cars.
Task4: The technological world continues to change and is impacting transportation options such as car-share and ride-share services, self-driving cars, rapid battery-swap stations for electric cars, and even flying cars and a Hyperloop. Comment on how these technologies might impact your analyses of the increasing use of electric vehicles.
Task5: Prepare a one-page handout written for the leaders of a wide range of countries who are attending an international energy summit. The handout should identify the key factors the leaders should consider as they return to their home country to develop a national plan to migrate personal transportation towards all-electric cars and set a gas vehicle-ban date.
Your submission should consist of:
- One-page Summary Sheet,
- One-page handout,
- Your solution of no more than 20 pages, for a maximum of 22 pages with your summary and handout.
Note: Reference list and any appendices do not count toward the 22-page limit and should appear after your completed solution.
Abstract
In this essay, we propose our model named Spatial-Temporal Linear Programming(STLP). We first integrate our solution into the framework of an Integer Linear Programming(ILP) taking only distance into consideration. In the following tasks, we gradually add more constraints to make our model more comprehensive and applicable. We abstract the problem of determining locations as minimizing an objective function under a set of constraints. Due to the NPhard complexity of the ILP problem, we employ the technique of simulated annealing algorithm to improve efficiency.
Firstly, we analyze the current network of charging stations of Tesla in the US and draw the conclusion that the attempt made by Tesla is actually leading in the effort of totally switching to EV. We then apply our model to both the US and the South Korea. While the preliminary version only considers the locations in a microscopic view, we now pay attention to vehicle density around a charging station since it affects number of chargers in average waiting time. We employ the Queuing Theory to model the situation of power shortage. This factor is gracefully integrated into our framework by adding additional constraints and a term in the objective function indicating minimizing the average waiting time.
Secondly, we further extend our model to a temporal perspective. In other words, we assume that the scheduling is not done overnight. We still apply the optimization tool to the objective function by making the assumption that the locations at a former stage remain optimal later since the cost of tearing down a station is considered intolerable. By merging both the spatial and temporal factors together, we’ve finally reached our version of STLP.
Thirdly, not only the distance and vehicle density influence our conclusion but also some other specific factors. After taking a closer look at countries such as China, Singapore with totally different geographical conditions, we propose a new classification system for determining the timeline to cater to specific conditions in economics, road construction and so on.
Finally, we spend some time discussing the possible influences of some emerging techniques on our model. We also write a handout for leaders from different countries to make decisions to better facilitate the proposal of EVs after they return.
Keywords: Linear Programming ; Queuing Theory; Simulated Annealing Algorithm