The multiple disposal facilities and multiple inventory locations rollon–rolloff vehicle routing problem

In the Multiple disposal facilities and multiple inventory locations rollon–rolloff vehicle routing problem (M-RRVRP), one of the very important pickup and disposal problems in the sanitation industry, tractors move large trailers, one at a time, between customer locations such as construction sites and shopping centers, disposal facilities and inventory locations. In this paper, we model the M-RRVRP as a time constrained vehicle routing problem on a multigraph (TVRP-MG). We then formulate the TVRP-MG as a set partitioning problem with an additional constraint and describe an exact method for solving the TVRP-MG. This exact method is based on a bounding procedure that combines three lower bounds derived from different relaxations of the formulation of the problem. Further, we obtain a valid upper bound and show how this bounding procedure can transform the solution of a Lagrangean lower bound into a feasible solution.     

Shipment partitioning and routing to minimize makespan in a transportation network

This paper addresses the problem of partitioning and transporting a shipment of known size through an n-node public transportation network with known scheduled departure and arrival times and expected available capacities for each departure. The objective is to minimize the makespan of shipping. The problem while practical in its scope, has received very little attention in the literature perhaps because of the concentration of research in vehicle routing without regard to partitioning and partitioning without regard to routing. A general non-linear programming model is developed. The model is then converted into a linear model through the Routing First and Assignment Second approach. This approach is different from the general decomposition approaches since they normally do not guarantee optimality. However, the linear model still involves a large number of constraints, and solution is not attempted here. Instead, three heuristics are proposed for solving the problem. Two of the heuristics use iterative techniques to evaluate all possible paths. The third heuristic uses a max-flows approach based upon aggregated capacities to reduce the size of the network presented to the other heuristics. This allows for a good starting point for other heuristics, and may impact the total computational effort. We find that the heuristics developed perform well because in the case of networks that are not congested, they find the optimal solution.     

A two-level location–allocation problem in designing local access fiber optic networks

This paper deals with a two-level facility location–allocation problem on tree topology arising from the design of access networks. The access network design problem seeks to find an optimal location of switch and allocation of demands such that the total cost of switch and fiber cable is minimized, while satisfying switch port constraint, switch capacity constraint, and no-split routing constraint. The problem is formulated as a mixed-integer programming model and alternative formulations are developed by the reformulation-linearization technique (RLT) for improving computational effectiveness. By exploiting the tree structure of the problem, we develop some valid inequalities that have complementary strength and devise separation problems for finding effective valid inequalities that cut off fractional LP solutions. Also, we develop an effective MIP-based tree partitioning heuristic for finding good quality solutions for large size problems. Computational results demonstrate the efficacy of the valid inequalities and the proposed heuristic.     

基于图多层K路划分的仿真节点映射策略

为了提高网络仿真系统中,多物理服务器情况下,服务器资源的利用率,提出一种基于图多层K路划分的仿真节点映射策略。首先对仿真网络拓扑图进行多层K路划分,将节点映射问题转化为图划分问题,然后依据划分结果将仿真节点映射到物理服务器。经过试验表明,相对于随机映射策略,该策略在保证物理服务器负载均衡的同时,可以有效减少物理服务器资源的消耗。     

Distributed stochastic multi-vehicle routing in the Euclidean plane with no communications

This paper presents an algorithm for the multi-vehicle routing problem with no communications among the vehicles. The scenario consists in a convex Euclidean mission space, where targets are generated according to a Poisson distribution in time and to a generic continuous spatial distribution. The targets must be visited by the vehicles, which, therefore, must act in coordination. Even if no communications are required, the proposed routing strategy succeeds in effectively partitioning the mission space among the vehicles: at low target generation rates, the algorithm leads to the well-known centroidal Voronoi tessellation, whereas at high target generation rates, simulation results show that it has better performances with respect to a reference algorithm with no communications among vehicles.     

用神经网络求解性能驱动的电路划分问题

文中考虑一种以连线代价最小目标的,以面积和时延为约束的,划分块与划分块之间有确定和拓扑关系的电路划分问题,提出了一个性能驱动电路划分的均场退火算法。算法通过换拉矩阵把问题映射为神经网络,并建立了包含优化目标项,面积约束项和时延约束项的能量函数,再用均场退火方程失代求解。     

Star p-hub center problem and star p-hub median problem with bounded path lengths

We consider two problems that arise in designing two-level star networks taking into account service quality considerations. Given a set of nodes with pairwise traffic demand and a central hub, we select p hubs and connect them to the central hub with direct links and then we connect each nonhub node to a hub. This results in a star/star network. In the first problem, called the Star p-hub Center Problem, we would like to minimize the length of the longest path in the resulting network. In the second problem, Star p-hub Median Problem with Bounded Path Lengths, the aim is to minimize the total routing cost subject to upper bound constraints on the path lengths. We propose formulations for these problems and report the outcomes of a computational study where we compare the performances of our formulations.     

A branch-and-cut algorithm for two-level survivable network design problems

This paper approaches the problem of designing a two-level network protected against single-edge failures. The problem simultaneously decides on the partition of the set of nodes into terminals and hubs, the connection of the hubs through a backbone network (first network level), and the assignment of terminals to hubs and their connection through access networks (second network level). We consider two survivable structures in both network levels. One structure is a two-edge connected network, and the other structure is a ring. There is a limit on the number of nodes in each access network, and there are fixed costs associated with the hubs and the access and backbone links. The aim of the problem is to minimize the total cost. We give integer programming formulations and valid inequalities for the different versions of the problem, solve them using a branch-and-cut algorithm, and discuss computational results. Some of the new inequalities can be used also to solve other problems in the literature, like the plant cycle location problem and the hub location routing problem.     

Stochastic routing in ad-hoc networks

We investigate a network routing problem where a probabilistic local broadcast transmission model is used to determine routing. We discuss this model's key features, and note that the local broadcast transmission model can be viewed as soft handoff for an ad-hoc network. We present results showing that an index policy is optimal for the routing problem. We extend the network model to allow for control of transmission type, and prove that the index nature of the optimal routing policy remains unchanged. We present three distributed algorithms which compute an optimal routing policy, discuss their convergence properties, and demonstrate their performance through simulation.     

One-dimensional partitioning for heterogeneous systems: Theory and practice

We study the problem of one-dimensional partitioning of nonuniform workload arrays, with optimal load balancing for heterogeneous systems. We look at two cases: chain-on-chain partitioning, where the order of the processors is specified, and chain partitioning, where processor permutation is allowed. We present polynomial time algorithms to solve the chain-on-chain partitioning problem optimally, while we prove that the chain partitioning problem is NP-complete. Our empirical studies show that our proposed exact algorithms produce substantially better results than heuristics, while solution times remain comparable.     

A Hopfield neural network approach for power optimization of real-time operating systems

The RTOS (Real-Time Operating System) is a critical component in the SoC (System-on-a-Chip), which is the main body for consuming total system energy. Power optimization based on hardware–software partitioning of a RTOS (RTOS–Power partitioning) can significantly minimize the energy consumption of a SoC. This paper presents a new model for RTOS–Power partitioning, which helps in understanding the essence of the RTOS–Power partitioning techniques. A discrete Hopfield neural network approach for implementing the RTOS–Power partitioning is proposed, where a novel energy function, operating equation and coefficients of the neural network are redefined. Simulations are carried out with comparison to other optimization techniques. Experimental results demonstrate that the proposed method can achieve higher energy savings up to 60% at relatively low costs of less than 4k PLBs while increasing the performance compared to the purely software realized SoC–RTOS.     

基于位置信息的移动SNS数据动态划分复制算法

现有社交网络数据划分算法大多关注于好友关系和交互关系,忽略了位置信息,造成基于位置查询的响应时间较长。针对该问题,设计了一种移动社交网络双层社交图模型,该模型考虑了移动社交网络中用户交互行为的位置依赖性特点;并在此基础上提出了一种基于位置信息的移动社交网络数据动态划分复制算法MSDPR,该算法采用改进的K-Means算法对位置信息进行聚类,再根据聚类结果对数据进行划分,并利用社交关系进行数据的复制。实验结果表明:MSDPR算法在移动社交网络环境下能够有效地提高本地访问率,降低访问延迟,并且在动态加入数据时具有较好的适应性。     

一种基于离散Hopfield神经网络的RTOS功耗优化方法

RTOS(Real-Time Operating System,实时操作系统)是SoC(System-on-a-Chip,系统芯片或片上系统)的一个重要组成部分,其功耗一般约占整个系统功耗30～40%的比例,而基于软/硬件划分的RTOS功耗优化方法(简称RTOS-Power划分)能够明显地减少SoC的功耗.因此,文中首先引入了RTOS-Power划分问题的一个新模型,这有助于理解RTOS-Power划分的本质.然后,提出了一种基于离散Hopfield神经网络的RTOS-Power划分方法,重新定义了神经网络的神经元表示、能量函数、运行方程和系数.最后,对该方法进行了仿真实验,并同遗传算法和蚂蚁算法进行了性能比较.实验结果表明:该文提出的方法能够以相对较小的代价(FPGA开销小于4K个可编程逻辑块)取得高达60%的功耗节省,同时,与纯软件实现的RTOS相比,系统性能也得到了相应的提高.     

Models and solution methods for the uncapacitated r‐allocation p‐hub equitable center problem

Hub networks are commonly used in telecommunications and logistics to connect origins to destinations in situations where a direct connection between each origin–destination (o‐d) pair is impractical or too costly. Hubs serve as switching points to consolidate and route traffic in order to realize economies of scale. The main decisions associated with hub‐network problems include (1) determining the number of hubs (p), (2) selecting the p‐nodes in the network that will serve as hubs, (3) allocating non‐hub nodes (terminals) to up to r‐hubs, and (4) routing the pairwise o‐d traffic. Typically, hub location problems include all four decisions while hub allocation problems assume that the value of p is given. In the hub median problem, the objective is to minimize total cost, while in the hub center problem the objective is to minimize the maximum cost between origin–destination pairs. We study the uncapacitated (i.e., links with unlimited capacity) r‐allocation p‐hub equitable center problem (with) and explore alternative models and solution procedures.     

MCM划分的自组织神经网络

本文在提出一个直接和间接相联模块间相似性的表示方法的基础上，提出了一个基于自组织神经网络的性能驱动ＭＣＭ划分的神经学习方法。算法求解如何在高层设计中将功能模块分配到ＭＣＭ芯片中。算法不仅考虑了模块间的相似关系，还考虑了ＭＣＭ的版图结构；具有芯片间连线数目最少和时钟周期最短双重优化目标；能使连线尽量产生在相邻近的芯片之间；能满足时延、散热和面积约束。文中还提出了一个层次神经网络模型和面积约束下的ＭＣ     

An efficient integer programming formulation for the assignment of base stations to controllers in cellular networks

In mobile networks, the assignment of base stations to controllers when planning the network has a strong impact on network performance. In a previous paper, the authors formulated the assignment of base stations to packet controllers in GSM-EDGE Radio Access Network (GERAN) as a graph partitioning problem, which was solved by a heuristic method. In this paper, an exact method is presented to find optimal solutions that can be used as a benchmark. The proposed method is based on an effective re-formulation of the classical integer linear programming model of the graph partitioning problem, which is solved by the branch-and-cut algorithm in a commercial optimization package. Performance assessment is based on an extensive set of problem instances built from data of a live network. Preliminary analysis shows some properties of the graphs in this problem justifying the limitations of heuristic approaches and the need for more sophisticated methods. Results show that the proposed method outperforms classical heuristic algorithms used for benchmarking, even under runtime constraints. Likewise, it improves the efficiency of exact methods previously applied to similar problems in the cellular field.     

Multi-product Capacitated Single-Allocation Hub Location Problems: Formulations and Inequalities

In this paper we extend the classical capacitated single-allocation hub location problem by considering that multiple products are to be shipped through the network. We propose a unified modeling framework for the situation in which no more than one hub can be located in each node. In particular, we consider the case in which all hubs are dedicated to handling a single-product as well as the case in which all hubs can handle all products. The objective is to minimize the total cost, which includes setup costs for the hubs, setup costs for each product in each hub and flow routing costs. Hubs are assumed to be capacitated. For this problem several models are proposed which are based on existing formulations for the (single-product) capacitated single-allocation hub location problem. Additionally, several classes of inequalities are proposed in order to strengthen the models in terms of the lower bound provided by the linear relaxation. We report results of a set of computational experiments conducted to test the proposed models and their enhancements.     

可充电无线传感网络能量均衡路由算法

针对可充电无线传感网络中的能量均衡路由问题,提出在稳定功率无线充电和监测数据收集网络场景下的多路径路由算法和机会路由算法,以实现网络的能量均衡。首先,通过电磁传播理论构建了无线传感节点的充电和接收功率关系模型;然后,考虑网络中无线传感节点的发送能耗和接收能耗,基于上述充电模型将网络能量均衡的路由问题转化为网络节点运行时间的最大最小化问题,通过线性规划得到的各链路流量用以指导路由中数据流量分配;最后,考虑一种更加现实的低功耗的场景,并提出了一种基于机会路由的能量均衡路由算法。实验结果表明,与最短路径路由（SPR）和期望周期最短路由（EDC）算法相比较,所提出的两种路由算法均能有效提高采集能量的利用率和工作周期内的网络生命周期。     

The q-Ad Hoc Hub Location Problem for Multi-modal Networks

This research proposes a spatial optimization problem over a multi-modal transportation network, termed the q-Ad-hoc hub location problem (AHLP), to utilize alternative hubs in an ad-hoc manner in the wake of a hub outage. The model aims to reorganize the spatial structure of disrupted networks: unaffected hubs are utilized as ad-hoc hubs through which alternative routes connect supply and demand nodes. As a case study, the AHLP is applied to a multi-modal freight transport system connecting international destinations with the United States. The models are utilized to establish a new ranking methodology for critical infrastructure by combining metrics capturing nodal criticality and network resilience and recuperability. The results show that the AHLP is both an effective and practical recovery approach for a hub network to respond to the potential disruptions of hubs and a novel methodology for ranking critical infrastructure.     

Routing and scheduling decisions in the hierarchical hub location problem

Hubs are facilities that consolidate and disseminate flow in many-to-many distribution systems. The hub location problem considers decisions that include the locations of hubs in a network and the allocations of demand (non-hub) nodes to these hubs. We propose a hierarchical multimodal hub network structure, and based on this network, we define a hub covering problem with a service time bound. The hierarchical network consists of three layers in which we consider a ring-star-star (RSS) network. This multimodal network may have different types of vehicles in each layer. For the proposed problem, we present and strengthen a mathematical model with some variable fixing rules and valid inequalities. Also, we develop a heuristic solution algorithm based on the subgradient approach to solve the problem in more reasonable times. We conduct the computational analysis over the Turkish network and the CAB data sets.