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 '17 at 7:33
  • \$\begingroup\$ On SO \$\endgroup\$
    – greybeard
    Dec 15 '17 at 7:59
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\$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .