The traditional traveling salesman
problem involves a salesman who must make a tour through some
set of cities. Starting at an arbitrary city, the salesman must
visit the other cities and then return to the starting city.
The distance between every city pair is specified and the salesman
is to visit each city once and only once. A solution is called
a tour and the goal is to find the minimum length tour. This
problem is considered by the Optimize add-in.
The routing problem addressed by the Combinatorics
add-in is similar to the TSP, but here we are dealing with a
vehicle that starts at a depot, visit several sites and returns
to the depot. The objective is to minimize the travel cost plus
a cost that depends on the times of deliveries to the cities.
The parameters of the problem are set in the dialog below.
Features of the problem are illustrated by the example. Two
additional sites are defined for the analysis. The site indexed
1 represents the depot at the start of the route, the site indexed
8 represents the depot at the end of the route, and the six
specified sites are indexed 2 through 7.
Time is the essence of this problem. A distance matrix (rows
16 to 23) describes the distances between each pair of sites.
Note that entry (i, j) holds the distance
to site i from site j. This is different than
the usual definition, but more convenient for modeling. Since
the random, Euclidean and integer options were specified, the
locations of the sites are randomly generated and shown in columns
L and M. Sites 1 and 8 both represent the depot and they have
the same location. The Euclidean distances between the site
locations are computed and the integer portions of the values
are placed in the table. If the Euclidean Formula option
had been chosen, Excel formulas evaluate the distances. The
user can then provide non-random locations for the sites in
columns L and M. If a density less than 100% is chosen cells
are randomly selected to hold a numeric value with the specified
probability. The remainder of the cells are made inadmissible
by placing the string "***" in them. The add-in assures
that at least one feasible tour exists.
Since the tour must start at index 1, all cells allowing a
transition from a site other than the last site are disallowed.
Similarly all cells representing a transition from the last
site to other sites, except the first, are disallowed. Also
the cell from 1 to 8 is disallowed. The cell from 8 to 1 completes
every feasible tour.
Refer to the figure below for the remainder of the discussion
about the example. Distances are translated into costs by cost/distance
factors (row 26), and into time by time/distance factors
(row 27). The vehicle must spend time at each site, perhaps
for loading and unloading, called the site time (row
28). There is also an available time for each site
that is the earliest time a site can accept the arriving vehicle.
The objective in this problem is to minimize the cost associated
with the route. The duration time penalty multiplies
the departure time from each site to determine the cost of the
tour. Early and late costs may also be included as described
later.
The sequence of sites visited by the vehicle is called a tour.
The tour begins at the depot and ends at the depot. The initial
default tour follows the sites in numerical order as in row
10. The decision variables for the problem specify the next
site to visit in row 9 and the tour is computed from these decisions.
Row 12 shows the travel distance from a site to the next site
in the tour. |