[GRASS-user] Road directed network partitioning in k-subgraphs around source node?

GRASS GRASS user
1

I’m looking for a method to parition a road network in k connected subgraphs around a starting node (i.e. the source node must be on a subgraph cut edge of each subgraph).

Is there anyone that have solved this kind of problem within GRASS?

Regards,

Giovanni

–
Giovanni Allegri
http://about.me/giovanniallegri
blog: http://blog.spaziogis.it
GEO+ geomatica in Italia http://bit.ly/GEOplus

2

I try to explain my problem with an example:

I have 3 vehicles that must do some work on a road netowk.

The morning they will leave the station and will go to their working area.

I need to partition the road network under the following heursitic constraints:

  • the subgraphs must be connected

  • they must have similar graph density

  • the transfer time for the vehicles must be similar

I can start simplifying the problem: paritioning the road graph in k subraphs, “radially” around the station, with k the number of vehicles.

giovanni

···

2013/9/5 G. Allegri <giohappy@gmail.com>

I’m looking for a method to parition a road network in k connected subgraphs around a starting node (i.e. the source node must be on a subgraph cut edge of each subgraph).

Is there anyone that have solved this kind of problem within GRASS?

Regards,

Giovanni

–
Giovanni Allegri
http://about.me/giovanniallegri
blog: http://blog.spaziogis.it
GEO+ geomatica in Italia http://bit.ly/GEOplus

–
Giovanni Allegri
http://about.me/giovanniallegri
blog: http://blog.spaziogis.it
GEO+ geomatica in Italia http://bit.ly/GEOplus

3

On 05/09/13 12:50, G. Allegri wrote:

I try to explain my problem with an example:

I have 3 vehicles that must do some work on a road netowk.
The morning they will leave the station and will go to their working area.
I need to partition the road network under the following heursitic
constraints:

  - the subgraphs must be connected
  - they must have similar graph density
  - the transfer time for the vehicles must be similar

I can start simplifying the problem: paritioning the road graph in k
subraphs, "radially" around the station, with k the number of vehicles.

Maybe you can try to create k nodes that are all very close to the starting point, but in different directions and then run v.net.alloc ?

Moritz

4

Good point Moritz, I will try your trick and I will let you know :wink:

···

2013/9/5 Moritz Lennert <mlennert@club.worldonline.be>

On 05/09/13 12:50, G. Allegri wrote:

I try to explain my problem with an example:

I have 3 vehicles that must do some work on a road netowk.
The morning they will leave the station and will go to their working area.
I need to partition the road network under the following heursitic
constraints:

  • the subgraphs must be connected
  • they must have similar graph density
  • the transfer time for the vehicles must be similar

I can start simplifying the problem: paritioning the road graph in k
subraphs, “radially” around the station, with k the number of vehicles.

Maybe you can try to create k nodes that are all very close to the starting point, but in different directions and then run v.net.alloc ?

Moritz

–
Giovanni Allegri
http://about.me/giovanniallegri
blog: http://blog.spaziogis.it
GEO+ geomatica in Italia http://bit.ly/GEOplus