Service network design for freight railway transportation: the Italian case

In this paper, we present a case study on freight railway transportation in Italy, which is a by-product of research collaboration with a major Italian railway company. We highlight the main features of the Italian reality and propose a customized mathematical model to design the service network, that is, the set of origin-destination connections. More specifically, the model suggests the services to provide, the number of trains travelling on each connection, the number of cars and their type. We consider both full and empty freight car movements and take handling costs into account. All decisions are taken in order to minimize the total costs. The quality of service is guaranteed by satisfying all the transportation demand and by implicitly minimizing the waiting time of cars at intermediate railway stations. Our approach yields to a multi-commodity network design problem with a concave cost function. To solve this problem, we implement a specialized tabu search procedure. Computational results on realistic instances show a significant improvement over current practice.     

Infrastructure security games

Infrastructure security against possible attacks involves making decisions under uncertainty. This paper presents game theoretic models of the interaction between an adversary and a first responder in order to study the problem of security within a transportation infrastructure. The risk measure used is based on the consequence of an attack in terms of the number of people affected or the occupancy level of a critical infrastructure, e.g. stations, trains, subway cars, escalators, bridges, etc. The objective of the adversary is to inflict the maximum damage to a transportation network by selecting a set of nodes to attack, while the first responder (emergency management center) allocates resources (emergency personnel or personnel-hours) to the sites of interest in an attempt to find the hidden adversary. This paper considers both static and dynamic, in which the first responder is mobile, games. The unique equilibrium strategy pair is given in closed form for the simple static game. For the dynamic game, the equilibrium for the first responder becomes the best patrol policy within the infrastructure. This model uses partially observable Markov decision processes (POMDPs) in which the payoff functions depend on an exogenous people flow, and thus, are time varying. A numerical example illustrating the algorithm is presented to evaluate an equilibrium strategy pair.     

网络安全漏洞信息披露中多元参与主体行为策略演化博弈分析

全球网络威胁日趋严峻,作为网络安全事件产生的根源之一,网络安全漏洞越来越被重视,对漏洞的披露已是国家网络安全应急体系建设的重要内容之一。本文构建了网络安全漏洞共享平台、软件厂商及黑客之间的三方博弈模型,并从演化博弈角度对模型进行了分析和数值模拟,确立了稳定均衡点存在的条件。研究结果表明:不同参数初始值对三方博弈结果存在显著差异,软件质量越差,平台越倾向于“封闭披露”策略;对漏洞发现者的支付积极影响软件厂商“注册会员”倾向,对黑客的“努力攻击”倾向产生负面影响;随披露成本的上升,平台更倾向于采纳“封闭披露”策略;预期损失过大,软件厂商倾向于“注册会员”策略。     

Effect of local information within network layers on the evolution of cooperation in duplex public goods games

Traditional works of public goods game (PGG) are often studied in simplex networks where agents play games through the same type of social interactions. In order to promote cooperation against the defection in PGGs in simplex network environment, many mechanisms have been proposed from different perspectives, such as the volunteering mechanisms, and the punishment and reward approaches. However, due to diverse types of interactions between agents in reality, the study of PGG should also consider the characteristic of multiplexity of networks. Hence, we firstly model the public goods game in the duplex network (for simplification of analysis, the duplex network is considered), in which agents have two types of social interactions, and thus the network is modeled as two network layers. This type of PGG is naturally named as duplex public goods game (D-PGG), in which agents can select one of the network layers to allocate their limited resources. Then for the new game environment (D-PGG), we propose a novel perspective to promote cooperation: degrading the information integrity, i.e., agents get information just from one network layer (local information) rather than from the whole duplex network (global information) in the evolution process. Finally, through theoretical analyses and simulations, we find that if agents imitate based on the local information of the payoff in the evolution, cooperation can be generally promoted; and the extent of promotion depends on both the network structure and the similarity of the network layers.     

基于CVaR的危险品公铁联运路径选择研究

公铁联运在危险品的多式联运中扮演着重要角色,为了降低危险品公铁联运风险,提高危险品公铁联运的安全性,危险品公铁联运的路径选择至关重要。本文运用条件风险价值(CVaR)理论,在对危险品公铁联运网络进行变形的基础上构建了考虑决策者风险规避程度的危险品公铁联运路径选择模型,设计了求解该模型的算法,并进行了算例分析。研究结果表明:通过该模型及其算法,可根据决策者对所需运输的危险品的运输风险规避程度,在危险品公铁联运网络中快速地选出使危险品公铁联运风险最小的运输路径和运输方式;决策者的风险规避程度会对危险品公铁联运过程中的运输路径和运输方式的选择产生重要影响。     

网络信息系统中信息安全防御资源分配策略分析——基于约束理论视角

安全经济性是企业信息安全防御决策的重要依据,在网络信息系统中企业需要权衡如何在众多不同信息资源节点间实施防御资源的合理分配。本文首先构建了无安全资源约束下的安全防御决策模型,研究企业在信息安全防御中如何来优化分配其防御资源,得出不同信息节点存在防御阀值以及各节点的相对经济防御水平值;在此模型基础上增加了安全防御资源约束条件,分析不同信息资源节点的防御价值、损失预期、攻击概率等因素对决策的影响,得出企业在不同节点上的防御优先级以及防御过程中投入资源量等相关结论。     

A polynomial expression for the Owen value in the maintenance cost game

The class of maintenance cost games was introduced in 2000 to deal with a cost allocation problem arising in the reorganization of the railway system in Europe. The main application of maintenance cost games regards the allocation of the maintenance costs of a facility among the agents using it. To that aim it was first proposed to utilize the Shapley value, whose computation for maintenance cost games can be made in polynomial time. In this paper, we propose to model this cost allocation problem as a maintenance cost game with a priori unions and to use the Owen value as a cost allocation rule. Although the computation of the Owen value has exponential complexity in general, we provide an expression for the Owen value of a maintenance cost game with cubic polynomial complexity. We finish the paper with an illustrative example using data taken from the literature of railways management.     

An improved local branching approach for train formation planning

The train formation plan (TFP) determines routing and frequency of trains, and assigns the demands to trains. In this paper, an improved local branching algorithm is proposed for the TFP model in Iranian railway. This solution strategy is exact in nature, although it is designed to improve the heuristic behavior of the mixed integer programming (MIP) solver at hand. In the local branching algorithm, additional constraints are built in the model for the binary variables, but in the improved local branching algorithm, the additional constraints are built in the model for integer variables. A state-of-the-art method is applied for parameter tuning using design of experiments approach. To evaluate the proposed solution method, we have simulated and solved twenty test problems. The results show the efficiency and effectiveness of the proposed approach. The proposed algorithm is implemented for Iranian Railway network as a case study.     

Community structure-based trilateral stackelberg game model for privacy protection

Location-based services are widely used in mobile applications, which not only bring convenience, but also cause serious privacy concerns. Based on the characteristics of social network, this work proposes a cooperative protection architecture to model the relationship among users, communities and location-based service. Furthermore, in order to construct K anonymity set, a novel community structure-based trilateral Stackelberg game model is developed for K-anonymity protection. In addition, an optimization method based on the proposed model is designed by the backward induction process. Finally, the security and the performance under different situations such as the anonymity parameter K and the community structure parameter overlapping weights are analyzed. The analysis results indicate that the proposed model and the optimization method are effective for privacy protection and can achieve high secure in location-based services.     

基于DEA的二阶段网络系统的固定成本分摊方法

结合DEA和博弈的思想研究二阶段网络系统的固定成本分摊问题,将分摊成本作为新的投入,可以证明存在某种分摊使DMU整体效率达到最优,在此基础上考虑各个DMU之间以及DMU内部之间的博弈,首先建立讨价还价乘积最大化模型,求出各DMU唯一的分摊解,然后建立DMU子系统之间的讨价还价模型,给出子系统的分摊解,最终的分摊方案满足系统效率和子系统效率为1,与现有的方法相比具有一定的优势.     

GRASP algorithms for the robust railway network design problem

This paper analyzes the solvability of a railway network design problem and its robust version. These problems are modeled as integer linear programming problems with binary variables, and their solutions provide topological railway networks maximizing the trip coverage in the presence of a competing mode, both assuming that the network works fine and that links can fail, respectively. Since these problems are computationally intractable for realistic sizes, GRASP heuristics are proposed for finding good feasible solutions. The results obtained in a computational experience indicate that our GRASP algorithms are suitable for railway network design problems.     

基于DEA-博弈论模型的铁路电子车票实名制查验评价分析

将基于数据包络分析(DEA)模型和纳什讨价还价博弈论结合, 作为一种合作博弈方法, 对铁路电子车票实名制的查验进行了综合评价, 为准确评估铁路电子车票实名制查验的效率, 加强铁路客运服务水平提供决策判断。本文以20个不同等级的铁路车站为研究对象, 分人工和机器两大类, 选取身份证购票比例、通勤员工购票比例、临时身份证购票比例, 以及人工查验旅客数/小时/通道、机器查验的通过人数/闸机/小时、闸机人脸自动识别比例和延误比例等7个指标作为投入指标, 选取人、证、票三证合一的实名制查验比例作为产出指标, 基于数据包络分析(DEA)和纳什讨价还价博弈论结合的合作博弈模型, 从人工查验和机器查验两个角度对铁路电子车票实名制查验进行统一综合评价。案例结果表明, 铁路电子车票实名制查验效率呈现出人工查验和机器查验效率不均衡的态势; 车站人脸识别闸机的数量投入与所需闸机数量的不匹配是造成实名制查验效率下降的主要原因。根据评价结果, 从人工和机器查验两个角度提出了可行建议, 促进了铁路电子车票实名制查验效率的进一步提升。     

Modeling networked systems using the topologically distributed bounded rationality framework

In networked systems research, game theory is increasingly used to model a number of scenarios where distributed decision making takes place in a competitive environment. These scenarios include peer‐to‐peer network formation and routing, computer security level allocation, and TCP congestion control. It has been shown, however, that such modeling has met with limited success in capturing the real‐world behavior of computing systems. One of the main reasons for this drawback is that, whereas classical game theory assumes perfect rationality of players, real world entities in such settings have limited information, and cognitive ability which hinders their decision making. Meanwhile, new bounded rationality models have been proposed in networked game theory which take into account the topology of the network. In this article, we demonstrate that game‐theoretic modeling of computing systems would be much more accurate if a topologically distributed bounded rationality model is used. In particular, we consider (a) link formation on peer‐to‐peer overlay networks (b) assigning security levels to computers in computer networks (c) routing in peer‐to‐peer overlay networks, and show that in each of these scenarios, the accuracy of the modeling improves very significantly when topological models of bounded rationality are applied in the modeling process. Our results indicate that it is possible to use game theory to model competitive scenarios in networked systems in a way that closely reflects real world behavior, topology, and dynamics of such systems. © 2016 Wiley Periodicals, Inc. Complexity 21: 123–137, 2016     

Network interdiction to minimize the maximum probability of evasion with synergy between applied resources

In this paper, we model and solve the network interdiction problem of minimizing the maximum probability of evasion by an entity traversing a network from a given source to a designated terminus, while incorporating novel forms of superadditive synergy between resources applied to arcs in the network. Inspired primarily by operations to coordinate Iraqi and U.S. security forces seeking to interdict an evader attempting to avoid detection while transiting part of the nearly rectilinear street network in East Baghdad, this study motivates and examines either linear or concave (nonlinear) synergy relationships between the applied resources within our formulations. We also propose an alternative model for sequential overt and covert deployment of subsets of interdiction resources, and conduct theoretical as well as empirical comparative analyses between models for purely overt (with or without synergy) and composite overt-covert strategies to provide insights into absolute and relative threshold criteria for recommended resource utilization. Our empirical results confirm the value of tactical patience regarding decisions on the covert utilization of resources for network interdiction. Furthermore, considering non-integral and integral resource allocations, we identify (theoretically and empirically) parametric characteristics of instances that exhibit the relative worth of employing partially covert operations. Under the relatively more practical scenario involving integral resource allocations, we demonstrate that the composite overt-covert strategy of deploying resources has a greater potential to improve over a purely overt resource deployment strategy, both with and without synergy, particularly when costs are positively correlated, resources are plentiful, and a sufficiently high ratio of covert to overt resources exists. Moreover, should an interdictor be able to ascertain an optimal evader path, the potential and magnitude of this relative improvement for the overt-covert resource allocation strategy is significantly greater.     

A Stackelberg game model for resource allocation in cargo container security

This paper presents a game theoretic model that analyzes resource allocation strategies against an adaptive adversary to secure cargo container transportation. The defender allocates security resources that could interdict an unauthorized weapon insertion inside a container. The attacker observes the defender’s security strategy and chooses a site to insert the weapon. The attacker’s goal is to maximize the probability that the weapon reaches its target. The basic model includes a single container route. The results in the basic model suggest that in equilibrium the defender should maintain an equal level of physical security at each site on the cargo container’s route. Furthermore, the equilibrium levels of resources to interdict the weapon overseas increase as a function of the attacker’s capability to detonate the weapon remotely at a domestic seaport. Investment in domestic seaport security is highly sensitive to the attacker’s remote detonation capability as well. The general model that includes multiple container routes suggests that there is a trade-off between the security of foreign seaports and the physical security of sites including container transfer facilities, container yards, warehouses and truck rest areas. The defender has the flexibility to shift resources between non-intrusive inspections at foreign seaports and physical security of other sites on the container route. The equilibrium is also sensitive to the cost effectiveness of security investments.     

An Ergodic Algorithm for the Power-Control Games for CDMA Data Networks

In this paper, we consider power control for the uplink of a direct-sequence code-division multiple-access data network. In the uplink, the purpose of power control is for each user to transmit enough power so that it can achieve the required quality of service without causing unnecessary interference to other users in the system. One method that has been very successful in solving this purpose for power control is the game-theoretic approach. The problem for power control is modified as a Nash equilibrium problem in which each user can choose its transmit power in order to maximize its own utility, and a Nash equilibrium is an ideal solution of the power-control game. We present a noncooperative power-control game in which each user can choose the transmit power in a way that it gets the sufficient signal-to-interference-plus-noise ratio and maximizes its own utility. To ensure the existence of a solution, we also propose the variational inequality problem which is connected with the proposed game. On a linear receiver, we deal with the matched filter receiver. Next we present a new ergodic algorithm for the proposed power control because the existing iterative algorithms can not be applied effectively to the proposed power control. We also present convergence analysis for the proposed algorithm. In addition, applying the proposed algorithm to the proposed power control, we provide numerical examples for the transmit power, the signal-to-interference-plus-noise ratio and so on. Numerical results for the proposed algorithm shall show that as compared with the existing power-control game and its method, all users in the network can enjoy the sufficient signal-to-interference-plus-noise ratio and achieve the required quality of service.      

Multi-period reverse logistics network design for used refrigerators

This paper focuses on the design of a multi-stage reverse logistics network for product recovery. Different recovery options such as product remanufacturing, component repairing and material recycling are simultaneously considered. Initially, we propose a mixed integer linear programming model – with a profit maximization objective – for the network design problem. The structure of the product, by way of bill of materials (BOM), is also incorporated into the proposed model in order to analyze the flow at component and material levels. Sensitivity analysis is carried out to study the effects of variations in the values of the input parameters such as product return quantity, unit transportation cost per unit distance, and unit processing cost. The analysis shows that the design decisions of different facilities considerably change even for 5–20%% variations in input parameter values. This led to the development of a refined mathematical model which incorporates variations in the different input parameter values over time. The new model provides a unified design for the entire planning horizon and has been validated with the design of a used refrigerator recovery network.     

恐怖分子入侵阻止网络的双层规划建模与禁忌搜索分析

“一带一路”战略加深了我国与邻国的合作交流,也为境外恐怖分子的潜入提供可乘之机。为防止恐怖分子潜入,提出一类新的恐怖分子入侵阻止网络设计问题,充分考虑恐怖分子的计算能力,通过决策有限安检资源在边境交通网络中的最优分配来降低袭击风险。首先,将该问题构造为双层规划模型,上层规划是政府的阻止网络设计问题,下层规划是恐怖分子的袭击节点选择和入侵路径优化问题;其次,设计一类用禁忌搜索处理上层规划,并结合下层规划直接求解的混合算法;最后,结合南疆实例进行仿真分析,结果发现:恐怖分子计算能力越强,网络城市节点受袭风险越大;政府最优阻断方案随恐怖分子计算能力强弱变化而变化,但存在一定共性原则;增加阻断资源投入可降低袭击风险,但两者存在“边际效用递减”关系。     

A robust P2P streaming architecture and its application to a high quality live-video service

This paper explores the design of a P2P architecture that sends real-time video over the Internet. The aim is to provide good quality levels in a highly dynamic P2P topology, where the frequent connections/disconnections of the nodes makes it difficult to offer the Quality-of-Experience (QoE) needed by the client.We study a multi-source streaming approach where the stream is decomposed into several flows sent by different peers to each client including some level of redundancy, in order to cope with the fluctuations in network connectivity. We employ the recently proposed PSQA technology for evaluating automatically the perceived quality at the client side. We introduce a mathematical programming model to maximize the global expected QoE of the network (evaluated using PSQA), selecting a P2P connection scheme which enhances topology robustness. In addition, we provide an approximated algorithm to solve the proposed model, and we apply it to solve a case study based on real life data.     

Representation of finite games as network congestion games

Weighted network congestion games are a natural model for interactions involving finitely many non-identical users of network resources, such as road segments or communication links. However, in spite of their special form, these games are not fundamentally special: every finite game can be represented as a weighted network congestion game. The same is true for the class of (unweighted) network congestion games with player-specific costs, in which the players differ in their cost functions rather than their weights. The intersection of the two classes consists of the unweighted network congestion games. These games are special: a finite game can be represented in this form if and only if it is an exact potential game.