Network Optimization

A Bi-directional Resource-bounded Dynamic Programming Approach for the Traveling Salesman Problem with Time Windows

  • Jing-Quan Li
    • Categories Network Optimization Tags , ,

    This paper presents a bi-directional resource-bounded label setting algorithm for the traveling salesman problem with time windows, in which the objective is to minimize travel times. Label extensions and dominance start simultaneously in both forward and backward directions: the forward direction from the starting depot and the backward direction from the terminating depot. The resultant … Read more

    A Bi-directional Resource-bounded Dynamic Programming Approach for the Traveling Salesman Problem with Time Windows

  • Jing-Quan Li
    • Categories Network Optimization Tags , ,

    This paper presents a bi-directional resource-bounded label setting algorithm for the traveling salesman problem with time windows, in which the objective is to minimize travel times. Label extensions and dominance start simultaneously in both forward and backward directions: the forward direction from the starting depot and the backward direction from the terminating depot. The resultant … Read more

    Solving multi-objective network flow problems with an interior point method

  • José Rui Figureira
  • Margarida Fonseca
  • Mauricio G.C. Resende
    • Categories Linear Programming, Multi-Criteria Optimization, Network Optimization Tags , , ,

    In this paper we present a primal-dual interior-point algorithm to solve a class of multi-objective network flow problems. More precisely, our algorithm is an extension of the single-objective primal-dual infeasible and inexact interior point method for multi-objective linear network flow problems. A comparison with standard interior point methods is provided and experimental results on bi-objective … Read more

    OSPF Routing with Optimal Oblivious Performance Ratio Under Polyhedral Demand Uncertainty

  • Aysegul Altin
  • Pietro Belotti
  • Mustafa C. Pinar
    • Categories Network Optimization, Robust Optimization, Telecommunications Tags , , , , , ,

    We study the best OSPF style routing problem in telecommunication networks, where weight management is employed to get a routing configuration with the minimum oblivious ratio. We consider polyhedral demand uncertainty: the set of traffic matrices is a polyhedron defined by a set of linear constraints, and the performance of each routing is assessed on … Read more

    Minimal Spanning Trees with Conflict Graphs

  • Andreas Darmann
  • Ulrich Pferschy
  • Joachim Schauer
    • Categories Graphs and Matroids, Network Optimization Tags ,

    For the classical minimum spanning tree problem we introduce disjunctive constraints for pairs of edges which can not be both included in the spanning tree at the same time. These constraints are represented by a conflict graph whose vertices correspond to the edges of the original graph. Edges in the conflict graph connect conflicting edges … Read more

    Core Routing on Dynamic Time-Dependent Road Networks

  • Daniel Delling
  • Giacomo Nannicini
    • Categories Network Optimization Tags , , ,

    Route planning in large scale time-dependent road networks is an important practical application of the shortest paths problem that greatly benefits from speedup techniques. In this paper we extend a two-levels hierarchical approach for point-to-point shortest paths computations to the time-dependent case. This method, also known as core routing in the literature for static graphs, … Read more

    Bidirectional A* Search on Time-Dependent Road Networks

  • Daniel Delling
  • Leo Liberti
  • Giacomo Nannicini
  • Dominik Schultes
    • Categories Network Optimization Tags , , ,

    The computation of point-to-point shortest paths on time-dependent road networks has a large practical interest, but very few works propose efficient algorithms for this problem. We propose a novel approach which tackles one of the main complications of route planning in time-dependent graphs, which is the difficulty of using bidirectional search: since the exact arrival … Read more

    Modeling and Solving Location Routing and Scheduling Problems

  • Z. Akca
  • Ted K. Ralphs
  • R.T. Berger
    • Categories 0-1 Programming, Network Optimization, Production and Logistics Tags , , ,

    This paper studies location routing and scheduling problems, a class of problems in which the decisions of facility location, vehicle routing, and route assignment are optimized simultaneously. For a version with capacity and time restrictions, two formulations are presented, one graph-based and one set-partitioning-based. For the set-partitioning-based formulation, valid inequalities are identified and their effectiveness … Read more

    Modelling Hop-Constrained and Diameter-Constrained Minimum Spanning Tree Problems as Steiner Tree Problems over Layered Graphs

  • Luís Gouveia
  • Eduardo Uchoa
  • Luidi Simonetti
    • Categories Branch and Cut Algorithms, Network Optimization Tags ,

    The Hop-Constrained Minimum Spanning Tree Problem (HMSTP) is a NP-hard problem arising in the design of centralized telecommunication networks with quality of service constraints. We show that the HMSTP is equivalent to a Steiner Tree Problem (STP) in an adequate layered graph. We prove that the directed cut formulation for the STP defined in the … Read more

    The Price of Atomic Selfish Ring Routing

  • Bo Chen
  • Xujin Chen
  • Xiaodong Hu
    • Categories Game Theory, Network Optimization Tags , ,

    We study selfish routing in ring networks with respect to minimizing the maximum latency. Our main result is an establishement of constant bounds on the price of stability (PoS) for routing unsplittable flows with linear latency. We show that the PoS is at most 6.83, which reduces to 4:57 when the linear latency functions are … Read more