Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

We use method 1 in our open source fleet scheduling app. We use the Graphhopper library to determine the travel time and distance matrix, between all pairs of points. We then use the jsprit project (which has now merged with Graphhopper) to solve the VRPTW (and many other routing and scheduling problem variants).

share|improve this answer

Your Answer


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.