Search

Traffic optimization normally improves flow conditions at the expense of increased vehicles’ emissions. This paper proposes a bi-objective optimization approach to address this situation. In contrast to existing literature, this study considers environmental and congestion impacts of Network Design Problems (NDPs) using the Markov chain traffic assignment approach instead of user equilibrium. The NDP model selectively reverses roads’ directions to improve network performance. The model is optimized by simultaneously minimizing maximum traffic density and total vehicles’ emissions cost using non-dominated sorting genetic algorithm. A realistic city example was used to demonstrate the approach’s efficiency. Results showed that a compromise solution between the two objectives is more practical than single-objective optimization solutions.

Traffic optimization normally improves flow conditions at the expense of increased vehicles' emissions. This paper proposes a bi-objective optimization approach to address this situation. In contrast to existing literature, this study considers environmental and congestion impacts of Network Design Problems (NDPs) using the Markov chain traffic assignment approach instead of user equilibrium. The NDP model selectively reverses roads' directions to improve network performance. The model is optimized by simultaneously minimizing maximum traffic density and total vehicles' emissions cost using non-dominated sorting genetic algorithm. A realistic city example was used to demonstrate the approach's efficiency. Results showed that a compromise solution between the two objectives is more practical than single-objective optimization solutions. Nomenclature BPR Bureau of public roads CO Carbon Monoxide GA Genetic algorithm GHG Greenhouse gas MCTA Markov chain traffic assignment NDP Network Design Problem NOx Nitrogen oxides TEC Total emissions cost UE User equilibrium VOC Volatile organic compounds NSGA-II Non-dominated sorting genetic algorithm [ABSTRACT FROM AUTHOR]

We study the approximability of two natural NP-hard problems. The first problem is congestion minimization in directed networks. In this problem, we are given a directed graph and a set of source-sink pairs. The goal is to route all the pairs with minimum congestion on the network edges. The second problem is machine scheduling, where we are given a set of jobs, and for each job, there is a list of intervals on which it can be scheduled. The goal is to find the smallest number of machines on which all jobs can be scheduled such that no two jobs overlap in their execution on any machine. Both problems are known to be O(log n/ log log n)-approximable via the randomized rounding technique of Raghavan and Thompson [1987]. However, until recently, only Max SNP hardness was known for each problem. We make progress in closing this gap by showing that both problems are Ω(log log n)-hard to approximate unless NP ⊆ DTIME(nO(log log log n)). [ABSTRACT FROM AUTHOR]

We study a basic resource allocation problem that arises in cloud computing environments. The physical network of the cloud is represented as a graph with vertices representing servers and edges corresponding to communication links. A workload is a set of processes with processing requirements and mutual communication requirements. The workloads arrive and depart over time, and the resource allocator must map each workload upon arrival to the physical network. We consider the objective of minimizing the congestion. We show that solving a subproblem (SingleMap) about mapping a single workload to the physical graph essentially suffices for solving the general problem. In particular, an α-approximation algorithm for SingleMap gives an O(α log nD) competitive algorithm for the general problem, where n is the number of nodes in the physical network and D is the maximum to minimum workload duration ratio. We then consider the SingleMap problem for two natural classes of workloads, namely depth-d trees and complete-graph workloads. For depth-d trees, we give an nO(d) time O(d2 log(nd))-approximation algorithm based on a strong LP relaxation inspired by the Sherali-Adams hierarchy. For complete graphs, we give a polylogarithmic approximation algorithm using Räcke decompositions [ABSTRACT FROM AUTHOR]

We show that there is no γ log log M/log log log M-approximation for the undirected congestion minimization problem unless NP ⊆ ZPTIME(npolylog n), where M is the size of the graph and γ is some positive constant. [ABSTRACT FROM AUTHOR]

This research focuses on the physical and logical control and reconfigurability of network topologies through intelligent and dynamic rearrangement of nodes in an optical wireless sensor network. We address high data rate sensor networks (e.g., infrastructure monitoring; surveillance), which consist of gigabit per second, narrow beam, free-space optical links between fixed and/or mobile nodes. In our approach, the seamless operation of such networks requires maintenance of wireless link connectivity and quality and at all times, amidst, for example, changing atmospheric, and traffic and platform conditions. This is achieved by dynamic reconfiguration through topology control. We address the problem of dynamic formulation of topologies, which contain only two transceivers per communications node or switch. The task of reconfiguration requires the formation of a biconnected graph or a ring topology. The problem is similar to the traveling salesman problem and is NP complete. We address the mixed integer programming formulation of this problem, and show that it does not scale even for a small network. We then focus on heuristics for dynamic, autonomous reconfiguration. Using simulations, we investigate tradeoff between solution quality and computational time. We also investigate the effectiveness of these dynamic reconfiguration heuristics compared to fixed, degraded topologies. [ABSTRACT FROM AUTHOR]