Introductory Problem and Solution for Chapter 1

of

The Keys to Linear Algebra

 

The Routing Problem of Best Paper Products

Best Paper Products supplies local-area businesses with a variety of paper products. Each day, a truck leaves the warehouse to make deliveries to a number of customers. The order in which the deliveries are made is determined manually by plotting the locations of the day's customers on a map and then rotating a horizontal line drawn through the warehouse in the counterclockwise direction 360 degrees, picking up each customer in turn. You have been asked to automate this procedure on their computer system.

NOTE: The following solution to the Routing Problem of Best Paper Products appears in the last numbered section of Chapter 1 and is designed to bring together the material the students have learned in the chapter.

Solving the Problem

The first step in solving this, and virtually all mathematical problems, is to identify the given data and the desired output. Here, the data are the known locations of the customers. The desired output is the order in which to visit those customers. From the description, you know how to solve this problem visually by plotting the customer locations on the map and rotating a horizontal line counterclockwise through the customers. The goal is to translate this visual solution to a numerical method in algebraic form---using vectors and their operations---so that the solution can be obtained using the company's computer system. The specific implementation of the steps described in what follows depends on whether the company uses a graphing calculator, a software package, such as MATLAB, Maple, and Mathematica, or a programming language, such as C++.

Solving this problem involves representing the data as vectors, performing operations on those vectors to obtain the solution, and displaying the results in an easy-to-understand manner.

Representing the Data. The first issue is how to represent the data corresponding to the locations of the customers on the day's delivery route. One approach is to use two numbers for each location. The first number represents the East-West distance in miles from the warehouse to the customer, in which a positive value means that the customer is to the East of the warehouse and a negative value means that the customer is to the West. The second number represents the North-South distance in miles, with a positive value meaning that the customer is to the North of the warehouse and a negative value to the South. For example, the following data represent the locations of six customers on today's delivery schedule:

Customer Number 1 2 3 4 5 6
East-West distance 1.2 -2.2 4.1 -3.5 4.0 -1.0
North-South distance -2.8 -2.5 3.0 1.4 -1.0 2.5

These six locations are plotted in Figure 1.25, with the warehouse located at the origin. As described in Section 1.1.3, you can represent these six locations by the six vectors (1.2, -2.8), (-2.2, -2.5), (4.1, 3.0), (-3.5, 1.4), (4.0, -1.0), and (-1.0, 2.5). An alternative---the one used from here on---is to represent these data by two vectors: one for the six East-West distances and one for the six North-Southdistances, as follows:

x = (1.2, -2.2, 4.1, -3.5, 4.0, -1.0) (1.40)

y = (-2.8, -2.5, 3.0, 1.4, -1.0, 2.5) (1.41)

Obtaining and Displaying the Solution. As indicated in the problem description, the order in which the customers are visited is determined by rotating the x-axis counterclockwise through 360 degrees. Doing so in Figure 1.25 leads to the order indicated by the following customer numbers: 3, 6, 4, 2, 1, 5. It is now necessary to translate this visual solution to symbolic form in terms of operations on the vectors x in (1.40) and y in (1.41). Doing so involves the following steps.

A Numerical-method Solution for Best Paper Products

Step 1. Use the vectors x and y to compute, for each customer, an angle between 0 and 360 degrees associated with rotating the x-axis in the counterclockwise direction until that axis reaches the location of that customer. In this example, that list of angles in degrees is:

Customer 1 2 3 4 5 6
Angle 293.20 228.65 36.19 158.20 345.96 111.80

Step 2. Sort the list of angles obtained in Step 1 in increasing order and record the sequence of the customer numbers that produces this ordering. In this example, you obtain the following:

Customer 1 2 3 4 5 6
Angle 36.19 111.80 158.20 228.65 293.20 345.96

Step 3. Draw a graph indicating the routing from the warehouse through all of the customers in the order obtained in Step 2. For this example, that graph is shown in Figure 1.25.

Implementing the Solution Using Technology

Now it is necessary to express these steps in terms of the given vectors x and y using vector operations. A general discussion of how to do so follows but the specific method depends on whether you are using a graphing calculator, a software package, or a programming language.

Finding the Angles. To perform Step 1 of the solution procedure, it is necessary to use the vectors x and y to determine the angles from the x-axis to the locations of the customers. Graphing calculators, computer software packages, and programming languages all provide built-in functions such as arccos, arcsin, and arctan for doing so. Care is needed when using these functions to ensure that the angle obtained represents a rotation in the counterclockwise direction.

To illustrate, suppose that the function atan2 in MATLAB is used. This function returns the arctangent, in radians between -p and p, of a point located in a quadrant of the plane. (This may not be the case for arctan functions in graphing calculators and programming languages.) In this numerical example, atan2(y, x) applied to the vectors y in (1.41) and x in (1.40) yields the following vector of angles (rounded to two decimal places):

a = (-1.17, -2.29, 0.63, 2.76, -0.24, 1.95)

For ease of understanding, you can convert these angles from radians to degrees by multiplying a by 180 / p:

b = (180 / p) a = (-67.04, -131.21, 36.10, 158.14, -13.75, 111.73)

It is now necessary to make all of these angles positive so that they reflect rotation of the x-axis in the counterclockwise direction. This is accomplished by adding 360 degrees to those angles in b whose values are negative. To do so using vector operations, first create a vector c whose components are 0, if the corresponding angle is positive and 360, if the corresponding angle is negative. In this case, the vector c is:

c = (360, 360, 0, 0, 360, 0)

The result of adding c to b is the following list of angles, in degrees, as measured from the x-axis in the counterclockwise direction:

d = b + c = (292.96, 228.79, 36.10,158.14, 346.25, 111.73)

Sorting the Angles. Now you can sort these angles in increasing order to obtain

e = (36.10, 111.73, 158.14, 228.79, 292.96, 346.25)

However, what you need is the order of the customers that leads to the vector e. That is, you need a permutation vector of {1, 2, 3, 4, 5, 6}, as described in Section 1.1.3. In this case, that permutation vector is

p = (3, 6, 4, 2, 1, 5)

Visiting the customers in the sequence indicated by p corresponds to the list of angles in increasing order, that is,

e = (dp1, dp2, dp3, dp4, dp5, dp6) = (d3, d6, d4, d2, d1, d5)

Displaying the Final Results. Having found the permutation vector, all that remains is to display the final sequence---as in Figure 1.25---that starts at the warehouse located at the origin and connects the locations of the customers in the order indicated by the permutation vector p.