## Travelling Salesman Problem using 3OPT and 2OPT Perturbation
A Simple Python based Travelling sales man problem which makes use of 3OPT move and 2OPT perturbation phase. The objective of the problem is to find the minimum distance to visit each city exactly once and then return to home city. Its a combinatorial optimization **(NP hard)** problem
The code makes use of heuristics search rather than exact search, so it is not guranteed that the calculated tour will be the best tour. The advantage of using heuristic search is shorter running time which makes it suitable for problems with large instances.
### Algorithm
The iterative local search comprises 2 phases. First, in a local search phase, the algorithm improves the current solution until reaching a local minimum. Second, in the perturbation phase, the algorithm perturbs the current incumbent solution (s*) in order to escape from difficult regions of the search (e.g., a
local minimum). Finally, the acceptance criterion decides whether to update s* or not.
1. S<sub>0</sub> = **Initial Solution**
2. S<sup>*</sup> = **Local Search (S<sub>0</sub>)**
3. **while some condition**
4. S<sup>'</sup> = **Perturbation(S<sup>*</sup>)**
5. S<sup>'*</sup> = **Local Search(S<sup>'</sup>)**
6. S<sup>*</sup> = **Acceptance criterion(S<sup>\*</sup>, S<sup>'\*</sup>)**
7. **Until no stopping criteria**
### Local search Algorithm
For the above **Local Search** Algorithm, 3 OPT move is applied but in modified way.
1. A random edge is selected as the first edge.
2. A 3OPT move is performed with the above edge and every possible combination of other 2 edges. (This is done inorder to spped up the process).
3. For each iteration in the local search, only the best one is retained.
### Perturbation Phase
Perturbation phase is simply 2OPT swap to escape local minima. This step is repeated 5 times to have some randomness.
### Local Search after Perturbation
Local search is again called after perturbation phase, with the route generated after perturbation phase.
### Acceptance Criterion
This step decides which solution to retain. A random 5% probability is added to select the solution generated from the above step blindly otherwise, only the best is retained.
### Code Usage
The code is written in a class and is as per the above algorithm. The main class of **tsp.py** uses MultiProcessing Process to spawn 5 different process to run the code 5 times at a time. You can make it 1 if you want to run it only once.
Logging is enabled and it continuously writes it to a log file. Check **run** method. Plotly is used to plot initial and final graph.
There are 2 ways of generating initial solution.
1. Random Solution (init_solution)
2. Nearest neighbour solution (generate_nearest_neighbour_solution)
> Eucliden distance is used to calculate the tour cost. (This can be optimizd as the cost is calculated after every 2opt / 3opt move. Any Suggestions ??)
The stopping criterion of this algorith is 300 seconds (However, it takes around 20 minutes to run the code), and is not hard enforced which means if the code execution has already started and has surpassed the given seconds, then it won't be terminated but however, it will be the last execution. The stopping criterion seconds is defined in **main** function of **TSP** class.
> 300 seconds execution time is quite less and it hugely depends on the complexity (number of data points) of the file / problem.
### Results
Running the code once, for inst-0.tsp, this is the initial random solution generated.
![Initial](images/init.png)
And after running the code, this is the final solution generated.
![Final](images/final.png)
As you can see from the graph above, the route is optimized, but we can clearly see that there is some more room for improvement. It may be because my stopping criterion was 300 seconds, so it might need some more time to improve the solution further.
### Requirements
- Python 3
- Plotly
> You can install the dependencies using the following code: (This assumes you have Python 3.6 installed on your machine)
`pip install -r requirements.txt`
### Running the code
Just run tsp.py.
> `python tsp.py`
Feel free to change number of parallel runs if you don't want your computer to be stuck with 100% Process usage.
### Testing Environment
This code is tested on Dell Alienware 17 R4 Machine for which the config is as follows:
- Windows 10 Pro (with latest patches and updates)
- Intel 7700Hq Processor
- 24 Gb DDR4 2400Mhz RAM (Memory)
- W.D Black 512G.B M.2 NVME SSD DRIVE
- JetBrains PYCharm Professional Edition (Latest version - 2018.3.1)
> **Note**: Make sure to initialize the project directory as a virtual environment.
## Feedback
It may not be very optimized, so if you tend to find any bug fixes, feature requests, pull requests, feedback, etc., are welcome...
If you like this project, please do give it a star.
You may use this tutorial freely at your own risk. See [LICENSE](https://github.com/source-nerd/tsp_3opt_2opt/blob/master/LICENSE).
没有合适的资源?快使用搜索试试~ 我知道了~
具有 3opt 移动和 2opt 扰动的旅行商问题_python_代码_下载
共11个文件
py:3个
tsp:3个
png:2个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
5星 · 超过95%的资源 2 下载量 82 浏览量
2022-06-22
17:45:29
上传
评论
收藏 138KB ZIP 举报
温馨提示
一个简单的基于 Python 的旅行推销员问题,它利用 3OPT 移动和 2OPT 扰动阶段。该问题的目标是找到每个城市恰好访问一次然后返回家乡的最小距离。它是一个组合优化(NP 难)问题 该代码使用启发式搜索而不是精确搜索,因此不能保证计算出的行程将是最佳行程。使用启发式搜索的优点是运行时间更短,这使其适用于大型实例的问题。 算法 迭代局部搜索包括 2 个阶段。首先,在局部搜索阶段,算法改进当前解,直到达到局部最小值。其次,在扰动阶段,该算法扰动当前的现有解决方案 (s*) 以逃离搜索的困难区域(例如,局部最小值)。最后,接受标准决定是否更新 s*。 更多详情、使用方法,请下载后阅读README.md文件
资源推荐
资源详情
资源评论
收起资源包目录
tsp_3opt_2opt-master.zip (11个子文件)
tsp_3opt_2opt-master
README.md 5KB
dataset
Inst
test-inst-0.tsp 164B
inst-0.tsp 3KB
inst-13.tsp 6KB
LICENSE 34KB
utils.py 2KB
tsp.py 12KB
cities_graph.py 1KB
requirements.txt 203B
images
final.png 50KB
init.png 68KB
共 11 条
- 1
资源评论
- qq_219397932023-12-11这个资源值得下载,资源内容详细全面,与描述一致,受益匪浅。
- 潦草奇遇记2023-02-10发现一个宝藏资源,赶紧冲冲冲!支持大佬~
快撑死的鱼
- 粉丝: 1w+
- 资源: 9154
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功