The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. The process is repeated with different samples to obtain candidate solutions along with statistical estimates of their optimality gaps.We present a detailed computational study of the application of the SAA method to solve three classes of stochastic routing problems. These stochastic problems involve an extremely large number of scenarios and first-stage integer variables. For each of the three problem classes, we use decomposition and branch-and-cut to solve the approximating problem within the SAA scheme. Our computational results indicate that the proposed method is successful in solving problems with up to 2¹⁶⁹⁴ scenarios to within an estimated 1.0% of optimality. Furthermore, a surprising observation is that the number of optimality cuts required to solve the approximating problem to optimality does not significantly increase with the size of the sample. Therefore, the observed computation times needed to find optimal solutions to the approximating problems grow only linearly with the sample size. As a result, we are able to find provably near-optimal solutions to these difficult stochastic programs using only a moderate amount of computation time.     

Performance Analysis for Mobile Ad Hoc Network in Random Graph Models with Spatial Reuse

In this paper,we present a random graph model with spatial reuse for a mobile ad hoc network(MANET) based on the dynamic source routing protocol.Many important performance parameters of theMANET are obtained,such as the average flooding distance (AFD),the probability generating function of theflooding distance,and the probability of a flooding route to be symmetric.Compared with the random graphmodel without spatial reuse,this model is much more effective because it has a smaller value of AFD and alarger probability for finding a symmetric valid route.     

求解无线传感器网络路由问题的蚁群最优化算法及其收敛性

首先将无线传感器网络的路由问题转化成求解最小Steiner树问题,然后给出了求解无线传感器网络路由的蚁群优化算法,并对算法的收敛性进行了证明．最后对找到最优解后信息素值的变化进行了分析．即在限制信息素取值的条件下,当迭代次数充分大时,该算法能以任意接近于1的概率找到最优解,并且当最优解找到后,最优树边上的信息素单调增加,而最优解以外边上的信息素在有限步达到最小值．     

Vehicle and personnel routing optimization in the service sector: application to water distribution and treatment

We present an overview of the author’s Ph.D. thesis, supervised by P. Dejax and N. Bostel, which was defended in February 2006 at école des Mines de Nantes, France. The thesis is written in French, and is available at . It was conducted in the context of a research contract with a water distribution company. In a first section, we define multiperiod routing problems for service technicians. In a second section, we present some heuristics and a memetic algorithm used to solve these problems. The third section introduces optimal and near-optimal approaches based on column generation. Finally, we present some applications to the real-life case. The methods presented in Sects. 2, 3 and 4 were tested over several sets of problems, based on real-life statistics provided by the company.      

Markovian network processes: Congestion-dependent routing and processing

A Markovian network process describes the movement of discrete units among a set of nodes that process the units. There is considerable knowledge of such networks, often called queueing networks, in which the nodes operate independently and the routes of the units are independent. The focus of this study, in contrast, is on networks with dependent nodes and routings. Examples of dependencies are parallel processing across several nodes, blocking of transitions because of capacity constraints on nodes, alternate routing of units to avoid congestion, and accelerating or decelerating the processing rate at a node depending on downstream congestion. We introduce a general network process representing the numbers of units at the nodes and derive its equilibrium distribution. This distribution takes the form of a product of functions of vectors in which the arguments of the functions satisfy an interchangeability property. This new type of distribution may apply to other multi-variate processes as well. A basic idea in our approach is a linking of certain micro-level balance properties of the network routing to the processing rates at the nodes. The link is via routing-balance partitions of nodes that are inherent in any network. A byproduct of this approach is a general characterization of blocking of transitions without the restriction that the process is reversible, which had been a standard assumption. We also give necessary and sufficient conditions under which a unit moving in the network sees a time average for the unmoved units (called the MUSTA property). Finally, we discuss when certain flows between nodes in an open network are Poisson processes.This research was sponsored in part by Air Force Office of Scientific Research contract 84-0367.     

A two-phase algorithm for the partial accessibility constrained vehicle routing problem

In the partial accessibility constrained vehicle routing problem, a route can be covered by two types of vehicles, i.e. truck or truck + trailer. Some customers are accessible by both vehicle types, whereas others solely by trucks. After introducing an integer programming formulation for the problem, we describe a two-phase heuristic method which extends a classical vehicle routing algorithm. Since it is necessary to solve a combinatorial problem that has some similarities with the generalized assignment problem, we propose an enumerative procedure in which bounds are obtained from a Lagrangian relaxation. The routine provides very encouraging results on a set of test problems.     

计算机网络技术的近期发展

目的 论述和分析计算机网络技术的近期发展。方法 通过分析交换技术,路由技术,第３层交换技术,实时信息传输技术和异步传输模式（ＡＴＭ）技术的特点,揭示各项网络技术适用面。结果 指出交换技术解决带宽问题,第３层交换技术解决路由瓶颈问题,ＡＴＭ等技术解雇实时信息传送问题。结论各项网技术都是针对某些实际需要提出的,都有其适用范围,用户选择时要从需求出发才能充分发挥网络的作用。     

多通道微位移报警装置

介绍了以89C52为核心的多通道微位移报警装置的整体结构、工作原理及检测系统的软硬件设计．微处理器实时检测多路传感器的位移值，超过设定的值时系统进行报警，并通过通信接口将检测数据上传至计算机，同时利用计算机的多媒体优势进行报警．实际运行结果表明：该系统稳定性好，精确度高，达到了预期的性能指标要求．     

交错波纹板原表面换热器通道内对流换热的数值研究

对具有正弦波形通道交叉排列的原表面换热器多通道单元内三维稳态层流流动与换热特性进行了分析，利用数值模拟方法探讨了上下波纹板交错角θ、波纹相对节距P／H(波长／波高)及雷诺数RP对流动与换热性能的影响．结果表明：在入口段流动与换热性能的变化较大，此变化在沿主流方向第4个单元后基本消失；在水力直径基本相同的前提下，阻力系数厂及平均努谢尔特数Nu随θ的增大而增大；f及Nu在P／H为1．5～3．1的范围内随P／H的增大而增大，在RP大于900及P／H为3．1～4．0时随P／H的增大却开始减小；壁面局部Nu的最大值发生在主流尾部以及与流体出口邻近的2个入口处附近，最小值在上下波纹板的接触点上产生。     

Mobile Ad Hoc NetWork与Internet互联的技术研究

分析了移动IP和AODV协议的工作机理．对MANET与Internet互联的关键技术，包括协议转换、地址分配、网关发现、路由发现与数据传输等问题进行了详细的讨论．并对今后的研究工作进行了展望。