ahmedtaha/travelling-salesman-path

There is no license information available for the latest version (dev-master) of this package.

The travelling salesman problem asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city

dev-master 2022-06-14 22:08 UTC

Requires (Dev)

• roave/security-advisories: dev-latest

Unknown License

• Ahmed Taha

README

Installation

You can install the package via Composer.

composer require ahmedtaha/travelling-salesman-path

Publish your oto config file with

php artisan vendor:publish --provider="Ahmedtaha\TravellingSalesman\TravellingSalesmanServiceProvider" --tag="tsp"

If you want to calculate distance using google places driving distance change your tsp config from config/tsp.php file or i will calculate direct distance automatically

    "google_api_key"     => "", // google places paid key

Usage

• 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.

       use Ahmedtaha\TravellingSalesman\Services\Concrete\TspBranchBound;

       $instance        = TspBranchBound::getInstance();
       
       #add starting point coordination
       $instance->addLocation([
        'id'            => 'Mansoura',
        'latitude'      => 31.0409,
        'longitude'     => 31.3785
      ]);
      
       #add array of another points coordination
      $instance->addLocation([
       [
            'id'        => 'Tanta',
            'latitude'  => 30.7865,
            'longitude' => 31.0004
        ],
        [
            'id'        => 'Ismailia',
            'latitude'  => 30.5965,
            'longitude' => 32.2715
        ],
        [
            'id'        => 'Damietta',
            'latitude'  => 31.4175,
            'longitude' => 31.8144
        ]
    ]);
    
     return $instance->solve();

Result

{
  "cost": 495.6299999999999,
  "locations": [
    {
      "latitude" : 31.0409,
      "longitude": 31.3785,
      "id"       : "Mansoura"
    },
    {
      "latitude" : 31.4175,
      "longitude": 31.8144,
      "id"       : "Damietta"
    },
    {
      "latitude" : 30.7865,
      "longitude": 31.0004,
      "id"       : "Tanta"
    },
    {
      "latitude" : 30.5965,
      "longitude": 32.2715,
      "id"       : "Ismailia"
    }
  ],
  "path": "Mansoura -> Damietta , Damietta -> Tanta , Tanta -> Ismailia , Ismailia -> Mansoura"
}

#Follow me

#References

• https://en.wikipedia.org/wiki/Travelling_salesman_problem
• https://www.srimax.com/2016/07/05/travelling-salesman-problem-using-branch-bound-approach-php/