Compact formulations of the Steiner traveling salesman problem and related problems

DOI10.1016/J.EJOR.2013.01.044zbMath1332.90329arXiv1203.3854OpenAlexW2116834205WikidataQ57702151 ScholiaQ57702151MaRDI QIDQ257227

Saeideh D. Nasiri, Adam N. Letchford, Dirk Oliver Theis

Publication date: 15 March 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.3854

zbMATH Keywords

integer programmingcombinatorial optimizationtraveling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Combinatorial optimization (90C27)

Related Items (30)

Optimal capacitated ring trees ⋮ The Steiner traveling salesman problem with online edge blockages ⋮ An algorithm for dynamic order-picking in warehouse operations ⋮ A new mathematical programming formulation for the single-picker routing problem ⋮ New formulations for the elementary shortest-path problem visiting a given set of nodes ⋮ Pricing routines for vehicle routing with time windows on road networks ⋮ Empirical analysis for the VRPTW with a multigraph representation for the road network ⋮ The Steiner traveling salesman problem with online advanced edge blockages ⋮ Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane ⋮ The multiple Steiner TSP with order constraints: complexity and optimization algorithms ⋮ Vehicle routing on road networks: how good is Euclidean approximation? ⋮ An efficient and general approach for the joint order batching and picker routing problem ⋮ Optimally solving the joint order batching and picker routing problem ⋮ A note on computational aspects of the Steiner traveling salesman problem ⋮ A multi-visit flexible-docking vehicle routing problem with drones for simultaneous pickup and delivery services ⋮ Arc routing based compact formulations for picker routing in single and two block parallel aisle warehouses ⋮ The Steiner bi-objective shortest path problem ⋮ Order picking with multiple pickers and due dates -- simultaneous solution of order batching, batch assignment and sequencing, and picker routing problems ⋮ Improving a constructive heuristic for the general routing problem ⋮ On the submodularity of multi-depot traveling salesman games ⋮ The Steiner traveling salesman problem and its extensions ⋮ Mixed integer formulations for a routing problem with information collection in wireless networks ⋮ Exact algorithms for the order picking problem ⋮ Coupling feasibility pump and large neighborhood search to solve the Steiner team orienteering problem ⋮ Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs ⋮ A new integer programming formulation of the graphical traveling salesman problem ⋮ A new integer programming formulation of the graphical traveling salesman problem ⋮ An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem ⋮ Modelling and Solving the Joint Order Batching and Picker Routing Problem in Inventories ⋮ An extensible multi-block layout warehouse routing optimization model

Uses Software

• CPLEX
• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• A theorem on flows in networks
• A comparative analysis of several asymmetric traveling salesman problem formulations
• Exploiting sparsity in pricing routines for the capacitated arc routing problem
• A cutting plane procedure for the travelling salesman problem on road networks
• An inexact algorithm for the sequential ordering problem
• The travelling salesman problem as a constrained shortest path problem: Theory and computational experience
• An analytical comparison of different formulations of the travelling salesman problem
• A classification of formulations for the (time-dependent) traveling salesman problem
• A branch-and-cut algorithm for the capacitated profitable tour problem
• Maximal Flow Through a Network
• Integer Programming Formulation of Traveling Salesman Problems
• A New Formulation for the Travelling Salesman Problem
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• The traveling salesman problem on a graph and some related integer polyhedra
• The orienteering problem
• The prize collecting traveling salesman problem
• Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph
• A fundamental problem in vehicle routing
• An Optimal Algorithm for the Traveling Salesman Problem with Time Windows
• On the Relation Between the Traveling-Salesman and the Longest-Path Problems
• Solution of a Large-Scale Traveling-Salesman Problem
• Solving the asymmetric travelling salesman problem with time windows by branch-and-cut

This page was built for publication: Compact formulations of the Steiner traveling salesman problem and related problems