Strict Standards: Non-static method Router::init() should not be called statically in /home/scrivna/public_html/app/webroot/index.php on line 48

Strict Standards: Non-static method Router::getInstance() should not be called statically in /home/scrivna/public_html/arpy-core/libs/router.php on line 16

Strict Standards: Non-static method Router::controller() should not be called statically in /home/scrivna/public_html/app/webroot/index.php on line 55

Strict Standards: Non-static method Router::getInstance() should not be called statically in /home/scrivna/public_html/arpy-core/libs/router.php on line 49

Strict Standards: Non-static method CCache::controller() should not be called statically in /home/scrivna/public_html/app/webroot/index.php on line 55

Strict Standards: Non-static method Router::action() should not be called statically in /home/scrivna/public_html/app/webroot/index.php on line 67

Strict Standards: Non-static method Router::getInstance() should not be called statically in /home/scrivna/public_html/arpy-core/libs/router.php on line 54

Strict Standards: Non-static method Router::part() should not be called statically, assuming $this from incompatible context in /home/scrivna/public_html/app/controllers/blog_controller.php on line 46

Strict Standards: Non-static method Router::getInstance() should not be called statically, assuming $this from incompatible context in /home/scrivna/public_html/arpy-core/libs/router.php on line 60

Deprecated: mysql_escape_string(): This function is deprecated; use mysql_real_escape_string() instead. in /home/scrivna/public_html/app/controllers/blog_controller.php on line 46

Strict Standards: Non-static method CCache::model() should not be called statically, assuming $this from incompatible context in /home/scrivna/public_html/app/controllers/blog_controller.php on line 48

Strict Standards: Non-static method CCache::plugin() should not be called statically, assuming $this from incompatible context in /home/scrivna/public_html/app/models/app_model.php on line 15

Strict Standards: Non-static method Config::get() should not be called statically, assuming $this from incompatible context in /home/scrivna/public_html/app/models/app_model.php on line 19

Strict Standards: Non-static method Config::get() should not be called statically, assuming $this from incompatible context in /home/scrivna/public_html/app/models/app_model.php on line 19

Strict Standards: Non-static method Config::get() should not be called statically, assuming $this from incompatible context in /home/scrivna/public_html/app/models/app_model.php on line 19

Strict Standards: Non-static method Config::get() should not be called statically, assuming $this from incompatible context in /home/scrivna/public_html/app/models/app_model.php on line 19

Deprecated: mysql_connect(): The mysql extension is deprecated and will be removed in the future: use mysqli or PDO instead in /home/scrivna/public_html/arpy-core/libs/mysql_database.php on line 16

Strict Standards: Non-static method Config::get() should not be called statically, assuming $this from incompatible context in /home/scrivna/public_html/app/controllers/blog_controller.php on line 58
Travelling Salesman Problem · Ross Scrivener

Travelling Salesman Problem

published on March 15th, 2008 · more from the blog →

So, as you may or may not know, I've been trying to calculate the shortest distance to travel between a number of points (aka The Travelling Salesman Problem) While i completely failed at doing this is Java i have created a way to do it in PHP. So without further hesitation here is the class and a quick usage example.

/* PHP Class TSP


Author: 	Ross Scrivener
WWW: 		http://scrivna.com
Description:
	This class is a calculator for the common "Travelling salesman" maths problem.


	It takes any number of coordinates and brute force calculates the shortest distance to travel to all those points.
	It doesn't do anything clever like forcing a starting / ending point, however this could easily be implemented.


Date: 		2008-03-15


Feel free to modify this script and use as you please, a little note saying original author would 
be nice and if you do use it, drop me a line, i'd like to see what you've done with it.


Please mail me any bug fixes etc. so i can update this script for others


*/


class TSP {


	private $locations 	= array();		// all locations to visit
	private $longitudes = array();
	private $latitudes 	= array();
	private $shortest_route = array();	// holds the shortest route
	private $shortest_routes = array();	// any matching shortest routes
	private $shortest_distance = 0;		// holds the shortest distance
	private $all_routes = array();		// array of all the possible combinations and there distances


	// add a location
	public function add($name,$longitude,$latitude){
		$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);


		foreach ($this->all_routes as $key=>$perms){
			$i=0;
			$total = 0;
			foreach ($perms as $value){
				if ($i<count($this->locations)-1){
					$total+=$this->distance($this->latitudes[$perms[$i]],$this->longitudes[$perms[$i]],$this->latitudes[$perms[$i+1]],$this->longitudes[$perms[$i+1]]);
				}
				$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;
		$unit = 'M';	// miles please!
		$theta = $lon1 - $lon2; 
		$dist = sin(deg2rad($lat1)) * sin(deg2rad($lat2)) +  cos(deg2rad($lat1)) * cos(deg2rad($lat2)) * cos(deg2rad($theta)); 
		$dist = acos($dist); 
		$dist = rad2deg($dist); 
		$miles = $dist * 60 * 1.1515;
		$unit = strtoupper($unit);


		if ($unit == "K") {
			return ($miles * 1.609344); 
		} else if ($unit == "N") {
			return ($miles * 0.8684);
		} else {
			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;
	}
}

Usage Example:

$tsp = new TSP;
$tsp->add('newquay',50.413608,-5.083364);
$tsp->add('london',51.500152,-0.126236);
$tsp->add('birmingham',52.483003,-1.893561);
$tsp->add('manchester',53.480712,-2.234377);
$tsp->compute();

echo 'Shortest Distance: '.$tsp->shortest_distance();
echo '<br />Shortest Route: ';
print_r($tsp->shortest_route());
echo '<br />Num Routes: '.count($tsp->routes());
echo '<br />Matching shortest Routes: ';
print_r($tsp->matching_shortest_routes());
echo '<br />All Routes: ';
print_r($tsp->routes());


It should work in PHP 4 & 5, (not that i've tested it on 4). My apologies if Wordpress has spacked the content up.

Feel free to use / abuse it as you wish.

TTFN


Strict Standards: Non-static method Config::get() should not be called statically, assuming $this from incompatible context in /home/scrivna/public_html/app/views/templates/default.php on line 61