What is Profile Routing?
What is Profile Routing?
Journey planning is usually framed as an optimization problem: it’s about maximizing or minimizing some criterion. Problems where we must find the best combination or sequence of steps to meet a quantitative goal have been studied in great detail. There’s a specific term for solving them (combinatorial optimization) and a whole discipline has been built around doing so (operations research). The most straightforward way to apply these methods to public transit itineraries is to set an exact departure time, then optimize arrival time, reaching the destination as soon as possible. This is referred to as the “earliest arrival problem”. A more nuanced search might optimize overall difficulty (“generalized cost”) or economic utility, accounting for the fact that transfers are bothersome and in-vehicle time is more pleasant than waiting at a bus stop, but still require the user to give a specific departure or arrival time.
However, when people plan a trip they often think in other terms. The departure time may not be set in stone, in which case they want to minimize the total travel time or difficulty as long as the departure time falls within a certain window. This is referred to as a “profile search” in the scientific literature on routing algorithms. It’s generally a more complicated result to compute, but important enough to receive attention in many recent papers.
At Conveyal when we talk about “profile routing” we have a similar but broader idea in mind: given a time window during which we want to travel, what are all the viable transport options that connect point A to point B? We’re not just interested in the ones that are absolutely optimal in terms of arrival time, elapsed time, or difficulty, but also the alternatives that one might choose as backup options or for subtle personal reasons. If there is a bus connection that always takes 5 minutes longer than the rail line, we still want to know about it. If four different bus routes run along a common trunk, we want all of them to be visible within the same itinerary as alternatives if they offer comparable travel times. In addition, we want to consider all mode combinations, including the use of park-and-ride facilities and bikes to reach transit.
Besides the variation in travel time experienced from one trip to the next and the options available to mitigate it, profile results also reveal the robustness of the transportation network when it is faced with congestion or service interruptions. In the simplest case this is expressed from the point of view of a the individual commuter or traveler, but we can also apply the logic behind these point-to-point searches in the one-to-many case. If we leave from a certain location during a certain time window, what are all the combinations of routes that are viable options for reaching any other location, and what range of travel times am I likely to experience using each of those options?
These profile routing extensions have been implemented in OpenTripPlanner and are a major part of Modeify, Conveyal’s transportation demand management system. Knowing the full range of route combinations that a traveler might use also greatly enriches our Transport Analyst results. It is problematic to use the fastest known itineraries when calculating access to job markets or drawing travel time isolines. By applying profile routing, we can paint a much more detailed picture of accessibility that includes the uncertainty and variance passengers experience due to poor frequency or redundancy in a network. Eventually we even plan to apply profile routing to basic trip planning, so that users are shown the full range of route combinations they might be interested in and can browse custom-generated timetables for their chosen options.
