Current travel itinerary planning approaches focus on deterministic shortest path algorithms that fail to factor in variability that can lead to delays or missed transfers. This dissertation focuses on utilizing distributions from large historical datasets for flight, driving and public transportation, in a network search algorithm to capture the reliability of an itinerary. This multi-modal reliability approach can help travelers make a better-informed decision when planning door-to-door travel itineraries in a world full of variability.