Journey Planner
Encyclopedia
A journey planner is 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.
, 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.
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 journey. 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.
A 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 as Transmodel
that ensure that these fit together.
, 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 minicomputer
s, Personal computer
s, and mobile devices, and as internet based services accessible though Web Browsers, Mobile browsers, SMS
, etc.
In the early 2000s Large scale metropolitan web planners such as Transport for London's
journey planner became available. Starting in 2000 the Traveline service provided all parts of the UK with multimodal journey planning and in 2003 the Transport Direct
portal was one of the first Nationwide systems, allowing comparison of travel by any mode between any two points in the country,
Many 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 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. Xephos is another example of a distributed journey planning network with information populated by its user base.
Another development in the 2000s 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.
. Real-world implementations involve a tradeoff of computational resource between accuracy and completeness of answer, and speed of the results.
Search engine
A search engine is an information retrieval system designed to help find information stored on a computer system. The search results are usually presented in a list and are commonly called hits. Search engines help to minimize the time required to find information and the amount of information...
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
User interface
The user interface, in the industrial design field of human–machine interaction, is the space where interaction between humans and machines occurs. The goal of interaction between a human and a machine at the user interface is effective operation and control of the machine, and feedback from the...
on a computer terminal
Computer terminal
A computer terminal is an electronic or electromechanical hardware device that is used for entering data into, and displaying data from, a computer or a computing system...
, and to support call centre
Call centre
A call centre or call center is a centralised office used for the purpose of receiving and transmitting a large volume of requests by telephone. A call centre is operated by a company to administer incoming product support or information inquiries from consumers. Outgoing calls for telemarketing,...
agents providing public transport information. With the advent of the internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
, self-service browser based
Web browser
A web browser is a software application for retrieving, presenting, and traversing information resources on the World Wide Web. An information resource is identified by a Uniform Resource Identifier and may be a web page, image, video, or other piece of content...
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 coordinatesGeographic coordinate system
A geographic coordinate system is a coordinate system that enables every location on the Earth to be specified by a set of numbers. The coordinates are often chosen such that one of the numbers represent vertical position, and two or three of the numbers represent horizontal position...
, 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
Search algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
to search a graph of nodes
Graph (data structure)
In computer science, a graph is an abstract data structure that is meant to implement the graph and hypergraph concepts from mathematics.A graph data structure consists of a finite set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices...
(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, e.g. rail, or many transport modes for a combined journey, e.g. bus rail, air, in which case it is an Intermodal Journey PlannerIntermodal Journey PlannerAn Intermodal Journey Planner , or Trip Planner is computer system which can provide a traveller with an itinerary for an intermodal passenger transport journey. The system can provide timetable, routing and other travel information...
.
- 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 plannerPublic transport route plannerA public transport route planner is a type of journey planner designed to provide information about available public transport journeys, nowadays often made available as a Web application...
) 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 journey. 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. Database 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.A single engine may contain the entire transport network, and its schedules, or may allow the distributed computation
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
of journeys using a distributed journey planning protocol such as JourneyWeb
JourneyWeb
JourneyWeb is an XML protocol to allow distributed journey planning engines to communicate in order to provide multimodal journeys spanning different regions....
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
User interface
The user interface, in the industrial design field of human–machine interaction, is the space where interaction between humans and machines occurs. The goal of interaction between a human and a machine at the user interface is effective operation and control of the machine, and feedback from the...
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
TransXChange
TransXChange is a UK national XML based data standard for the interchange of bus route and timetable information between bus operators, the Vehicle and Operator Services Agency, local authorities and passenger transport executives, and others involved in the provision of passenger information.The...
, NaPTAN
NaPTAN
The National Public Transport Access Node database is a UK nationwide system for uniquely identifying all the points of access to public transport in the UK...
as well as such as Transmodel
Transmodel
Transmodel is the CEN European Reference Data Model for Public Transport Information; it provides an abstract model of common public transport concepts and data structures that can be used to build many different kinds of public transport information system, including for timetabling, fares,...
that ensure that these fit together.
History
A journey optimisation problem Seven Bridges of KönigsbergSeven Bridges of Königsberg
The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology....
, was central to the original formulation of Graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
by Leonhard Euler
Leonhard Euler
Leonhard Euler was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion...
.
Dijkstra's algorithm
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
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
Computer reservations system
A computer reservations system is a computerized system used to store and retrieve information and conduct transactions related to air travel. Originally designed and operated by airlines, CRSes were later extended for the use of travel agencies...
(CRS) include Sabre
Sabre (computer system)
Sabre Global Distribution System , owned by Sabre Holdings, is used by more than 55,000 travel agencies around the world with more than 400 airlines, 88,000 hotels, 24 car rental brands, and 13 cruise lines...
, Amadeus, Galileo, and the Rail Journey Information System developed by British Rail
British Rail
British Railways , which from 1965 traded as British Rail, was the operator of most of the rail transport in Great Britain between 1948 and 1997. It was formed from the nationalisation of the "Big Four" British railway companies and lasted until the gradual privatisation of British Rail, in stages...
.
As computing resources became more widely available, journey planner engines were developed to run on minicomputer
Minicomputer
A minicomputer is a class of multi-user computers that lies in the middle range of the computing spectrum, in between the largest multi-user systems and the smallest single-user systems...
s, Personal computer
Personal computer
A personal computer is any general-purpose computer whose size, capabilities, and original sales price make it useful for individuals, and which is intended to be operated directly by an end-user with no intervening computer operator...
s, and mobile devices, and as internet based services accessible though Web Browsers, Mobile browsers, SMS
SMS
SMS is a form of text messaging communication on phones and mobile phones. The terms SMS or sms may also refer to:- Computer hardware :...
, etc.
In the early 2000s Large scale metropolitan web planners such as Transport for London's
Transport for London
Transport for London is the local government body responsible for most aspects of the transport system in Greater London in England. Its role is to implement the transport strategy and to manage transport services across London...
journey planner became available. Starting in 2000 the Traveline service provided all parts of the UK with multimodal journey planning and in 2003 the Transport Direct
Transport Direct
Transport Direct is a division of the UK Department for Transport to develop better information technology systems to support public transport. It developed and operates the Transport Direct Portal which is a public facing multi-modal journey planner...
portal was one of the first Nationwide systems, allowing comparison of travel by any mode between any two points in the country,
Many 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
EasyJet
EasyJet Airline Company Limited is a British airline headquartered at London Luton Airport. It carries more passengers than any other United Kingdom-based airline, operating domestic and international scheduled services on 500 routes between 118 European, North African, and West Asian airports...
, National Rail Enquiries or Deutsche Bahn
Deutsche Bahn
Deutsche Bahn AG is the German national railway company, a private joint stock company . Headquartered in Berlin, it came into existence in 1994 as the successor to the former state railways of Germany, the Deutsche Bundesbahn of West Germany and the Deutsche Reichsbahn of East Germany...
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 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
JourneyWeb
JourneyWeb is an XML protocol to allow distributed journey planning engines to communicate in order to provide multimodal journeys spanning different regions....
and the Delfi Protocol are all examples of distributed journey planning protocols. Xephos is another example of a distributed journey planning network with information populated by its user base.
Another development in the 2000s 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
Google Maps
Google Maps is a web mapping service application and technology provided by Google, free , that powers many map-based services, including the Google Maps website, Google Ride Finder, Google Transit, and maps embedded on third-party websites via the Google Maps API...
, 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 theoryComputational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
. Real-world implementations involve a tradeoff of computational resource between accuracy and completeness of answer, and speed of the results.
See also
- JourneyWebJourneyWebJourneyWeb is an XML protocol to allow distributed journey planning engines to communicate in order to provide multimodal journeys spanning different regions....
- Intermodal Journey PlannerIntermodal Journey PlannerAn Intermodal Journey Planner , or Trip Planner is computer system which can provide a traveller with an itinerary for an intermodal passenger transport journey. The system can provide timetable, routing and other travel information...
- Public Transport Route plannerPublic transport route plannerA public transport route planner is a type of journey planner designed to provide information about available public transport journeys, nowadays often made available as a Web application...
. - Google Transit
- Route planner