README

安装

您可以通过Composer安装此包。

composer require ahmedtaha/travelling-salesman-path

使用以下命令发布您的oto配置文件

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

如果您想使用谷歌地点的驾车距离来计算距离，请将tsp配置从config/tsp.php文件更改，或者我将自动计算直接距离

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

用法

• 问题是找到所需位置的最短路线。让我们考虑一些您必须访问的城市。您应该以最低成本访问所有城市一次。

       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();

结果

{
  "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"
}

#关注我

#参考

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