# Optimized Path

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)

## WHAT IS IT?

This model uses the Dijkstra’s algorithm of the Netlogo Network extension to compute the optimal path between several waypoints.

## HOW IT WORKS

It selects one waypoint as a starting point, learns the shortest paths to every other waypoint, selects the closest one and iterates from the latter until all waypoints are visited. To ensure that all paths are considered the simulation is run so that every waypoint is tested as the starting point. These paths are compared and the shortest one is selected as the optimal path between all waypoints.

## HOW TO USE IT

GRID-SIZE – Controls the extent of the network

NB-WAYPOINTS – Controls the number of waypoints to be created

SHOW_NAMES_NODES? – Determined whether or not the “Who” attribute of each node is displayed

SHOW_NAMES_WAYPOINTS? - Determined whether or not the “Who” attribute of each waypoint is displayed

## THINGS TO TRY

Try running the model with more or less waypoints.

Try different sizes of grid.

## NETLOGO FEATURES

The code used to setup the initial grid of nodes forming the network was based on the “Diffusion on a Directed Network” model available in the Model Library.

## Comments and Questions

extensions [nw table] breed [waypoints waypoint] breed [nodes node] globals [ list-distance list-path-waypoint list-distance-path list-dist-path list-links list-all-path list-total-distance waypoint-count number-waypoint list-waypoints strating-point path previous-waypoint total-distance final-distance fp ] waypoints-own [ distances-to-other-waypoint ] links-own [ street-length ] ;*********SETUP************* to setup clear-all set-default-shape nodes "dot" set-default-shape waypoints "dot" ask patches with [abs pxcor < (grid-size / 2) and abs pycor < (grid-size / 2)][ sprout-nodes 1 [ set color blue] ] ask nodes [ if Show_Names_Nodes? = True [ ifelse label = "" [set label (word who " ")] [set label ""] ] let neighbor-nodes turtle-set [turtles-here] of neighbors4 create-links-with neighbor-nodes [ set street-length link-length set color grey set thickness 0.1 ] ] ask nodes [ setxy (xcor * (max-pxcor - 1) / (grid-size / 2 - 0.5)) (ycor * (max-pycor - 1) / (grid-size / 2 - 0.5)) ] create-waypoints nb-waypoints ask waypoints [ setxy random-xcor random-ycor set color red if Show_Names_Waypoints? = True [ ifelse label = "" [set label (word who " ")] [set label ""] ] let closest-node min-one-of nodes [distance myself] create-link-with closest-node [ set street-length 0 set thickness 0.1 set color white] ] end ;*********GO************* to-report optimized-path let select-optimized-path [] set list-distance [] set list-path-waypoint [] set list-distance-path [] set list-dist-path [] set list-links [] set list-all-path [] set list-total-distance [] set waypoint-count count waypoints set number-waypoint count waypoints set list-waypoints sort-on [who] waypoints let r 0 let h 0 let i 0 while [r < number-waypoint][ let first-waypoint item r list-waypoints set strating-point item r list-waypoints set list-waypoints remove first-waypoint list-waypoints while [h < number-waypoint - 1][ while [i < waypoint-count - 1][ ask first-waypoint [ let waypoint-next item i list-waypoints set path nw:weighted-path-to waypoint-next "street-length" set distances-to-other-waypoint nw:weighted-distance-to waypoint-next "street-length" set list-distance lput distances-to-other-waypoint list-distance set list-path-waypoint lput waypoint-next list-path-waypoint ] set i i + 1 ] let dw (map [(list ?1 ?2)] list-distance list-path-waypoint) set list-distance-path sort-by [first ?1 < first ?2] dw let closest-waypoint last (item 0 list-distance-path) ask first-waypoint [ set path nw:weighted-path-to closest-waypoint "street-length" set distances-to-other-waypoint nw:weighted-distance-to closest-waypoint "street-length" set list-links lput path list-links set list-dist-path lput distances-to-other-waypoint list-dist-path set previous-waypoint first-waypoint ask closest-waypoint [set first-waypoint closest-waypoint] ] set i 0 set h h + 1 set list-distance [] set list-path-waypoint [] set list-distance-path [] set list-waypoints remove previous-waypoint list-waypoints set list-waypoints remove first-waypoint list-waypoints set waypoint-count waypoint-count - 1 ] set total-distance sum list-dist-path set list-all-path lput list-links list-all-path set list-total-distance lput total-distance list-total-distance set h 0 set r r + 1 set list-waypoints sort-on [who] waypoints set waypoint-count count waypoints set list-dist-path [] set list-links [] ] let temp (map [(list ?1 ?2)] list-total-distance list-all-path) let fpt sort-by [first ?1 < first ?2] temp set select-optimized-path item 0 fpt report select-optimized-path end to compute-optimized-path ask links [set color grey] let temp optimized-path set final-distance item 0 temp set fp item 1 temp let s 0 let total count waypoints while [s < total - 1][ let dummy item s fp let t 0 while [t < length(dummy)][ ask item t dummy [ set color yellow set thickness 0.3 ] set t t + 1 ] set s s + 1 ] print (word "The shortest path between all waypoint is " fp) print (word "and has a length of " final-distance " meters ") end

There is only one version of this model, created over 3 years ago by Laure Vacquie.

## Attached files

File | Type | Description | Last updated | |
---|---|---|---|---|

Optimized Path.png | preview | Preview for 'Optimized Path' | over 3 years ago, by Laure Vacquie | Download |

This model does not have any ancestors.

This model does not have any descendants.