Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
From MaRDI portal
Publication:2276891
The paper deals with various kinds of vehicle routing problems (VRP): (i) the capacitated VRP (CVRP): every vertex \(v_ i\) has a positive weight \(q_ i\) and the total weight of any route must not exceed Q, the capacity of each vehicle. (ii) The distance constrained VRP (DVRP): the total length of any route may not exceed a given bound L. (iii) The VRP with time windows (TWVRP): every vertex \(v_ i\) must be visited within a time window \([a_ i,b_ i]\), where waiting at \(v_ i\) is allowed. As the classical subtour elimination constraints (due to Dantzig, Fulkerson and Johnson) are hard to adapt to the DVRP and no generalization of DFJ-constraints are known with respect to the TWVRP, the authors propose to improve and to extend the subtour elimination constraints of \textit{C. E. Miller, A. W. Tucker} and \textit{R. A. Zemlin} [J. Assoc. Comput. Mach. 7, 326-329 (1960; Zbl 0100.151)], \[ (MTZ)\quad u_ i-u_ j+(n-1)x_{ij}\leq n-2\quad (i,j=2,...,n;\quad i\neq j),\quad 1\leq u_ i\leq n-1\quad (i=2,...,n). \] By a lifting technique they get valid inequalities for the TSP, CVRP, DVRP and TWVRP. Some analysis of the induced polytopes and facets are given for the asymmetric TSP too. A couple of experiments indicate that the lifted MTZ-constraints are of relative strength even for TSP.
Recommendations
- A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for routing problems with time windows
- Requiem for the Miller-Tucker-Zemlin subtour elimination constraints?
- A conditional-logic interpretation for Miller-Tucker-Zemlin inequalities and extensions
- A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem
- On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
- Formulations and valid inequalities for the heterogeneous vehicle routing problem
- A new subtour elimination constraint for the vehicle routing problem
- Polyhedral study of the capacitated vehicle routing problem
- Two exact algorithms for the distance-constrained vehicle routing problem
- New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
Cites work
- Classification of travelling salesman problem formulations
- Faces for a linear inequality in 0–1 variables
- scientific article; zbMATH DE number 3989085 (Why is no real title available?)
- scientific article; zbMATH DE number 4047423 (Why is no real title available?)
- scientific article; zbMATH DE number 192876 (Why is no real title available?)
- scientific article; zbMATH DE number 3895002 (Why is no real title available?)
- Integer Programming Formulation of Traveling Salesman Problems
- On the facial structure of set packing polyhedra
- Optimal Routing under Capacity and Distance Restrictions
- Partial linear characterizations of the asymmetric travelling salesman polytope
- Solution of a Large-Scale Traveling-Salesman Problem
Cited in
(only showing first 100 items - show all)- Lasso solution strategies for the vehicle routing problem with pickups and deliveries
- An optimization-based heuristic for the robotic cell problem
- The traveling salesman problem: An overview of exact and approximate algorithms
- On symmetric subtour problems
- A bilevel programming approach to the travelling salesman problem.
- Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times
- The time constrained maximal covering salesman problem
- The driver and vehicle routing problem
- Multiscale production routing in multicommodity supply chains with complex production facilities
- On the exact solution of the no-wait flow shop problem with due date constraints
- An exact algorithm for a vehicle-and-driver scheduling problem
- Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations
- 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
- A matheuristic for the asymmetric capacitated vehicle routing problem
- Formulations for the orienteering problem with additional constraints
- Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems
- An unpaired pickup and delivery problem with time dependent assignment costs: application in air cargo transportation
- The selective traveling salesman problem with emission allocation rules
- The robust vehicle routing problem with time windows: solution by branch and price and cut
- Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the asymmetric traveling salesman problem
- Hybrid optimization methods for time-dependent sequencing problems
- Identification of unidentified equality constraints for integer programming problems
- The inventory-routing problem with transshipment
- The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
- New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
- Routing problems: A bibliography
- Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
- The close-open mixed vehicle routing problem
- A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for routing problems with time windows
- Selective capacitated location-routing problem with incentive-dependent returns in designing used products collection network
- Mathematical formulations and improvements for the multi-depot open vehicle routing problem
- Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem
- A personalized walking bus service requiring optimized route decisions: a real case
- The traveling salesman puts-on a hard hat -- tower crane scheduling in construction projects
- A variable neighborhood search for the last-mile delivery problem during major infectious disease outbreak
- A covering traveling salesman problem with profit in the last mile delivery
- Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation
- A binary decision diagram based algorithm for solving a class of binary two-stage stochastic programs
- A waste collection problem with service type option
- MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles
- A branch-and-cut algorithm for the generalized traveling salesman problem with time windows
- Degree-constrained \(k\)-minimum spanning tree problem
- Goal programming model applied to waste paper logistics processes
- Relations, models and a memetic approach for three degree-dependent spanning tree problems
- Facility location with tree topology and radial distance constraints
- Models and algorithms for the traveling salesman problem with time-dependent service times
- Two-stage vehicle routing problem with arc time windows: a mixed integer programming formulation and a heuristic approach
- Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs
- A recourse goal programming approach for airport bus routing problem
- Connected power domination in graphs
- New mathematical models of the generalized vehicle routing problem and extensions
- Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem
- Bike sharing systems: solving the static rebalancing problem
- New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP
- Formulations and exact algorithms for the vehicle routing problem with time windows
- Solving an urban waste collection problem using ants heuristics
- 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
- Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs
- Integer linear programming formulations of multiple salesman problems and its variations
- Requiem for the Miller-Tucker-Zemlin subtour elimination constraints?
- A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem
- A symmetry-free polynomial formulation of the capacitated vehicle routing problem
- Compact formulations for multi-depot routing problems: theoretical and computational comparisons
- Optimal fleet deployment for electric vehicle sharing systems with the consideration of demand uncertainty
- Multi-objective optimization for a combined location-routing-inventory system considering carbon-capped differences
- An exact method for the combinatorial bids generation problem with uncertainty on clearing prices, bids success, and contracts materialization
- A conditional-logic interpretation for Miller-Tucker-Zemlin inequalities and extensions
- A new approach on auxiliary vehicle assignment in capacitated location routing problem
- Strength of three MIP formulations for the prize collecting Steiner tree problem with a quota constraint
- A branch-and-cut algorithm for the preemptive swapping problem
- Multi-objective evolutionary approach for supply chain network design problem within online customer consideration
- Solving diameter-constrained minimum spanning tree problems by constraint programming
- Models for a Steiner multi-ring network design problem with revenues
- A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading
- The traveling salesman problem with time-dependent service times
- A branch-and-cut framework for the consistent traveling salesman problem
- Looking for edge-equitable spanning trees
- Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations
- Models and hybrid methods for the onshore wells maintenance problem
- An adaptive large neighborhood search heuristic for the electric vehicle scheduling problem
- Integer Programming Formulations for the k-Cardinality Tree Problem
- Recent models and algorithms for one-to-one pickup and delivery problems
- One-to-many-to-one single vehicle pickup and delivery problems
- Modeling the Mobile Oil Recovery Problem as a Multiobjective Vehicle Routing Problem
- On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
- Generalized Subtour Elimination Constraints and Connectivity Constraints
- Lower and upper bounds for the spanning tree with minimum branch vertices
- New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints
- Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing
- Efficient operation of a surface mounting machine with a multihead turret
- Multiperiod location-routing with decoupled time scales
- A polyhedral study of the asymmetric traveling salesman problem with time windows
- The stop-and-drop problem in nonprofit food distribution networks
- An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem
- 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
- Exact algorithms on reliable routing problems under uncertain topology using aggregation techniques for exponentially many scenarios
This page was built for publication: Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2276891)
