Tag Info

Hot answers tagged

27

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: ...


24

Hang on surely Rudolph knows where to go. He's been doing it for years.


19

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


16

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): ...


15

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


13

[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 ...


13

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


12

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


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

Although the thread is a bit old, I wanted to add a few links about routing in case someone ends here like I did: OSRM <- Recommended Routino


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


9

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.


8

GRASS' v.net.iso can be used to to create the drive time 'network' which you could pass into a 'convex hull' command to get a polygon. Perhaps not ideal, but would work!


8

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: ...


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

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.


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

Travelling Salesman is supported by pgRouting: http://www.pgrouting.org/docs/1.x/index.html, so no need to implement something yourself if you alread have PostGIS at hand.


6

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


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

You can extract types with v.extract and then patch them with v.patch.


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


6

The question has been asked before on Stack Overflow: Find all paths between two graph nodes; and Graph Algorithm To Find All Connections Between Two Arbitrary Vertices


6

We are working on a multimodal routing for Austria (also for pedestrians). What I can say till now: You need the data: It took at least 4 years and even longer to collect all the necessary walkways, barriers, steps, opening times, streets, railways, bikeways, ferrys, and, and and...and its still going on You need a router which can interprete theses graphs ...


6

I think that the type of software you are looking for is called a chart plotter software. There are several solutions used in navigation, where using a laptop is more and more common. I will not list here the solutions using dedicated hardware (AIS/navigation systems for example). Amongst paying options you have the "best seller" called MaxSea ...


6

The link given by MappaGnosis is the first attempt to implement Graph theory algorithms in Python (by Guido van Rossum, the creator of Python). Since, many modules were developed: Graph theory network routing network One of the most comprehensive is NetworkX, mentioned before in GS it can read or write shapefiles natively (thanks to bwreilly in ...


5

http://osm2postgis.sourceforge.net/ has all the components for routing with Geoserver (is in development and in Alpha)


5

Check out the OpenGraphRouter project. Stephen Woodbridge has created a demo demonstrating the driving directions.[Dead link] There is a pretty good thread on the PostGIS-users list related to this.[Dead link]


5

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.



Only top voted, non community-wiki answers of a minimum length are eligible