Graph theory and the (hopefully) green future of transportation

On March 31 of this year, Elon Musk announced one of his yet-again highly-anticipated, highly controversial products: the Tesla Model 3. At this point, most of us are familiar with Tesla, particularly living in Silicon Valley. The electric car company made relatively little impact upon its entry to the market with the Roadster, but saw huge success with its Model S. The Model S had a combined fuel economy gas equivalent of 89 miles/gallon, a 265 mile range, and an extremely high safety rating. These properties and more led it to be the top-selling plug-in electric vehicle in 2015, with over 100,000 sold worldwide by December 2015. By this time, Tesla Motors was being praised as leading the green, electric-car revolution.

However, one of the primary prohibitive elements of joining this revolution is the cost. The base price for a Model S is $70,000 as of 2016, with the price after custom options often reaching upwards of $100,000. This emphasized Tesla’s niche as catering to the rich. Enter the Model 3. Rumors of a low-cost Tesla vehicle had been swirling since the company entered the public eye, but no official announcement was ever made until a month ago. Delivering on his promise, Musk is offering the Model 3, a Model S knockoff, for the price of $35,000 before incentives, without sacrificing much on quality (215 mile range, anticipated 5-star safety rating, 0-60mph in < 6 seconds). The company received over 325,000 $1000 deposits for pre-orders within a week of announcing the vehicle. That number has now climbed past 400,000. Seemingly, the electric car revolution is well underway, with Tesla’s biggest challenge instead simply meeting global demand, right?

Not quite. Despite the apparent undeniable success of the movement, significant challenges remain: developing appropriate networks for charging and repairs, and mitigating negative climate effects.

This is where there are interesting applications of graph theory. In terms of networks of charge stations, there are several interesting algorithms that can be written to optimize placement of new charging stations based on customer density, future customer density, popular roads and destinations, installation/upkeep costs, access to renewable energy, and more. Obviously, the company is well aware of such constraints and must have sophisticated algorithms for planning these installations, so it would also be interesting to do a backwards analysis of where they chose to install the already-built supercharging stations, pictured below.

Screen Shot 2016-04-29 at 11.22.40 PM

Map of supercharging stations, from Tesla website

In fact, Tesla has developed a technology called the Trip Planner that also makes use of graph theoretical tools to help their customers find routes to their destinations based on their time constraints and available charging networks.

Another similar network problem is the problem of repair services. Up until now, Tesla has occupied a small, niche market in the automobile industry. Due to the unique mechanical structure of its vehicles (all-electric drivetrain, large lithium-ion battery, aluminum body), most auto repair shops are unable to service their vehicles. Therefore, a “Tesla Ranger” — a roving specialized mechanic — has done most of the minor repairs and special, certified body shops have done the major repairs. However, while the premiums associated with such luxury services have been affordable for Tesla’s previous market, now that they are intending to enter the common market, they face the issue of being able to provide adequate repairs and customer service to their 400,000+ new customers starting next year. So, similarly, there are interesting optimization problems to consider for being able to cover the maximum area, the maximum number of customers, and what level of coverage to be able to provide to what areas.

Both of these problems can clearly be quite complicated. Interestingly, these are not only graph theory problems, but involve some game theory as well. Primarily simply from a corporate-interest standpoint, behavioral game theory has certainly been applied to these graph theory problems. One might imagine it as a game on the customers’ utility from receiving services versus the company’s utility from having faithful customers and minimizing costs.

How this kind of technology will change the automobile industry’s effect on the climate remains to be seen. Needless to say, in terms of emissions, electric vehicles vastly outperform cars with internal combustion engines. However, questions have been raised about the energy required to create these vehicles: to make the batteries, rare metals such as lithium have to be mined in large quantities, which is an energy-expensive process. The lifetime and storage and recycling capabilities of such batteries are heavily researched areas of the process currently, and a lot of Tesla’s “green” impact depends on the success of that research.

The answers to the questions raised and more are not far off. Musk claims it is a top priority for the company to meet its 2017 shipping deadline for the Model 3. As that deadline approaches, we will see how Musk plans to meet demands for vehicles, charging networks using clean energy, repair services, and more.

Relevant links:

(repeated from above)

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s