束东来，张玉州

（安庆师范大学 计算机与信息学院，安徽安庆246133）

限容量多旅行商问题（LCMTSP）是对经典旅行商问题（TSP）及多旅行商问题（MTSP）的模型扩展。

实际问题中让一个人从一个城市出发去拜访若干个城市，其工作量是巨大的，所以考虑到工作效率等问题，MTSP更符合实际，而每个旅行商的精力是有限的，安排一个合理访问城市个数的范围是有必要的[2]，LCMTSP问题在MTSP问题基础上，给每个旅行商施加了一个访问城市个数的限制条件，显然更符合实际意义。

本文以3个旅行商、每个旅行商访问城市不少于3个但不多于10个、从一个城市出发访问其余19个城市并回到出发城市问题为例，对传统的遗传算子稍加改进，实验证明能够较好的解决限容量多旅行商问题。

1 LCMTSP数学模型

带有容量限制的多旅行问题是在原有的多旅行商问题的基础上多了一个容量限制的约束条件。其目标函数为m个旅行商所走的路程最短，其约束条件为m个旅行商中每个旅行商访问城市的个数有上下限。

本文模型与基本TSP问题一样，是寻找加权图中最短回路问题[4]，假设城市号从1～n，其中城市1为出发城市，m个旅行商。

定义变量：

其中i=1,2...N，k=1,2...M

目标函数为：

约束条件：

其中Si,k为第k个人访问的城市的合集，sik代表第k个人访问的第i个城市，q代表访问者访问的城市数目

公式（4）代表从指定城市1出发，所有城市仅有1个访问者严格访问一次；

公式（5）表示任意一条路线的次终点城市（iq,k）仅有一个起始点城市与之相连；

公式（6）表示任意一条路线的起始点城市仅有一个次终点城市（iq,k）与之相连；……