Optimized Path

Optimized Path preview image

1 collaborator

Default-person Laure Vacquie (Author)

Tags

network 

Tagged by Laure Vacquie about 3 years ago

path 

Tagged by Laure Vacquie about 3 years ago

path finding 

Tagged by Laure Vacquie about 3 years ago

shortest path 

Tagged by Laure Vacquie about 3 years ago

Visible to everyone | Changeable by the author
Model was written in NetLogo 5.2.0 • Viewed 812 times • Downloaded 59 times • Run 0 times
Download the 'Optimized Path' modelDownload this modelEmbed this model

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

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

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 about 3 years ago by Laure Vacquie.

Attached files

File Type Description Last updated
Optimized Path.png preview Preview for 'Optimized Path' about 3 years ago, by Laure Vacquie Download

This model does not have any ancestors.

This model does not have any descendants.