竞争环境下的轴-辐式集装箱海运网络设计问题

针对航运企业的重组与全球扩张引起的竞争问题,提出了竞争环境下的轴-辐式集装箱海运网络设计模型。模型采用基于路径的变量作为决策变量,利用离散函数来表示航运企业与航运联盟的竞争可吸引的流量(或客户),目的在于通过设计混合轴-辐式集装箱海运网络,实现以更低的服务成本和更短的服务时间最大化可吸引的流量,建立了枢纽港口数量约束、航线连接约束、航线中转约束、流量竞争约束等,运用多点交叉遗传算法进行求解,最后结合亚欧航线的集装箱海运市场进行实例分析,对考虑客户需求多样性与航运联盟对策下的轴-辐式集装箱海运网络进行设计,并验证了算法的计算效果。     

Design Improvements for Message Propagation in Malleable Social Networks

This study presents the formal problem definition and computational analysis of the network design improvements for idea and message propagation in both enterprise and consumer social networks (ESN and CSN, respectively). Message propagation in social networks is impacted by how messages are seeded in the network, and by propagation characteristics of the network topology itself. It has been recognized that the propagation properties of these networks can be actively influenced by network design interventions, such as the deliberate creation of new connections. We address the problem of finding cost‐effective message seeding, and identifying potential new network connections that allow improved propagation in social networks with cascade propagation. We use the hop‐constrained minimum spanning tree (HMST) model to find the seeds and possible new connections that result in networks with improved propagation properties. Moreover, we present new heuristic algorithms that substantially improve the solution quality for the HMST problem. Computational results posit that the design improvements proposed by the HMST approach can greatly improve cascade propagation performance of the networks at low cost.     

The mixed evacuation problem

A dynamic network introduced by Ford and Fulkerson is a directed graph with capacities and transit times on its arcs. The quickest transshipment problem is one of the most fundamental problems in dynamic networks. In this problem, we are given sources and sinks. Then the goal of this problem is to find a minimum time limit such that we can send the right amount of flow from sources to sinks. In this paper, we introduce a variant of this problem called the mixed evacuation problem. This problem models an emergent situation in which people can evacuate on foot or by car. The goal is to organize such a mixed evacuation so that an efficient evacuation can be achieved. In this paper, we study this problem from the theoretical and practical viewpoints. In the first part, we prove the polynomial-time solvability of this problem in the case where the number of sources and sinks is not large, and also prove the polynomial-time solvability and computational hardness of its variants with integer constraints. In the second part, we apply our model to the case study of Minabe town in Wakayama prefecture, Japan.     

A linear programming duality approach to analyzing strictly nonblocking <Emphasis Type="Italic">d</Emphasis>-ary multilog networks under general crosstalk constraints

When a switching network topology is used for constructing optical cross-connects, as in the circuit switching case, no two routes are allowed to share a link. However, if two routes share too many switching elements, then crosstalk introduced at those switching elements degrades signal quality. Vaez and Lea (IEEE Trans. Commun. 48:(2)316–323, 2000) introduced a parameter c which is the maximum number of distinct switching elements a route can share with other routes in the network. This is called the general crosstalk constraint. This paper presents a new method of analyzing strictly nonblocking multi-log networks under this general crosstalk constraint using linear programming duality.     

Separator-based data reduction for signed graph balancing

Polynomial-time data reduction is a classical approach to hard graph problems. Typically, particular small subgraphs are replaced by smaller gadgets. We generalize this approach to handle any small subgraph that has a small separator connecting it to the rest of the graph. The problem we study is the NP-hard Balanced Subgraph problem, which asks for a 2-coloring of a graph that minimizes the inconsistencies with given edge labels. It has applications in social networks, systems biology, and integrated circuit design. The data reduction scheme unifies and generalizes a number of previously known data reductions, and can be applied to a large number of graph problems where a coloring or a subset of the vertices is sought. To solve the instances that remain after reduction, we use a fixed-parameter algorithm based on iterative compression with a very effective heuristic speedup. Our implementation can solve biological real-world instances exactly for which previously only approximations were known. In addition, we present experimental results for financial networks and random networks.     

Traffic engineering of tunnel-based networks with class specific diversity requirements

Tunnel-based networks such as Multi-protocol Label switching (MPLS) are suitable for providing diversity guarantees to different service classes or customers. Based on the number of active tunnels to handle, router capabilities can be taxed due to the limited amount of memory and/or processing power of these routers. In this paper, we present a mixed-integer linear program formulation for a traffic engineering problem where such tunnel restrictions are taken into account in addition to standard capacity constraints while addressing diversity requirement of services. Due to large size of the formulation, we also present an accompanied solution approach based on Lagrangian relaxation and sub-gradient optimization. We then present results towards impact of diversity constraint upon the tunneling and capacity restrictions. We observed that the networks having higher amounts of capacity and demands with higher level of survivability are much more sensitive to number of allowed tunnels in the network. The impact is even more prominent for sparsely-connected, large-sized networks.     

A set covering approach to bus stop location

This paper considers the problem of locating bus stops in the context of a set covering problem. Zero-one integer programming models are suggested for use in the location of bus stops on new routes and for use in the location of express bus stops on current routes. The models may be used to locate the minimum number of (express) bus stops required to ensure that no passenger need walk more than a specified distance to reach an (express) bus stop. A modified version of the model is presented which enables the router to locate a specified number of (express) bus stops in such a manner that the total distance walked by all boarders is minimized.     

Entrepreneurial Marketing in Online-Netzwerken

A growing number of professionals use online social networks (e.g., Xing or LinkedIn) for business reasons by specifically promoting themselves. Especially executives and entrepreneurs use business social networks as a marketing tool in order to manage their business contacts and, thus, positioning themselves as a brand. Using on Keller’s (1993) customer-based brand equity model, we focus on the special behavior of entrepreneurs in such social networks. Based on the a large data set from a leading social network, we empirically analyze whether entrepreneurs act differently than other users and whether this strategy pays off. Based on a SUR model, we determine what the drivers for entrepreneurs’ profile views and contacts are. The results show that entrepreneurs focus on communicating their intentions and competencies and engage actively in the community. Especially participating in user groups and attending community events are key drivers for success.     

A multi-criteria approach to fair and efficient bandwidth allocation

In systems which serve many users there is a need to respect some fairness rules while looking for the overall efficiency. This applies among others to network design where a central issue is how to allocate bandwidth to flows efficiently and fairly. The so-called max–min fairness is widely used to meet these goals. However, allocating the bandwidth to optimize the worst performance may cause a large worsening of the overall throughput of the network. In this paper we show how the concepts of mult-criteria equitable optimization can effectively be used to generate various fair and efficient allocation schemes. We introduce a multi-criteria model equivalent to equitable optimization and we develop a corresponding reference point procedure to generate fair and efficient bandwidth allocations. Our analysis is focused on the nominal network design for elastic traffic that is currently the most significant traffic of IP networks. The procedure is tested on a sample network dimensioning problem for elastic traffic and its abilities to model various preferences are demonstrated.     

A joint optimization of data ferry trajectories and communication powers of ground sensors for long-term environmental monitoring

Recently, various hybrid wireless sensor networks which consist of several robotic vehicles and a number of static ground sensors have been investigated. In this kind of system, the main role of the mobile nodes is to deliver the messages produced by the sensor nodes, and naturally their trajectory control becomes a significant issue closely related to the performance of the entire system. Previously, several communication power control strategies such as topology control are investigated to improve energy-efficiency of wireless sensor networks. However, to the best of our knowledge, no communication power control strategy has been investigated in the context of the hybrid wireless sensor networks. This paper introduces a new strategy to utilize the communication power control in multiple data ferry assisted wireless sensor network for long-term environmental monitoring such that the lifetime of the sensor network is maximized. We formally define the problem of our interest and show it is NP-hard. We further prove there exists no approximation algorithm for the problem which can produce a feasible solution for every possible problem instance even though there is a feasible solution. Then, we propose heuristic algorithms along with rigorous theoretical performance analysis for both the single data ferry case and the multiple data ferry case under certain condition.     

Telecommunications Network Design—Comparison of Alternative Approaches

The design and development of the network infrastructure to support mission‐critical applications has become a critical and‐complex activity. This study explores the use of genetic algorithms (GA) for network design in the context of degree‐constrained minimal spanning tree (DCMST) problem; compares for small networks the performance of GA with a mathematical model that provides optimal solutions; and for larger networks, compares GA's performance with two heuristic methods—edge exchange and primal algorithm. Two performance measures, solution quality and computation time, are used for evaluation. The algorithms are evaluated on a wide variety of network sizes with both static and dynamic degree constraints on the network nodes. The results indicate that GA provides optimal solutions for small networks. For larger networks it provides better solution quality compared to edge exchange and primal method, but is worse than the two methods in computation time.     

Bound and exact methods for assessing link vulnerability in complex networks

Assessing network systems for failures is critical to mitigate the risk and develop proactive responses. In this paper, we investigate devastating consequences of link failures in networks. We propose an exact algorithm and a spectral lower-bound on the minimum number of removed links to incur a significant level of disruption. Our exact solution can identify optimal solutions in both uniform and weighted networks through solving a well-constructed mixed integer program. Also, our spectral lower-bound derives from the Laplacian eigenvalues an estimation on the vulnerability of large networks that are intractable for exact methods. Through experiments on both synthetic and real-world networks, we demonstrate the efficiency of the proposed methods.     

Near-optimal control policy for loss networks

In this paper, the phenomenon of the optimal management of requests of service in general networks is formulated as a control problem for a finite number of multiserver loss queues with Markovian routing. This type of problem may arise in a wide range of fields, e.g., manufacturing industries, storage facilities, computer networks, and communication systems. Using inductive approach of dynamic programming, the optimal admission control can be induced to be the functions of the number of requested service in progress. However, for large-scale network, the computational burden to find optimal control policy may be infeasible due to its involvement of the states for all stations in the networks. Hence, the idea of bottleneck modeling is borrowed to compute the near-optimal admission control policy. We reduced the scale of loss network and decreased the difference between the original and reduced models by making compensation for system parameters. A novel method is proposed in this paper to compute the compensation. Numerical results show that the near-optimal control policy demonstrates close performance to the optimal policy.     

The Effect of Misclassification Costs on Neural Network Classifiers

The potential of neural networks for classification problems has been established by numerous successful applications reported in the literature. One of the major assumptions used in almost all studies is the equal cost consequence of misclassification. With this assumption, minimizing the total number of misclassification errors is the sole objective in developing a neural network classifier. Often this is done simply to ease model development and the selection of classification decision points. However, it is not appropriate for many real situations such as quality assurance, direct marketing, bankruptcy prediction, and medical diagnosis where misclassification costs have unequal consequences for different categories. In this paper, we investigate the issue of unequal misclassification costs in neural network classifiers. Through an application in thyroid disease diagnosis, we find that different cost considerations have significant effects on the classification performance and that appropriate use of cost information can aid in optimal decision making. A cross-validation technique is employed to alleviate the problem of bias in the training set and to examine the robustness of neural network classifiers with regard to sampling variations and cost differences.     

Relay node placement in two-tiered wireless sensor networks with base stations

This paper addresses the relay node placement problem in two-tiered wireless sensor networks with base stations, which aims to deploy a minimum number of relay nodes to achieve certain coverage and connectivity requirement. Under the assumption that the communication range of the sensor nodes is no more than that of the relay node, we present a polynomial time (5+?)-approximation algorithm for the 1-coverage 1-connected problem. Furthermore, we consider the fault tolerant problem in the network, we present a polynomial time (20+?)-approximation algorithm for the 2-coverage 2-connected problem, where ? is any given positive constant. For the k-coverage 2-connected situation, we present a polynomial time (15k?10+?)-approximation algorithm.     

A combinatorial model and algorithm for globally searching community structure in complex networks

Community structure is one of the important characteristics of complex networks. In the recent decade, many models and algorithms have been designed to identify communities in a given network, among which there is a class of methods that globally search the best community structure by optimizing some modularity criteria. However, it has been recently revealed that these methods may either fail to find known qualified communities (a phenomenon called resolution limit) or even yield false communities (the misidentification phenomenon) in some networks. In this paper, we propose a new model which is immune to the above phenomena. The model is constructed by restating community identification as a combinatorial optimization problem. It aims to partition a network into as many qualified communities as possible. This model is formulated as a linear integer programming problem and its NP-completeness is proved. A qualified min-cut based bisecting algorithm is designed to solve this model. Numerical experiments on both artificial networks and real-life complex networks show that the combinatorial model/algorithm has promising performance and can overcome the limitations in existing algorithms.     

A robust branch-and-cut approach for the minimum-energy symmetric network connectivity problem

This paper considers the minimum-energy symmetric network connectivity problem (MESNC) in wireless sensor networks. The aim of the MESNC is to assign transmission power to each sensor node such that the resulting network, using only bidirectional links, is connected and the total energy consumption is minimized. We first present two new models of this problem and then propose new branch-and-cut algorithms. Based on an existing formulation, we present the first model by introducing additional constraints. These additional constraints allow us to relax certain binary variables to continuous ones and thus to reduce significantly the number of binary variables. Our second model strengthens the first one by adding an exponential number of lifted directed-connectivity constraints. We present two branch-and-cut procedures based on these proposed improvements. The computational results are reported and show that our approaches, using the proposed formulations, can efficiently solve instances with up to 120 nodes, which significantly improve our ability to solve much larger instances in comparison with other exact algorithms in the literature.     

Multimodal hub location and hub network design

Through observations from real life hub networks, we introduce the multimodal hub location and hub network design problem. We approach the hub location problem from a network design perspective. In addition to the location and allocation decisions, we also study the decision on how the hub networks with different possible transportation modes must be designed. In this multimodal hub location and hub network design problem, we jointly consider transportation costs and travel times, which are studied separately in most hub location problems presented in the literature. We allow different transportation modes between hubs and different types of service time promises between origin–destination pairs while designing the hub network in the multimodal problem. We first propose a linear mixed integer programming model for this problem and then derive variants of the problem that might arise in certain applications. The models are enhanced via a set of effective valid inequalities and an efficient heuristic is developed. Computational analyses are presented on the various instances from the Turkish network and CAB data set.     

Modeling and solution of practical management problems through netforms

This paper shows some useful schemes to graphically depict netform models of practical inventory problems. We begin with a simple inventory problem and then progress to more comprehensive representations of an inventory system by network and netform model techniques. Some text books mention that very basic inventory problems may be modeled as networks. But they usually offer very little instruction in the actual development of a network inventory model, and invariably conclude that network models can't accommodate the complications of the vast majority of realworld inventory problems. Further, they completely fail to convey the modeling power available to more general netform (network-related formulation) techniques. As text books catch up to the recent innovations now being applied in practical settings, this deficiency will change. Our purpose is to introduce the fundamental ideas and to provide an understanding of the possibilities inherent in these model innovations. We begin from first principles, so that no prior familiarity with network model representations is necessary to follow the exposition. Because of a heavy reliance on pictorial illustrations (another of the unique advantages of networks and netforms), we have also avoided the use of complex mathematical notation, and develop the key concepts by informal discussion.     

电信社群网络用户行为特征及演化分析

通过某地移动客户的通话数据构建电信社群网络,并对其网络结构进行分析,发现电信社群网络并不满足小世界特征,而且该网络的演化是以边生长为主导。基于该结构特征,构建电信社群网的演化模型,发现网络非均匀性与节点的朋友圈数目、连接概率和新增节点边数有关。其研究结论对新运营商通过营销策略的制定,推动电信社群网络快速向小世界网络演化具有积极的现实意义。