Optimization of multiple criteria in journey planning

A system for identifying candidate paths between an origin and a destination, comprising:

• memory which stores a network graph in which toll road entries and exits and toll crossings are represented by nodes of the graph, the nodes being connected by edges, each edge being associated with a respective duration;
• a criteria setting component which establishes a constraint for each of a plurality of criteria, based on input from a user;
• a candidate path computation component for computing a set of Pareto optimal candidate paths from the origin to the destination based on the network graph, which respect the constraints on the criteria and which are all Pareto optimal;
• a display component for causing at least a subset of the Pareto optimal candidate paths to be displayed to the user;
• and
• a processor which implements the criteria setting component, the candidate path computation component and display component.

A method for identifying candidate paths between an origin and a destination, comprising:

• receiving information from a user for identifying an origin and a destination in a road network which includes a toll road network;
• identifying a shortest duration path from the origin to the destination;
• providing for the user to input constraints on three criteria, at least one of the criteria being a maximum duration on a candidate path from the origin to the destination which is at least the duration of the shortest duration path;
• generating a set of Pareto optimal candidate paths from the origin to the destination comprising:
• providing a search graph representing a part of the road network between the origin and destination, in which toll network entries and exits and intermediate tollbooths between the entries and exits are represented as nodes connected by edges, each edge being associated with a duration;
• pruning nodes of the search graph, each of the pruned nodes being a node for which no path from the origin to the destination which contained the node could satisfy the maximum arrival time constraint;
• and
• from the pruned search graph, identifying a set of Pareto optimal candidate paths from the origin to the destination, which respect the constraints on the criteria and which are all Pareto optimal;
• displaying at least a subset of the Pareto optimal candidate paths to the user, wherein at least one of generating a candidate set of paths, generating a candidate set of paths, and displaying at least a subset of the candidate paths is performed with a processor.