Get on the Bus. Simple or Not?
From ASKOH Wiki
New Mexico Supercomputing Challenge Final Report
April 1, 2009
Team 45 Homeschool/LAHS
Team Member: Isaac Koh
Teacher: Aik-Siong Koh
Mentor: Aik-Siong Koh
Contents |
Summary:
This year for my Supercomputing Challenge problem, I wanted to create a program for the Atomic City Transit bus system that would let a user input his/her starting point, destination, and desired time of arrival, and the program would tell the user when and where to catch the bus, and when to switch buses if necessary. I had no programming experience prior to this Challenge and started out learning C#. I went through the tutorials that Microsoft provided and then proceeded to building my program. At first it looked like it was a lot more than I could chew, but gradually with my teacher's help the program took shape. We had several iterations and by the Midterm presentations, we could produce the bus trips (circuits) and the times that they ran on. After the presentations we turned to solving the case where the start point and destination were on the same Route. We first looked for the Route that had both the start and end on it. Then we looked for the Trip that had the selected time in it. That set of code was good until we noticed that some Trips pass certain stops multiple times during the course of the circulation. That made the program say that we would arrive at our destination earlier than we caught the bus, which is physically impossible. To solve this problem we strung together two consecutive trips. Then we found the destination, and traced backwards until we met the starting point. After that, we turned to the problem of switching buses. We had the code look for the Routes that had the start and the Routes that had the end. Then we found the intersection of the stops between each start and each end Route. Using the end Route we traced backwards from the end to the nearest intersection. Then we treated the intersection time as the end time and had the program trace back to the starting point along the start Route. Thus we were able to return all the information from start to end including the bus change. This was our last major obstacle and our program is functioning very nicely now. In the future I will put my program on a website, and then look into making a similar program for Santa Fe.
Resources:
[Microsoft Visual C# 2008 Express Edition]
Google Search
Atomic City Transit Schedule
Compaq Presario V3000 Laptop
Problem Investigated:
I wanted to make a program for the Los Alamos Atomic City Transit bus system that lets the user input his/her starting place, destination, and the time they want to arrive. Then the program will return when and where to catch the bus, when and where to switch if necessary and when the user will arrive.
Methods:
1.Create the Route class to store the bus route name, list of TripPatterns, and a list of all Trips for the day. 2.Create Trip class to store list of stops, list of arrival times, list of waiting times, and name. A Trip is one circuit that starts and ends at the Transit Center. 3.Create TripPattern class as sub-class of Trip to store the schedule repetition time (minutes), start and end time of schedule, and a list of Trips. 4.Input the Atomic City Transit schedule into TripPatterns and have them generate the Trips for all the Routes thoughout the day. (Appendix A) Example:
route1.name = "Route 1";
route1.cTripPattern = new List<TripPattern>();
aTripPattern = new TripPattern();
aTripPattern.cDest = new List<string>();
aTripPattern.name = "Route 1";
aTripPattern.cDest.Add("Transit Center");
aTripPattern.cDest.Add("Diamond & Trinity");
aTripPattern.cDest.Add("Trinity & Oppenheimer");
aTripPattern.cDest.Add("Trinity & 15th");
aTripPattern.cDest.Add("4th & Central");
aTripPattern.cDest.Add("Central & 15th");
aTripPattern.cDest.Add("Central & Canyon");
aTripPattern.cDest.Add("Canyon & Diamond");
aTripPattern.cDest.Add("Transit Center");
int[] c1ArrivalTime = { 8 , 10 , 11 , 12 , 14 , 16 , 18 , 21 , 23 };
aTripPattern.cArrivalTime = c1ArrivalTime.ToList();
aTripPattern.repeatMinutes = 20; // repeats every 20 minutes
aTripPattern.firstRepeatTime = 5 * 60 + 40; // 5:40 AM in minutes
aTripPattern.lastRepeatTime = 19 * 60; // 7:00 PM in minutes
aTripPattern.setcTrip();
route1.cTripPattern.Add(aTripPattern);
TripPatterns will generate Trips like the one below. Example Trip: cDest cArrivalTime
("Transit Center"); 7:08 AM
("Diamond & Trinity"); 7:10 AM
("Trinity & Oppenheimer"); 7:11 AM
("Trinity & 15th"); 7:12 AM
("4th & Central"); 7:14 AM
("Central & 15th"); 7:16 AM
("Central & Canyon"); 7:18 AM
("Canyon & Diamond"); 7:21 AM
("Transit Center"); 7:23 AM
5. Write algorithm as explained in the section below. The source code is in Appendix B.
Problems and How I Solved Them:
The programming was initially difficult. I was not familiar with the language and my project required many operations that had not been covered in the tutorials, but as the project continued I got the hang of it.
Inputing times for the Downtown route was rather straight forward. But we found that all the other routes had three different sub-schedules within the day: all day, AM peak, and PM peak. This led to us creating TripPatterns that generated individual Trips (circuits) and treated each of the above sub-schedules as a different TripPattern. Therefore each route had several TripPatterns, and each contained several Trips that each represented one circulation. A Trip has the stops and the times of arrival.
The White Rock route has a 14 minute stop in the middle of it. We then added another property in Trip called WaitTime that we could set and left it at zero for all the other stops that didn't need it.
We had simplified our code so much that when it started returning the time to get on and off, we were told to get on after reaching our destination. This happened because we were finding the solution all within one Trip. Also, some Trips visited the same stops more that once. To fix this we strung two consecutive Trips together and traced from the end of the combined Trips backwards until we found the endpoint. Then we continued backwards until we found the endpoint again or the start point. If we found the endpoint again we used that instance instead of the previous one, and continued backwards to find the start point. When we find the start point, we have the solution and return the following: Start Time, Starting Point, Bus Route End Time, Destination The above worked when consecutive Trips did not overlap, but during the peak hours consecutive Trips often overlapped. Therefore we had to search for the nearest non-overlapping Trip before joining the two Trips.
The above algorithm works when a start point and end point are on the same Route. When they are on separate Routes we adjusted the algorithm as follows: We find the Routes that contain the end and the Routes that contain the start. Then we find the common stops of each combination of each start Route and end Route. Then starting from the end point we trace backwards along the end Route to the nearest common stop and treat that as the new starting point. Since the new starting point and the original end point are now on the same Route we can use the previous algorithm to find the best times for this connecting Trip. Now we make the connection stop the new destination and find the best time between it and the actual starting point. Hence we have the solution for the following: Start Time, Starting Point, Bus Route Arrival at Intersection Time, Intersection Point Connection Time, Connection Bus Route End Time, Destination
Results:
Conclusions:
It is possible to create a program to make using a bus system easier. I have learned a lot from this project, and will learn more as I polish it. It is satisfying to know that this program can actually help people. Looking ahead I will put this program on a website, and make it accessible from the web browser. Then I will look into making a similar program for Santa Fe.
Code:
See Appendix B
Achievements:
There is no other program for the Atomic City Transit that will tell you when and where to catch the bus. This saves you from having to go through the schedule every time.
Chicago has a program that tells you when the bus will arrive at a certain place, but you still have to plan out your own route.
http://www.ctabustracker.com/bustime/home.jsp
Acknowledgements:
I would like to thank my dad for being my teacher, sponsor, and for helping me do this project. I would also like to thank the Supercomputing Challenge organizers for the encouragement and feedback throughout this Challenge.
Appendix A: Bus Routes
The letters stand for major points on a route. The numbers stand for minutes, and they repeat every hour. Look at A on Route 1. The bus passes there at 5:50 AM, 6:10 AM, 6:30 AM, 6:50 AM, 7:10 AM and so on until 7:10 PM. The same goes for all the other stops and routes.
Route 2 does not exist.
