Equilibria for networks with malicious users

We consider the problem of characterizing user equilibria and optimal solutions for selfish routing in a given network. We extend the known models by considering malicious behavior. While selfish users follow a strategy that minimizes their individual cost, a malicious user will use his flow through the network in an effort to cause the maximum possible damage to the overall cost. We define a generalized model, present characterizations of flows at equilibrium and prove bounds for the ratio of the social cost of a flow at equilibrium over the cost when centralized coordination among users is allowed. An extended abstract of this work appeared in the Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC) 2003. G. Karakostas’ research was supported by an NSERC Discovery research grant and MITACS. Part of this research was done when Viglas was a postdoctoral fellow at the University of Toronto, Canada.     

Formulations and Valid Inequalities for the Heterogeneous Vehicle Routing Problem

We consider the vehicle routing problem where one can choose among vehicles with different costs and capacities to serve the trips. We develop six different formulations: the first four based on Miller-Tucker-Zemlin constraints and the last two based on flows. We compare the linear programming bounds of these formulations. We derive valid inequalities and lift some of the constraints to improve the lower bounds. We generalize and strengthen subtour elimination and generalized large multistar inequalities.     

基于伪态协议的量子密钥分配系统研究

采用包含两个伪态和一个信号态的双伪态协议分析了量子密钥分配系统的性能,比较了双伪态（真空态—弱伪态）和单伪态协议条件下密钥生成率与通信距离的关系,分析了信号态的强度、量子比特误码率、单光子的增益和单光子的误码率对系统密钥生成率的影响,得出密钥生成率的最优化条件,为实现实用安全的量子密钥分配系统奠定理论基础. 关键词： 伪态协议 量子密钥生成率 量子比特误码率     

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.     

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.     

GPS/LEO掩星正则变换反演方法

利用无线电全息方法, 如正则变换方法或全谱反演方法, 可以有效地解决大气多路径条件下GPS掩星信号的反演问题. 本文采用正则变换方法反演掩星资料, 模拟仿真反演结果显示正则变换方法可以准确地反演包含大气多路径效应的信号. 在模拟信号的相位中加入不同程度的高斯相位噪声后, 正则变换方法的反演结果会受到不同程度的影响. 用正则变换方法对2007年第71天至73天共约4500个COSMIC数据进行处理. 将其折射率反演结果和atmPrf资料 (利用全谱反演方法计算得到) 一起, 与对应的ECMWF 分析场资料进行统计比较, 结果表明: 在5 km以下, 正则变换方法计算的折射率的相对误差的平均值普遍大于atmPrf资料. 其原因可能为: 正则变换方法将信号从LEO轨迹后传播至辅助屏, 造成孔径缩小, 精度下降. 同时也讨论了信号截断对低对流层中反演精度和掩星个数的影响. 关键词： 无线电掩星 大气多路径 多相位屏技术 正则变换方法     

Heuristics for the multi-depot petrol station replenishment problem with time windows

In the multi-depot petrol station replenishment problem with time windows (MPSRPTW), the delivery of petroleum products stored in a number of different petroleum depots to a set of petrol distribution stations has to be optimized. Each depot has its own fleet of heterogeneous and compartmented tank trucks. Stations specify their demand by indicating the minimum and maximum quantities to be delivered for each ordered product and require the delivery within a predetermined time window. Several inter-related decisions must be made simultaneously in order to solve the problem. For this problem, the set of feasible routes to deliver all the demands, the departure depot for each route, the quantities of each product to be delivered, the assignment of these routes to trucks, the time schedule for each trip, and the loading of the ordered products to different tanks of the trucks used need to be determined. In this paper, we propose a mathematical model that selects, among a set of feasible trips, the subset that allows the delivery of all the demands while maximizing the overall daily net revenue. If this model is provided with all possible feasible trips, it determines the optimal solution for the corresponding MPSRPTW. However, since the number of such trips is often huge, we developed a procedure to generate a restricted set of promising feasible trips. Using this restricted set, the model produces a good but not necessarily optimal solution. Thus the proposed solution process can be seen as a heuristic. We report the results of the extensive numerical tests carried out to assess the performance of the proposed heuristic. In addition, we show that, for the special case of only one depot, the proposed heuristic outperforms a previously published solution method.     

An adaptive large neighborhood search heuristic for the Pollution-Routing Problem

The Pollution-Routing Problem (PRP) is a recently introduced extension of the classical Vehicle Routing Problem with Time Windows which consists of routing a number of vehicles to serve a set of customers, and determining their speed on each route segment so as to minimize a function comprising fuel, emission and driver costs. This paper presents an adaptive large neighborhood search for the PRP. Results of extensive computational experimentation confirm the efficiency of the algorithm.     

考虑订单取件时间和柔性时间窗的取送货车辆路径问题

研究了同城配送中考虑订单取货时间和柔性时间窗的取送货车辆路径问题,考虑同城配送中订单起终点,订单取货时间和订单配送的柔性时间窗,车容量限制等因素。首先构建以配送成本与超时惩罚成本之和最小化为目标的混合整数线性模型。其次,设计了含多种有效不等式及其对应分离算法的改进分支切割算法对该模型进行精确求解。最后通过实验测试分析了不等式的性能,验证了算法的有效性,实验表明适当的减少车辆数和增大装载能力能够有效的减少成本。     

State-Dependent Coupling in General Networks

In this paper we extend a result which holds for the class of networks of quasireversible nodes to a class of networks constructed by coupling Markov chains. We begin with a network in which the transition rates governing the stochastic behaviour of the individual nodes depend only on the state of the node. Assuming that the network has an invariant measure, we construct another network with transition rates at each node depending on the state of the entire network, and obtain its invariant measure.