Route Planner

During the ``zeroth'' iteration the route planner reads the trip file and a (potentially time-dependent) link travel-times file to generate a route set. For each subsequent iteration, it uses the route set of the previous iteration (which contains the trips, i.e. the origin-destination information, implicitly) and re-routes a fraction of all trips. The travel-time feedback from the microsimulation is averaged over bins of width t_b=900 seconds. Both for the initial route planning and for re-planning, each route is handled independently, i.e. the planner itself does not keep track of the delays that will be caused by travelers on the links they are intending to use. The algorithm is a fast implementation of a time-dependent Dijkstra [].

In order to obtain more computational speed, the route planner uses a classical master-slave parallelization with PVM as message passing library. The master reads in the current route-plan and distributes trips by coding them into messages and sending them to the slaves. Each slave reads a copy of the travel-time feedback file for its shortest path computations. The slaves return routes which are sorted with respect to departure time and written to a new route set file by the master. Since the computations of the routes are completely independent, there is no communication between the slaves at all.

Figure 5 shows the execution times for processing 100,000 plans at two different re-planning fractions. The data refers to the 24622 link network used for Dallas, run on a SUN Enterprise 4000 with 14 CPUs running at 250 MHz. The speedup is better for larger re-planning fractions f_r because the ratio between shortest path computations and I/O overhead improves. Still, current speed-up is not very satisfactory and we may have to think about more efficient methods such as packaging several route requests into single messages, or maybe even completely abandoning the master-slave approach.

  

Figure: Execution times of the Route Planner. Network with 24622 links; input 100000 routes; replanning fraction $f_r = 5\%$ and $10\%$ (that is, real computation is only needed for the fraction f_r of the 100000 routes).