Self-driving car

John Toczekpuzzlor@gmail.com

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: How far must the car travel to get everyone where they want to be?

Figure 1 shows 10 people in need of transportation. Their current location (the pick-up point) is indicated by the person icon and their desired destination (the drop-off location) is indicated by the building icon. The purple arrow indicates the path from the pickup location to the drop-off 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 drop-off point is 3.162 km.


What is the minimum distance the car must travel in order to transport all of the passengers from their pick-up points to their drop-off points?
Send your answer to puzzlor@gmail.com by Aug. 15. The winner, chosen randomly from correct answers, will receive a Magic 8 Ball. Past questions can be found at puzzlor.com.

John Toczek is the director of Decision Support and Analytics for ARAMARK Corporation in the Global Risk Management group. He earned his bachelor’s of science degree in chemical engineering at Drexel University (1996) and his master’s degree in operations research from Virginia Commonwealth University (2005).