Simulation System Behavior

The Scenario Generator runs first and generates a directory hierarchy of scenario data and a makefile that allows us to run simulations in parallel and only on scenario data that has not yet been computed. This allows us to add data points to large data sets without having to spend a lot of time recomputing existing results.

Snapshots of the simulation state occur regularly and trigger the creation of new optimization formulation files, which might be solved by Python's LP-Solve module several times throughout the evolution of the simulation. The optimization returns an object with a list of schedule results referenced by entities in the simulation to determine their actions.

After the runs are complete, the yEd graph viewer can neatly organize and display state snapshots of the transit entities in its pseudo-UML object view[47]. These visualizations of the simulation's graphML state dumps greatly assisted development and debugging. An example is depicted by Figure 5.2.

Finally, a post processing script assembles the raw output of SimPy data monitor taps into histograms for collective display on a summary web page for comparison. It also condenses a spreadsheet of input parameters and output metrics for each scenario to allow further data reduction as described in Section5.6.1.

The program uses the Psyco and SciPy modules to greatly increase the execution speed of most operations. Simply including the Psyco optimizer replaces certain commonly-used interpreted Python routines with optimized native code that gives the overall model a 1-2 order of magnitude increase in computation speed. [39] The SciPy library additionally gives us a high performance numerical library for performing calculations and efficiently manipulating large matrices. [35]

Statistical Scenario Comparison

The simulation uses some pseudo-random distributions to initialize demand curves. In order for our simulation runs to maintain repeatability, each of the scenarios include an initial random seed. A simulation run with the same seed will always generate the same random variables. Conversely, we can also vary the initial random seed across several runs of the same scenario in order to do Monte Carlo type simulations that gives us a proper distribution of output metrics as well.

The use of randomized initial distributions has another useful feature, in that it prevents the optimization problem from becoming too symmetric. Too much symmetry would result in multiple equal-cost branches to search exhaustively. So adding a touch of entropy to the our system allows our MIP solver to converge on a better solution slightly faster.

Computational Considerations

Large scale global optimization falls under the class of NP-hard problems that scale exponentially with the number of transit nodes we add to the transportation system. Accordingly, the simulation is set up to run in parallel across several CPUs, scalable to a massive clustered system with a shared filesystem. Some linear and mixed integer solvers also have the capability to partition and solve individual optimization problems in parallel. Unfortunately LP-Solve is not one of them, but it does have the ability to export its model into other optimization problem formulation language formats such as CPLEX or the industry standard MPS, so we need not worry about supporting parallelization.

We still would need to resort to a host of other tricks to reduce the computational complexity enough to approach problems of any appreciable size. Most of them involve introducing some sort of constraint to reduce the number of branch and bound paths search in the solution space. But primarily we resort to LP-Solve options that allow us to accept suboptimal but feasible solutions.

• The easiest way to reduce the computational complexity is to partition the problem into smaller parts. Since these types of ``traveling salesman'' problems scale exponentially with respect to the number of nodes, the number of branches to search would be drastically reduced by replacing an exponential term with a linear one.
• Adding link constraints is also another way of reducing the search space. Not every node needs to be linked to every other node. So often we will resort to building a connectivity matrix to define which source nodes can get to which destination nodes. With road and rail, only adjacent nodes are directly connected. Distant nodes would require transit through other city or station ``nodes''
• With aircraft, of course, most vehicles can travel directly from any node to just about any other node in the network. In this case, it may be helpful to add ``max passenger transfer'' constraints, to keep the system for searching through impractically long schedules. An itinerary that made a passenger jump between more than two or three connecting airports would likely be rejected by that person. On the other hand, low priority bulk cargo may find some cost advantage through waiting for these multiple connections, filling in otherwise ``empty'' space leftover on flights that could get closer to its destination. But at some point all of the extra handling and transfer overhead ought to outweigh the cost saved.
• Any constraint that would help ``lock down'' otherwise free variables would help reduce the search space. Feeding in initial conditions - like the current locations of the vehicles in the fleet, or stops that must be made by a certain time (for example, to ensure buses take all passengers to a stadium well before a game starts) may help speed the optimization solution search along.
• Sometimes it may be necessary to simply add other heuristic or even arbitrary constraints to help the system converge on a solution. By design, many of these constraints might not even affect the final solution, but constrain the search space enough to deliver an answer more quickly.

All else failing, many mixed-integer programming solvers, including LP-solve, can return ``good enough'' solutions without completing an exhaustive search of the solution space. Modern MIP solvers can also be pretty clever about searching the ``most promising'' paths close to the relaxed linear solution first. Completing the exhaustive search often yields little incremental improvement over the best previously discovered feasible objective. Of course, this technique applies only if a feasible integer solution can be found in reasonable time at all.

LP-Solve has a host of options that can allow it to return suboptimal solutions before completing an exhaustive branch-and-bound search of the solution space. It can simply provide the first MIP solution it finds after locating the relaxed linear solution using its simplex solver. We can also converge upon solutions faster by increasing its MIP gap tolerance, which is the relative improvement between suboptimal solutions it finds along its way. This effectively reduces the ``depth'' of its branch-and-bound search. Finally, it also offers a wall clock timeout that stops an optimization from running virtually forever and returns the current best suboptimal solution.

Finally, a sophisticated optimization could involve pre-computing most of the possible schedules in advance, and then have the ability to account for the effects of small changes with only minimal recalculation of the final optimal solution. This type of ``warm start'' optimization could help recover the schedule quickly after small, unexpected breakdowns. Suppose a vehicle suddenly announces that it will be arriving 30 minutes late to a hub node. If recomputing the entire optimal solution taking this new information into account would take a few hours of number crunching, we obviously don't want everything to grind to a halt while waiting for the scheduler to tell us what to do next. A warm start optimization would minimize recomputation, perhaps by determining a subset of decision variables which would likely be affected and formulating a highly-constrained problem that only searches through variables linked to unexpected changes in one or two input values. We'd need to develop a heuristic to determine exactly how far out this limited set of affected variables should reach.

Another warm start scheme might involve jumping back into a computational snapshot of the state of the large optimization and only recalculating internal values that have changed with the modified inputs. Perhaps some solvers have this ability.