Vehicle routing involves travel and distances and the corresponding travel times are important to routing decisions. The concept used for this analysis tool is that most travel is between major travel points in a local region. Rather than determining carefully, the travel time between every pair of deliveries, the analyst will concentrate on a number of locations within the area such as major intersections, apartment complexes, shopping malls and business parks. Over time the distances or travel times between these fixed locations can be measured carefully or obtained from some database of travel times such as Google maps or GPS systems. Individual delivery locations can be located relative to these fixed location and the extra travel time estimated using the Euclidean measure and average travel speeds.

The Distance worksheet holds data related to distances or travel times between a collection of fixed locations in an area. It is created by clicking the Distance button on the Start worksheet. Of course, when a large number of locations are specified, the matrix defining the distances is correspondingly large. Although Excel allows large matrices, computational memory and speed may be compromised by a large set locations. An alternative, is to assume Euclidean distances between location, an option that does not require the matrix.

A dialog is presented requesting the name for the distance worksheet and the number of map locations to provide. The first checkbox, Random Coordinates, generates random coordinates for the locations. This is handy to view how the add-in works. The values can be changed on the worksheet. The second checkbox, Truncate to Integer, truncates computed distances to integer values. The last checkbox, Provide Matrix for Distances, builds a matrix showing location to location distances for all pairs of locations. The distances are initially computed with the Euclidean metric using the Pythagorean theorem. These values might be changed using modern mapping techniques such as Google maps for determining travel time or distance between locations.

The worksheet created by the add-in is illustrated below. The location coordinates are in columns E and F. These can be measured in kilometers, miles or any distance metric. The numbers shown are random, but may be replaced with the coordinates of traffic centers such as intersections or apartment complexes. The matrix for the example is 30 cells by 30 cells so not all columns are shown. The values in the matrix are computed using Excel formulas from the coordinates based on the Euclidean metric.

In practice, the matrix can be modified with realistic travel time data for the local area. The matrix can indicate either distances or travel times.

Changes

Once constructed, locations can be added or deleted using the Change button. It presents the dialog below. For the example shown, clicking OK will add two additional locations before the location currently indexed 15. New rows and columns are added to the coordinate list and distance matrix.

Euclidean Distances