CSCI 385 - Lab 9
Optimization
Oil Spill
An oil spill has fouled 200 miles of Pacific shoreline. The oil company responsible has
been given 14 days to clean up the shoreline, after which a fine will be levied in the
amount of $10,000/day. The local cleanup crew can scrub five miles of beach per week at
a cost of $500/day. Additional crews can be brought in at a cost of $18,000 plus $800/day
for each crew.
How many additional crews should be brought in to minimize cost? What is total cost?
How long will the cleanup take?
TSP Extensions
- Create a Tour with 80 random points.
- Draw a plot of the cost of a tour over time using gradient descent.
- Draw a plot of the cost of a tour over time using simulated annealing.
- Draw a scatter plot of the probability of accepting a bad move over time using simulated annealing.
- Extend the Tour object to include an "interchange" function. Similar to swap,
it will bring in an ith and jth city, and reverse the order of all cities
in between them, including the ith and jth city.
- Rerun your simulated annealing algorithm and gradient descent algorithm above, using
the interchange neighborhood function. How do the results compare?
Interstellar Journey
You are planning a journey for a robotic probe to survey all of the
closest stars.
Your probe will start at Earth, visit each star once, and return home.
Convert the distance, right ascension and declination for each
star to cartesian coordinates, and plan
out a close-to-optimal journey using the techniques we have learned in class.
Assume the probe can travel at half the speed of light.
State any other assumptions you need to make to solve this problem. Draw a
3D plot of your resulting journey, and show how long this journey will take.