Decision Support Puzzles for Applied Mathematicians
June 2013 - Self Driving Cars
Self-driving cars are cars that can drive themselves without a human behind the wheel. This technology should be available in the not-too-distant future. New algorithms will need to be developed to help route these cars to get their passengers to their desired destinations efficiently.
Figure 1 shows 10 people in need of transportation. Their current location (the pickup point) is indicated by the person icon and their desired destination (the dropoff location) is indicated by the building icon. The purple arrow indicates the path from the pickup location to the dropoff location. Your job is to order the passengers so that they are picked up in an order that minimizes the total distance travelled by the self-driving car.
The car can start at any pickup point. You may only carry one person at a time. The car does not need to return to its starting point after the last person is dropped off. There is only one self-driving car available for use. Use Pythagorean theorem to calculate the distance between cells. For example, the distance between the person nearest the lower left corner and her dropoff point is 3.162 km.
Question: What is the minimum distance the car must travel in order to transport all of the passengers from their pickup points to their dropoff points?
Send your answer to firstname.lastname@example.org by August 15th, 2013. The winner, chosen randomly from correct answers, will receive a Magic 8 Ball. Past questions can be found at puzzlor.com.