Aaron Zhang's REU 2017 Web Page

About My Project

I am working with Professor Desheng Zhang and PhD student Zhihan Fang to study traffic patterns in large cities. We want to propose a method to reduce traffic during rush hours through off-peak transportation. First, we will model travel times and passenger distributions throughout the day in several transportation systems including subways, buses, taxis, and private vehicles. We will create this model by analyzing data sets such as card swipe data from public transportation and GPS traces from private vehicles. Then, we will model how increasing off-peak transportation, for example by shifting working hours, can affect traffic during rush hours.

Research Log

Week 1

On my first day at Rutgers, I attended the DIMACS REU orientation and met my fellow students. This week, I read papers covering background material on urban computing, modeling travel times in cities, and off-peak transportation. Finally, I gave a presentation about my project and enjoyed learning about everyone else's projects as well!

Week 2

I learned how to use Spark for data analysis and familiarized myself with my advisor's existing codebase for analyzing subway data. Then I started working on modeling bus delay times at different hours of the day by using card swipe data and GPS data.

Week 3

First, I worked with our existing algorithm for estimating delay times throughout the day based on trip data. Trip data consists of records that contain the start time, start location, end time, and end location of a commuter's trip. I managed to design a new algorithm that improves on the space complexity and, as a result, can handle much larger datasets! I ran the algorithm on a dataset of bus trip data, but found that there were inaccuracies in the trip data that were distorting the delay time estimates. So, next I worked on improving the preprocessing step of converting raw card swipe data and bus GPS data to bus trip data. The challenge is that card swipe data contains information about the start of a commuter's trip, but not the end. I came up with a new approach to estimate the end time and location of a trip, processed the card swipe data and GPS data to trip data, and finally produced an estimate of average bus delay times throughout the day.

Week 4

I extended my model from the previous week to include taxi and private vehicle data as well, and also to separate the trip time for buses into waiting time and travel time components. I started working on a method to estimate taxi waiting time, and will continue to work on this next week. Finally, I also did a bit of theoretical work regarding one of the applications my advisor and I were thinking of for our model. I proved that the algorithmic problem of the application was NP-hard by reduction from a variant of 3SAT, justifying our use of heuristics along with the data in our model to approach this problem.

Week 5

Estimating taxi waiting times was more difficult than I thought because of the limited types of data available, but I was able to make progress by the end of the week. Next, I'll try using a similar method to refine my waiting time estimates for bus commuters. This week, my advisor and I also started working on a paper describing our uniform model that incorporates different modes of transportation (subway, bus, taxi, private vehicle) and different components of travel time (walking time, waiting time, in-vehicle time).

Week 6

This week, I worked on my final presentation and prepared to leave for Prague.

Week 7

This week, the Prague group departed. On our first full day there, we attended a combinatorics lecture on graph homomorphisms.

Week 8

I finished up the new method for estimating bus waiting times and worked on my final report. We also attended more lectures on combinatorics. My favorite one talked about Helly's theorem and some surprising applications of it. This lecture was the first time I've seen the field of discrete geometry, which I intend to read more about!

Week 9

We attended the first two days of the Midsummer Combinatorial Workshop. On the first day, we heard lectures on different topics in combinatorics including graph coloring, drawings of trees, and matchings on the hypercube. The second day featured lectures on Ramsey classes. Finally, we left Prague and returned to the U.S. This concludes the REU, and I'll spend some time in the next two weeks to finish up a paper that we plan to submit to a conference.