Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax k vertex-disjoint paths in a directed acyclic graph

This paper is composed of two parts. In the first part, an improved algorithm is presented for the problem of finding length-bounded two vertex-disjoint paths in an undirected planar graph. The presented algorithm requires O(n³bmin) time and O(n²bmin) space, where bmin is the smaller of the two given length bounds. In the second part of this paper, we consider the minmax k vertex-disjoint paths problem on a directed acyclic graph, where k?2 is a constant. An improved algorithm and a faster approximation scheme are presented. The presented algorithm requires O(nk+1Mk−1) time and O(nkMk−1) space, and the presented approximation scheme requires O((1/?)^k−1n2klogk−1M) time and O((1/?)^k−1n2k−1logk−1M) space, where ? is the given approximation parameter and M is the length of the longest path in an optimal solution.     

Optimizing the use of public transit system during no-notice evacuation of urban areas

This paper proposes a methodology that can be used to design plans for evacuating transit-dependent citizens during no-notice disasters. A mixed-integer linear program is proposed to model the problem of finding optimal evacuation routes. The objective of the problem is to minimize the total evacuation time and the number of casualties, simultaneously. A traffic simulation package is used to explicitly incorporate the traffic flow dynamics into our model in order to generate solutions which are consistent with the dynamics of traffic network. Due to the long running time of CPLEX, a Tabu search algorithm is designed that finds evacuation routes for transit vehicles. Computational experiments demonstrate that the solutions found are of high-quality. Numerical experiments are conducted using the transportation network of the city of Forth Worth, TX to illustrate the modeling procedure and solution approach.     

多层建筑应急疏散仿真

以多层建筑为背景,研究应急疏散问题,基于改进的路径规划算法,并将多智能体技术应用在模型间的通信交流上.采用机器人感知周围环境,通过设置机器人个数以及初始位置,对灾情中室内被困人员进行智能搜救,并采集现场实时数据,作出决策分析.机器人实时感知现场状况的变化,引导人员疏散,并将实时数据传输给施救人员,采取进一步救援措施.结果表明,该三维仿真技术为有效减少人员疏散中的伤亡和最佳救援方案的制定提供了参考,具有一定的现实指导意义.     

Polygonal approximation of closed discrete curves

Optimal polygonal approximation of closed curves differs from the case of open curve in the sense that the location of the starting point must also be determined. Straightforward exhaustive search would take N times more time than the corresponding optimal algorithm for an open curve, because there are N possible points to be considered as the starting point. Faster sub-optimal solution can be found by iterating the search and heuristically selecting different starting point at each iteration. In this paper, we propose to find the optimal approximation of a cyclically extended closed curve of double size, and to select the best possible starting point by search in the extended search space for the curve. The proposed approach provides solution very close to the optimal one using at most twice as much time as required by the optimal algorithm for the corresponding open curve.     

A column generation approach for a school bus routing problem with resource constraints

The Multiple Vehicle Traveling Purchaser Problem describes a school bus routing problem that combines bus stop selection and bus route generation. This problem aims at selecting a set of bus stops from among a group of potential locations to pick up students, and for designing bus routes to visit the selected stops and to carry the students to their school. We address a variation of this problem that considers certain constraints on each bus route, such as bounds on the distances traveled by the students, bounds on the number of visited bus stops, and bounds on the minimum number of students that a vehicle has to pick up.     

Dynamic shortest path problems: Hybrid routing policies considering network disruptions

Traffic network disruptions lead to significant increases in transportation costs. We consider networks in which a number of links are vulnerable to these disruptions leading to a significantly higher travel time on these links. For these vulnerable links, we consider known link disruption probabilities and knowledge of transition probabilities for recovering from or getting into a disruption. We develop a framework based on dynamic programming in which we formulate and evaluate different known online and offline routing policies. Next to this, we develop computation-time-efficient hybrid routing policies. To test the efficiency of the different routing policies, we develop a test bed of networks based on a number of characteristics and analyze the results in terms of routes, cost performance and calculation times. Our results show that a significant part of the cost reduction can be obtained by considering only a limited part of the network in detail. The performance of our proposed hybrid policy is only slightly worse than the optimal policy.     

融合多种上下文的室内应急疏散导航位置模型

针对室内应急响应中如何科学、高效地对人员进行个性化实时疏散导航问题进行了研究,构建了一种面向复杂室内环境下融合多种上下文的应急疏散导航位置模型。利用改进的Dijkstra算法,结合实际环境动态上下文计算出实时疏散导航路径,为不同类型用户提供地图导航、语音导航、短信导航等个性化服务,同时为应急指挥者提供辅助决策支持。并以医院为例进行了实验,实验表明基于该模型及算法能够高效计算出满足不同类型用户需求的实时疏散导航路径,可应用于医院、商场等环境的应急疏散导航与救援中。     

Comparing accuracy of second-order approximation and dynamic programming

The accuracy of the solution of dynamic general equilibrium models has become a major issue. Recent papers, in which second-order approximations have been substituted for first-order, indicate that this change may yield a significant improvement in accuracy. Second order approximations have been used with considerable success when solving for the decision variables in both small and large-scale models. Additionally, the issue of accuracy is relevant for the approximate solution of value functions. In numerous dynamic decision problems, welfare is usually computed via this same approximation procedure. However, Kim and Kim (Journal of International Economics, 60, 471–500, 2003) have found a reversal of welfare ordering when they moved from first- to second-order approximations. Other researchers, studying the impact of monetary and fiscal policy on welfare, have faced similar challenges with respect to the accuracy of approximations of the value function. Employing a base-line stochastic growth model, this paper compares the accuracy of second-order approximations and dynamic programming solutions for both the decision variable and the value function as well. We find that, in a neighborhood of the equilibrium, the second-order approximation method performs satisfactorily; however, on larger regions, dynamic programming performs significantly better with respect to both the decision variable and the value function. We want to thank Jinill Kim and Harald Uhlig for discussions and a referee of the Journal for extensive comments on a previous version of our paper.     

移动AdHoc网络中基于动态规划法的OoS路由研究

在移动AdHoc网络中,为不同的多媒体应用需求提供QoS保证已经成为一个热点问题。目前,大多数的研究者都将研究点关注于QoS路由的度量选择上,而忽视了移动AdHoc网络自身的能量局限性的问题,而能量又是影响AdHoc网络一个极其关键的因素。因此,在本文中我们使用一种动态规划算法来解决AdHoc网络的电池约束。首先,我们构建了一个基于动态规划法的QoS路由模型,然后分析了该算法的时间复杂度,最后通过仿真验证了本文提出的改进算法的优越性。     

基于启发式模拟退火的曲线多边形近似算法

针对平面曲线最优多边形近似问题,结合曲线的局部和全局特征,提出一种新的基于启发式模拟退火思想的多边形近似方法。将曲线多边形近似问题转换为最小化代价函数的问题,利用模拟退火算法对其求解最优解,并采用启发式方法将曲线的局部特征作为先验知识引入退火过程加速其收敛。通过与多种局部及全局算法的实验比较表明,该方法在数据压缩率和近似误差等方面具有更好的性能,且有效地压缩了运行时间。     

基于ACP方法的高层建筑火灾中人员疏散策略研究

高层建筑结构规模巨大、人员众多,而疏散出口数量有限,如何有效安排疏散出口人员分布,提高疏散效率,是火灾应急管理的重要研究内容. 以人为中心的疏散系统是典型的复杂系统,具有难以真实实验分析的困难. 本文基于ACP（人工系统、计算实验、平行执行）方法,以智能体技术为核心建立了人工疏散系统,基于火灾场景,利用计算实验对疏散策略进行了验证、评估,给出了实际疏散系统与人工疏散系统的平行执行实现思想. 最后,通过案例验证了方法的可行性.     

欧氏空间货郎担问题的一个多项式时间近似方案的改进与实现

货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离di,j,要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究的热点之一.在过去几十年中,这一经典问题成为许多重要算法思想的测试平台,并促使一些研究领域的出现,如多面体理论和复杂性理论.欧氏空间上的货郎担问题,结点限制在欧氏空间,距离定义为欧氏距离.即使是这样,欧氏空间上的货郎担问题仍然是NP难的.1996年,Arora提出欧氏空间上货郎担问题的第1个多项式时间近似方案.对其中货郎担问题的算法进行了改进：提出一种新的构造方法,使应用于该算法的“补丁引理”结论由常数6改进到常数3,从而使算法的时间复杂度大幅减少;同时,编程实现了该算法,并对实验结果进行了分析.     

Piecewise linear approximation of plane curves by perimeter optimization

A method for the piecewise linear approximation of a plane curve is described. An approximate curve is obtained by choosing a certain number of points from a set of sampled points of the original curve. A “point choice function” that represents the relation between the original points and the chosen points is formulated. The approximation is performed by the dynamic programming principle searching for the optimal point choice function that attains the minimal error about arc length of the curve. Evaluation of the global approximate error provides efficient curve approximations, irrespective of shape complexity, number of sampled points, and irregularity of sampling interval.     

基于动态规划的红外弱小运动目标的实时检测方法研究

文章针对低信噪比下红外弱小运动目标的特点,提出了一种正向动态规划算法。分析了算法的检测性能,并对算法实现中的一些关键问题进行了讨论。实验表明,该算法适应性强,能有效地完成对低信噪比下弱小运动目标的实时检测、识别与跟踪。     

人群疏散虚拟现实模拟系统——Guarder

人群疏散的虚拟现实模拟就是利用虚拟现实技术,在计算机生成空间中建立公共设施和人群的三维模型,设定各种可能发生的安全危机和相应的疏散预案,模拟并三维地展示人群疏散场景;通过对模拟结果进行统计分析,可以验证人群疏散应急预案的合理性和有效性.介绍了人群疏散模拟虚拟现实系统Guarder设计的核心思想,提出了技术框架,详细阐述了其中的复杂环境语义表示、群体运动仿真等关键技术,并给出了应用实例,最后列举了几个前沿研究问题.     

Bounded parallel-batch scheduling on single and multi machines for deteriorating jobs

We consider the bounded parallel-batch scheduling problem in which the processing time of a job is a simple linear function of its starting time. The objective is to minimize the makespan. When the jobs have identical release dates, we present an optimal algorithm for the single-machine problem and an fully polynomial-time approximation scheme for the parallel-machine problem. When the jobs have distinct release dates, we show that the single-machine problem is NP-hard and present an optimal algorithm for one special case.     

Optimal Routing for Maximizing the Travel Time Reliability

Optimal path problems are important in many science and engineering fields. Performance criteria may vary in coping with uncertainty, such as expectation, reliability, value at risk, etc. In this paper, we will first summarize our recent work on a dynamic programming based optimal path algorithm for maximizing the time reliability. We then study the convergence properties of the algorithm by introducing two special successive approximation sequences. Finally we will show the connection between the maximum reliability problem and the shortest and k-shortest path problems.