Optimize travel sales person algorithm

Question

I'm trying to find a way to optimize travel sales person algorithm. It's pretty simple but takes a lot of time to calculate best possible route. What do you think?

class TSP {
 private $locations = []; // all locations to visit
 private $longitudes = [];
 private $latitudes = [];
 private $shortest_route = []; // holds the shortest route
 private $shortest_routes = []; // any matching shortest routes
 private $shortest_distance = 0; // holds the shortest distance
 private $all_routes = []; // array of all the possible combinations and there distances
 //LAT LON Location - added method for parameter order
 public function _add($latitude,$longitude,$name){
 $this->locations[$name] = array('longitude'=>$longitude,'latitude'=>$latitude);
 }
 // the main function that des the calculations
 public function compute(){
 $locations = $this->locations;
 foreach ($locations as $location=>$coords){
 $this->longitudes[$location] = $coords['longitude'];
 $this->latitudes[$location] = $coords['latitude'];
 }
 $locations = array_keys($locations);
 $this->all_routes = $this->array_permutations($locations);
 $cache = array();
 foreach ($this->all_routes as $key=>$perms){
 $i=0;
 $total = 0;
 $n = count($this->locations)-1;
 foreach ($perms as $value){
 if ($i<$n){
 $source = $perms[$i];
 $dest = $perms[$i+1];
 if(isset($cache[$source][$dest])){
 $dist = $cache[$source][$dest];
 } elseif (isset($cache[$dest][$source])) {
 $dist = $cache[$dest][$source];
 } else {
 $dist = $this->distance($this->latitudes[$source],$this->longitudes[$source],$this->latitudes[$dest],$this->longitudes[$dest]);
 $cache[$source][$dest] = $dist;
 }
 $total+=$dist;
 }
 $i++;
 }
 $this->all_routes[$key]['distance'] = $total;
 if ($total<$this->shortest_distance || $this->shortest_distance ==0){
 $this->shortest_distance = $total;
 $this->shortest_route = $perms;
 $this->shortest_routes = array();
 }
 if ($total == $this->shortest_distance){
 $this->shortest_routes[] = $perms;
 }
 }
 }
 // work out the distance between 2 longitude and latitude pairs
 function distance($lat1, $lon1, $lat2, $lon2) {
 if ($lat1 == $lat2 && $lon1 == $lon2) return 0;
 $theta = $lon1 - $lon2;
 $r_l1 = deg2rad($lat1);
 $r_l2 = deg2rad($lat2);
 $dist = sin($r_l1) * sin($r_l2) + cos($r_l1) * cos($r_l2) * cos(deg2rad($theta));
 $dist = acos($dist);
 $dist = rad2deg($dist);
 $miles = $dist * 69.09;
 return $miles;
 }
 // work out all the possible different permutations of an array of data
 private function array_permutations($items, $perms = array()){
 static $all_permutations;
 if (empty($items)) {
 $all_permutations[] = $perms;
 } else {
 for ($i = count($items) - 1; $i >= 0; --$i) {
 $newitems = $items;
 $newperms = $perms;
 list($foo) = array_splice($newitems, $i, 1);
 array_unshift($newperms, $foo);
 $this->array_permutations($newitems, $newperms);
 }
 }
 return $all_permutations;
 }
 // return an array of the shortest possible route
 public function shortest_route(){
 return $this->shortest_route;
 }
 // returns an array of any routes that are exactly the same distance as the shortest (ie the shortest backwards normally)
 public function matching_shortest_routes(){
 return $this->shortest_routes;
 }
 // the shortest possible distance to travel
 public function shortest_distance(){
 return $this->shortest_distance;
 }
 // returns an array of all the possible routes
 public function routes(){
 return $this->all_routes;
 }
}

Example:

$tsp = new TSP;
$tsp->_add(32.7308117, -117.1492819, 'Museum1');
$tsp->_add(32.7352917, -117.1491861, 'Zoo');
$tsp->_add(32.72098, -117.1739938, 'Maritime Museum');
$tsp->_add(32.7631797, -117.2276874, 'Seaworld');
$tsp->_add(32.8645458, -117.2517528, 'Birch');
$tsp->_add(32.7700125, -117.2532622, 'Belmont');
$tsp->_add(32.5876277, -117.0112877, 'Aquatica');
$tsp->_add(32.6894411, -117.1829472, 'Coronado');
$tsp->_add(32.7803722, -117.0442201, 'Lake Murray');
 
$tsp->compute();
echo "<pre>";
echo 'Shortest Distance: '.$tsp->shortest_distance();
echo '<br />Shortest Route: ';
print_r($tsp->shortest_route());
echo '<br />Num Routes: '.count($tsp->routes());

• greybeard: I seem to remember the problem: are you seeking to substantially speed up an exact solution? (While your comments aren't half bad, there's a typo in the non-comment to compute())
• greybeard: On SO

Answer 1

Algorithm

One optimization in terms of space complexity would be to store the names in a separate array and use a simpler data type for the permutations (e.g. integer - could be indexes of the array).

I also see this block within the compute method:

 $i=0;
 $total = 0;
 $n = count($this->locations)-1;
 foreach ($perms as $value){
 if ($i<$n){
 ....
 }
 $i++;
 }

It likely isn't a major point of optimization but $perms has numeric indexes so those can be used instead of manually initializing and incrementing $i:

 $total = 0;
 $n = count($this->locations)-1;
 foreach ($perms as $i => $value){
 if ($i < $n){
 ....
 }
 }

Beyond that it might be helpful to store the distances in a 2-D array, potentially calculating the distances whenever a point is added to the list.

Other Review Points

• Standards Recommendations: It is recommended to follow PSRs like PSR-12 - it has many recommendations for common conventions for readability - e.g. spaces after commas within argument lists
• strict equality it is a good habit to use strict comparison operators - i.e. === and !== when possible - e.g. $this->shortest_distance ==0
• short array syntax - is used in some places - e.g. initializing member variables, but it can be used instead of array()