Integer Programming Formulation of Traveling Salesman Problems

DOI10.1145/321043.321046zbMath0100.15101OpenAlexW2049287714WikidataQ56619951 ScholiaQ56619951MaRDI QIDQ3281501

C. E. Miller, R. A. Zemlin, Albert W. Tucker

Publication date: 1960

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321043.321046

zbMATH Keywords

applications of probability theory and statistics

Related Items

Mixed integer formulations for a coupled lot-scheduling and vehicle routing problem in furniture settings, Path inequalities for the vehicle routing problem with time windows, A branch‐and‐cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks, Learn global and optimize local: a data-driven methodology for last-mile routing, The profit-oriented hub line location problem with elastic demand, Factors affecting the final solution of the bike-sharing rebalancing problem under heuristic algorithms, A GRASP/Path‐Relinking algorithm for the traveling purchaser problem, MIP formulations for induced graph optimization problems: a tutorial, Mixed integer programming formulations for the generalized traveling salesman problem with time windows, Formulations for the clustered traveling salesman problem with \(d\)-relaxed priority rule, Optimization of gas metering maintenance services: A multiobjective vehicle routing problem with a set of predefined overlapping time windows, A two‐tier urban delivery network with robot‐based deliveries, Two dependency constrained spanning tree problems, A new formulation for the liner shipping network design problem, Computational comparisons of different formulations for the Stackelberg minimum spanning tree game, Variable neighborhood search to solve the generalized orienteering problem, Polarization reduction by minimum‐cardinality edge additions: Complexity and integer programming approaches, Maximum weighted induced forests and trees: new formulations and a computational comparative review, Clustered coverage orienteering problem of unmanned surface vehicles for water sampling, Biobjective UAV routing for a mission to visit multiple mobile targets, Arc routing based compact formulations for picker routing in single and two block parallel aisle warehouses, An integer program for positive semidefinite zero forcing in graphs, A b<scp>ranch‐and‐cut</scp> approach and alternative formulations for the traveling salesman problem with drone, Heuristics for a cash-collection routing problem with a cluster-first route-second approach, Minimum weight clustered dominating tree problem, Asymmetric probabilistic minimum-cost Hamiltonian cycle problem considering arc and vertex failures, Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm, 0-1 mathematical programming models for flexible process planning, Valid inequalities and extended formulations for lot-sizing and scheduling problem with sequence-dependent setups, Operational Research in the Wine Supply Chain, An efficient mixed integer linear programming model for the minimum spanning tree problem, On solving bi-objective constrained minimum spanning tree problems, Drone location and vehicle fleet planning with trucks and aerial drones, Resilience of long chain under disruption, The travelling salesman problem with positional consistency constraints: an application to healthcare services, Some contributions of Ailsa H. Land to the study of the traveling salesman problem, On the generation of metric TSP instances with a large integrality gap by branch-and-cut, A flexible robust model for blood supply chain network design problem, Integrated optimal scheduling and routing of repair crew and relief vehicles after disaster: a novel hybrid solution approach, The hazardous orienteering problem, Connected graph partitioning with aggregated and non‐aggregated gap objective functions, The cumulative school bus routing problem: Polynomial‐size formulations, The capacitated family traveling salesperson problem, Vehicle routing problems with multiple trips, Vehicle routing problems with multiple trips, Models for a Steiner ring network design problem with revenues, The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints, A comparison of Steiner tree relaxations, An improved formulation for the multi-depot open vehicle routing problem, An exact method for solving the bi-objective Minimum Diameter-Cost Spanning Tree Problem, Efficient Large-Scale Multi-Drone Delivery using Transit Networks, A new formulation approach for location-routing problems, Use of the BATA algorithm and MIS to solve the mail carrier problem, Scheduling electric vehicles and locating charging stations on a path, Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems, The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm, An improved binary programming formulation for the secure domination problem, A matheuristic approach to the orienteering problem with service time dependent profits, Optimization of wireless sensor networks deployment with coverage and connectivity constraints, Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times, Computational approaches for zero forcing and related problems, The time constrained maximal covering salesman problem, The multiple vehicle pickup and delivery problem with LIFO constraints, A matheuristic for the team orienteering arc routing problem, Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem, Evaluating the quality of online optimization algorithms by discrete event simulation, The traveling salesman problem with time-dependent service times, A branch-and-cut framework for the consistent traveling salesman problem, Core-based cost allocation in the cooperative traveling salesman problem, Thirty years of heterogeneous vehicle routing, Optimal design of compact and functionally contiguous conservation management areas, Integer programming formulations for the elementary shortest path problem, A new mathematical programming formulation for the single-picker routing problem, Lower bounding procedure for the asymmetric quadratic traveling salesman problem, A survey on single crane scheduling in automated storage/retrieval systems, Orienteering problem: a survey of recent variants, solution approaches and applications, An optimal path planning problem for heterogeneous multi-vehicle systems, Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles, GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem, Looking for edge-equitable spanning trees, A branch-and-bound algorithm for the acyclic partitioning problem, A hierarchical compromise model for the joint optimization of recovery operations and distribution of emergency goods in Humanitarian logistics, The dynamic multiperiod vehicle routing problem with probabilistic information, Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations, Approaches for solving the container stacking problem with route distance minimization and stack rearrangement considerations, Model-based automatic neighborhood design by unsupervised learning, The production routing problem: a review of formulations and solution algorithms, Optimal solutions to minimum total energy broadcasting problem in wireless ad hoc networks, A bi-objective model for the used oil location-routing problem, History-dependent scheduling: models and algorithms for scheduling with general precedence and sequence dependence, Solution algorithms for synchronous flow shop problems with two dominating machines, The load-balanced multi-dimensional bin-packing problem, Heuristic and lower bound for a stochastic location-routing problem, A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem, The coastal seaspace patrol sector design and allocation problem, Competitiveness based on logistic management: a real case study, The orienteering problem: a survey, A hybrid algorithm for the DNA sequencing problem, Lower bounds on the sizes of integer programs without additional variables, New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints, An investigation into two bin packing problems with ordering and orientation implications, Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing, Multiperiod location-routing with decoupled time scales, Classification of travelling salesman problem formulations, Data transfer planning with tree placement for collaborative environments, Cost allocation: The traveling salesman, bin packing, and the knapsack, A multi-criteria optimization model for humanitarian aid distribution, Creating lasso-solutions for the traveling salesman problem with pickup and delivery by tabu search, The stop-and-drop problem in nonprofit food distribution networks, The pickup and delivery problem with time windows, An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem, An analytical comparison of different formulations of the travelling salesman problem, Solving the minimum label spanning tree problem by mathematical programming techniques, A randomized granular tabu search heuristic for the split delivery vehicle routing problem, Robust UAV mission planning, Preprocessing for a map sectorization problem by means of mathematical programming, The Steiner tree problem with delays: a compact formulation and reduction procedures, The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm, The traveling salesman problem: An overview of exact and approximate algorithms, On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches, Exact methods for solving the elementary shortest and longest path problems, An interactive approach for biobjective integer programs under quasiconvex preference functions, Minisum and maximin aerial surveillance over disjoint rectangles, A comparative analysis of several asymmetric traveling salesman problem formulations, The multiple-robot assembly plan problem, On symmetric subtour problems, Models, relaxations and exact approaches for the capacitated vehicle routing problem, A heuristic approach for a scheduling problem with periodic maintenance and sequence-dependent setup times, A single machine scheduling problem with availability constraints and sequence-dependent setup costs, An efficient optimal solution to the coil sequencing problem in electro-galvanizing line, New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints, MIP models for connected facility location: a theoretical and computational study, The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation, Industrial aspects and literature survey: fleet composition and routing, Integer programming formulation of combinatorial optimization problems, The indefinite period traveling salesman problem, Strong multi-commodity flow formulations for the asymmetric traveling salesman problem, The multi-vehicle probabilistic covering tour problem, Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints, An approach for solving a class of transportation scheduling problems, Concurrent optimization of harvesting and road network layouts under steep terrain, A framework for multi-robot node coverage in sensor networks, A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem, A tabu search heuristic for the split delivery vehicle routing problem with production and demand calendars, An optimization-based heuristic for the robotic cell problem, Optimal multiple stage expansion of competence set, Integer linear programming formulation for a vehicle routing problem, Methods for routing with time windows, Mathematical programming formulations for machine scheduling: A survey, Compact formulations of the Steiner traveling salesman problem and related problems, Projection, lifting and extended formulation integer and combinatorial optimization, An algorithm for the one commodity pickup and delivery traveling salesman problem with restricted depot, Multiple-stage multiple-machine capacitated lot-sizing and scheduling with sequence-dependent setup: a case study in the wheel industry, An Exact Algorithm for the Steiner Tree Problem with Delays, Strength of Three MIP Formulations for the Prize Collecting Steiner Tree Problem with a Quota Constraint, When road trains supply freight trains: scheduling the container loading process by gantry crane between multi-trailer trucks and freight trains, Some comments on Chen et al. ‘Production scheduling optimization algorithm for the hot rolling processes’, A correlated storage location assignment problem in a single-block-multi-aisles warehouse considering BOM information, Distribution network design on the battlefield, A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem, Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem, A guided local search metaheuristic for the team orienteering problem, A robust optimization approach to wine grape harvesting scheduling, Length-constrained cycle partition with an application to UAV routing*, Robust Team Orienteering Problem with Decreasing Profits, Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, A branch-and-cut algorithm for the preemptive swapping problem, An effective and fast heuristic for the dial-a-ride problem, Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder), Selective generalized travelling salesman problem, A MILP model for then-job,M-stage flowshop with sequence dependent set-up times, Integer Programming, Constraint Programming, and Hybrid Decomposition Approaches to Discretizable Distance Geometry Problems, Picker Routing in AGV-Assisted Order Picking Systems, Network Models for Multiobjective Discrete Optimization, A symmetry-free polynomial formulation of the capacitated vehicle routing problem, Quota travelling salesman problem with passengers, incomplete ride and collection time optimization by ant-based algorithms, A branch-cut-and-price algorithm for the traveling salesperson problem with hotel selection, Compact formulations for multi-depot routing problems: theoretical and computational comparisons, Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem, Modeling and optimization of multiple traveling salesmen problems: an evolution strategy approach, The traveling salesman problem with job-times (\textit{TSPJ}), Continuous maximal covering location problems with interconnected facilities, Reinforcement learning for combinatorial optimization: a survey, The heterogeneous flexible periodic vehicle routing problem: mathematical formulations and solution algorithms, The traveling purchaser problem with fast service option, A column generation and combinatorial Benders decomposition algorithm for the selective dial-a-ride-problem, A partitioning column approach for solving LED sorter manipulator path planning problems, Strategies for Generating Well Centered Tetrahedral Meshes on Industrial Geometries, A multi-start evolutionary local search for the one-commodity pickup and delivery traveling salesman problem, Inventory policy and heuristic for long-term multi-product perishable inventory routing problem with static demand, Multiperiod integrated spare parts and tour planning for on-site maintenance activities with stochastic repair requests, A branch-and-cut approach for the distributed no-wait flowshop scheduling problem, Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints, SFCDecomp: Multicriteria Optimized Tool Path Planning in 3D Printing using Space-Filling Curve Based Domain Decomposition, Integer Programming Formulations for the k-Cardinality Tree Problem, Connected power domination in graphs, The Surgical Patient Routing Problem: A Central Planner Approach, A conditional-logic interpretation for Miller-Tucker-Zemlin inequalities and extensions, Formulations and Branch-and-Cut Algorithms for Multivehicle Production and Inventory Routing Problems, Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem, On the multistage shortest path problem under distributional uncertainty, A branch-and-cut algorithm for the soft-clustered vehicle-routing problem, Characterizing acyclic graphs by labeling edges, A hybrid genetic algorithm for the multi-depot open vehicle routing problem, Optimization Methods: An Applications-Oriented Primer, Arc flow formulations based on dynamic programming: theoretical foundations and applications, Formulations and exact algorithms for the vehicle routing problem with time windows, Routing a Heterogeneous Fleet of Vehicles, A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times, Integer programming approaches to the travelling salesman problem, Goal programming model applied to waste paper logistics processes, Solving an urban waste collection problem using ants heuristics, Time-dependent travelling salesman problem., Relations, models and a memetic approach for three degree-dependent spanning tree problems, Solving a bi-objective transportation location routing problem by metaheuristic algorithms, Exact algorithms for the traveling salesman problem with draft limits, The distance constrained multiple vehicle traveling purchaser problem, The travelling salesman problem with neighbourhoods: MINLP solution, A location-routing problem in glass recycling, Formulations and valid inequalities for the heterogeneous vehicle routing problem, A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints, On pedigree polytopes and Hamiltonian cycles, Formulation and a two-phase matheuristic for the roaming salesman problem: application to election logistics, Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints, VEHICLE ROUTE OPTIMIZATION FOR RFID INTEGRATED WASTE COLLECTION SYSTEM, Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints, Matching preclusion for the (n, k)-bubble-sort graphs, Integer linear programming formulations of multiple salesman problems and its variations, A robust optimization approach for humanitarian needs assessment planning under travel time uncertainty, Requiem for the Miller-Tucker-Zemlin subtour elimination constraints?, A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse, Metaheuristics for the Asymmetric Hamiltonian Path Problem, Models and algorithms for the traveling salesman problem with time-dependent service times, A mathematical programming model for integrating production and procurement transport decisions, Traveling Salesman Problem and Membership in Pedigree Polytope - A Numerical Illustration, Modeling the Mobile Oil Recovery Problem as a Multiobjective Vehicle Routing Problem, The Humanitarian Pickup and Distribution Problem, COMPARATIVE STUDY OF SOME SOLUTION METHODS FOR TRAVELING SALESMAN PROBLEM USING GENETIC ALGORITHMS, Formulations for an inventory routing problem, An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system, Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, Modeling Single-Picker Routing Problems in Classical and Modern Warehouses, The traveling salesman problem: An update of research, IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem, A combinatorial approach to the design of vaccines, A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem, A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem, Approximate extended formulations, The minimum flow cost Hamiltonian cycle problem: a comparison of formulations, Routing with time windows by column generation, Two-stage vehicle routing problem with arc time windows: a mixed integer programming formulation and a heuristic approach, Optimizing vehicle routing via Stackelberg game framework and distributionally robust equilibrium optimization method, Designing radio-mobile access networks based on synchronous digital hierarchy rings, New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints, A compact model and tight bounds for a combined location-routing problem, An effective iterated two-stage heuristic algorithm for the multiple traveling salesmen problem, Dealing with time in the multiple traveling salespersons problem with moving targets, The driver and vehicle routing problem, Solving the bus evacuation problem and its variants, Vehicle routing with probabilistic capacity constraints, An exact algorithm for a vehicle-and-driver scheduling problem, A branch-and-cut algorithm for the minimum branch vertices spanning tree problem, MIP neighborhood synthesis through semantic feature extraction and automatic algorithm configuration, Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations, An open source spreadsheet solver for vehicle routing problems, Routing and scheduling decisions in the hierarchical hub location problem, A branch-and-cut algorithm for the time window assignment vehicle routing problem, Vehicle routing with backhauls: review and research perspectives, Picker routing in rectangular mixed shelves warehouses, Integer programming models and linearizations for the traveling car renter problem, A profit-maximization location-routing-pricing problem: a branch-and-price algorithm, A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs, Matheuristic algorithms for the parallel drone scheduling traveling salesman problem, Container supply with multi-trailer trucks: parking strategies to speed up the gantry crane-based loading of freight trains in rail yards, A waste collection problem with service type option, The referenced vertex ordering problem: theory, applications, and solution methods, Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope, Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints, An integer programming approach for the search of discretization orders in distance geometry problems, MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles, A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings, A distributed approximation algorithm for the bottleneck connected dominating set problem, A branch-and-cut algorithm for the Steiner tree problem with delays, The team orienteering problem with time windows: an LP-based granular variable neighborhood search, A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem, Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems, Covering and connectivity constraints in loop-based formulation of material flow network design in facility layout, Liner shipping network design, Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods, Formulations for the orienteering problem with additional constraints, A branch-and-cut algorithm for the generalized traveling salesman problem with time windows, The assembly line balancing and scheduling problem with sequence-dependent setup times: problem extension, model formulation and efficient heuristics, A model for finding transition-minors, A lexicographical goal programming based decision support system for logistics of humanitarian aid, Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems, Modelling beneficiaries' choice in disaster relief logistics, The selective traveling salesman problem with emission allocation rules, Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem, Crane scheduling in railway yards: an analysis of computational complexity, A branch-price-and-cut algorithm for the capacitated multiple vehicle traveling purchaser problem with unitary demand, A branch-and-Benders-cut algorithm for the crew scheduling and routing problem in road restoration, A vehicle routing problem arising in unmanned aerial monitoring, The green location-routing problem, A self-organizing neural network approach for the single AGV routing problem, Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the asymmetric traveling salesman problem, Revisiting the Hamiltonian \(p\)-median problem: a new formulation on directed graphs and a branch-and-cut algorithm, Reformulated acyclic partitioning for rail-rail containers transshipment, A comparison of algorithms for finding an efficient theme park tour, Multiobjective mathematical models and solution approaches for heterogeneous fixed fleet vehicle routing problems, Bi-objective safe and resilient urban evacuation planning, Selective capacitated location-routing problem with incentive-dependent returns in designing used products collection network, Alternative mathematical models and solution approaches for lot-sizing and scheduling problems in the brewery industry: analyzing two different situations, The traveling purchaser problem and its variants, Integrated production and distribution scheduling with a perishable product, Traveling worker assembly line (re)balancing problem: model, reduction techniques, and real case studies, Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem, Ordered weighted average optimization in multiobjective spanning tree problem, Clustering data that are graph connected, A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints, Models and linearizations for the Traveling Car Renter with passengers, Mathematical formulations and improvements for the multi-depot open vehicle routing problem, An exact and heuristic approach for the \(d\)-minimum branch vertices problem, A hybrid VNS/tabu search algorithm for solving the vehicle routing problem with drones and en route operations, The traveling salesman problem with draft limits, Heuristic approaches for the optimal wiring in large scale robotic skin design, Multiperiod multi traveling salesmen problem considering time window constraints with an application to a real world case, Multi-trip time-dependent vehicle routing problem with soft time windows and overtime constraints, On the core of traveling salesman games, Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem, Vehicle routing with endogenous learning: application to offshore plug and abandonment campaign planning, Planning a multi-sensors search for a moving target considering traveling costs, Preemptive stacker crane problem: extending tree-based properties and construction heuristics, Outreach strategies for vaccine distribution: a multi-period stochastic modeling approach, Drone-assisted deliveries: new formulations for the flying sidekick traveling salesman problem, Fleet assignment and routing with schedule synchronization constraints, The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints, Integer linear programming formulation for vehicle routing problems, A branch-and-price procedure for clustering data that are graph connected, SAT encodings for pseudo-Boolean constraints together with at-most-one constraints, A variable neighborhood search for the last-mile delivery problem during major infectious disease outbreak, Routing for unmanned aerial vehicles: touring dimensional sets, Reinforcement learning of simplex pivot rules: a proof of concept, An extensible multi-block layout warehouse routing optimization model, The pickup and delivery problem with transshipments: critical review of two existing models and a new formulation, Robust drone selective routing in humanitarian transportation network assessment, Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation, Solving the integrated multi-period scheduling routing problem for cleaning debris in the aftermath of disasters, A location-or-routing problem with partial and decaying coverage, A multi-stage stochastic programming model of lot-sizing and scheduling problems with machine eligibilities and sequence-dependent setups, Vehicle dispatching with time-dependent travel times, Solving the shortest route cut and fill problem using simulated annealing