State-space relaxation procedures for the computation of bounds to routing problems
From MaRDI portal
Publication:3908783
DOI10.1002/net.3230110207zbMath0458.90071OpenAlexW2163873159MaRDI QIDQ3908783
Paolo Toth, Aristide Mingozzi, Nicos Christofides
Publication date: 1981
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230110207
combinatorial optimizationvehicle routingtraveling salesman problemrouting problemssubgradient optimizationcomputation of boundsstate space ascentstate-space relaxation procedures
Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Dynamic programming (90C39)
Related Items
Constraint programming and operations research, A dynamic programming method for single machine scheduling, Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Min-Max vs. Min-Sum vehicle routing: a worst-case analysis, Improving Variable Orderings of Approximate Decision Diagrams Using Reinforcement Learning, Dynamic Programming for the Time-Dependent Traveling Salesman Problem with Time Windows, Procedures for the bin packing problem with precedence constraints, A bi-criteria heuristic for the vehicle routing problem with time windows, A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times, A traveling salesman problem with pickups and deliveries, time windows and draft limits: case study from chemical shipping, History-dependent scheduling: models and algorithms for scheduling with general precedence and sequence dependence, A new exact algorithm for the vehicle routing problem based on \(q\)-paths and \(k\)-shortest paths relaxations, Routing problems: A bibliography, A column generation approach to the heterogeneous fleet vehicle routing problem, Stochastic decision diagrams, A result on projection for the vehicle routing problem, A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem, A branch-and-price approach to the feeder network design problem, An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts, A classification of formulations for the (time-dependent) traveling salesman problem, Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery, Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints, Decision Diagrams for Discrete Optimization: A Survey of Recent Advances, Exact and anytime approach for solving the time dependent traveling salesman problem with time windows, Solving the single crane scheduling problem at rail transshipment yards, Exact and heuristic methods for a workload allocation problem with chain precedence constraints, Multistart Branch and Bound for Large Asymmetric Distance-Constrained Vehicle Routing Problem, An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem, A general variable neighborhood search for the traveling salesman problem with time windows under various objectives, An efficient filtering algorithm for the unary resource constraint with transition times and optional activities, The hazardous orienteering problem, A dynamic programming based algorithm for the crew scheduling problem., Exact solution of network flow models with strong relaxations, A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time, The use of state space relaxation for the dynamic facility location problem, Discrete optimization by optimal control methods. I: Separable problems, Discrete optimization by optimal control methods. II: The static traveling salesman problem, Network-Based Approximate Linear Programming for Discrete Optimization, Arc flow formulations based on dynamic programming: theoretical foundations and applications, A variable iterated greedy algorithm for the traveling salesman problem with time windows, Formulations and exact algorithms for the vehicle routing problem with time windows, Route relaxations on GPU for vehicle routing problems, Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints, The vehicle routing problem: An overview of exact and approximate algorithms, Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming, Scheduling examinations to reduce second-order conflicts, A dynamic programming based heuristic for the assembly line balancing problem, Perspectives on integer programming for time-dependent models, Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints, Scheduling tasks on moving executors to minimise the maximum lateness, The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem, A lower bound for the adaptive two-echelon capacitated vehicle routing problem, An efficient optimal solution to the coil sequencing problem in electro-galvanizing line, New integer linear programming formulation for the traveling salesman problem with time windows: minimizing tour duration with waiting times, Models for a traveling purchaser problem with additional side-constraints, An exact algorithm for single-machine scheduling without machine idle time, Lower bounds from state space relaxations for concave cost network flow problems, A branch-and-bound algorithm for concave network flow problems, Beam-ACO for the travelling salesman problem with time windows, A polyhedral study of the asymmetric traveling salesman problem with time windows, \( \mathrm{A}^*\) -based construction of decision diagrams for a prize-collecting scheduling problem, A branch and bound algorithm for the capacitated vehicle routing problem, Exact solution techniques for two-dimensional cutting and packing, An iterative dynamic programming approach for the temporal knapsack problem, An exact solution framework for a broad class of vehicle routing problems, Discrete Optimization with Decision Diagrams, A survey of algorithms for the single machine total weighted tardiness scheduling problem, A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows, New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows, An MDD-Based Lagrangian Approach to the Multicommodity Pickup-and-Delivery TSP, A genetic algorithm for service level based vehicle scheduling, MIP modelling of changeovers in production planning and scheduling problems, Stronger \(K\)-tree relaxations for the vehicle routing problem, Analysis of partial setup strategies for solving the operational planning problem in parallel machine electronic assembly systems, Algorithms for large scale set covering problems, Unconstrained binary models of the travelling salesman problem variants for quantum optimization, Iterated maximum large neighborhood search for the traveling salesman problem with time windows and its time-dependent version, Methods for routing with time windows, State space relaxation for set covering problems related to bus driver scheduling, A heuristic for cumulative vehicle routing using column generation
Cites Work
