Millions of people use public transportation and consult electronic timetable information systems. Selecting a connection is typically a mutli-criteria decision (based on travel time, ticket cost, and other criteria). As an evolution of the classical Pareto optimality approach we developed our concept of Advanced Pareto Optimality to deliver more attractive alternatives to choose from. We describe the fully realistic modeling of schedules as time-expanded or time-dependent graphs and introduce suitable generalizations of Dijkstra's shortest-path algorithm together with adapted and newly developed speed-up techniques resulting in fast response times of our prototypes. Our Multi Objective Traffic Information System (MOTIS) has been extended to cover further criteria (special offers, reliability of connections) and special search forms (e.g. for night trains). Information about delayed, canceled and additional trains is incorporated into our system, thus, valid connections can be computed in the presence of delays and a new service can be offered to travelers providing better alternatives.