Readme taken from the final report, which can be found here...
java AnalyzeData (departure file name) (arrival file name)
One of the goals of this analysis is to assess the fleet of aTaxis we would need to service the demand in our counties. Our objective is to acquire the fewest number of aTaxis and minimize the miles each taxi drives without passengers. Moreover, we expect to maintain an AVO within the range of 3-3.5, well above the NJ average, while accommodating every departure from our pixels with minimal or no delay (<5 minutes).
In order to ease some of the difficulties of this analysis, a few constraints and assumptions were given to all counties, internal and external. The first was briefly mentioned above. We must commit to a level-of-service that takes at least 3 people going in similar directions, where each destination does not significantly change the time / miles it takes to reach the other destinations. In addition to that, no departure can leave more than 5 minutes past its scheduled departure. Simplified, this is just an aTaxi management plan with CD=3, DD=300, and MaxCircuity=20%. On top of that, we assume that each county has its own independent aTaxi Service Company. This means the aTaxis owned by each county will be returned empty to the origin pixel 10 minutes after discharging its last passenger in a “foreign” county. The only exception to this rule is if there is a known departure destined to the origin county within those 10 minutes. Then, the foreign service company will load those passengers into the returning aTaxi - negating the expected empty miles burden on both ends. Since this constraint applies to all NJ counties being analyzed, our counties extend the same courtesy. Furthermore, when an aTaxi returns to the county empty, it will arrive and be available for loading/further dispatch after 30mph/(1.2cartesianDistance) minutes, where cartesianDistance is the distance between the origin pixel and the destination pixel, and 1.2cartesianDistance is the empty mile burden between those pixels. Because each of our counties can be defined as a supply station for New Jersey, we expect to see both a large fleet size and empty mile burden.
Focusing on the fact that each of our counties is a supply station for NJ, our approach was to find the fleet size needed to meet the demand presented in the input files. Once found, ideally, the taxis would be placed in a garage/lot near the station when not in use, deployed to the station when a departure is needed, and returned to the station after a trip (if not immediately needed for another departure). Following this logic, and applying the constraints, we approached this optimization problem with a “sink”-like algorithm. We created two data structures, “Trip” and “Taxi”, to hold the inputted trip data. The Trip data structure held information about the departure pixel/time, arrival pixel/time, and the time it takes to return to the origin pixel, while the Taxi data structure held an itinerary of trips, and kept track of the size.
Using these two data structures, we gave each inputted trip (arrival and departure) its own personal taxi. We then compared the list of arrival taxis with the list of departure taxis, checking for the 10-minute return constraint. If an arrival from a pixel was found within 10 minutes of a departure to that same pixel, the departing taxi was deleted from the final list of taxis we would need to supply. Continuing after that iteration, we further reduced the number of aTaxis we would need by cycling through the remaining list of departing taxis, adding multiple trips to each taxi. This was done by comparing each of the 1-trip taxis to the rest of the taxis in the list. If a taxi had returned before the current taxi departed (and the size of the taxi was large enough to accommodate the departure), then the trip(s) in the current taxi would be added to the taxi that had returned, and the current taxi would be deleted.
This algorithm left us with a final list of taxis necessary to meet the demands created in the input files (see Appendix 5 for raw code). Granted, the numbers produced for this algorithm are just a rough estimate of the demand needed for our counties, but the estimates seem plausible. Additionally, extra taxis will need to be on reserve for unforeseen events, and, at least one taxi of each size will need to be at the station at all times for the same reason.
Unfortunately, as with any algorithm, there are limitations and room for improvement. For our optimization problem, one of our largest setbacks was the empty mile burden. Because each county was only represented by one pixel, there was no “closer” pixel to which the taxis could return. Every taxi dropped off their passengers, then returned to the home pixel. This created a large empty mile burden for each taxi. Fortunately, this burden could be relieved by collecting more data and treating the externalities like the internal counties. However, the feasibility of this is very low. Another way of alleviating this burden is if the counties share their taxi information with each other. That way, before a taxi returns, it could check surrounding pixels for a return trip, instead of coming back empty. But again, the feasibility of this is very low.
On another note, there is more room for improvement in the algorithm itself. The algorithm should be updated to deal with time wrapping over midnight. As of right now, 0:05 is treated as a time before 11:59, even though midnight should be counted as coming after. The only issue is knowing how far into the day one must get before the wrap-around is no longer needed. This question/issue is the reason why it is currently not implemented in the algorithm.
Furthermore, even though the algorithm does provide rough estimates for the fleet size, it is a very static calculation and needs to be updated to calculate the need for taxis dynamically. This can be done using Poisson processes, or another prediction model. It can also be made more “dynamic” by deliberately delaying some of the departures in order to increase the number of ride-sharers, while decreasing the fleet size. For example, a taxi would wait no more than 5 minutes to depart, and if another departure was scheduled to the same pixel / a nearby pixel, then that ride would be included in the taxi and depart at the same time. On the other hand, using the information in the algorithm to create a more detailed breakdown of taxis based on time could just be used to dynamically forecast how many taxis would need to be present at the station.