Journey planner: Difference between revisions

Content deleted Content added

Inline

Revision as of 15:00, 11 May 2017

A journey planner, trip planner, or route planner is a specialised search engine used to find an optimal means of travelling between two or more given locations, sometimes using more than one transport mode. 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. A single journey may use a sequence of several modes of transport, meaning that the system may know about public transport services (bus, train, aeroplane, etc.) and about transport networks (streets, footpaths, etc.) for private transportation (automobile, walking, bicycle).

Journey planners have been widely used in the travel industry since the 1970s by booking agents^{[citation needed]}. The growth of the Internet, the proliferation of geospatial data, and the development of information technologies generally has led to the rapid development of many self-service browser-based on-line intermodal trip planners such as Rome2rio, Google Transit and FromAtoB.com.

A journey planner may be used in conjunction with ticketing and reservation systems, or just to provide travel information.

Basic features

There is a great deal of variation among different journey planner applications, yet many share several common features. These typically include an interface for helping the user identify their origin and destination locations. These may include a geocoder which can find locations from street addresses or a web map that users can click on. 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.

There are often some number of options the user can select from including:

Desired transport mode
Time and/or date of travel
Other criteria specific to a travel mode
- For flights: cheapest ticket vs. shortest trip
- For bicycles: shortest path vs. avoiding traffic
- For transit: shortest trip vs. minimizing transfers
- etc.

After the journey planner has computed a trip or set of trips for the user to choose from, these are usually displayed either on a map (for most modes) or in a list (typical for flights). Often a journey planner will offer turn by turn directions for different legs of a trip, especially where the user needs to switch vehicles make turns, or change modes.

Some journey planners offer features like highly interactive maps, timetable displays for public transit modes, real-time traffic conditions, and suggested alternate routes. A journey planner may also have more than one user interface, with each optimised for different purposes. For example, online self-service done with a Web browser, an interface for call centre agents, one for use on mobile devices, or special interfaces for visually impaired users.

Some commercial journey planners include aspects of discovery shopping for accommodation and activities and price comparison for some aspects of a trip.

History

The first digital public transport journey planner software was developed by Eduard Tulp, a informatica student at the Amsterdam University on a Atari PC.^[1] He was hired by the Dutch Railways to built a digital journey planner for the train services. In 1990 the first digital journey planner for the Dutch Railways (on diskette) was sold to be installed on PC´s and computers for off-line consultation.^[2] The principles of the software program was published in a Dutch university paper in 1991^[3] This was soon expanded to include all public transport in the Netherlands. Other European countries soon followed with their own journey planners. The software supported all telefoon inquiries for the public transport compagnies. Before experienced staff was needed with good geografical knowledge and experience in consulting the paper timetables.

Early journey 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 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.

Mode-specific considerations

Public transport routing

For public transport routing the journey planner is constrained by times of arrival or departure. It may also support different routing criteria - for example, fastest route, least changes, cheapest, etc. Most trip planners are not capable of multiple simultaneous optimisations (e.g. cheapest, or most flexible) but may be able to advise fares for a single trip.

Car routing

The planning of road legs is sometimes done by a separate subsystem within a journey planner, but may consider both single mode trip calculations as well as intermodal scenarios (e.g. Park and Ride, kiss and ride, etc.). Typical optimisations for car routing are shortest route, fastest route, cheapest route and with constraints for specific waypoints. Some advanced journey planners can take into account average journey times on road sections, or even real-time predicted average journey times on road sections.

Pedestrian routing

A journey planner will ideally provide detailed routing for pedestrian access to stops, stations, points of interest etc. This will include options to take into account accessibility requirements for different types of users, for example; 'no steps', 'wheelchair access', 'no lifts', etc.

Bicycle routing

Some journey planning systems can calculate bicycle routes^[4], integrating all paths accessible by bicycle and often including additional information like topography, traffic, on-street cycling infrastructure, etc. These systems assume, or allow the user to specify, preferences for quiet or safe roads, minimal elevation change, bicycle lanes, etc.

Data requirements

Journey planners are no better than the data they have available to them. Some journey planners integrate many different kinds of data from numerous sources. Others may work with one type only, such as flight itineraries between airports, or only the street network for driving directions.

Street network data

The most basic journey planners, route planners, work only with street network data. Such data can come from one or more public, commercial or crowdsourced datasets such as TIGER, Esri or OpenStreetMap.

Public transport timetables

Data on public transport comes in a number of different standard formats such as GTFS or Transmodel.

Real-time prediction information

Automatic Vehicle Location (AVL) Systems know the actual position of their vehicles compared to the timetable and can pass on the real-time and forecast information to the journey planning system. The journey planning engine incorporates this up-to-date information into its database and considers it in all requests. Based on this information the journey planner is able to indicate the punctuality or delays for each mode of transport in a departure monitor. A journey planner will use a real time interface such as Service Interface for Real Time Information to obtain this data. Real time road Information may come from systems such as UTMC

Situation information

A situation is a software representation of an incident^{[citation needed]} (for example security alert, cancellation or bad weather) or event that is affecting or is likely to affect the transport network. A journey planner can integrate situation information and use it both to revise its journey planning computations and to annotate its responses so as to inform users through both text and map representations. A journey planner will typically use a standard interface such as SIRI, TPEG or DATEX II to obtain situation information.

Incidents are captured through an incident capturing system (ICS) by different operators and stakeholders, for example in transport operator control rooms, by broadcasters or by the emergency services. Text and image information can be combined with the trip result. Recent incidents can be considered within the routing as well as visualized in an interactive map.

Route planners

Route planning is sometimes distinguished from journey planning^[5]. Route planning is typically thought of as using only one mode which is not normally time-dependent, such as walking, cycling or driving. Journey planning by contrast makes use of at least one public transport mode which operates according to published schedules. Technically, route planning is an easier problem to solve^[6] as it generally involves less data and fewer constraints. 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 of journeys using a distributed journey planning protocol such as JourneyWeb or Delfi Protocol. A journey planning 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.

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.

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. Journey planning algorithms are a classic example of problems in the field of Computational complexity theory. Real-world implementations involve a tradeoff of computational resources between accuracy, completeness of the answer, and the time required for calculation^[5].

Commercial software

Distribution companies may incorporate route planning software into their fleet management systems to optimize route efficiency. A route planning setup for distribution companies will often include GPS tracking capability and advanced reporting features which enable dispatchers to prevent unplanned stops, reduce mileage, and plan more fuel-efficient routes.

Notable examples

References

^ Trouw, 05/06/1998
^ 175 years of travel information, chapter:Wel of geen vervoer?
^ http://kinkrsoftware.nl/contrib/Artikel16b.2a/tulp.pdf, Tulp, Eduard, Searching time-table networks, proefschrift Vrije Universiteit Amsterdam, 1991
^ Yoon, Ji Won; Pinelli, Fabio; Calabrese, Francesco (2012). "Cityride: A Predictive Bike Sharing Journey Advisor". Mobile Data Management (MDM), 2012 IEEE 13th International Conference: 306–311.
^ ^a ^b Bast, Hannah; Delling, Daniel; Goldberg, Andrew; Müller-Hannemann, Matthias; Pajor, Thomas; Sanders, Peter; Wagner, Dorothea; Werneck, Renato F. (2016-01-01). Kliemann, Lasse; Sanders, Peter (eds.). Algorithm Engineering. Lecture Notes in Computer Science. Springer International Publishing. pp. 19–80. doi:10.1007/978-3-319-49487-6_2. ISBN 9783319494869.
^ Delling, Daniel; Sanders, Peter; Schultes, Dominik; Wagner, Dorothea (2009-01-01). "Engineering Route Planning Algorithms". In Lerner, Jürgen; Wagner, Dorothea; Zweig, Katharina A. (eds.). Algorithmics of Large and Complex Networks. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 117–139. doi:10.1007/978-3-642-02094-0_7. ISBN 9783642020933.

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.

[1] Trouw, 05/06/1998

[2] 175 years of travel information, chapter:Wel of geen vervoer?

[3] ttp://kinkrsoftware.nl/contrib/Artikel16b.2a/tulp.pdf, Tulp, Eduard, Searching time-table networks, proefschrift Vrije Universiteit Amsterdam, 1991

[4] Yoon, Ji Won; Pinelli, Fabio; Calabrese, Francesco (2012). "Cityride: A Predictive Bike Sharing Journey Advisor". Mobile Data Management (MDM), 2012 IEEE 13th International Conference: 306–311.

[:0-5] Bast, Hannah; Delling, Daniel; Goldberg, Andrew; Müller-Hannemann, Matthias; Pajor, Thomas; Sanders, Peter; Wagner, Dorothea; Werneck, Renato F. (2016-01-01). Kliemann, Lasse; Sanders, Peter (eds.). Algorithm Engineering. Lecture Notes in Computer Science. Springer International Publishing. pp. 19–80. doi:10.1007/978-3-319-49487-6_2. ISBN 9783319494869.

[6] Delling, Daniel; Sanders, Peter; Schultes, Dominik; Wagner, Dorothea (2009-01-01). "Engineering Route Planning Algorithms". In Lerner, Jürgen; Wagner, Dorothea; Zweig, Katharina A. (eds.). Algorithmics of Large and Complex Networks. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 117–139. doi:10.1007/978-3-642-02094-0_7. ISBN 9783642020933.

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 75: / Line 75: @@
 ==Route planners==
-'''Route planning''' is sometimes distinguished from '''journey planning'''<ref name=":0">{{Cite book|url=http://link.springer.com/chapter/10.1007/978-3-319-49487-6_2|title=Algorithm Engineering|last=Bast|first=Hannah|last2=Delling|first2=Daniel|last3=Goldberg|first3=Andrew|last4=Müller-Hannemann|first4=Matthias|last5=Pajor|first5=Thomas|last6=Sanders|first6=Peter|last7=Wagner|first7=Dorothea|last8=Werneck|first8=Renato F.|date=2016-01-01|publisher=Springer International Publishing|isbn=9783319494869|editor-last=Kliemann|editor-first=Lasse|series=Lecture Notes in Computer Science|pages=19–80|language=en|doi=10.1007/978-3-319-49487-6_2|editor-last2=Sanders|editor-first2=Peter}}</ref>. Route planning is typically thought of as using only one mode which is not normally time-dependent, such as walking, cycling or driving. Journey planning by contrast makes use of at least one [[public transport]] mode which operates according to [[Public transport timetable|published schedules]]. Technically, route planning is usually an easier problem to solve as it does not require the inclusion of a temporal dimension. 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.
+'''Route planning''' is sometimes distinguished from '''journey planning'''<ref name=":0">{{Cite book|url=http://link.springer.com/chapter/10.1007/978-3-319-49487-6_2|title=Algorithm Engineering|last=Bast|first=Hannah|last2=Delling|first2=Daniel|last3=Goldberg|first3=Andrew|last4=Müller-Hannemann|first4=Matthias|last5=Pajor|first5=Thomas|last6=Sanders|first6=Peter|last7=Wagner|first7=Dorothea|last8=Werneck|first8=Renato F.|date=2016-01-01|publisher=Springer International Publishing|isbn=9783319494869|editor-last=Kliemann|editor-first=Lasse|series=Lecture Notes in Computer Science|pages=19–80|language=en|doi=10.1007/978-3-319-49487-6_2|editor-last2=Sanders|editor-first2=Peter}}</ref>. Route planning is typically thought of as using only one mode which is not normally time-dependent, such as walking, cycling or driving. Journey planning by contrast makes use of at least one [[public transport]] mode which operates according to [[Public transport timetable|published schedules]]. Technically, route planning is an easier problem to solve<ref>{{Cite book|url=http://link.springer.com/chapter/10.1007/978-3-642-02094-0_7|title=Algorithmics of Large and Complex Networks|last=Delling|first=Daniel|last2=Sanders|first2=Peter|last3=Schultes|first3=Dominik|last4=Wagner|first4=Dorothea|date=2009-01-01|publisher=Springer Berlin Heidelberg|year=|isbn=9783642020933|editor-last=Lerner|editor-first=Jürgen|series=Lecture Notes in Computer Science|location=|pages=117–139|language=en|chapter=Engineering Route Planning Algorithms|doi=10.1007/978-3-642-02094-0_7|editor-last2=Wagner|editor-first2=Dorothea|editor-last3=Zweig|editor-first3=Katharina A.}}</ref> as it generally involves less data and fewer constraints. 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 ==