Introduction
For this project we set out to use information about the University of Arkansas’ (UArk) transit system with the tools we’ve learned this semester to create our own set of bus routes. The information we used, including the ridership data for the month of October, information on the buses used during that time, and the information on the individual stops within the system, was all generously provided by Razorback Transit (UArk Transit Department). Our main personal goals with this project were to gain an understanding into the methodology utilized to create the currently utilized routes and to compare these routes with what could be created using our skill set. We more broadly also sought to create a tool that provided useful insight into ours and the University’s thought processes and methodology. All of this was developed using Tablesaw, Google OR Tools Java, and Vaadin. Tablesaw assisted in the processing of the data into Java while Google OR Tools built and solved the model and Vaadin displayed all of our work. The skills we learned throughout this semester in Computing Methods are what made this whole project possible. Obviously, without the class we wouldn’t have even known how to use the aforementioned packages; however, we also learned how to use ArrayLists, file input, GitHub collaboration, and how to use custom classes to simplify our Java workflow, all of which were used in this project.
Initial Plans/Goals & How They Changed
Our initial plan was admittedly ambitious. We wanted to use the ridership data, bus information, and stop information to create a demand-based capacity constrained vehicle routing problem (CVRP). This plan would have use taking in the data, using it to create a number of routes working with Google’s Maps API (for real world distances and travel times), and varying bus assignment based on the demand curves of stops. What this would mean, is that a given bus could serve Route A while its in high demand, and then pivot to Route B if it A’s demand died down while B’s increased. This plan had its problems though. Firstly, individual behaviors weren’t tracked (where a given person gets on and off), just quantity and times that people got on/off, which means we would have no context for where people would like to travel to and from specifically, just more population level trends in boarding and departing. Secondly, the Maps API is an enterprise tool that carries with it an enterprise price that our group couldn’t justify. Lastly, frequent rerouting of buses from one route to another is confusing for users and difficult to program on the back end.
For each of these roadblocks, our team pushed forward and did our best to find a solution that enabled us to create the best solution possible. Firstly, we started by sitting down and assessing what our end goal would be for this project. Once we arrived at the conclusion that our timeline and resources wouldn’t allow for the perfect solution, we were able to navigate to a more educational standpoint of trying to use this project to allow us to understand what goes into transportation logistics and to see how UArk’s current routes compared to a more simple methodology of solving. To get around not being about to use Google’s Maps API, we created our own methods and tools to substitute. The most major of which was a method to generate a matrix of rectilinear distances between stops to substitute for Google’s Route Distance Matrix tool. Lastly, we made the decision to let go of the bus demand change concept in favor of a more simple and real world solution.
Most of our major changes happened over time, not just at the beginning. Our largest change was the decision to pivot to a standard, distance constrained VRP over distance and capacity constrained one. We made this pivot after developing an initial CVRP as attempts to failed to compute in any effective amount of time as the amount of constraints on the model rendered it difficult or impossible to solve. All of these changes left us with a project very different than the one we initially set out to create but not one we are wholly unsatisfied with. Though our final solution was less than ideal, we believe it was a great attempt given the time frame and, more than anything, we found the whole experience greatly pushed our knowledge and skills and many Industrial Engineering areas.
Key Features & Components
While we are proud of the project as a whole and feel that all aspects are best when viewed as aspects of the whole, there are some components we believe shine on their own as well that we’d like to highlight.
RDMatrix
RDMatrix is the aforementioned method that is utilized to generate the matrix of rectilinear distances. This method takes in an ArrayList of Stop objects (each of which store stopID, stopName, xCoordinate, and yCoordinate) and outputs a 2D matrix of double values (double[ ][ ]), each of which representing the rectilinear distance from stop i to stop j. Shown below is a code block with the function as well as the mathematical equation driving it. The large multipliers in front of the distance calculations are the conversion factor from coordinate difference to meters, which were chosen to move as much of the distance information before the decimal place as Google OR Tools only accepts long values which don’t read after the decimal point.
\[RD_{i,j} = \sqrt{(111,205.70(x_{i}-x_{j}))^2+(89,962.33(y_{i}-y_{j}))^2}\]
public static double[][] RDMatrix(ArrayList<Stop> stopList) {
//Note that absolute value was used in place of squaring
//and square rooting to make the code simpler to understand
double[][] RDMatrix = new double[stopList.size()][stopList.size()];
for (int i = 0; i < stopList.size(); i++) {
for (int j = 0; j < stopList.size(); j++) {
double dx = (stopList.get(i).getxCoordinate() - stopList.get(j).getxCoordinate()) * 111205.7;
double dy = (stopList.get(i).getyCoordinate() - stopList.get(j).getyCoordinate()) * 89962.33;
RDMatrix[i][j] = Math.abs(dx) + Math.abs(dy);
}
}
return RDMatrix;
}Solver Class
The fundamental part of our project is the Google OR Tools Solver. To keep our MainLayout class (Vaadin main view) from being overcrowded with building our entire model in the main page, we created a Solver class that handles storage, calling, and building of the Solver, so that all that is required in the main class is the actual instantiation . The Solver class holds most of the relevant data in constructed Solver objects with methods for actually executing solving the model. The fields include ArrayList<Bus> buses, ArrayList<Stop> stops, double[ ][ ] RDMatrix, int vehicleNumber, int mainHubIndex, RoutingIndexManager manager, RoutingModel model, RoutingSearchParameters parameters, and Assignment solution. This class has the constructor method, the Getter/Setter methods, as well as 2 custom methods. There is the buildSolver method as well the solveModel method, which build and solve the OR Tools model. Outlined below is the code behind these models.
public void buildSolver(long slackMax, long capacity, long globalSpanCoefficient) {
//**********Solver building following the VRP example given by Google with a mix of adapted and copied methods depending on code compatibility**********//
manager = new RoutingIndexManager(RDMatrix.length, vehicleNumber, mainHubIndex);
model = new RoutingModel(manager);
final int transitCallbackIndex = model.registerTransitCallback((long fromIndex, long toIndex) -> {
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return (long) RDMatrix[fromNode][toNode];
});
model.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
boolean unused = model.addDimension(transitCallbackIndex, slackMax, capacity, true, "Distance");
RoutingDimension distanceDimension = model.getMutableDimension("Distance");
distanceDimension.setGlobalSpanCostCoefficient(globalSpanCoefficient);
parameters = main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.setTimeLimit(Duration.newBuilder().setSeconds(120).build())
.build();
}
public Assignment solveModel() {
return model.solveWithParameters(parameters);
}Reflection
Overall this project has taught me a lot about Java and given me a much more solid understanding about the logistics that go into public transit. While I don’t feel this project necessarily taught me any new skills in object-oriented programming, it definitely served to solidify my understands of the concepts that are key to it as well improve my knowledge of quick commands such as fn + alt + del for quick insertion of common methods. This project did teach me a lot more about collaboration however. The main things I learned from scratch in this project are the hard skills required for programming with a team such as utilization of GitHub Teams/Repos and proper code merging practices. Though not learned from scratch, this project also improved a lot of my soft skills in teamwork and collaboration such as communication, compromise, and scheduling. I am truly proud of what my team was able to accomplish, going from never having met before to working together to make a useful and educational tool. I am proud that I was able to take on a coordinating role in the group, often initiating conversations about work splitting, scheduling, and meetings, as well as my hard contributions to the code such as the methods and classes mentioned above. This project has made me grow vastly more competent in my researching skills when it comes to tracking down methods of completing a goal as I often had to search out tools and resources to be able to accomplish such an open-ended project. I am extremely grateful for my teammates Zach and Rachel, as well as my teacher Mr. Crisel and my coordinating TA, Ahmed Khan.