5
\$\begingroup\$

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());
\$\endgroup\$
2
  • \$\begingroup\$ 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()) \$\endgroup\$
    – greybeard
    Dec 15, 2017 at 7:33
  • \$\begingroup\$ On SO \$\endgroup\$
    – greybeard
    Dec 15, 2017 at 7:59

1 Answer 1

1
\$\begingroup\$

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()
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.