How to integrate road networks into Vehicle Routing Problem with Time Windows (VRPTW) algorithms?

Question

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?

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.