多目标应用：多目标蜣螂优化算法求解多旅行商问题（Multiple Traveling Salesman Problem, MTSP）

一、多旅行商问题

多旅行商问题（Multiple Traveling Salesman Problem, MTSP）是著名的旅行商问题（Traveling Salesman Problem, TSP）的延伸，多旅行商问题定义为：给定一个𝑛座城市的城市集合，指定𝑚个推销员，每一位推销员从起点城市出发访问一定数量的城市，最后回到终点城市，要求除起点和终点城市以外，每一座城市都必须至少被一位推销员访问，并且只能访问一次，需要求解出满足上述要求并且代价最小的分配方案，其中的代价通常用总路程长度来代替，当然也可以是时间、费用等。围绕着各推销员的起始点和终止点来划分，多旅行商问题大致可以分为四种，其中单仓库多旅行商问题是其中一种。多旅行商问题
单仓库多旅行商问题（Single-Depot Multiple Travelling Salesman Problem, SD-MTSP）：𝑚个推销员从同一座中心城市出发，访问其中一定数量的城市并且每座城市只能被某一个推销员访问一次，最后返回到中心城市，通常这种问题模型被称之为SD-MTSP。

1.1多旅行商多目标问题描述

对于推销员人数为𝑚，所需要访问的城市总数为𝑛的多旅行商问题而言，记中心城市为0，其双目标的数学模型可以表述为：
$$\min f={\left[f_1,f_2\right]}^T$$
f 1 = ∑ k = 1 m ∑ i = 0 n ∑ j = 0 n d i j x i j k f 2 = max ⁡ 1 ≤ k ≤ m ∑ i = 0 n ∑ j = 0 n d i j x i j k − min ⁡ 1 ≤ k ≤ m ∑ i = 0 n ∑ j = 0 n d i j x i j k

f1​=∑k=1m​∑i=0n​∑j=0n​dij​xijk​f2​=max1≤k≤m​∑i=0n​∑j=0n​dij​xijk​−min1≤k≤m​∑i=0n​∑j=0n​dij​xijk​​
其中：
x i j k = { 1  推销员  k  由城市  i  到达城市  j 0  否则   s.t.  ∑ k = 1 m ∑ i = 1 n x i 0 k = m ∑ k = 1 m ∑ j = 1 n x 0 j k = m ∑ k = 1 m ∑ i = 1 n x i j k = 1 ∀ j = 1 , … , n ∑ k = 1 m ∑ j = 1 n x i j k = 1 ∀ i = 1 , … , n

\begin{array}{l} x_{i j k}=\left\{\begin{array}{lc} 1 & \text { 推销员 } k \text { 由城市 } i \text { 到达城市 } j \\ 0 & \text { 否则 } \end{array}" role="presentation" style="position: relative;">\begin{array}{l} x_{i j k}=\left\{\begin{array}{lc} 1 & \text { 推销员 } k \text { 由城市 } i \text { 到达城市 } j \\ 0 & \text { 否则 } \end{array}$$\text{begin{array}{l} x\_{i j k}=left{begin{array}{lc} 1 \& text { 推销员 } k text { 由城市 } i text { 到达城市 } j 0 \& text { 否则 } end{array}}$$

\right. \\ \text { s.t. } \\ \sum_{k=1}^{m} \sum_{i=1}^{n} x_{i 0 k}=m \\ \sum_{k=1}^{m} \sum_{j=1}^{n} x_{0 j k}=m \\ \sum_{k=1}^{m} \sum_{i=1}^{n} x_{i j k}=1 \quad \forall j=1, \ldots, n \\ \sum_{k=1}^{m} \sum_{j=1}^{n} x_{i j k}=1 \quad \forall i=1, \ldots, n \\ \end{array} xijk​={10​ 推销员 k 由城市 i 到达城市 j 否则 ​ s.t. ∑k=1m​∑i=1n​xi0k​=m∑k=1m​∑j=1n​x0jk​=m∑k=1m​∑i=1n​xijk​=1∀j=1,…,n∑k=1m​∑j=1n​xijk​=1∀i=1,…,n​
其中，$f_1$表示所有推销员的总路程，$f_2$代表推销员中最长路线与最短路线的差值（平衡度）。约束条件1和约束条件2表示编号为 0 的中心城市的入度和出度都必须为𝑚，即代表𝑚个推销员均从中心城市出发并且完成行程后都回到了中心城市。约束条件3和约束条件4表示除中心城市外的其他所有城市的出度和入度均为 1，即每个城市能且只能被推销员中的一个人访问。

参考文献：
[1]杨帅. 求解多旅行商问题的进化多目标优化和决策算法研究[D].武汉科技大学,2020.

二、多目标蜣螂优化算法

非支配排序的蜣螂优化算法（Non-Dominated Sorting Dung beetle optimizer，NSDBO）

三、NSDBO求解多旅行商问题

本文选取国际通用的TSP实例库TSPLIB中的测试集bayg29，bayg29中城市分布如下图所示：

本文采用NSDBO求解bayg29，两个目标函数分别是：$f_1$表示所有推销员的总路程，$f_2$代表推销员中最长路线与最短路线的差值（平衡度）。设置城市13作为两个旅行商的起点城市，部分代码如下：

close all;
clear ; 
clc;

TestProblem=1;%1
MultiObj = GetFunInfo(TestProblem);
MultiObjFnc=MultiObj.name;%问题名
% Parameters
params.Np = 100;        % Population size
params.Nr = 200;        % Repository size
params.maxgen =5000;    % Maximum number of generations
numOfObj=MultiObj.numOfObj;%目标函数个数
D=MultiObj.nVar;%维度
f = NSDBO(params,MultiObj);
X=f(:,1:D);%PS
Obtained_Pareto=f(:,D+1:D+numOfObj);%PF
save f f
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

NSDBO求解得到的Pareto前沿：

NSDBO求解得到的Pareto前沿值$f_1$（总路程）与$f_2$（平衡度）如下：

22102.9727798521	0.00168180065520573
22102.9727798521	0.00168180065520573
20329.0091686614	0.0896807373028423
20329.0091686614	0.0896807373028423
15456.3506535282	1.33753213901582
15456.3506535282	1.33753213901582
13950.3392331925	695.147203595617
14420.4208157020	64.1232588333942
13922.7061066601	722.780330128020
14053.9188784077	591.567558380348
13801.7974549415	843.688981846539
14400.5426626992	244.943774088882
21666.5808905080	0.0437079968960461
21666.5808905080	0.0437079968960461
13879.7557217029	765.730715085202
14219.2814238736	426.205012914498
14259.9199643935	385.566472394623
13576.1099393706	1069.37649741747
14274.5105510786	370.975885709519
14187.8876952665	457.598741521547
13592.8678000419	1052.61863674616
13405.1284596659	1240.35797712221
14057.8134204866	587.673016301442
13601.5016056637	1043.98483112440
14595.0969246490	50.3895121391015
14285.0633767127	360.423060075419
14250.8059878040	394.680448984042
13638.7940708342	1006.69236595388
13563.0504709883	1082.43596579977
14270.4999860843	374.986450703771
14034.0203420467	611.466094741369
14413.6027244188	231.883712369266
14644.0574853126	1.42895147543368
13819.0824906934	826.403946094693
13395.6431995137	1249.84323727441
14180.6060656979	464.880371090151
13870.0498645105	775.436572277533
13939.7611609484	705.725275839711
14420.0001688052	225.486267982903
14264.7872139482	380.699222839900
13405.1284596659	1240.35797712221
13962.9518331561	682.534603631974
13412.3745988936	1233.11183789447
13655.5519315055	989.934505282572
14045.2478310867	600.238605701406
13679.3964854527	966.089951335388
14026.1398964906	619.346540297437
14098.7532568577	546.733179930393
14618.5185669984	26.9678697896543
13696.8739147629	948.612522025227
13664.5719518761	980.914484912005
13936.7403600022	708.746076785834
13731.9599733822	913.526463405907
13796.4774910062	849.008945781922
14339.6906369881	305.795799799950
13755.7555255629	889.730911225152
14230.2555149456	415.230921842478
13755.7555255629	889.730911225152
14075.4804896908	570.005947097243
14288.6127867984	356.873649989633
14368.6697670641	276.816669724018
14607.6529096612	37.8335271268925
14002.5714775335	642.914959254576
14161.5141852619	483.972251526198
14382.7329591811	262.753477606963
13776.9216244865	868.564812301621
14317.4067712580	328.079665530078
14166.6544834181	478.831953370019
13738.9976648916	906.488771896463
13521.4744741303	1124.01196265782
13826.3329814449	819.153455343180
13784.7296079061	860.756828882028
13916.2244996389	729.261937149149
13976.6848214007	668.801615387379
14257.0766510210	388.409785767103
14312.3050031855	333.181433602567
14628.5102433837	16.9761934043490
14077.7837516092	567.702685178916
13887.8238203771	757.662616410972
13833.3772965324	812.109140255715
13436.7083012567	1208.77813553138
14088.0610029341	557.425433853994
13809.5751207736	835.911316014491
14113.9329148047	531.553521983379
14082.5893944871	562.897042300954
14300.6489105867	344.837526201390
13904.1650632058	741.321373582243
13853.2481981306	792.238238657443
14128.6338178830	516.852618905066
13821.0433350971	824.443101691019
13864.1807704821	781.305666305961
13896.8478118052	748.638624982852
13604.9130781688	1040.57335861927
14409.1938928293	236.292543958801
13576.1099393706	1069.37649741747
13956.5785499213	688.907886866759
13980.0588635344	665.427573253641
14363.1056599183	282.380776869733
13676.7180304290	968.768406359041
13566.4242494531	1079.06218733502
13499.2228447289	1146.26359205914
13499.2228447289	1146.26359205914
13851.4600244969	794.026412291182
13369.9522776565	1407.65153624345
13716.8037297586	928.682707029437
14375.9303533726	269.556083415446
13775.3113920826	870.175044705454
13520.3889436525	1125.09749313561
13859.2706574781	786.215779310020
13594.6303125791	1050.85612420895
14236.9511003133	408.535336474735
14198.1049883458	447.381448442302
14049.1379747565	596.348462031567
14633.5007437487	11.9856930393889
13395.6431995137	1249.84323727441
14586.7033097544	58.7831270336346
14614.5413354607	30.9451013274302
14328.8775983163	316.608838471781
14139.5171512169	505.969285571210
14137.1833694194	508.303067368681
14211.7359073611	433.750529426938
14063.4210532577	582.065383530337
14173.0376035351	472.448833253017
14020.6014731387	624.884963649392
13534.9758344685	1110.51060231963
13930.6918937885	714.794542999563
13689.5831246536	955.903312134470
13929.0756214169	716.410815371169
13670.0038946683	975.482542119748
13457.8744001802	1187.61203660785
14389.8358659876	255.650570800486
13789.7429864621	855.743450325952
14103.8422445527	541.644192235358
13844.6837666621	800.802670126003
13615.7964115027	1029.69002528542
14007.7447084211	637.741728366974
13836.2330110090	809.253425779076
13584.2165699118	1061.26986687624
13412.4010601850	1233.08537660310
14038.1089258591	607.377510928947
13971.5053321160	673.981104672085
13716.8037297586	928.682707029437
13731.9599733822	913.526463405907
14588.2825964126	57.2038403755196
13985.3186270225	660.167809765614
13994.1550223314	651.331414456641
13461.8156004230	1183.67083636509
13426.2945585894	1219.19187819868
14293.7515820089	351.734854779168
14325.7364561681	319.749980619964
13709.6557064622	935.830730325880
13805.8957068296	839.590729958496
14351.8856863840	293.600750404034
14394.4781343436	251.008302444491
13907.9095224934	737.576914294700
13738.9976648916	906.488771896463
13426.2945585894	1219.19187819868
13513.8097355449	1131.67670124316
13610.3107205101	1035.17571627802
13482.9816993465	1162.50473744156
13433.5671591085	1211.91927767957
15948.7678292123	0.108952378204776
14069.0409095266	576.445527261479
13767.6797855170	877.806651271094
13482.9816993465	1162.50473744156
14622.6276397819	22.8587970062299
14243.7207815203	401.765655267734
13643.8754436191	1001.61099316897
14307.1410311894	338.345405598670
14145.4970568141	499.989379973967
13989.5438116728	655.942625115286
14126.0632200757	519.423216712366
14216.4557735630	429.030663225126
13689.5831246536	955.903312134470
14119.8505980888	525.635838699319
14360.0618842428	285.424552545263
13883.4155821249	762.070854663193
14639.6224207000	5.86401608805682
14335.2573198184	310.229116969712
13659.9601697577	985.526267030351
13534.9758344685	1110.51060231963
14148.7146707741	496.771766013964
13369.9522776565	1407.65153624345
13513.8097355449	1131.67670124316
13584.2165699118	1061.26986687624
14155.0961810537	490.390255734353
15815.4017049468	1.13979477541398
13626.0791770923	1019.40725969574
15815.4017049468	1.13979477541398
13632.5966503624	1012.88978642570
14601.3731536162	44.1132831718569
13968.0335912706	677.452845517460
13649.5132494857	995.973187302346
14012.5704338590	632.916002929059
13765.4113625185	880.075074269558
13474.6746390399	1170.81179774814
14581.7524217132	63.7340150748669
14204.5192799572	440.967156830911
13474.6746390399	1170.81179774814
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199

部分规划路径如下：

四、完整MATLAB代码