Hot answers tagged routing
20
GRASS v.net.iso will give you a result like this in this example.
You might not want to run a convex hull algorithm on this output. Imagine the blue roads: A convex hull around them would contain a lot of parts that are not reachable in the time represented by "blue".
Instead, you might want to look into alpha-shapes (related question: Concave Hull: ...
17
The truth is that most people use a custom variation of the A* algorithm. You will see this across the most of the "big guys"(I can't say who they are in a public forum, but I can tell you that you probably use one of them - guaranteed), where the modification of the heuristics is very dependent on the datasets that they use.
You mentioned pgrouting ...
14
The geometric network is used to model things like utility networks, drainage, or any other network where the commodity does not have free will.
Network dataset is used for networks where "an agent" can choose the path, such as transportation networks.
There a description here (scroll down to the What is a network? section):
...
13
Often it is good to address the need that is stated rather than answering the question that was asked. I would like only to point out that there is a well-known parallel solution that neatly circumvents all the technical computing issues: Santa has helpers. These agents work asynchronously and independently to identify the houses that need visits and carry ...
12
Not sure if it is newer but pgRouting has a Shooting-Star algorithm:
Shooting-Star algorithm is the latest
of pgRouting shortest path algorithms.
Its speciality is that it routes from
link to link, not from vertex to
vertex as Dijkstra and A-Star
algorithms do. This makes it possible
to define relations between links for
example, and it ...
11
[Edit: this has been superseded by nx_spatial which is available from pypi (easy_install nx_spatial). Importing shapefiles is now standard in networkx 1.4]
I've been kind of disappointed by the lack of geometric network tools in ESRI's Python GP API, so I wrote up something that loads Shapefiles and Feature Classes into networkx directional graphs ...
11
Via Michelin
Total Costs from københavn(denmark) to tekirdağ(turkey) (based on default values)
252.61 EUR
Toll 0.00 EUR | Petrol 223.22 EUR | Road tax 29.39 EUR
Time
27h19 which 17h10 on motorways
Distance
2500 km which 1900 km on motorways
You can custom your route in fine detail - by type of car - engine size etc:
Routing options:
...
10
pgRouting has a function called DARP (Dial-a-Ride Problem) solver:
The Dial-a-Ride Problem (DARP) solver tries to minimize transportation cost while satisfying customer service level constraints (time windows violation, waiting and travelling times) and fleet constraints (number of cars and capacity, as well as depot location).
More on DARP and ...
7
Routing in Postgres / PostGIS is handled by the pgRouting library from
http://pgrouting.postlbs.org/
It looks like a script has already been written to handle osm straight into pgRouting at
http://pgrouting.org/docs/tools/osm2pgrouting.html
You will need to install pgRouting within Postgres before running the osm2pgrouting script.
7
Something like
SELECT
source,
target,
(SELECT SUM(cost) FROM -- or whatever you want to do with the routing result
(SELECT * FROM shortest_path_astar('...',
source,
target,
false,
false)
) AS foo
) AS cost
FROM all_to_all;
7
Contraction Hierarchy is a very fast algorithm:
http://algo2.iti.kit.edu/1087.php
This algorithm is RAM friendly while executing a query (to hold a contracted graph some more RAM is necessary as well as massive preprocessing)
There are some other algorithms - including the ones that solve public transit routing:
...
6
Well, potentially you could use v.net.iso from GRASS GIS. However it doesn't create polygons (AFAIK), but splits the lines by cost classes from the source.
As for calculating drive times from OSM, you could import the data into GRASS with v.in.osm, and use the v.net.iso to calculate the cost zones. If you wanted travel times and you don't have road speed ...
6
Depending on your purpose and the number of requests you need to put through the service, the Bing Maps REST APIs are generally free to use - they just require you to sign up for a key first from http://bingmapsportal.com.
The API for the Route service is at:
http://msdn.microsoft.com/en-us/library/ff701717.aspx, which can return driving distances and ...
6
OSM has a page dedicated to routing, which is worth going over:
http://wiki.openstreetmap.org/wiki/Routing
There is a special tool for importing OSM data into a PGRouting system and generating the required structure:
https://github.com/pgRouting/osm2pgrouting
Lastly, there is a workshop tutorial on getting routing working with OSM data here:
...
6
The only practical way is to add the 'missing' routes the data yourself. OSM probably shouldn't be putting parking lots into its walking routes. There are liability issues with adding routes that aren't real, properly maintained pedestrian paths. A parking lot, though walkable, could be dangerous and could be private property. You'll have similar issues with ...
5
Check out the OpenGraphRouter project.
Stephen Woodbridge has created a demo demonstrating the driving directions.
There is a pretty good thread on the PostGIS-users list related to this.
5
(This is not exactly the solution you require - but close.)
Google Maps API (v2) Driving Radius
This takes a starting location (city centre of Memphis)
and radiates out (like a spider) to 10 miles (default)
http://maps.forum.nu/gm_driving_radius.html#
FULL CREDIT goes to Marcelo Montagna
5
I'm currently exploring the same problem as you, for the purpose of research paper. Before I started to test these two databases, I had the same presumption as you. That Neo4j graph database would be perfect solution for this kind of problem. And partially it is, but with lot of problems.
First problem is that A-Star is only implemented if you are using ...
5
Disclaimer:
I haven't been up to speed on the research or best practice on this so forgive me if I miss anything and it's been 3 years since I worked with a Travel Demand Model. And when I did travel demand models, I didn't spend a whole lot of time and effort into building turning penalty/restriction models.
Turning restrictions and penalty settings ...
5
I have not used ArcGIS Schematics for more than some quick demos quite a few years ago, but there is a blog posting on Create route maps with the ArcGIS Schematics extension that may provide a solution.
5
The question has been asked before:
http://stackoverflow.com/questions/9535819/find-all-paths-between-two-graph-nodes and
http://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices
4
In general terms, you're dealing with a Knapsack problem by trying to choose route legs (based on time) to add up to a specific time [rather than finding the fastest/shortest routes]. Look online for Dynamic and Greedy algorithms for Knapsack to help optimize the speed, otherwise it's NP-complete and you're looking at exponential run time.
4
There's Flowmap, a niche GIS package designed for dealing with network analysis issues.
If you have a fairly simple use-case, the QGIS-based Quantum Navigator might do the trick.
GRASS also supports network analysis, though it may not be worth the friction of getting things set up inside of the environment.
4
If you can use an external service, the Google Directions API provides this functionality directly. It supports waypoints along the path, so you could do:
http://maps.google.com/maps/api/directions/json?origin=Redmond+Avenue+12,01864
&destination=Concord,MA&waypoints=lat1,long1|lat2,long2|lat3,long3&sensor=true
This will return a JSON document ...
4
The Weather Underground does this - Road Trip Planner (with Weather)
http://www.wunderground.com/roadtrip/
Example Route above:
...
4
This is known as the Travelling Salesman Problem. To do want you want, you would probably first calculate all your driving distances between the N points, then use one of the known algorithms to solve the problem.
4
there are some source on net when you googling. you can check following links for some information.
1.Graphserver - The open-source multi-modal trip planner.
2.pgRouting III: PHP + OpenLayers Interface
3.pgRouting 1.01 with OpenLayers 2.5 on Ubuntu 7.10
4.Getting the OpenLayers-Code for the Routing-application
EDIT:
if you search ready to use service ...
4
Okay, I looked further into the idea of Steve above. I'll try to demontrate his idea in a QGIS/PostGIS/pgrouting environment. You will get results such as this:
First, let's assume you have a geodata table with your shelves/obstacles looking like this (I made them up for this purpose):
Make sure your shelf data is in a projected coordinate system with ...
4
you can achieve this with Google Maps JavaScript API v3 - Directions Service. There is a doc here. and you can see stand-alone google example here.
and in this doc. you can get information about Travel Modes.
When you calculate directions, you need to specify which
transportation mode to use. The following travel modes are currently
supported:
...
4
Bearing in mind Sean's answer (that you have to add 'missing' pats yourself) as well as that these missing parts technically are parts of road-graph which are in turn are just lines, here is the quick'n'dirty workaround you may use. If the walking path has a common point with a "walkable" polygon, export this polygon's border as a line into your road-graph ...
Only top voted, non community-wiki answers of a minimum length are eligible
