一、问题定义

大规模多仓库多旅行商问题（Large - Scale Multi - Depot Multi - Traveling Salesman Problem，简称 LS - MDMTSP）是在经典旅行商问题基础上拓展而来的复杂组合优化问题。与单仓库情形不同，该问题设定了多个仓库，这些仓库均能作为旅行商的出发地与归宿。存在数量众多的客户节点分布在特定地理区域，同时有多支旅行商队伍。每支旅行商从各自选定的仓库出发，遍历若干客户节点后再返回出发仓库 。核心目标是确保所有客户节点都被至少一次访问，通常以最小化整体运营成本为优化方向，成本涵盖运输距离、时间消耗、车辆使用成本等多个维度。例如在全国性物流配送网络中，分布于不同城市的区域中心作为多仓库，各地的配送车辆作为旅行商，为分散在城市各处的客户提供服务。

二、问题特点

仓库选址与分配复杂性：不仅要考虑客户节点的分组和旅行商路径规划，还需合理确定每个旅行商从哪个仓库出发，以及如何将客户节点分配到各个仓库服务范围，这大大增加了问题复杂度。例如，不同仓库的运营成本、服务能力不同，需综合权衡。

规模庞大且复杂度高：随着客户节点、旅行商和仓库数量增加，解空间呈指数级膨胀。相较于单仓库问题，多仓库引入了更多变量，使得计算量和求解难度剧增。

多约束融合：除了单仓库多旅行商问题中的容量限制、时间窗约束、路径连通性约束外，还存在仓库容量约束，即每个仓库能够处理的货物量或服务客户数有限；以及仓库与旅行商的匹配约束，如特定旅行商只能从特定仓库出发等。

三、应用场景

区域物流协同配送：在城市群物流配送中，多个城市分别设有物流仓库，共同为区域内的企业和消费者提供货物配送服务。合理规划各仓库出发的配送车辆路径，能实现区域物流资源的高效利用，降低配送成本。

连锁企业物资调配：大型连锁超市或便利店，在不同地区设有多个配送中心（仓库），各配送中心派出配送车辆（旅行商）为旗下众多门店（客户节点）补货。优化调配方案可保障门店物资及时供应，同时减少配送资源浪费。

分布式能源巡检维护：在分布式能源系统中，存在多个能源管理中心（仓库），各中心派出巡检团队（旅行商）对分布在不同区域的能源设备（客户节点）进行定期巡检和维护。科学规划巡检路线，能提高能源系统的可靠性和稳定性。

四、常用求解方法

精确算法改进：针对大规模多仓库多旅行商问题，一些精确算法如分支定价法，通过将问题分解为定价子问题和主问题，利用列生成技术逐步生成最优解的列，相较于传统分支定界法，一定程度上提高了大规模问题的求解效率，但计算量依然较大，难以应对超大规模实例。

启发式与元启发式算法：

禁忌搜索算法：通过禁忌表记录已搜索过的解，避免算法重复搜索，引导搜索过程跳出局部最优解。在多仓库多旅行商问题中，用于探索不同的仓库 - 旅行商 - 客户节点组合，寻找较优路径。

模拟退火算法：模拟物理退火过程，从一个初始解出发，通过随机扰动产生新解，并以一定概率接受较差解，随着温度降低，逐渐收敛到全局最优解或近似最优解。在解决该问题时，可用于平衡全局搜索和局部搜索能力。

混合智能算法：将多种算法优势结合，如将遗传算法与局部搜索算法结合。先利用遗传算法的全局搜索能力对仓库分配和客户分组进行初步探索，再通过局部搜索算法对生成的路径进行精细优化，提高求解质量和效率。

五、案例分析

某大型快递企业在华东地区设有 5 个分拨中心（仓库），每天需向数千个快递网点（客户节点）派送包裹，涉及上百辆派送车辆（旅行商）。在未优化前，各分拨中心各自为政，派送路线混乱，导致成本高且派送时效低。通过引入基于混合智能算法的大规模多仓库多旅行商问题解决方案，对各分拨中心的服务范围重新划分，优化派送车辆路径。实施后，该地区快递派送成本降低了 20%，平均派送时效提高了 15%，有效提升了企业竞争力。

六、向光生长算法

向光生长算法（Phototropic growth algorithm，PGA）是2025年提出的一种元启发算法，该算法的灵感来自植物细胞响应阳光的生长模式。

参考文献

[1]Bohat V K, Hashim F A, Batra H, et al. Phototropic growth algorithm: A novel metaheuristic inspired from phototropic growth of plants[J]. Knowledge-Based Systems, 2025, 322: 113548.

七、向光生长算法求解LS-MDMTSP

figure

bar(path_length)

ylabel(‘路径长度’)

set(gca,‘xtick’,1:1:m);

set(gca,‘XTickLabel’,salemans)

title(Name)

figure

semilogy(CurveLine,‘LineWidth’,2);

xlabel(‘迭代次数’)

ylabel(‘总路径长度’)

legend(‘’)

title(Name)

%% 显示结果

fprintf(‘数据集：%s\n’,Name)

for j=1:length(saleman_path)

Kd=saleman_path{j};

fprintf(‘算法得到的路径%d:\n’,j)

fprintf(‘具体路径信息：%d’,Kd(1))

for i=2:length(Kd)

fprintf(’ > %d’,Kd(i));

end

fprintf(’ 路径长度%f\n’,path_length(j))

end

fprintf(‘算法求解得到的总路径长度:%f\n’,sum(path_length));

（1）数据集：a280

算法得到的路径1:

具体路径信息：143 > 147 > 148 > 142 > 205 > 213 > 214 > 226 > 225 > 224 > 223 > 222 > 219 > 220 > 217 > 218 > 215 > 216 > 204 > 143 路径长度257.000000

算法得到的路径2:

具体路径信息：212 > 211 > 227 > 234 > 235 > 236 > 237 > 232 > 233 > 228 > 229 > 230 > 210 > 209 > 208 > 206 > 149 > 141 > 207 > 212 路径长度301.000000

算法得到的路径3:

具体路径信息：231 > 238 > 239 > 240 > 241 > 242 > 244 > 245 > 247 > 250 > 249 > 255 > 254 > 139 > 140 > 253 > 252 > 251 > 246 > 231 路径长度287.000000

算法得到的路径4:

具体路径信息：243 > 2 > 1 > 280 > 3 > 279 > 278 > 259 > 260 > 262 > 263 > 264 > 138 > 266 > 265 > 257 > 256 > 258 > 248 > 243 路径长度316.000000

算法得到的路径5:

具体路径信息：267 > 137 > 136 > 268 > 269 > 272 > 273 > 274 > 9 > 10 > 8 > 7 > 6 > 5 > 4 > 277 > 276 > 275 > 261 > 267 路径长度270.000000

算法得到的路径6:

具体路径信息：270 > 135 > 134 > 132 > 133 > 17 > 18 > 19 > 20 > 25 > 23 > 24 > 14 > 13 > 12 > 11 > 15 > 271 > 16 > 270 路径长度227.000000

算法得到的路径7:

具体路径信息：22 > 26 > 27 > 28 > 29 > 32 > 33 > 31 > 30 > 125 > 126 > 127 > 128 > 129 > 154 > 150 > 131 > 130 > 21 > 22 路径长度285.000000

算法得到的路径8:

具体路径信息：155 > 153 > 156 > 121 > 40 > 39 > 48 > 49 > 52 > 51 > 50 > 38 > 37 > 36 > 35 > 34 > 124 > 123 > 122 > 155 路径长度279.000000

算法得到的路径9:

具体路径信息：53 > 54 > 55 > 56 > 57 > 58 > 59 > 44 > 43 > 60 > 61 > 119 > 152 > 120 > 41 > 42 > 45 > 46 > 47 > 53 路径长度289.000000

算法得到的路径10:

具体路径信息：68 > 69 > 70 > 71 > 72 > 85 > 86 > 116 > 157 > 151 > 115 > 117 > 118 > 62 > 63 > 65 > 64 > 66 > 67 > 68 路径长度307.000000

算法得到的路径11:

具体路径信息：73 > 84 > 87 > 113 > 114 > 158 > 178 > 159 > 111 > 110 > 112 > 88 > 83 > 82 > 76 > 77 > 75 > 74 > 73 路径长度296.000000

算法得到的路径12:

具体路径信息：81 > 89 > 109 > 108 > 107 > 177 > 160 > 105 > 104 > 90 > 91 > 93 > 94 > 96 > 95 > 78 > 79 > 80 > 81 路径长度291.000000

算法得到的路径13:

具体路径信息：97 > 98 > 99 > 100 > 101 > 169 > 170 > 172 > 171 > 161 > 176 > 175 > 174 > 173 > 106 > 103 > 102 > 92 > 97 路径长度249.000000

算法得到的路径14:

具体路径信息：162 > 163 > 164 > 165 > 166 > 168 > 167 > 188 > 189 > 186 > 187 > 185 > 184 > 183 > 182 > 180 > 179 > 181 > 162 路径长度231.000000

算法得到的路径15:

具体路径信息：190 > 191 > 192 > 194 > 195 > 196 > 201 > 200 > 202 > 221 > 203 > 144 > 146 > 145 > 199 > 198 > 197 > 193 > 190 路径长度272.000000

算法求解得到的总路径长度:4157.000000

一键三连，私信获取完整MATLAB代码

微信：djpcNLP123

免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删