Journey Planner

A specialised electronic search engine used to find the best journey between two points by some means of transport. Journey planners have been widely used in the Travel industry since the 1970s by booking agents accessed through a User interface on a computer terminal, and to support Call Centre agents providing public transport information. With the advent of the internet, self-service browser based on-line journey planner interfaces for use by the general public have become widely available. A journey planner may be used in conjunction with ticketing and reservation systems, or just to provide schedule information.

Scope

A journey planner finds one or more suggested journeys between an origin and a destination. The origin and destination may be specified as geospatial coordinates, named topographical places (e.g. 'Timperley', 'Scunthorpe', 'Grimsby' ), Points of Interest e.g. 'British Museum', or names or identifiers of points of access to public transport such as bus stops, stations, airports or ferry ports. A location finding process will typically first resolve the origin and destination into the nearest known nodes on the transport network in order to compute a journey plan over its data set of known journeys.

Journey planners for large networks typically use a search algorithm to search a graph of nodes (representing access points to the transport network) and edges (representing possible journeys between points). Different weightings such as distance, cost or accessibility may be associated with each edge.

Searches may be optimised on different criteria, for example "fastest", "shortest", "least changes", "cheapest". They may be constrained for example to leave or arrive at a certain time, to avoid certain waypoints, etc.

* Also known as a "Trip Planner", a Journey Planner may cover a single mode of transport, eg rail, or many transport modes for a combined journey, e.g. bus rail, air, in which case it is an Intermodal Journey Planner.

* A Road Route Planner is a journey planner specialised for road network use. Road networks are characterised by a large number of nodes and edges which may typically be used at any time.
* A Public Transport Journey Planner (or in American English usage, a Public Transport Route planner) is specialised for journeys on Public Transport. A public transport network is characterised by a smaller graph, with services that typically run only at a particular time or at a specified frequency.

Historically a Route planner has covered just the Route, showing a path by which it is possible to travel between two points at any time; in contrast a Journey Planner has also take into account the timetable of services that run over the network only at certain times, and so the time of travel is relevant when computing a joruney. However with the development of "road timetables", associating different journey times for road links at different times of day, time of travel is also relevant for road route planners.

Technology

Typically Journey Planners use an efficient in memory representation of the network and timetable to allow the rapid searching of a large number of paths. Databases queries may also be used where the number of nodes needed to compute a journey is small, and to access ancillary information relating to the journey.

An single engine may contain the entire transport network, and its schedules, or may allow the distributed computation of journeys using a distributed journey planning protocol such as JourneyWeb or Delfi Protocol.

A Journey Planner engine may be accessed by different front ends, using a Software Protocol or Application Program Interface specialised for journey queries, to provide a User Interface on different types of device.

The development of Journey Planning engines has gone hand in hand with the development of data standards for representing the stops, routes and timetables of the network, such as TransXChange, NaPTAN as well as such asTransmodel that ensure that these fit together.

History

A journey optimisation problem Seven Bridges of Königsberg, was central to the original formulation of Graph theory by Leonhard Euler.

Dijkstra's algorithm forms the basis of modern journey planner search algorithms and provides an optimal solution to simple searches. Early journey planning planning engines were typically developed as part of the booking systems for high value transport such as air and rail, using mainframes databases and OLTP systems. Well known examples of such Computer reservations system (CRS) include Sabre , Amadeus, Galileo, and the Rail Journey Information System developed by British Rail.

As computing resources became more widely available, journey planner engines were developed to run on minicomputers, Personal computers, and mobile devices, and as internet based services accessible though Web Browsers, Mobile browsers, SMS, etc. In the early 2000's Large scale metropolitan web planners such as Transport for London's journey planner became available. The UK's Transport Direct portal is one of the first Nationwide systems, allowing comparison of travel by any mode between any two points in the country, ThMany entities, including municipal government, state and federal government, and for profit companies operate web sites now offer trip planning services for large metropolitan areas, or even country-wide. For profit companies such as EasyJet, National Rail Enquiries or Deutsche Bahn typically operate sites free to people planning trips, relying on ticket sales and advertising for revenues.

As the size of the transport systems covered by journey planners has increased, protocols and algorithms for [Distributed Journey Planner| distributed journey planning] have been developed, allowing the distributed computation of journeys using networks of journey planners, each computing parts of the journey for different parts of the country. The EU Spirit, JourneyWeb and the Delfi Protocol are all examples of distributed journey planning protocols. [http://www.internet.xephos.com/site/xephos/en/journeys.php Xephos] is another example of a distributed journey planning network with information populated by its user base.

Another development in the 2000's has been the addition of Real-time travel information to update the current schedules to include any delays or changes that will affect the journey plan.

In 2005 Google started developing Google Transit a journey planning engine that works in conjunction with Google Maps, using data imported in the Google Transit Data Feed Specification.

Optimisation

Journey planning algorithms are a classic example of problems in the field of Computational complexity theory. Real-world implementations involve a tradeoff of computational resource between accuracy and completeness of answer, and speed of the results.

See also

*JourneyWeb
*Intermodal Journey Planner
*Public Transport Route planner.
*Google Transit
*Route planner

References

* [Transport for London] [http://www.tfl.gov.uk]
*JourneyWeb 2.1.0 Specification 2003 Atkins / UK [Department of Transport]
* Delfi : Report on the current status of the DELFI-system implementation. Federal Ministry of Transport, Germany and the Companies of DB AG, HaCon, HBT, IVU, mdv. Edited by Stephan Schnittger. 18 July 2006.
* google Transit: http://www.google.com/transit