| Let G = (V,E) be a graph with time-dependent edges where the cost of a path p through the graph is determined by a vector functions F(p) = [f 1 (p), f2( p),…, fn(p)] T, where f1, f 2,…, fn are independent objective functions. Where n > 1 there is no clear idea of what a “best” solution is, instead we turn to the idea of Pareto-optimality to define the efficiency of a path. Given the set of paths P through the network, a path p′ is Pareto-optimal if for every p ∈ P, (fi(p) ≥ f i(p′)).; The problem of planning itineraries on a transportation system involves computing the set of optimal paths through a time-dependent network where the cost of a path is determined by more than one, possibly non-linear and non-additive, cost function. This thesis introduces an algorithmic toolkit for finding the set of Pareto-optimal paths in time-dependent networks in the presence of multiple objective functions.; Multi-criteria path optimization problems are known to be NP-Hard, however, by exploiting geometric and periodic properties of the dynamic graphs that model transit networks we show that it is possible to compute the Pareto-optimal solutions sets rapidly without using heuristics. We show that we can solve the itinerary problem in the presence of response time constraints for a large scale graph. |
