# Optimize travel sales person algorithm

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());  • 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()) Dec 15, 2017 at 7:33 • On SO Dec 15, 2017 at 7:59 ## 1 Answer ## 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()