MATLAB遗传算法的改进及其在TSP问题中的应用(4)
数学模型：
G=(V，E)为一个带权图，V={1，2，⋯，n}为顶点集，E={eij= (i，j)li，j∈V，i j}为边集。d ij(i，j∈V，i j)为顶点
i到顶点j的距离，其中 且 dij>0且dij≠∞，同时dij=dji (i，j∈V)，则经典TSP(Classical TSP，CTSP)的数学模型为：
minF= (1)
st.xij= （2）
， i∈V (3)
， j∈V (4)
i≠j
， s为G的子图 (5)
其中ISI为图S的顶点数。(1)为CTSP的目标函数，求经过所有顶点的回路的最小距离。(2)~(4)限定回路上每个顶点仅有一条入边和一条出边。(5)限定在回路中不出现子回路。模型实质上是在一个带权图中求一条Hamilton回路。若对所有i，j，k∈V，不等式dij+djk+ ≥ 均成立，则称该问题是满足三角不等式的。
1.2.2旅行商问题研究的意义
TSP是最有代表性的优化组合问题之一，它的应用已逐步渗透到各个技术领域和我们的日常生活中，至今还有不少学者在从事这方面的研究工作，一些项目还得到美国军方的资助。就实际应用而言，一个典型的例子就是机器在电路板上钻孔的调度问题(注：在该问题中，钻孔的时间是固定的，只有机器移动时间的总量是可变的)，在这里，电路板上要钻的孔相当于TSP中的“城市”，钻头从一个孔移到另一个孔所耗的时间相当于TSP中的“旅行费用”。
交通管理的主要目的是在保证全部仓库具有必要库存情况下，减少交通费用。在复杂的地理网络中优化决定车辆线路是交通服务的核心问题。减少交通费用依赖最佳地在由库存节点构成的网络中确定车辆路径，最佳地安排车辆的出发时间，以及有效的利用车辆。一个经典的路由问题是在一个网络上发现从源节点到一个目的节点的最佳交通线路，使与距离成比例的流动费用降低到最小。这个问题的关键是在交通网络上计算从源节点到目的节点之间的最短路径。在文献中人们提出了许多最短路径的算法，给工程技术人员提供了多种选择。对这个最小费用流动问题进行扩展，就构TSP问题，在这个问题中，车辆从源点出发访问多个目的地并且最后回到源点。事实上，除了需求量和交通时间，在交通运输中还需要考虑更多变量。
在大规模生产过程中，寻找最短路径能有效地降低成本，这类问题的解决还可以延伸到其他行业中去，如运输业、后勤服务业等。然而，由于TSP会产生组合爆炸的问题，因此寻找切实可行的简化求解方法就成为问题的关键。遗传算法由于其具有良好的全局搜索能力，成为了目前解决各种优化问题的有效方法。在遗传算法的研究中，TSP问题也已被广泛的用于评价不同的遗传操作及选择机制的性能。原因如下：
下一篇：基于PLC的变频恒压供水系统设计