Presentation to community of distributed OpenTripPlanner
Aitzol Egia
During the last few months we have been working on a distributed version of OpenTripPlanner: OpenMove (www.open-move.org). The idea is to make two or more independent OpenTripPlanner installations, one of each covering a region and the regions being neighbours, to work together to be able to find a route with origin in one region and destination in the other one. We have now a first working prototype ready and we would like to show it to the OTP community and have some feedback. The prototype has a lot of room for improvement but it is usable and we are willing to work together with OTP community to improve it if the community considers it is worth it.
The following video shows what our prototype does: http://www.open-move.org/demo-2/
Our work has been funded by a public grant from the Basque Government (http://www.basquecountry.eus) in Spain. This made us to develop OpenMove as an independent and isolated entity apart from OpenTripPlanner project. However, we are not willing to create a fork of OpenTripPlanner and we would like Openmove to be integrated into OpenTripPlanner.
OpenMove has been promoted by Solid Rock IT and has been developed by University of Deusto (http://www.deusto.eus) and a company consortium from several member companies of ESLE (Association of Basque Open Source Companies - http://www.esle.eu). We have made an 860 hours development effort, mainly oriented to modify OTP (extended graph with new node types, enhanced API, new functionality to request routes to “neighbour” multimodal planners, modification of A* algorithm,...). We have also designed a new algorithm to optimize path search between Openmove servers, based on Biomimetics (not implemented yet).
OpenMove is specially useful in the case of two metropolitan areas nearly located and with independent transit networks. In these cases it is usual to find two transit planners for each transit network, but each of them can only find routes within its own transit network. This makes Google Transit the only alternative for routes spanning more than one transit system. For example, Trimet and C-TRAN operate a transit system in Portland, OR and Vancouver, WA respectively. In this case it is not possible to find a route with origin in Portland and destination in Vancouver using “Trimet interactive Map”. The following picture shows an example of this situation at http://ride.trimet.org by searching for a route with the following parameters:
- From place=45.524036,-122.644116
- To place=45.662698,-122.621679
- mode=TRANSIT,WALK
It's time for us to return to OTP community our work, because we think OpenMove has no sense outside OTP.
Would it be possible to schedule a demo for the community to know OpenMove? Feel free to contact me if you are interested.
Kind regards,
Aitzol Egia Amezua
Solid Rock IT
andrew byrd
Thanks for sharing your work with the mailing list. This is an important
subject and I'm glad to see someone doing serious work in this
direction. We will seriously consider either merging your work directly
or cooperating with you to adapt the implementation to meet the most
users' needs.
The subject of distributed / federated route planning has come up
before, and there are a couple of reasons we have not attacked this
problem in the past. I first encountered federated route planning as a
way for transport operators (often large passenger rail operators) to
sidestep or downplay the importance of opening up their schedule data.
In response to government open data requirements they tend to promote
proprietary route planning APIs rather than raw data distribution,
implying that some intercity and international software layers will tie
all these APIs together. This may be feasible and may turn out to be the
only expedient way to provide national and international routing, but
strikes me as a politically and commercially motivated solution rather
than a technically efficient one.
Today, given the speed of networks and the storage capacity of commodity
computer hardware, it is entirely possible to organize and exchange raw
schedule data for an entire continent (or the world for that matter)
such that each routing instance has access to all raw schedule data. The
only real barrier to this is apprehension about openness on the part of
large, relatively cautious companies (who have however benefited
greatly throughout their history from public funding). Many approaches
to federated search assume a speed and geographic hierarchy in the
transport network with a number of bridge edges conveniently situated on
the borders of sub-server coverage areas
(http://en.wikipedia.org/wiki/Minimum_cut), and this is not necessarily
the case. It really depends on the country (compare France and the
Netherlands or Germany). Hiding the raw data behind a service API can
create a great deal of inefficiency in the search process and lead to a
slower progress requiring more network activity before a solution is
found.
All that said, A) I am very interested in your work and still need to
review the implementation details, and B) independent of any concerns
about open data vs. service APIs, imposing a hierarchy on a search can
greatly speed it up (cf. contraction hierarchies in street searches), so
these search techniques could help keep search times reasonable at
continental scales, contributing to the geographic scalability of OTP.
This last point is quite important to us as we are working on
increasingly large OTP deployments.
-Andrew
> - To place=45.662698,-122.621679
> - mode=TRANSIT,WALK
>
> <https://lh5.googleusercontent.com/-nuYUU_9LI0s/VE4r6R7FlJI/AAAAAAAAAJo/wct1dXJOcf0/s1600/trimetMap.png>
>
> In the example above, the planner returns a transit route to the border
> between Oregon and Washington states and then it suggests the user to
> walk
> to his final destination in Vancouver, WA. It would be great if Trimet
> Interactive Map would also be able to show transit routes for C-TRAN
> network by working together with C-PAN's planner. That is exactly what
> OpenMove offers.
>
> It's time for us to return to OTP community our work, because we think
> OpenMove has no sense outside OTP.
>
> Would it be possible to schedule a demo for the community to know
> OpenMove?
> Feel free to contact me if you are interested.
>
> Kind regards,
>
> Aitzol Egia Amezua
> Solid Rock IT
>
> You received this message because you are subscribed to the Google Groups
> "OpenTripPlanner Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to opentripplanner...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
Aitzol Egia
Hello Andrew,
I'm glad to know there has been some debate about this issue in the community. I understand also your concerns about the use of APIs in contrast of schedule data publication.
I can see that the solution provided in the work we've done has its advantages and disadvantages, and some of them were considered when we started our work. Some disadvantages that we identified are the longer times needed to find a solution and the possibility of not finding the optimal result. However, we also think that the use of federated route search brings some advantages and that it is a path that should be explored.
This solution could be a good option for decentralized countries such as Spain, where one or a few small transit authorities operate in each region. I find it hard to convince this small transit authorities about their need to allocate funds to build OTP instances with a continental scale, even though the costs of computational resources are becoming increasingly cheaper. In the meantime, Google Transit remains the only viable option that offers good results for both local transit routes and routes across a nation or continent. In this scenario most agencies, after an unsuccessful experience with their own multimodal planner, prefer to make a Google Transit based solution. I think also that it will be hard for these continental-scale OTP instances to keep all GTFS feeds regularly updated, that would lead to results with out-of-date schedules. This problem will hopefully be reduced as real-time feeds become more popular, but this is still an issue nowadays. This problem would be tackled in OpenMove because each agency would be responsible for keeping their graphs with up-to-date schedule data in the their OTP instance. This up-to-date data would also be used by other planners to find a transit route across a neighbouring region.
In any case, I think that the solution to this issue is not A (release of schedules in open data schemes) or B (APIs) but a combination of both. We have conceived our work inspired by DNS which has several centralized zones while still being a distributed system. IHMO, OTP could include the distributed feature as an option that administrator could enable if the deployment scenario requires it. An OTP with this feature enabled would then become an incentive to deploy a neighbour OTP instance as it would give more value to users.
I'm glad that you found the work interesting and I will be very happy to show you the results of our work. As I've mentioned in the previous message, there is still a lot of room for improvement and I am sure there will be some fixes to do, should our code be merged into the project.
Kind regards,
Aitzol
Aitzol Egia
Hello Andrew,
I am wondering if you have had time to review the work we have done about distributed route planning in OpenTripPlanner. Did you find it interesting? As I mentioned in a prior message the developed prototype has still a lot of room for improvement but we think it can be a good start. The code should also be refactored in order to be pulled to master repository as the current work is based on a previous OpenTripPlanner version.
I have also seen that the instructions in OpenMove's wiki (https://github.com/solidrockit/OpenMove/wiki/SetUpDevelopmentEnvironment) may not be enough for an easy installation of OpenMove. I am working on improving this instructions, just in case anyone wants to install it. I am also thinking about setting up two OpenMove servers in AWS.
Kind regards,
Aitzol