Efficient solution of a class of location–allocation problems with stochastic demand and congestion

We consider a class of location–allocation problems with immobile servers, stochastic demand and congestion that arises in several planning contexts: location of emergency medical clinics; preventive healthcare centers; refuse collection and disposal centers; stores and service centers; bank branches and automated banking machines; internet mirror sites; web service providers (servers); and distribution centers in supply chains. The problem seeks to simultaneously locate service facilities, equip them with appropriate capacities, and allocate user demand to these facilities such that the total cost, which consists of the fixed cost of opening facilities with sufficient capacities, the access cost of users׳ travel to facilities, and the queuing delay cost, is minimized. Under Poisson user demand arrivals and general service time distributions, the problem is set up as a network of independent M/G/1 queues, whose locations, capacities and service zones need to be determined. The resulting mathematical model is a non-linear integer program. Using simple transformation and piecewise linear approximation, the model is linearized and solved to ϵ-optimality using a constraint generation method. Computational results are presented for instances up to 400 users, 25 potential service facilities, and 5 capacity levels with different coefficients of variation of service times and average queueing delay costs per customer. The results indicate that the proposed solution method is efficient in solving a wide range of problem instances.     

Modeling and analysis of the effects of QoS and reliability on pricing, profitability, and risk management in multiperiod grid-computing networks

In this paper we develop a network equilibrium model for optimal pricing and resource allocation in Computational Grid Network. We consider a general network economy model with Grid Resource Providers, Grid Resource Brokers and Grid Users. The proposed framework allows for the modeling and theoretical analysis of Computational Grid Markets that considers a non-cooperative behavior of decision-makers in the same tier of the grid computing network (such as, for example, Grid Resource Providers) as well as cooperative behavior between tiers (between Resource Providers and Grid Brokers). We introduce risk management into the decision making process by analyzing the decision-marker's reliability and quality of service (QoS) requirement. We analyze resource allocation patterns as well as equilibrium price based on demand, supply, and cost structure of the grid computing market network. We specifically answer the following questions with several numerical examples: How do system reliability levels affect the QoS levels of the service providers and brokers under competition? How do system reliability levels affect the profits of resource providers and brokers in a competitive market? How do system reliability levels influence the pricing of the services in a competitive environment? How do users' service request types, QoS requirements, and timing concerns affect users' behaviors, costs and risks in equilibrium? How does the market mechanism allocate resources to satisfy the demands of users? We find that for users who request same services certain timing flexibility can not only reduce the costs but also lower the risks. The results indicated that the value of QoS can be efficiently priced based on the heterogeneous service demands.     

Facilitating the development of cross-platform software via automated code synthesis from web-based programming resources

When a mobile application is supported on multiple major platforms, its market penetration is maximized. Such cross-platform native applications essentially deliver the same core functionality, albeit within the conventions of each supported platform. Maintaining and evolving a cross-platform native application is tedious and error-prone, as each modification requires replicating the changes for each of the application׳s platform-specific variants. Syntax-directed source-to-source translation proves inadequate to alleviate the problem, as native API access is always domain-specific.In this paper, we present a novel approach—Native-2-Native—that uses program transformations performed on one platform to automatically synthesize equivalent code blocks to be used on another platform. When a programmer modifies the source version of an application, the changes are captured. Based on the changes, Native-2-Native identifies the semantic content of the source code block and formulates an appropriate query to search for the equivalent target code block using popular web-based programming resources. The discovered target code block is then presented to the programmer as an automatically synthesized target language source file for further fine-tuning and subsequent integration into the mobile application׳s target version. We evaluate the proposed method using common native resources, such as sensors, network access, and canonical data structures. We show that our approach can correctly synthesize more than 74% of iOS code from the provided Android source code and 91% of Android code from the provided iOS source code. The presented approach effectively automates the process of extracting the source code block׳s semantics and discovering existing target examples with the equivalent functionality, thus alleviating some of the most laborious and intellectually tiresome programming tasks in modern mobile development.     

A heuristic algorithm for a supply chain׳s production-distribution planning

In this paper we consider the problem of planning the production and distribution in a supply chain. The situation consists in a set of distribution centers seeking to serve to a set of retailers; these distribution centers are supplied by a set of plants trying to minimize the operation and transportation costs. The problem is formulated as a bilevel mathematical problem where the upper level consists of deciding the amount of product sent from the distribution centers to the retailers trying to minimize the transportation costs and also by considering the costs of acquiring the products that come from the plants. Meanwhile the lower level consists in minimizing the plants׳ operations cost meeting the demand grouped in the distribution centers. We propose a heuristic algorithm based on Scatter Search that considers the Stackelberg׳s equilibrium; numerical tests show that our proposed algorithm improves the existing best known results in the literature.     

Competitive Liner Shipping Network Design

We present a solution method for the liner shipping network design problem which is a core strategic planning problem faced by container carriers. We propose the first practical algorithm which explicitly handles transshipment time limits for all demands. Individual sailing speeds at each service leg are used to balance sailing speed against operational costs, hence ensuring that the found network is competitive on both transit time and cost. We present a matheuristic for the problem where a MIP is used to select which ports should be inserted or removed on a route. Computational results are presented showing very promising results for realistic global liner shipping networks. Due to a number of algorithmic enhancements, the obtained solutions can be found within the same time frame as used by previous algorithms not handling time constraints. Furthermore, we present a sensitivity analysis on fluctuations in bunker price which confirms the applicability of the algorithm.     

Designing and constructing networks under uncertainty in the construction stage: Definition and exact algorithmic approach

The present work proposes a novel Network Optimization problem whose core is to combine both network design and network construction scheduling under uncertainty into a single two-stage robust optimization model. The first-stage decisions correspond to those of a classical network design problem, while the second-stage decisions correspond to those of a network construction scheduling problem (NCS) under uncertainty. The resulting problem, which we will refer to as the Two-Stage Robust Network Design and Construction Problem (2SRNDC), aims at providing a modeling framework in which the design decision not only depends on the design costs (e.g., distances) but also on the corresponding construction plan (e.g., time to provide service to costumers). We provide motivations, mixed integer programming formulations, and an exact algorithm for the 2SRNDC. Experimental results on a large set of instances show the effectiveness of the model in providing robust solutions, and the capability of the proposed algorithm to provide good solutions in reasonable running times.     

基于云计算数字标牌管理平台的研究与设计

针对目前数字标牌网络系统的安装、运行、维修成本较高的情况,提出将云计算技术应用到数字标牌领域的设计思想．研究一种基于云计算智能数字标牌系统．它使信息推送更加精准化、个性化、低碳化。通过研究云计算体系结构和云服务层次的特点,实现了基于云计算智能数字标牌系统的设计。该设计解决了安装和运行数字标牌网络的低成本．实现多租户不同的个性化需求,为信息的时速性、多样化、特殊性带来极大的提升,正好满足了当前网络化数字标牌的市场需求．     

Airline network design and hub location problems

Due to the popularity of hub-and-spoke networks in the airline and telecommunication industries, there has been a growing interest in hub location problems and related routing policies. In this paper, we introduce flow-based models for designing capacitated networks and routing policies. No a priori hub-and-spoke structure is assumed. The resulting networks may suggest the presence of “hubs”, if cost efficient. The network design problem is concerned with the operation of a single airline with a fixed share of the market. We present three basic integer linear programming models, each corresponding to a different service policy. Due to the difficulty of solving (even small) instances of these problems to optimality, we propose heuristic schemes based on mathematical programming. The procedure is applied and analyzed on several test problems consisting of up to 39 U.S. cities. We provide comments and partial recommendations on the use of hubs in the resulting network structures.     

Complex log file synthesis for rapid sandbox-benchmarking of security- and computer network analysis tools

Today Information and Communications Technology (ICT) networks are a dominating component of our daily life. Centralized logging allows keeping track of events occurring in ICT networks. Therefore a central log store is essential for timely detection of problems such as service quality degradations, performance issues or especially security-relevant cyber attacks. There exist various software tools such as security information and event management (SIEM) systems, log analysis tools and anomaly detection systems, which exploit log data to achieve this. While there are many products on the market, based on different approaches, the identification of the most efficient solution for a specific infrastructure, and the optimal configuration is still an unsolved problem. Today׳s general test environments do not sufficiently account for the specific properties of individual infrastructure setups. Thus, tests in these environments are usually not representative. However, testing on the real running productive systems exposes the network infrastructure to dangerous or unstable situations. The solution to this dilemma is the design and implementation of a highly realistic test environment, i.e. sandbox solution, that follows a different – novel – approach. The idea is to generate realistic network event sequence (NES) data that reflects the actual system behavior and which is then used to challenge network analysis software tools with varying configurations safely and realistically offline. In this paper we define a model, based on log line clustering and Markov chain simulation to create this synthetic log data. The presented model requires only a small set of real network data as an input to understand the complex real system behavior. Based on the input׳s characteristics highly realistic customer specified NES data is generated. To prove the applicability of the concept developed in this work, we conclude the paper with an illustrative example of evaluation and test of an existing anomaly detection system by using generated NES data.     

Detection of redundant expressions: A precise,efficient, and pragmatic algorithm in SSA

Detection of redundant expressions in a program based on values is a well researched problem done with a view to eliminate redundancies so as to improve run-time efficiency of the program. The problem entails detection of equivalent expressions in a program. An iterative data-flow analysis algorithm is presented to detect equivalent expressions in SSA for the purpose of detection of redundancies. The challenge is detection of equivalence of expressions at join points, in polynomial time, that enable detection of later redundancies. This is achieved by the use of value ϕ-function. The proposed algorithm is as precise as Kildall׳s in detection of redundant expressions and takes only polynomial time. The algorithm is implemented in LLVM. An experimental analysis demonstrates that the algorithm is as precise as Kildall׳s and outperforms some existing algorithms in terms of run-time efficiency indicating its practical significance.     

Line planning on tree networks with applications to the Quito Trolebús system

We discuss an optimization model for the line planning problem in public transport in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the computational complexity of this problem for tree network topologies as well as several categories of line operations that are important for the Quito Trolebús system. In practice, these instances can be solved quite well, and significant optimization potentials can be demonstrated.     

A hybrid Lagrangean heuristic with GRASP and path-relinking for set k-covering

The set multicovering or set k-covering problem is an extension of the classical set covering problem, in which each object is required to be covered at least k times. The problem finds applications in the design of communication networks and in computational biology. We describe a GRASP with path-relinking heuristic for the set k-covering problem, as well as the template of a family of Lagrangean heuristics. The hybrid GRASP Lagrangean heuristic employs the GRASP with path-relinking heuristic using modified costs to obtain approximate solutions for the original problem. Computational experiments carried out on 135 test instances show experimentally that the Lagrangean heuristics performed consistently better than GRASP as well as GRASP with path-relinking. By properly tuning the parameters of the GRASP Lagrangean heuristic, it is possible to obtain a good trade-off between solution quality and running times. Furthermore, the GRASP Lagrangean heuristic makes better use of the dual information provided by subgradient optimization and is able to discover better solutions and to escape from locally optimal solutions even after the stabilization of the lower bounds, when other Lagrangean strategies fail to find new improving solutions.     

Minimum disruption service composition and recovery in mobile ad hoc networks

The dynamic nature of mobile ad hoc networks poses fundamental challenges to the design of service composition schemes that can satisfy the end-to-end quality of service requirements and minimize the effect of service disruptions caused by dynamic link and node failures. Although existing research on mobile ad hoc networks has focused on improving reliability, little existing work has considered service deliveries spanning multiple components. Moreover, service composition strategies proposed for wireline networks (such as the Internet) are poorly suited for highly dynamic wireless ad hoc networks.This paper proposes a new service composition and recovery framework designed to achieve minimum service disruptions for mobile ad hoc networks. The framework consists of two tiers: service routing, which selects the service components that support the service path, and network routing, which finds the optimal network path that connects these service components. Our framework is based on the disruption index, which is a novel concept that characterizes different service disruption aspects, such as frequency and duration, that are not captured adequately by conventional metrics, such as reliability and availability.Using the definition of disruption index, we formulate the problem of minimum-disruption service composition and recovery (MDSCR) as a dynamic programming problem and analyze the properties of its optimal solution for ad hoc networks with known mobility plan. Based on the derived analytical insights, we present our MDSCR heuristic algorithm for ad hoc networks with uncertain node mobility. This heuristic algorithm approximates the optimal solution with one-step lookahead prediction, where service link lifetime is predicted based on node location and velocity using linear regression. We use simulations to evaluate the results of our algorithm in various network environments. The results validate that our algorithm can achieve better performance than conventional methods.     

多等级蓄意攻击下的第三方物流可靠性网络设计

在考虑多等级蓄意攻击的情况下,研究第三方物流(3PL)可靠性网络设计问题.建立问题的多层优化模型:3PL网络设计模型在可靠性约束下通过开设不同安全等级的物流设施来最小化总物流成本;蓄意攻击模型选择不同等级的攻击策略使网络的服务水平最低;网络流决策模型可最大化网络受攻击后的服务能力.根据问题模型的特点,设计改进两层人工蜂群(ABC)算法,上层ABC算法求解3PL网络设计问题,下层ABC算法求解蓄意攻击优化问题.网络流决策问题则通过网络流算法进行求解.最后,通过仿真实验来验证所提出模型的合理性及算法的有效性.     

Branch Network and Modular Service Optimization for Community Banking

In the information society, what is clearly changing is the role and image of bank branches in order to satsify in a more efficient way customers' needs. This paper develops an integrated approach to assist the bank's management in reconfiguring a branch network according to the dictates of the market. We are seeking the optimum number of branches and the optimum mix of services that each branch should offer in order to maximize the revenue–generating measures of the branches within a community. The problem is modeled using a linear program that accounts for community performance as a function of performance variables that are explained by a set of external and internal factors, which reflect community characteristics and modular branch banking parameters, respectively. The relationships between factor and performance variables are identified using regression analysis. An iterative algorithm allows convergence to a solution that provides the best configuration of branches after all possible branch mergers and modular branch adjustments are accomplished.     

有时间窗物流配送路径优化问题的并购算法

通过对市场资源优化配置中市场行为的了解,提取企业在市场中的行为之一并购行为的精华,并简化并购行为的模型。根据计算得到的企业劣信度,企业间进行合理的并购和重组,也是对市场资源再整合,使资源得到充分的优化配置,进而提高整体企业的市场竞争力。在建立有时间窗物流配送路径优化问题的数学模型基础上,构造有时间窗物流配送路径优化的并购算法模型。该模型包含编码、初始化、预处理、劣信度评估、并购操作、重组操作以及选择操作等七个模块。在Solomon数据集上进行多次实验,并与目前实验已经获得的最优解做比较,获取有时间窗物流配送路径优化问题的最优解或近似最优解。     

Enforcing Service-Level Constraints in Supply Chains With Assembly Operations

We study a feedforward supply network that involves assembly operations. We compute optimal stock levels which minimize inventory costs and maintain stockout probabilities below given desirable levels (service-level constraints). To that end, we develop large deviations approximations for inventory costs and service level constraints and formulate the stock level selection problem as a nonlinear programming problem which can be solved using standard techniques. This results in significant computational savings when compared to exhaustive search using simulation. Our distributional assumptions are general enough to include temporal dependencies in the demand and production processes. We leverage the solution of the inventory control problem in the design of supply contracts under explicit service-level constraints     

Exploring interactive style and user experience design for social web of things of Chinese users: A case study in Beijing

This study designed an interactive IoT (Internet of Things) service on mobile devices based upon the concept of Social Web of Things (SWoT), with which users can interact with IoT in the same way they use the social network services. In order to integrate IoT into Chinese daily use, this study also investigated how Chinese users interact with things and IoT technologies. A four-phase study among users living in Beijing was conducted with a lifecycle of user-centered design. Results revealed that SWoT could activate users׳ intuitive understanding of social network services, and make the interaction with SWoT natural in their own ways. Users living in Beijing tended to be utility-oriented and highly emphasized efficiency; they were distinctive in uncertainty avoidance and preference of hierarchical way of managing things. Our results suggested implications for the design of user-centered IoT systems in China, and shed light on improvements for the performance of IoT systems and balance of requirements between users and system design.     

集成整车物流系统的网络规划问题研究

综合考虑运输、库存、设施、服务质量等决策因素，建立了整车物流网络规划集成优化模型，针对由工厂、集货中心和分销中心构成的基本物流网络，提出了用于运输路径优化的流预测算法，并嵌入到遗传算法，解决了适应值的计算难点，给出了基于流预测的遗传算法求解框架．通过实例分析了运输规模效应、库存控制策略、服务质量指标等因素对物流网络结构设计方案的影响。     

Study on continuous network design problem using simulated annealing and genetic algorithm

In general, a continuous network design problem (CNDP) is formulated as a bi-level program. The objective function at the upper level is defined as the total travel time on the network, plus total investment costs of link capacity expansions. The lower level problem is formulated as a certain traffic assignment model. It is well known that such bi-level program is non-convex and non-differentiable and algorithms for finding global optimal solutions are preferable to be used in solving it. Simulated annealing (SA) and genetic algorithm (GA) are two global methods and can then be used to determine the optimal solution of CNDP. Since application of SA and GA on continuous network design on real transportation network requires solving traffic assignment model many times at each iteration of the algorithm, computation time needed is tremendous. It is important to compare the efficacy of the two methods and choose the more efficient one as reference method in practice. In this paper, the continuous network design problem has been studied using SA and GA on a simulated network. The lower level program is formulated as user equilibrium traffic assignment model and Frank–Wolf method is used to solve it. It is found that when demand is large, SA is more efficient than GA in solving CNDP, and much more computational effort is needed for GA to achieve the same optimal solution as SA. However, when demand is light, GA can reach a more optimal solution at the expense of more computation time. It is also found that increasing the iteration number at each temperature in SA does not necessarily improve solution. The finding in this example is different from [Karoonsoontawong, A., & Waller, S. T. (2006). Dynamic continuous network design problem – Linear bilevel programming and metaheuristic approaches. Network Modeling 2006 Transportation Research Record (1964) (pp. 104–117)]. The reason might be the bi-level model in this example is nonlinear while the bi-level model in their study is linear.