It's my first time trying to use routing software. I prefer to use free and open source software but ArcGIS Network Analyst is available, too.

For an university course i need a solution for the following simulated problem: Due to the deactivation of a bomb a part of a city (let's say 2 square kilometres) is evacuated. In order to make sure that everyone has left the area, a number (let's say 4 or more) of groups have to walk through the evacuated area covering all the roads to find out if someone remains in the area. This task has to be finished within one hour.

Vehicle Routing Problem?
I've read in this forum that tasks like that are called "Vehicle Routing Problem"(VRP), but i've also read a post suggesting that there's no solution for VRP in current pgrouting software.

Splitting the network?
Another approach is to split the whole road network into parts of same length, one part for each group. In the next step I would be able to calculate a route for each network. I think it's enough to consider the road length, because people will control the evacuation walking, so there is no speed limit and road surface doesn't really matter.

The problem is: As I'm just starting to get in touch with pgrouting I have abolutely no idea how to do this. Is it possible to split the network with pgrouting or is it better to use standard desktop gis software?

  • I don't suppose its a nice regular gridded city is it? – Spacedman May 29 '15 at 14:31
  • Absolutely not. It's a 1200 years old german city which has experienced a lot of changes and damages. The evacuation zone includes residential and industrial area, parks and a river. – dijea May 29 '15 at 15:18
  • 1
    Sounds more like a Route Inspection ("Chinese Postman") Problem (en.wikipedia.org/wiki/Route_inspection_problem) complicated by having four post-deliverers. – Spacedman May 29 '15 at 15:33
  • There's an old-looking QGIS plugin which probably doesn't work with the latest QGIS: github.com/rkistner/chinese-postman but it might give you some code and ideas to use! – Spacedman May 29 '15 at 15:51
  • Optimally splitting the network is hard. Imagine a block-design city. If you split down the middle of a block, you end up with lots of dead-end arcs that will get traversed twice. The better solution is to split across four-way intersections to create edges that look like brickwork. Hard to explain in words! The edge problem might only be significant if your areas are going to be mostly edges. Hmm this is a fun problem... – Spacedman May 29 '15 at 16:05

Browse other questions tagged or ask your own question.