Concorde
iOS App Help:
Example 2: explicit distances给出了一个矩阵输入的例子
.tsp
The TSPLIB format is used in a library of TSP instances maintained at
the University of Heidelberg. Concorde interpretes only those TSPLIB
files that define sets of nodes in two dimensional space.
Obtaining file:///D:/mine/Github/pyconcorde Installing build dependencies ... done WARNING: Missing build requirements in pyproject.toml for file:///D:/mine/Github/pyconcorde. WARNING: The project does not specify a build backend, and pip cannot fall back to setuptools without 'wheel'. Getting requirements to build wheel ... done Installing backend dependencies ... done Preparing wheel metadata ... done Requirement already satisfied: numpy>=1.10.0in d:\anaconda3\lib\site-packages (from pyconcorde==0.1.0) (1.22.2) Requirement already satisfied: cython>=0.22.0in d:\anaconda3\lib\site-packages (from pyconcorde==0.1.0) (0.29.27) Installing collected packages: pyconcorde Running setup.py develop for pyconcorde ERROR: Command errored out with exit status 1: command: 'D:\anaconda3\python.exe' -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'D:\\mine\\Github\\pyconcorde\\setup.py'"'"'; __file__='"'"'D:\\mine\\Github\\pyconcorde\\setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' develop --no-deps cwd: D:\mine\Github\pyconcorde\ Complete output (44 lines): running develop running egg_info writing pyconcorde.egg-info\PKG-INFO writing dependency_links to pyconcorde.egg-info\dependency_links.txt writing requirements to pyconcorde.egg-info\requires.txt writing top-level names to pyconcorde.egg-info\top_level.txt reading manifest file 'pyconcorde.egg-info\SOURCES.txt' reading manifest template 'MANIFEST.in' adding license file 'COPYING' running build_ext C:\Users\Carlos\AppData\Local\Temp\pip-build-env-84ozjlf8\overlay\Lib\site-packages\setuptools\command\easy_install.py:158: EasyInstallDeprecationWarning: easy_install command is deprecated. Use build and pip and other standards-based tools. warnings.warn( C:\Users\Carlos\AppData\Local\Temp\pip-build-env-84ozjlf8\overlay\Lib\site-packages\setuptools\command\install.py:34: SetuptoolsDeprecationWarning: setup.py install is deprecated. Use build and pip and other standards-based tools. warnings.warn( C:\Users\Carlos\AppData\Local\Temp\pip-build-env-84ozjlf8\overlay\Lib\site-packages\pkg_resources\__init__.py:122: PkgResourcesDeprecationWarning: 4.0.0-unsupported is an invalid version and will not be supported in a future release warnings.warn( Traceback (most recent call last): File "<string>", line 1, in <module> File "D:\mine\Github\pyconcorde\setup.py", line 143, in <module> setup( File "C:\Users\Carlos\AppData\Local\Temp\pip-build-env-84ozjlf8\overlay\Lib\site-packages\setuptools\__init__.py", line 155, in setup return distutils.core.setup(**attrs) File "C:\Users\Carlos\AppData\Local\Temp\pip-build-env-84ozjlf8\overlay\Lib\site-packages\setuptools\_distutils\core.py", line 148, in setup return run_commands(dist) File "C:\Users\Carlos\AppData\Local\Temp\pip-build-env-84ozjlf8\overlay\Lib\site-packages\setuptools\_distutils\core.py", line 163, in run_commands dist.run_commands() File "C:\Users\Carlos\AppData\Local\Temp\pip-build-env-84ozjlf8\overlay\Lib\site-packages\setuptools\_distutils\dist.py", line 967, in run_commands self.run_command(cmd) File "C:\Users\Carlos\AppData\Local\Temp\pip-build-env-84ozjlf8\overlay\Lib\site-packages\setuptools\_distutils\dist.py", line 986, in run_command cmd_obj.run() File "C:\Users\Carlos\AppData\Local\Temp\pip-build-env-84ozjlf8\overlay\Lib\site-packages\setuptools\command\develop.py", line 34, in run self.install_for_development() File "C:\Users\Carlos\AppData\Local\Temp\pip-build-env-84ozjlf8\overlay\Lib\site-packages\setuptools\command\develop.py", line 114, in install_for_development self.run_command('build_ext') File "C:\Users\Carlos\AppData\Local\Temp\pip-build-env-84ozjlf8\overlay\Lib\site-packages\setuptools\_distutils\cmd.py", line 313, in run_command self.distribution.run_command(command) File "C:\Users\Carlos\AppData\Local\Temp\pip-build-env-84ozjlf8\overlay\Lib\site-packages\setuptools\_distutils\dist.py", line 986, in run_command cmd_obj.run() File "D:\mine\Github\pyconcorde\setup.py", line 114, in run download_concorde_qsopt() File "D:\mine\Github\pyconcorde\setup.py", line 66, in download_concorde_qsopt qsopt_a_url, qsopt_h_url = QSOPT_LOCATION[platform.system()] KeyError: 'Windows' qsopt is missing, downloading ---------------------------------------- ERROR: Command errored out with exit status 1: 'D:\anaconda3\python.exe' -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'D:\\mine\\Github\\pyconcorde\\setup.py'"'"'; __file__='"'"'D:\\mine\\Github\\pyconcorde\\setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' develop --no-deps Check the logs for full command output.
git clone https://github.com/jvkersch/pyconcorde cd pycvoncorde pip install -e .
目前不支持输入距离矩阵求解, 需要官方安装求解器后重新安装包, 具体见Can I solve a
TSP problem with this solver using a distance matrix instead of inputing
the latitude and longitude nodes? #28.
对坐标点是有要求的, 见Issues with
coordinates < 1, Issue with big
coordinates.
Concorde TSP
Solver
Concorde
README and Installation guide:
安装时函数如configure的参数说明
参照How to install Concorde
in Ubuntu 14.04 LTS?, 运行如下命令:
1 2 3 4 5
wget http://www.math.uwaterloo.ca/tsp/concorde/downloads/codes/src/co031219.tgz tar xf co031219.tgz cd concorde ./configure make
之后运行~/src/concorde/TSP/concorde -s 99 -k 100测试,
发现如评论所述报错, 且参考How
to install Concorde in Ubuntu 14.04 LTS?安装qsopt后依然报错:
1 2 3 4 5 6 7 8 9 10 11
/home/carlos/concorde/TSP/concorde -s99 -k 100 Host: DESKTOP-R4H3HQA Current process id: 8201 Using random seed 99 Random 100 point set XSet initial upperbound to 780 (from tour) need to link an lp solver to use this function CClp_create_info failed need to link an lp solver to use this function CCtsp_read_probfile or first_lp failed need to link an lp solver to use this function CCtsp_init_lp failed</pre>
按照concorde:
strange warning #42在Linux的装法重新安装:
1 2 3 4 5 6
gunzip co031219.tgz tar xvf co031219.tar mkdir concorde_build cd concorde_build ../concorde/configure --with-qsopt=<FULL (non-recursive) PATH TO QSOPT> make
事实证明该版本不能求解非欧氏空间的问题,
输入EDGE_WEIGHT_FORMAT为LOWER_DIAG_ROW的.tsp示例后报错:
File Format Error: Can't read Explicit Lengths norm.
🌟alberto-santini/concorde-easy-build
Ubuntu下安装成功! 😁
1 2 3 4 5
git clone git@github.com:alberto-santini/concorde-easy-build.git cd concorde-easy-build/ cmake -DCMAKE_BUILD_TYPE=Release -DCPLEX_ROOT_DIR=/opt/ibm/ILOG/CPLEX_Studio221/ make -j5 ./concorde-bin -s 99 -k 100 -o test.txt
输出如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Host: DESKTOP-R4H3HQA Current process id: 3375 Using random seed 99 Random100 point set XSet initial upperbound to 780 (from tour) LP Value 1: 738.500000 (0.00 seconds) LP Value 2: 768.642857 (0.01 seconds) LP Value 3: 774.000000 (0.03 seconds) LP Value 4: 775.097826 (0.03 seconds) LP Value 5: 777.718750 (0.06 seconds) LP Value 6: 779.000000 (0.08 seconds) LP Value 7: 780.000000 (0.11 seconds) New lower bound: 780.000000 Final lower bound 780.000000, upper bound 780.000000 Exact lower bound: 780.000000 DIFF: 0.000000 Final LP has 187 rows, 313 columns, 2352 nonzeros Optimal Solution: 780.00 Number of bbnodes: 1 Total Running Time: 0.15 (seconds)
