A Python-based solution submitted to CodeEval's Commuting Engineer Challenge.
Submission notes have been pulled from file and are provided below:
Solution to Commuting Engineer Challenge(Traveling Salesman Problem) is based on the hill climbing principle for finding the best solution through stochastic optimization based on random initializations and solution sets/move operators(Sources 1 and 2).
Source code was merged to a single file and modified to satisfy the conditions/constraints of the challenge.
Further changes were inspired to be made to the construction of the distance matrix for objective scoring to utilize Google Maps API for actual distance/duration calculations based on street conditions instead of cartesian coordinates. distance_matrix method was optimized to fully take advantage of Google's Distance Matrix API(Source 4).
Simulated Annealing was considered but discarded due to expected small sample size of 10 locations and lack of sufficient improvements from the publication(Source 3).
Note: Final submission was adjusted to utilize default cartesian distance matrix due to urllib2:urlopen errors with code submissions.
Sources: 1. Tackling the Travelling Salesman Problem Part One 2. Hill Climbing 3. Simulated Annealing 4. https://github.com/mabounassif/traveling_salesman
Socring of final submission was 100/100 thus passing all test cases for the challenge.
The Google distance calculations proved to be unnecessary for the challenge but are left intact for those that are curious. Included is a json response from the Google Distance Matrix API containing all 10 locations provided in the challenge description. For more information see Google Distance Matrix.
Python 2.7.2 was used to execute the code:
$ python cec-tsp.py [FILENAME]