Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I'm trying to determine how routing software integrate road networks. Is there a best-practice (or standard) as to what part of the routing solution road networks are inserted specific to Vehicle Routing Problem with Time Windows (VRPTW)?

I've considered the following methods;

  1. Using the network first to determine shortest-path between each and every waypoint, and then performing VRPTW algorithms (large up-front cost as number of waypoints increase)
  2. Building initial populations first, and then using the road network only when executing cost function evaluations (as in the diagram Fig 1, Page 3 of this document)
  3. Executing the full VRPTW solution process and then performing shortest-path calcs only on successive waypoints defined per route sequence. (sub-optimal, road network not taken into account when evaluating route costs)

Where in the Vehicle Routing Problem (VRP) or VRPTW solving process is the road network accounted for?

share|improve this question
    
Your link seems to be broken... –  whuber Sep 14 '12 at 16:59
    
@whuber thanks, fixed. –  Stafford Williams Sep 14 '12 at 17:45
add comment

1 Answer 1

We are using method 1 from the list above in our FleetEngine software. This works well in small areas, where all waypoints could potentially be on the same route in the solution. If on the other hand the waypoints are far between and are only relevant for different depots, then it may not be the best strategy. One advantage of having the full matrix is much simpler and faster lookup of values in the optimizer. Downside (besides speed of calculation) is the matrix/matrices may get too big for the available RAM.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.