Travelling Salesman Problem using Branch and Bound Approach in PHP

 
Travelling Salesman Problem using Branch and Bound Approach in PHP

Overview

The problem is to find the shorter route for desired locations. let’s consider some cities you’ve to visit. you should be visit all cities once with a least cost.

Solving TSPs with PHP

The sales person needs to visit some cities or places. we had to plan him routes, from house to house. the shorter route would be good. we can solve this by TSP algorithm. we could take him places as latitudes and longitudes. from this locations details, we can generates a possible ways matrix. then we can apply the TSP for this matrix to find a path. i just converted the algorithm from a CPP code. By this way, we can be found the least cost of travel or distance or time. here i used distance matrix to find shorter route.

References

<?php
class TspLocation
{
	public $latitude;
	public $longitude;
	public $id;

	public function __construct($latitude, $longitude, $id = null)
	{
		$this->latitude = $latitude;
		$this->longitude = $longitude;
		$this->id = $id;
	}

	public static function getInstance($location)
	{
		$location = (array) $location;
		if (empty($location['latitude']) || empty($location['longitude']))
		{
			throw new RuntimeException('TspLocation::getInstance could not load location');
		}

		// Instantiate the TspLocation.
		$id = isset($location['id']) ? $location['id'] : null;
		$tspLocation = new TspLocation($location['latitude'], $location['longitude'], $id);

		return $tspLocation;
	}

	public static function distance($lat1, $lon1, $lat2, $lon2, $unit = 'M')
	{
		if ($lat1 == $lat2 && $lon1 == $lon2) return 0;

		$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;
	}
}

class TspNode
{

	public $path = array();
	public $reducedMatrix = array();
	public $cost;
	public $vertex;
	public $level;

	/**
	 * Constructor
	 *
	 * @param   array    $parentMatrix   The parentMatrix of the costMatrix.
	 * @param   array    $path           An array of integers for the path.
	 * @param   integer  $level          The level of the node.
	 * @param   integer  $i, $j          They are corresponds to visiting city j from city i
	 *
	 */
	public function __construct($parentMatrix, $path, $level, $i, $j)
	{
		// stores ancestors edges of state space tree
		$this->path = $path;

		// skip for root node
		if ($level != 0)
			// add current edge to path
			$this->path[] = array($i, $j);

		// copy data from parent node to current node
		$this->reducedMatrix = $parentMatrix;

		// Change all entries of row i and column j to infinity
		// skip for root node
		for ($k = 0; $level != 0 && $k < count($parentMatrix); $k++)
		{
			// set outgoing edges for city i to infinity
			$this->reducedMatrix[$i][$k] = INF;
			// set incoming edges to city j to infinity
			$this->reducedMatrix[$k][$j] = INF;
		}

		// Set (j, 0) to infinity 
		// here start node is 0
		$this->reducedMatrix[$j][0] = INF;

		$this->level = $level;
		$this->vertex = $j;
	}
}

class PqTsp extends SplPriorityQueue
{
	public function compare($lhs, $rhs) {
		if ($lhs === $rhs) return 0;
		return ($lhs < $rhs) ? 1 : -1;
	}
}

class TspBranchBound
{
	protected $n = 0;
	protected $locations = array();
	protected $costMatrix = array();

	/**
	 * @var    array  TspBranchBound instances container.
	 */
	protected static $instances = array();

	/**
	 * Constructor
	 */
	public function __construct($costMatrix = array())
	{
		if ($costMatrix) {
			$this->costMatrix = $costMatrix;
			$this->n = count($this->costMatrix);
		}
	}

	/**
	 * Method to get an instance of a TspBranchBound.
	 *
	 * @param   string  $name     The name of the TspBranchBound.
	 * @param   array   $locations  An array of locations.
	 *
	 * @return  object  TspBranchBound instance.
	 *
	 * @throws  Exception if an error occurs.
	 */
	public static function getInstance($name = 'TspBranchBound', $locations = null)
	{
		// Reference to array with instances
		$instances = &self::$instances;

		// Only instantiate if it does not already exist.
		if (!isset($instances[$name]))
		{
			// Instantiate the TspBranchBound.
			$instances[$name] = new TspBranchBound();
		}

		$instances[$name]->locations = array();
		$instances[$name]->costMatrix = array();

		// Load the data.
		if ($locations)
		{
			if ($instances[$name]->load($locations) == false)
			{
				throw new RuntimeException('TspBranchBound::getInstance could not load locations');
			}
		}

		return $instances[$name];
	}

	public function load($locations)
	{
		if (empty($locations))
			return false;

		foreach ($locations as $location)
		{
			if (empty($location))
				return false;

			if ($this->addLocation($location) == false)
				return false;
		}

		return $this->loadMatrix();
	}

	public function loadMatrix()
	{
		if (empty($this->locations))
			return false;

		$this->costMatrix = array();
		$n_locations = count($this->locations);
		for ($i = 0; $i < $n_locations; $i++)
		{
			echo $i+1 . ". " . $this->locations[$i]->id . "\n";
			for ($j = 0; $j < $n_locations; $j++)
			{
				$distance = INF;
				if ($i!=$j)
				{
					$loc1 = $this->locations[$i];
					$loc2 = $this->locations[$j];
					$distance = TspLocation::distance($loc1->latitude, $loc1->longitude, $loc2->latitude, $loc2->longitude);
				}
				$this->costMatrix[$i][$j] = $distance;
			}
		}

		$this->n = count($this->costMatrix);

		return true;
	}

	public function addLocation($location)
	{
		try
		{
			$location = TspLocation::getInstance($location);
		}
		catch (Exception $e)
		{
			return false;
		}

		$this->locations[] = $location;

		return true;
	}

	protected function rowReduction(&$reducedMatrix, &$row)
	{
		// initialize row array to INF 
		$row = array_fill(0, $this->n, INF);

		// row[i] contains minimum in row i
		for ($i = 0; $i < $this->n; $i++)
			for ($j = 0; $j < $this->n; $j++)
				if ($reducedMatrix[$i][$j] < $row[$i])
					$row[$i] = $reducedMatrix[$i][$j];

		// reduce the minimum value from each element in each row.
		for ($i = 0; $i < $this->n; $i++)
			for ($j = 0; $j < $this->n; $j++)
				if ($reducedMatrix[$i][$j] !== INF && $row[$i] !== INF)
					$reducedMatrix[$i][$j] -= $row[$i];
	}

	protected function columnReduction(&$reducedMatrix, &$col)
	{
		// initialize row array to INF 
		$col = array_fill(0, $this->n, INF);

		// col[i] contains minimum in row i
		for ($i = 0; $i < $this->n; $i++)
			for ($j = 0; $j < $this->n; $j++)
				if ($reducedMatrix[$i][$j] < $col[$j])
					$col[$j] = $reducedMatrix[$i][$j];

		// reduce the minimum value from each element in each row.
		for ($i = 0; $i < $this->n; $i++)
			for ($j = 0; $j < $this->n; $j++)
				if ($reducedMatrix[$i][$j] !== INF && $col[$j] !== INF)
					$reducedMatrix[$i][$j] -= $col[$j];
	}

	protected function calculateCost(&$reducedMatrix)
	{
		// initialize cost to 0
		$cost = 0;

		// Row Reduction
		$row = array();
		$this->rowReduction($reducedMatrix, $row);

		// Column Reduction
		$col = array();
		$this->columnReduction($reducedMatrix, $col);

		// the total expected cost 
		// is the sum of all reductions
		for ($i = 0; $i < $this->n; $i++) {
			$cost += ($row[$i] !== INF) ? $row[$i] : 0;
			$cost += ($col[$i] !== INF) ? $col[$i] : 0;
		}

		return $cost;
	}

	public function printPath($list)
	{
		echo "\nPath: \n";
		for ($i = 0; $i < count($list); $i++) {
			$start = $list[$i][0] + 1;
			$end = $list[$i][1] + 1;
			echo $start . " -> " . $end . "\n";
		}
	}

	public function solve()
	{
		if (empty($this->costMatrix))
		{
			if (!$this->loadMatrix())
				return false;
		}

		$costMatrix = $this->costMatrix;
		// Create a priority queue to store live nodes of
		// search tree;
		$pq = new PqTsp();

		// create a root node and calculate its cost
		// The TSP starts from first city i.e. node 0
		$root = new TspNode($costMatrix, null, 0, -1, 0);
		// get the lower bound of the path starting at node 0
		$root->cost = $this->calculateCost($root->reducedMatrix);

		// Add root to list of live nodes;
		$pq->insert($root, $root->cost);

		// Finds a live node with least cost,
		// add its children to list of live nodes and
		// finally deletes it from the list.
		while($pq->valid())
		{
			// Find a live node with least estimated cost
			$min = $pq->extract();

			// Clear the max estimated nodes
			$pq = new PqTsp();

			// i stores current city number
			$i = $min->vertex;

			// if all cities are visited
			if ($min->level == $this->n - 1)
			{
				// return to starting city
				$min->path[] = array($i, 0);
				// print list of cities visited;
				$this->printPath($min->path);

				// return optimal cost & etc.
				return array ('cost' => $min->cost, 'path' => $min->path, 'locations' => $this->locations);
			}

			// do for each child of min
			// (i, j) forms an edge in space tree
			for ($j = 0; $j < $this->n; $j++)
			{
				if ($min->reducedMatrix[$i][$j] !== INF)
				{
					// create a child node and calculate its cost
					$child = new TspNode($min->reducedMatrix, $min->path, $min->level+1, $i, $j);

					/* Cost of the child = 
						cost of parent node + 
						cost of the edge(i, j) +
						lower bound of the path starting at node j
					*/
					$child->cost = $min->cost + $min->reducedMatrix[$i][$j] + $this->calculateCost($child->reducedMatrix);

					// Add child to list of live nodes
					$pq->insert($child, $child->cost);
				}
			}

			// free node as we have already stored edges (i, j) in vector
			// So no need for parent node while printing solution.
			$min = null;
		}
	}
}
?>

Example

<?php
try
{
	$tsp = TspBranchBound::getInstance();
	$tsp->addLocation(array('id'=>'newquay', 'latitude'=>50.413608, 'longitude'=>-5.083364));
	$tsp->addLocation(array('id'=>'manchester', 'latitude'=>53.480712, 'longitude'=>-2.234377));
	$tsp->addLocation(array('id'=>'london', 'latitude'=>51.500152, 'longitude'=>-0.126236));
	$tsp->addLocation(array('id'=>'birmingham', 'latitude'=>52.483003, 'longitude'=>-1.893561));
	$ans = $tsp->solve();
	echo "\nTotal cost: " . ceil($ans['cost']) . "\n\n";
}
catch (Exception $e)
{
	echo $e;
	exit;
}
?>

Result

1. newquay
2. manchester
3. london
4. birmingham

Path: 
1 -> 3
3 -> 4
4 -> 2
2 -> 1

Total cost: 645