MGMTMSA 408 – Operations Analytics
Homework 4 – Traveling Salesman Problem (Question Sheet)
Due May 30, 2025 (Sections 1 & 2) at 11:59pm PST
1 Cargo freight scheduling
A freight company operating out of Los Angeles, CA needs to make a number of deliveries by air
to a set of cities in the continental United States. Each city corresponds to one delivery.
The company has a single DC-10-30 aircraft available to make these deliveries, and needs to
decide in what order to make deliveries (i.e., in what order to visit these cities) so as to minimize
the time traveled. The aircraft departs from Los Angeles, and must return to Los Angeles after
visiting all of the remaining 67 cities. Each city must be visited exactly once.
You are provided a data set ([Link]) consisting of the locations of the
cities by their latitude and longitude coordinates. There are 68 cities, including Los Angeles.
Part 1: Building our data
In order to solve the problem, we will need to calculate the flight time between each pair of cities
in the data set. We will do this by applying a little bit of geometry.
For each pair of cities i and j, first convert the latitudes lati and longitudes loni , which are
given in degrees, to radians:
latr,i = lati /360 × 2π,
lonr,i = loni /360 × 2π,
latr,j = latj /360 × 2π,
lonr,j = lonj /360 × 2π.
Then, we will use the haversine formula to calculate the angle corresponding to the great circle
distance (see Figure 1 below) between cities i and j. The haversine Hi,j of cities i and j can be
calculated as
1 − cos(latr,j − latr,i ) 1 − cos(lonr,j − lonr,i )
Hi,j = + cos(latr,i ) × cos(latr,j ) × (1)
2 2
We can now calculate the distance, di,j as
di,j = 2r sin−1 ( Hi,j )
p
(2)
where r is the radius of the earth, which we can assume to be 6378.137 km.
Lastly, you can use the fact that the average cruise speed of a DC-10 aircraft is 908 km / hour
to convert these distances into travel times. This will yield us an approximate travel time between
each pair of cities.
1
Figure 1: Visualization of great circles (grey and red circles on the left) and
the great circle distance between New York City and New Delhi (right). (Source:
[Link]
To help you with these calculations you can use the numpy functions cos, sin, arcsin (the
arcsine function, which is just the inverse sine function sin−1 (·)) and sqrt (the square root).
To verify that you have implemented your distance calculations correctly, you should find that
the travel time from Des Moines, IA to Baton Rouge, LA is 1.3857 hours, corresponding to a
distance of 1258.226 kilometers.
a) Which two cities have the highest travel travel time?
b) Which two cities have the smallest travel time?
c) Which city has the smallest average travel time to all of the other cities? (Here, the average is
taken over the other 67 cities.)
Part 2: Finding a schedule
a) Suppose that we randomly selected a sequence of cities. In numpy, you can construct a random
sequence by using the commands
import numpy as np
nCities = 68
temp = [Link](nCities)
which will generate a list with the integers from 0 to 67 in random order. You can then calculate
the travel time by iterating through the list and looking up the travel time of consecutive cities
in the list, and adding them up. At the end, you would finally add the travel time corresponding
to traveling from city temp[67] to city temp[0].
Set your seed to 50. Randomly generate 100 sequences of the 68 cities, and calculate the total
travel time required to visit the cities according to each sequence. What is the average of the
total travel times of these 100 randomly generated sequences, in hours?
Page 2
b) Suppose that we design the sequence of cities using the following heuristic. Starting from Los
Angeles, the next city in the schedule is the one that is closest to the current city in travel time
and has not been visited yet. What is the total travel time of this sequence, in hours?
c) Solve an optimization problem to find the order in which the cities should be visited, so as to
minimize the total travel time. What is the total travel time of this sequence, in hours?
Page 3