|
|
| GeoCommunity Mailing List |
| |
| Mailing List Archives |
| Subject: | GISList: SUM: Network Analyst Routing algorithms |
| Date: |
12/23/2001 09:22:53 PM |
| From: |
Jan Husdal |
|
|
In response to my question
"Does anybody know which algorithm ArcView Network Analyst uses? Dijkstra?
Bellmann-Ford? Gateway Shortest Path? Going further into the proprietary
programming, which I guess is C/C++, what data structure is most likely to
have been utilized?
Is there somewhere in the literature or on the web that I can find anything
of this documented or at least indicated ?"
Here are the results:
1.
ArcView Network Analyst uses a modified Dijkstar with a 2 D-Heap.
It was written in C. There are a number of things that are done
in addition as the algorithm finds a path from any location to any
other location (not just node to node) on a network. The network
representation of the spatial data is a propiretery data structure
that was built for ArcView Network Analyst to facilitate quick access
to the topology of the spatial data.
2.
> For shortest path, we use a modified Dijkstra with a d-heap and custom
> memory management to deal with very large networks.
>
> For the Travelling Salesman Problem, we use a TABU search based
> heuristic. This gives us very good results and can handle quite
> large problems. (Workstation ArcInfo NETWORK's TSP solver uses an
> OR-OPT based heuritic.)
jan
Jan Husdal, MSc in GIS
jan@husdal.com
www.husdal.com
To unsubscribe, write to gislist-unsubscribe@geocomm.com
________________________________________________________________________
Setup a GeoCommunity Account and have access to FAST DataDownloads
and Premium Career Posting at a discounted rate!
https://www.geocomm.com/cgi-bin/accounts/login
On-line Archives available at
http://spatialnews.geocomm.com/community/lists/
|
|
Sponsored by:
For information
regarding
advertising rates
Click Here!
|
