Journey planner

Screenshot of OpenTripPlanner journey planning application with highlighted route by transit.

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.[1][2] Searches may be optimised on different criteria, for example fastest, shortest, least changes, cheapest.[3] 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 as well as transport networks for private transportation. Journey planning is sometimes distinguished from route planning,[4] where route planning is typically thought of as using only one mode of private transportation such as driving, walking, or cycling. Journey planning by contrast would makes use of at least one public transport mode which operates according to published schedules.

Journey planners have been widely used in the travel industry since the 1970s by booking agents. 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, FromAtoB.com and DistancesBetween.com.

A journey planner may be used in conjunction with ticketing and reservation systems.

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:

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 University of Amsterdam on an Atari PC.[5] He was hired by the Dutch Railways to build a digital journey planner for train services. In 1990 the first digital journey planner for the Dutch Railways (on diskette) was sold to be installed on PCs and computers for off-line consultation.[6] The principle of the software program was published in a Dutch university paper in 1991[7] 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 telephone inquiries to public transport companies. Before, experienced staff was needed with good geographical 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 mainframe 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 multi-modal 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 now operate web sites offering trip planning services for large metropolitan areas, or even whole countries. Transport 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. JourneyWeb, EU Spirit, Xephos, and the Delfi Protocol are all examples of distributed journey planning protocols. Another development in the 2000s has been the addition of real-time 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,[8] 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, sometimes referred to as 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. Transit networks can be connected to a street network by creating links between stop or station locations and nearby streets.[1]

Real-time prediction information

Journey planners may be able to incorporate real-time information into their database and consider them in the selection of optimal routes.[2] Automatic vehicle location (AVL) systems monitor the position of vehicles using GPS systems and can pass on real-time and forecast information to the journey planning system.[1] A journey planner may 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. Based on this information the journey planner is able to indicate the punctuality or delays for each mode of transport in a departure monitor.

Situation information

A situation is a software representation of an incident (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.

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.

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, Transmodel or GTFS 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.[4]

The sub-problem of route planning is an easier problem to solve[9] 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 increasingly relevant for route planners as well.

Algorithms

Journey planners use a routing algorithm to search a graph representing the transport network. In the simplest case where routing is independent of time, the graph uses (directed) edges to represent street/path segments and nodes to represent intersections. Routing on such a graph can be accomplished effectively using any of a number of routing algorithms such as Dijkstra's, A*, Floyd-Warshall, or Johnson's algorithm.[10] Different weightings such as distance, cost or accessibility may be associated with each edge, and sometimes with nodes (e.g. where there are traffic signals).

When time-dependent features such as public transit are included, there are several proposed ways of representing the transport network as a graph and different algorithms may be used such as RAPTOR[11]

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

See also

References

  1. 1 2 3 Li, Jing-Quan; Zhou, Kun; Zhang, Liping; Zhang, Wei-Bin (2012-04-01). "A Multimodal Trip Planning System With Real-Time Traffic and Transit Information". Journal of Intelligent Transportation Systems. 16 (2): 60–69. ISSN 1547-2450. doi:10.1080/15472450.2012.671708.
  2. 1 2 Zografos, Konstantinos; Spitadakis, Vassilis; Androutsopoulos, Konstantinos (2008-12-01). "Integrated Passenger Information System for Multimodal Trip Planning". Transportation Research Record: Journal of the Transportation Research Board. 2072: 20–29. ISSN 0361-1981. doi:10.3141/2072-03.
  3. ↑ "Bike Triangle | OpenTripPlanner". GitHub. Retrieved 2017-05-11.
  4. 1 2 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. ISBN 9783319494869. doi:10.1007/978-3-319-49487-6_2.
  5. ↑ Trouw, 05/06/1998
  6. ↑ 175 years of travel information, chapter:Wel of geen vervoer?
  7. ↑ http://kinkrsoftware.nl/contrib/Artikel16b.2a/tulp.pdf, Tulp, Eduard, Searching time-table networks, proefschrift Vrije Universiteit Amsterdam, 1991
  8. ↑ 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.
  9. ↑ Delling, Daniel; Sanders, Peter; Schultes, Dominik; Wagner, Dorothea (2009-01-01). "Engineering Route Planning Algorithms". In Lerner, Jürgen; Wagner, Dorothea; Zweig, Katharina A. Algorithmics of Large and Complex Networks. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 117–139. ISBN 9783642020933. doi:10.1007/978-3-642-02094-0_7.
  10. ↑ "Routing Functions — pgRouting Manual (2.0.0)". docs.pgrouting.org. Retrieved 2017-05-13.
  11. ↑ Delling, Daniel; Pajor, Thomas; Werneck, Renato F. (2014-10-30). "Round-Based Public Transit Routing". Transportation Science. 49 (3): 591–604. ISSN 0041-1655. doi:10.1287/trsc.2014.0534.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.