汽配件颜色喷涂顺序问题的TSP转化与建模

汽配件颜色喷涂顺序问题通常以生产线上相邻汽配件颜色切换次数少为最优目标,以进一步降低生产成本.该类问题具有所有汽配件都必须喷涂一次且只喷涂一次的特点,为此提出了TSP转化与建模的方法.将待喷涂汽配件定义为TSP顶点,任意两个待喷涂汽配件的颜色切换定义为顶点的距离,仿照TSP问题构建0-1规划模型;类似于顶点距离,将某些汽配件的颜色或类别不相邻要求定义为0-1矩阵,巧妙地构造了喷涂生产的约束条件.该建模方法简单快速,通用性高,适用于具有类似特点的各类生产实践问题.     

Optimal deterministic algorithms for some variants of Online Quota Traveling Salesman Problem

This paper is concerned with the Online Quota Traveling Salesman Problem. Depending on the symmetry of the metric and the requirement for the salesman to return to the origin, four variants are analyzed. We present optimal deterministic algorithms for each variant defined on a general space, a real line, or a half-line. As a byproduct, an improved lower bound for a variant of Online TSP on a half-line is also obtained.     

自适应多种群回溯群居蜘蛛算法求解TSP问题

在群居蜘蛛优化算法中引入自适应决策半径,将蜘蛛种群动态地分成多个种群,种群内适应度不同的个体采取不同的更新方式.在筛选全局极值的基础上,根据进化程度执行回溯迭代更新,提出一种自适应多种群回溯群居蜘蛛优化算法,旨在提高种群样本多样性和算法全局寻优能力.函数寻优结果表明改进算法具有较快的收敛速度和较高的收敛精度.最后将其应用于TSP问题的求解.     

基于不同条件的旅游路线规划问题研究

运用2015年全国研究生数学建模竞赛F题的数据资料,针对旅游路线合理规划问题的第一问展开研究.以F题的问题一为起点进行了分析研究,是因为第一问的完成是解决后续问题的关键.首先通过地图搜集并补全了缺失数据并对数据进行合理的处理,然后采用将旅游年数最少目标转化为该最小生成树的"最少圈覆盖"方法来进行对问题一的求解,也可以理解为一个广义的多旅行商问题,以旅行商的人数(即年数)最少为目标.采用Dijkstra算法、最少圈覆盖法、智能算法和图论聚类等方法,通过这些方法建立了单目标优化模型,并运用旅行商问题和模型之间的转换来对问题进行分析与求解.     

The snowblower problem

We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a short tour for the snowblower to follow to remove all the snow from a domain (driveway, sidewalk, etc.). When a snowblower passes over each region along the tour, it displaces snow into a nearby region. The constraint is that if the snow is piled too high, then the snowblower cannot clear the pile.We give an algorithmic study of the SBP. We show that in general, the problem is NP-complete, and we present polynomial-time approximation algorithms for removing snow under various assumptions about the operation of the snowblower. Most commercially available snowblowers allow the user to control the direction in which the snow is thrown. We differentiate between the cases in which the snow can be thrown in any direction, in any direction except backwards, and only to the right. For all cases, we give constant-factor approximation algorithms; the constants increase as the throw direction becomes more restricted. Our results are also applicable to robotic vacuuming (or lawnmowing) with bounded-capacity dust bin.     

旅游路线规划问题

对旅游爱好者游遍201个5A级景点的旅行方案进行研究.首先,建立以总的旅游时间达到最小的0-1数学规划模型,利用枚举法将景点划分成若干类,并将其视为TSP问题,用蚁群算法得出常住地为西安的旅游者游遍所有景点至少需要的时间和最优路线;其次,考虑了费用最小,旅游体验最好的因素,建立多目标规划模型,通过模糊隶属度函数的构造,将多目标规划模型进行线性加权组合转化为单目标规划问题进行求解.还引入TOPSIS模型,对常住地在北京的自驾游爱好者提供了一个简要版旅游计划.最后,用因子分析和灰关联分析相结合的方法遴选了相应5A级和4A级旅游景区,并给出该旅游爱好者合理的十年旅游规划.     

具有动态阈值的人工神经网络

在研究神经元阈值作用的基础上,提出了神经网络中神经元的动态阈值选择作用和神经元之间抑制作用模型,研究表明,这种模型能降低应用对象模型的复杂性,简化网络运行的中间过程,修正二值输出函数的性能,使收敛速度和有效性得到改善.将这种人工神经网络用于求解TSP问题,显示系统还具有模拟退火作用的效果.     

基于TSP规划模型的碎纸片拼接复原问题研究

引入差异度指标描述碎纸片图像边缘的匹配程度,以差异度最小为目标建立TSP问题的数学模型,并按照指派模型求解。设计“按行聚类-行内排序”算法,以降低算法的时间复杂度;同时,对字符进行聚类分析,并利用模式识别技术降低拼接的错误率,减少人工干预;通过纵切、纵横切、双面的中英文碎纸片的复原,验证了拼接模型和算法的准确性和有效性。