货郎担问题的几何分块算法及ChinaTSP问题的最终解决

本文提出了货郎问题后一种新的求解方法，即几何分块算法，用该方法找到了ＣｈｉａｎＴＳＰ问题的最短路径，并分析了求解中的一些策略问题。     

Theoretical and experimental analysis of heuristics for the "freeze-tag" robot awakening problem

In the "freeze-tag" problem, we are given a swarm of n sleeping (frozen or inactive) robots and a single awake (active) robot. The goal is to awaken all robots in the shortest possible time. A robot is awakened when an active robot "touches" it. The goal is to compute an optimal awakening schedule such that all robots are awake by time t/sup */, for the smallest possible value of t/sup */. We devise and test a variety of heuristic strategies on geometric and network datasets. Our experiments show that all of the strategies perform acceptably well, with the simple greedy strategy performing particularly well. A theoretical analysis of the greedy strategy gives a tight approximation bound of /spl Theta/(/spl radic/logn) for points in the plane. We show more generally a tight performance bound of /spl Theta/((logn)/sup 1-1/d/) in d dimensions. The geometric case contrasts with the case of general metric spaces, where greedy is known to have a /spl Theta/(logn) approximation factor, and no method is known to achieve an approximation factor of o(logn).     

多周期家庭护理的路径规划与调度算法

在家庭护理服务质量方面,现有研究大多考虑老人的服务需求是否得到满足、服务是否及时、老人对服务是否满意等因素,忽略了老人在选择护工上的偏好习惯。提出带服务约束的多周期家庭护理路径规划与调度问题,并将其归约为多车场车辆路径优化问题,证明该问题的NP难解性。为了在老人提供的黑名单、必选服务技能、服务价格等约束下最优化家庭护理机构的服务质量,提出贪心算法,优先为服务开始时间早的老人提供服务,为老人安排最高服务质量的护工。以贪心算法求得的结果作为初始解,并针对该问题的多周期性质,定制一个遗传算法对初始解进行优化,以获得更优的多周期护工路径规划方案。在3组不同规模的开源数据集上进行实验,结果表明,与基准算法和随机算法相比,所提出的贪心算法将服务质量分别提高了31.7%和79.8%,定制的遗传算法将服务质量分别提高了65.7%和126.3%。     

$K$ Constrained Shortest Path Problem

Motivated by a real project for a sophisticated automated storage and retrieval system (AS/RS), we study the problem of generating K shortest paths that are required to satisfy a set of constraints. We propose a structural branching procedure that decomposes the problem into at most K|N| subproblems, where |N| is the number of nodes in the network. By using a Network Modification procedure, each subproblem can be transformed into a constrained shortest path problem (CSP). When these constraints satisfy a so called separable property, the subproblem can be further simplified. Based on this branching procedure, we propose a specific algorithm for an application where resource and loopless constraints have to be respected. Numerical results show that our algorithm is very efficient and robust.     

传感器网络中数据时新性移动设备的调度

为了在传感器网络中收集时间敏感性的数据,引入了移动设备来收集数据。提出了两种启发式算法,一种是基于货郎担问题的解法,将原问题分割成较小集合,然后逐步求解小问题,该算法适用于数据敏感性要求相对较低的应用;而当数据敏感性要求较高时,提出的贪婪式算法逐步建立移动设备的移动路径,即从基站(Sink)开始迭代选择代价值最小的节点,直到不能再添加节点进移动路径中。理论分析和模拟结果表明,提出的算法可以减少数据收集过程中所需要的移动设备的数目,而且大大节省了数据收集的总时间,从而可以应用在大规模网络中。     

大规模图上具有约束的多起点路径规划算法

路径规划查询是图数据上的一个基本问题,在众多的领域都有重要的应用价值。通常在实际问题中查询的路径是具有约束的,例如在外卖配送和共享出行问题中路径具有节点约束,其路径需要满足节点之间的先后关系约束。目前对于具有节点约束的路径查询问题,大多数的工作都在研究单起点的节点约束路径查询,但很难拓展到多起点节点约束问题中。因为具有节点约束的多起点路径查询问题是NP-hard的,所以该问题的大多数已有方法是使用贪心增量处理,但对于处理静态规则集拓展性不足。因此,提出了基于子路径的启发式算法和基于约束集拓展的精确算法,并在真实数据集上验证了算法的有效性。实验结果表明,启发式算法能够给出问题的精确解,而启发式算法能快速给出较好的近似解。     

Dynamically-Stable Motion Planning for Humanoid Robots

We present an approach to path planning for humanoid robots that computes dynamically-stable, collision-free trajectories from full-body posture goals. Given a geometric model of the environment and a statically-stable desired posture, we search the configuration space of the robot for a collision-free path that simultaneously satisfies dynamic balance constraints. We adapt existing randomized path planning techniques by imposing balance constraints on incremental search motions in order to maintain the overall dynamic stability of the final path. A dynamics filtering function that constrains the ZMP (zero moment point) trajectory is used as a post-processing step to transform statically-stable, collision-free paths into dynamically-stable, collision-free trajectories for the entire body. Although we have focused our experiments on biped robots with a humanoid shape, the method generally applies to any robot subject to balance constraints (legged or not). The algorithm is presented along with computed examples using both simulated and real humanoid robots.     

求解TSP问题的一种改进的遗传算法

TSP问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种理想方法。文章针对解决TSP问题,提出使用改进的遗传算法,即用浓度控制选择策略以保证群体的多样性,用贪婪交叉算子和启发式倒位变异算子来提高算法的收敛速度,较好地解决了群体的多样性和收敛速度的矛盾。算法的分析和测试表明,该文算法的改进是有效的。     

Solving the Orienteering Problem with Time Windows via the Pulse Framework

The Orienteering Problem with Time Windows (OPTW) is the problem of finding a path that maximizes the profit available at the nodes in a time-constrained network. The OPTW has multiple applications in transportation, telecommunications, and scheduling. First, we extend an exact method for shortest path problems with side constraints into a general-purpose framework for hard shortest path variants. Then, using this framework, we develop a new method for the OPTW that incorporates problem-specific knowledge. Our method outperforms the state-of-the-art algorithm on instances derived from benchmark datasets from the literature achieving speedups of up to 266 times and is able to find optimal solutions to large-scale problems with up to 562 nodes in short computational times.     

求解TSP问题的改进模拟退火遗传算法

巡回旅行商问题（TSP）是最典型的NP的难题,遗传算法（GA）是解决这类问题的有效方法之一。由于该问题的解是一种特殊的序列,一般的交叉算子在该问题的求解效果方面并不理想,提出了贪心的3PM交叉算子,同时又引入退火选择方法,形成一种新的模拟退火遗传算法GCBSAGA（Greed Cross-3PM Based on Simulated Annealing Genetic Algorithms）。该算法还将模拟退火算法与遗传算法相结合,使得遗传算法在前期发挥着全局搜索的强大功能,很容易收敛到全局较优解;后期用模拟退火算法来处理遗传算法前期的全局较优解,充分利用模拟退火算法后期局部搜索的强大功能,最终收敛到全局最优解。经过国际公认的TSPLIB提供的实验数据的验证,GCBSAGA在实例eil76、eil101、pr144、st70均找到了比TSPLIB提供的最优路径更优的解。     

Optimizing Recursive Information Gathering Plans in EMERAC

In this paper we describe two optimization techniques that are specially tailored for information gathering. The first is a greedy minimization algorithm that minimizes an information gathering plan by removing redundant and overlapping information sources without loss of completeness. We then discuss a set of heuristics that guide the greedy minimization algorithm so as to remove costlier information sources first. In contrast to previous work, our approach can handle recursive query plans that arise commonly in the presence of constrained sources. Second, we present a method for ordering the access to sources to reduce the execution cost. This problem differs significantly from the traditional database query optimization problem as sources on the Internet have a variety of access limitations and the execution cost in information gathering is affected both by network traffic and by the connection setup costs. Furthermore, because of the autonomous and decentralized nature of the Web, very little cost statistics about the sources may be available. In this paper, we propose a heuristic algorithm for ordering source calls that takes these constraints into account. Specifically, our algorithm takes both access costs and traffic costs into account, and is able to operate with very coarse statistics about sources (i.e., without depending on full source statistics). Finally, we will discuss implementation and empirical evaluation of these methods in Emerac, our prototype information gathering system.     

A Probabilistic Approach to Concurrent Mapping and Localization for Mobile Robots

This paper addresses the problem of building large-scale geometric maps of indoor environments with mobile robots. It poses the map building problem as a constrained, probabilistic maximum-likelihood estimation problem. It then devises a practical algorithm for generating the most likely map from data, along with the most likely path taken by the robot. Experimental results in cyclic environments of size up to 80 by 25 meter illustrate the appropriateness of the approach.     

基于自组织优化算法的一类多旅行商问题

多旅行商问题作为旅行商问题的一个扩展,是一个经典的组合优化问题,具有更高的复杂性,也具有更广泛的实际意义。针对每个旅行商允许经过的城市数有上限的多旅行商问题,通过引入虚拟城市把多旅行商问题转化为单旅行商问题,并且应用自组织优化算法进行了求解。虚拟城市局部适值的定义很好地处理了此类问题的能力约束,针对多旅行商问题的实例进行的仿真表明自组织优化算法可以很好地求解此类问题。     

A Probabilistic Approach to Concurrent Mapping and Localization for Mobile Robots

This paper addresses the problem of building large-scale geometric maps of indoor environments with mobile robots. It poses the map building problem as a constrained, probabilistic maximum-likelihood estimation problem. It then devises a practical algorithm for generating the most likely map from data, along with the most likely path taken by the robot. Experimental results in cyclic environments of size up to 80×25 m illustrate the appropriateness of the approach.     

一种求解旅行商问题的高效混合遗传算法

旅行商问题(TravellingSalesmanProblemTSP)是一个典型的组合优化难题,论文提出一种求解旅行商问题的高效混合遗传算法。该算法结合遗传算法和2-opt邻域搜索优化技术,并针对旅行商问题的特点,提出K近邻点集以缩减搜索空间从而加快求解速度。基于典型实例的仿真结果表明,此算法的求解效率比较高。     

基于轨迹受限的移动Sink低能耗数据收集协议

无线传感器网络数据收集的能耗问题一直以来都是研究的热点。本文主要研究基于移动Sink轨迹受限的数据收集协议。首先针对轨迹受限的无线传感网络提出一种通用的系统模 型,将该问题形式化为最大化降低全网总路径长度轨迹设计问题 (Maximizing total length reduction for constrained trajectory, MTRC),并证明了MTRC为NP-Hard问题;然后设计一种轨迹约束低能耗贪心算法 (Trajectory constrain of low energy consumption, TCLEC),通过 TSP近似算法设计最大化降低有效长度的Sink移动轨迹。理论分析和仿真实验结果表明,TCLEC在网络拓扑数据收集树的初始化以及优化方面是高效的,并且相对于同类基于移动Sink的无线传感网络分层数据收集方法,其能耗降低了7%左右。     

求解TSP问题的混合遗传算法

TSP问题是一类经典的NP问题,目前有很多方法对其求解,而用混合遗传算法对其求解取得了很好的成效。常见的混合遗传算法有遗传算法与最速下降法相结合（GACSDM）、遗传算法与模拟退火法相结合（SAGA）。设计了贪婪的复合变异算子（GCM）,并引入隔代爬山法算子（Climb）增加遗传算法的局部搜索能力。实验结果表明该算法是有效的。     

求解TSP问题的拟人算法

基于贪心算法提出了一种改进的求解旅行商问题(TSP)的拟人算法.该算法采用邻域定义,主要思想是:给定一个所有城市的全排列,依此全排列的指挥用贪心算法生成一个回路.通过城市交换和城市序列平移,在当前的邻域中搜索比它更好的解,如能找到如此的解,则使之成为新的当前解,然后重复上述过程.在搜索的过程中,采取跳坑策略以跳出局部最...     

旅行商问题的一种插入交叉算子

求解TSP问题是遗传算法应用的一个重要领域,其本质是TSP问题中巡回路径编码串的组合最优化问题。对于符号编码方式的遗传算法,通常需要设计特定的交叉算子以提高算法的运行效率和性能。该文针对自然数编码的方式,提出了一种较适合于大规模TSP问题求解的遗传交叉算子:插入交叉(InsertCrossover,简称IX)算子。该算子以优良的交叉策略,保证了算法的快速收敛和全局寻优。仿真实验结果证明,IX算子对于大规模TSP问题具有比较好的性能。     

Solving minimum constraint removal (MCR) problem using a social-force-model-based ant colony algorithm

The minimum constraint removal (MCR) motion planning problem aims to remove the minimum geometric constraints necessary for removing a free path that connects the starting point and the target point. In essence, discrete MCR problems are non-deterministic polynomial-time (NP)-hard problems; there is a “combinatorial explosion” phenomenon in solving such problems on a large scale. Therefore, we are searching for highly efficient approximate solutions. In the present study, an ant colony algorithm was used to solve these problems. The ant colony algorithm was improved based on the social force model during the solving process, such that it was no longer easy for the algorithm to fall into local extreme, and the algorithm was therefore suitable for solving the MCR problem. The results of the simulation experiments demonstrated that the algorithm used in the present study was superior to the exact algorithm and the greedy algorithm in terms of solution quality and running time.