灰狼算法求解多旅行商问题

一、问题描述

假设城市数目为n，旅行商数目为m，则MTSP可简单的描述为：m个旅行商从同一城市出发，分别沿一条旅行路线行走，使每个城市有且仅有一个旅行商经过（除出发城市），这m个旅行商最后返回起始城市。MTSP的目标是最小化m个旅行商行走距离的最大值。

综上所述，可以将MTSP定义在有向图G=（V，A），其中V是n个顶点的集合，A是弧的集合。$d_{ij}$表示节点$i$和节点$j$之间的距离。$x_{ij}$表示弧$(i,j)$是否被选择，如果被选择，则$x_{ij}=1$，否则$x_{ij}=0$。$u_i$表示一个旅行商从起点出发前往节点$i$时经过的节点数目，即节点$i$在当前旅行商路径中的位置序号。因此，MTSP的数学模型如下（其中节点1是所有旅行商的起点和终点）：

$$min[max(z_1,z_2,...,z_m)] \tag{1}$$ $$z_k=\sum_{i=1}^n\sum_{j=1}^nc_{ij}x_{ijk},k=1,2,\cdots,m \tag{2}$$ $$\sum_{j=2}^nx_{1j}=m \tag{3}$$ $$\sum_{j=2}^nx_{j1}=m \tag{4}$$ $$\sum_{i=1}^nx_{ij}=1,j=2,3,\cdots,n \tag{5}$$ $$\sum_{j=1}^nx_{ij}=1,i=2,3,\cdots,n \tag{6}$$ $$u_i-u_j+(n-m)x_{ij} \le n-m-1 \tag{7}$$ $$2 \le i \ne j \le n \tag{8}$$ $$x_{ij} \in \{0,1\},\forall(i,j) \in A \tag{9}$$

式(1)表示最小化m个旅行商中行走距离最大的那个值；式(2)表示各个旅行商的行走距离；约束(3)和(4)保证恰好有m个旅行商从节点1出发，最后返回节点1；约束(5)和(6)保证每个节点只能被访问一次（除节点1外）；约束(7)防止形成任何不包含节点1的路线。

二、算法简介

赞赏

感谢鼓励