多旅行商问题模型.doc

《多旅行商问题模型.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、以点0表示旅行商的出发城市，称为源点，点表示个旅行商需访问的城市。MTSP问题的数学模型可以表示为：令模型表示如下：式中：为增广费用。若用表示旅行商经过对应弧度所花的费用，如时间、距离、花费等，那么给增加行和列，每一新的行或列是的最后一行或列的复制，增广矩阵的其他元素为无穷大，由此构成了增广费用。一般MTSP中，旅行商访问个城市必须满足以下2个条件。条件1：从指定城市出发，对其他所有城市严格访问一次后返回原出发城市。条件2：一条有效路径严格由条非平凡子路径(NontrivialSubtours)组成。所谓

2、非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。用遗传算法求解MTSP，可通过附加虚拟城市的方法把MTSP转化为TSP。将另外个旅行商理解为个虚拟城市，这个虚拟城市标号分别为，它们与城市0具有相同的坐标(即相同位置)。在旅行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市，从而组成一个回路。每个回路表示MTSP中一个旅行商的旅行路径。需注意的是，为了避免出现平凡子路径，必须假设个虚拟城市到原点的距离为为一无穷大的正数（即永远不能达到），到其他各点距离与原点一致，这样遗传算法就不会出现0

3、-0-0的途径。将源点0复制个，个源点编号为每一个同源点0一样与其他点相连，而个源点互相不连接，这样在结点集上，可得到TSP线路，然后各源点合并成一个点。这样MTSP线路就分解成个分线路。