Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks

A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. One of the key communication operations is to broadcast a message from a source node. This paper studies the minimum latency broadcast scheduling problem in wireless ad hoc networks under collision-free transmission model. The previously best known algorithm for this NP-hard problem produces a broadcast schedule whose latency is at least 648（rmax/rmin）^2 times that of the optimal schedule, where rmax and rmin are the maximum and minimum transmission ranges of nodes in a network, respectively. We significantly improve this result by proposing a new scheduling algorithm whose approximation performance ratio is at most （1 ＋ 2rmax/rmin）^2＋32, Moreover, under the proposed scheduling each node just needs to forward a message at most once.     

An average case analysis of the minimum spanning tree heuristic for the power assignment problem

We present an average case analysis of the minimum spanning tree heuristic for the power assignment problem. The worst‐case approximation ratio of this heuristic is 2. We show that in Euclidean d‐dimensional space, when the vertex set consists of a set of i.i.d. uniform random independent, identically distributed random variables in [0,1]^d, and the distance power gradient equals the dimension d, the minimum spanning tree‐based power assignment converges completely to a constant depending only on d.     

A Neural-Tabu Search Heuristic for the Real Time Vehicle Routing Problem

The Real Time Vehicle Routing Problem RTVRP is a dynamic routing problem where requests are generated dynamically during the operation horizon without any previous knowledge. Received requests need to be answered as fast as possible and then assigned to a vehicle to be served. Due to timing constraints of the RTVRP, a solving approach should give the best compromise between the cost of the provided solution and the computation time needed to find it. In this paper, we present a neural-tabu search solving scheme for the RTVRP. The developed approach is composed by two phases; The first part consists of learning and reproducing previous routing decisions using a feed forward neural network with a particular structure. The second phase is based on a tabu search heuristic that takes its initial solution from the assignment provided by the neural module. If the reaction time is still available, the tabu search module will continue ameliorating the final solution. To evaluate the proposed approach a set of problems are simulated and solved. The obtained results are compared to those given by the First Come First Served FCFS and Nearest Neighbor NN policies and also to the optimal solutions provided by the GNU Linear Programming Kit GLPK.      

Deep generative models for vehicle speed trajectories

Generating realistic vehicle speed trajectories is a crucial component in evaluating vehicle fuel economy and in predictive control of self-driving cars. Traditional generative models rely on Markov chain methods and can produce accurate synthetic trajectories but are subject to the curse of dimensionality. They do not allow to include conditional input variables into the generation process. In this paper, we show how extensions to deep generative models allow accurate and scalable generation. Proposed architectures involve recurrent and feed-forward layers and are trained using adversarial techniques. Our models are shown to perform well on generating vehicle trajectories using a model trained on GPS data from Chicago metropolitan area.     

带有变时滞延迟和分布延迟的竞争型神经网络周期解在时间尺度上的的全局指数稳定性

In this paper, competitive neural networks with time-varying and distributed delays are investigated. By utilizing Lyapunov functional methods, the global exponential stability of periodic solutions of the neural networks is discussed on time scales. In addition, an example is given to illustrate the effectiveness of the theoretical results.     

时间窗变动的车辆调度干扰管理模型与算法

针对客户时间窗变动对原物流配送车辆调度方案造成干扰的问题,运用干扰管理思想,分析干扰事件对路径、成本和服务时间三个方面的影响,对其干扰程度加以度量;以该干扰事件对原方案造成的广义费用偏离最小为目标,建立客户时间窗变动的干扰管理模型,通过判断客户时间窗变动对原方案是否产生影响进行干扰辨识,并基于该干扰辨识结果,设计基于禁忌搜索新的调度算法;算例不仅验证了模型和算法的有效性,而且,敏感性分析也验证了其对各种不同价值货物的适用性。实验结果表明,本文提出的干扰管理模型可以全面地刻画干扰对原方案的影响,干扰处理方法优于全局重调度方法,且能够在更短时间内生成满意的物流配送车辆调度调整方案。     

Formulas and representations for cyclic Markovian networks via Palm calculus

We present an extension of the arrival theorem for the output process from a node in closed Markovian networks which we use to obtain simple representations and explicit expressions for the throughput, the distribution of the cycle time, and the joint distribution of interoutput times from a node in single class closed networks with exponential servers. Our approach uses tools from Palm calculus to obtain a recursion on the number of customers in the system. The analysis relies on a non-overtake condition and thus many of the results obtained here apply only to cyclic, single server networks. One of the surprising conclusions of our analysis is that the interoutput times that comprise the cycle time of a customer are (finitely) exchangeable, i.e., that their joint distribution is invariant under permutations. This revised version was published online in June 2006 with corrections to the Cover Date.     

具有分布时滞的非自治Cohen-Grossberg神经网络稳定性研究

对具有分布时滞的非自治Cohen-Grossberg神经网络进行了研究.通过构造适当的Lyapunov函数,利用不等式分析方法,引入多参数,得到了一系列解的一致有界性且最终有界性和全局指数稳定性的判别准则.     

基于IMO-SLFDA的大规模分布式光伏并网的智能配电网相位平衡研究

分布式光伏的大量接入智能配电网后,可能导致三相电流的失衡,进而破坏配电系统的安全稳定性。对此,本文构建了以电流不平衡和电能损失最小化为目标的含分布式光伏的配电网优化的多目标模型,旨在解决大规模分布式光伏发电并网后配电网相位平衡的问题;然后,用随机单纯形法对混合蛙跳算法进行优化,改进了蛙跳算法求解优化问题时极易陷入局部最优以及计算效率较低的缺点,并和决策算法相结合,提出适用本文算例的改进的多目标混合蛙跳决策算法,确保能以极快的搜索速度和较高的计算精度得到最优解;最后,以IEEE-123节点三相不平衡测试系统为例,通过控制变量的相关操作实现配电系统的三相平衡。对比分析基础案例和优化算例的差异,验证了本文所提算法的先进性和实用性。     

时间窗约束下的车辆路径问题多目标优化算法

讨论了带时间窗约束的车辆路径问题(VRPTW)其数学模型,分析了以遗传算法求解该类问题时的染色体表示和有关遗传操作,将VRPTw视为一个多目标优化问题,用Pareto评等技术来求解最优解,并以Solomen基准问题为例验证了该方法的有效性.结果表明:该方法与以往文献中的最好结果具有竞争性.