VRPTW的扰动恢复及其TABU SEARCH算法

本文对带时间窗的车辆路线安排扰动恢复问题进行了讨论,分析了各种可能的扰动:增加减少客户,时间窗、客户需求及路线可行性的扰动,构造了扰动模型.利用禁忌搜索算法对问题进行求解,同时通过对模型参数重新设置,得到了多个满足要求的不同的解,这样使解更具有实际可行性和有效性.     

网络路由收敛性能测试研究

在网络建设和运行中,采用测试的方法对其性能进行评估对于网络的正常运营具有重要的意义.本文研究了网络路由收敛性能测试方法,为得到路由收敛性能指标,对OSPF和iBGP的路由收敛时间进行了测量.提出了一种简化的路由收敛时间测量方法,通过测量数据平面的传输性能指标,对路由控制平面的收敛时间进行估算.该方法对于测试设备要求不高,实施简单方便.采用该方法在CERNET2投入运营之前对其进行了路由性能测试,实验结果表明CERNET2在路由变化时具有较好的路由收敛性能.     

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.     

The Downs-Thomson Paradox: Existence, Uniqueness and Stability of User Equilibria

Consider a network where two routes are available for users wishing to travel from a source to a destination. On one route (which could be viewed as private transport) service slows as traffic increases. On the other (which could be viewed as public transport) the service frequency increases with demand. The Downs-Thomson paradox occurs when improvements in service produce an overall decline in performance as user equilibria adjust. Using the model proposed by Calvert [10], with a ⋅|M|1 queue corresponding to the private transport route, and a bulk-service infinite server queue modelling the public transport route, we give a complete analysis of this system in the setting of probabilistic routing. We obtain the user equilibria (which are not always unique), and determine their stability.AMS subject classification: 60K30, 90B15, 90B20, 91A10, 91A13This revised version was published online in June 2005 with corrected coverdate     

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.     

Solving a multiobjective location routing problem with a metaheuristic based on tabu search. Application to a real case in Andalusia

In this work we present a multiobjective location routing problem and solve it with a multiobjective metaheuristic procedure. In this type of problem, we have to locate some plants within a set of possible locations to meet the demands of a number of clients with multiple objectives. This type of model is used to solve a problem with real data in the region of Andalusia (Spain). Thus, we study the location of two incineration plants for the disposal of solid animal waste from some preestablished locations in Andalusia, and design the routes to serve the different slaughterhouses in this region. This must be done while taking into account certain economic objectives (start-up, maintenance, and transport costs) and social objectives (social rejection by towns on the truck routes, maximum risk as an equity criterion, and the negative implications for towns close to the plant).     

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

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

Linux系统QoS原理与应用

介绍Linux系统中网络服务质量的原理与应用。全文分两个部分,第一部分探讨了Linux系统上QoS的工作原理,Linux在系统内核中实现了QoS,其QoS管理的核心是流量控制,由队列规定、类和过滤器三部分构成;后一部分介绍了Linux系统提供的配置与监控流量控制的用户程序-tc,并给出了一个实际应有的具体案例。     

A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows

Vehicle routing problem with time windows (VRPTW) involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. The problem is solved by optimizing routes for the vehicles so as to meet all given constraints as well as to minimize the objectives of traveling distance and number of vehicles. This paper proposes a hybrid multiobjective evolutionary algorithm (HMOEA) that incorporates various heuristics for local exploitation in the evolutionary search and the concept of Pareto's optimality for solving multiobjective optimization in VRPTW. The proposed HMOEA is featured with specialized genetic operators and variable-length chromosome representation to accommodate the sequence-oriented optimization in VRPTW. Unlike existing VRPTW approaches that often aggregate multiple criteria and constraints into a compromise function, the proposed HMOEA optimizes all routing constraints and objectives simultaneously, which improves the routing solutions in many aspects, such as lower routing cost, wider scattering area and better convergence trace. The HMOEA is applied to solve the benchmark Solomon's 56 VRPTW 100-customer instances, which yields 20 routing solutions better than or competitive as compared to the best solutions published in literature.     

Approximating the single source unsplittable min-cost flow problem

In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed along a single path so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed a given budget. This problem has been introduced by Kleinberg [7] and generalizes several NP-complete problems from various areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing, and virtual-circuit routing. Kolliopoulos and Stein [9] and Dinitz, Garg, and Goemans [4] developed algorithms improving the first approximation results of Kleinberg for the problem of minimizing the violation of edge capacities and for other variants. However, known techniques do not seem to be capable of providing solutions without also violating the cost constraint. We give the first approximation results with hard cost constraints. Moreover, all our results dominate the best known bicriteria approximations. Finally, we provide results on the hardness of approximation for several variants of the problem. Received: August 23, 2000 / Accepted: April 20, 2001?Published online October 2, 2001