Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming

DOI10.1016/j.cor.2008.01.003zbMath1162.90548OpenAlexW1991744719MaRDI QIDQ958452

Giovanni Righini, Matteo Salani

Publication date: 4 December 2008

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2008.01.003

zbMATH Keywords

dynamic programmingcombinatorial optimizationtraveling salesman problemshortest path problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items

Iterated local search for the team orienteering problem with time windows ⋮ A column generation approach for a multi-attribute vehicle routing problem ⋮ Efficient meta-heuristics for the multi-objective time-dependent orienteering problem ⋮ Orienteering problem: a survey of recent variants, solution approaches and applications ⋮ Scheduled penalty variable neighborhood search ⋮ Solving the orienteering problem with time windows via the pulse framework ⋮ A branch-and-price approach for a multi-period vehicle routing problem ⋮ A tabu search algorithm for the multi-period inspector scheduling problem ⋮ A hybrid variable neighborhood search for the orienteering problem with mandatory visits and exclusionary constraints ⋮ Hybrid dynamic programming with bounding algorithm for the multi-profit orienteering problem ⋮ A hybrid dynamic programming for solving fixed cost transportation with discounted mechanism ⋮ An exact algorithm for Agile Earth Observation Satellite scheduling with time-dependent profits ⋮ Effective neighborhood search with optimal splitting and adaptive memory for the team orienteering problem with time windows ⋮ An \(\varepsilon \)-constraint column generation-and-enumeration algorithm for bi-objective vehicle routing problems ⋮ The team orienteering problem with time windows: an LP-based granular variable neighborhood search ⋮ Coupling ant colony systems with strong local searches ⋮ Design of diversified package tours for the digital travel industry: a branch-cut-and-price approach ⋮ Algorithms for non-linear and stochastic resource constrained shortest path ⋮ The orienteering problem: a survey ⋮ A hybrid algorithm for the DNA sequencing problem ⋮ Exact and heuristic methods for a workload allocation problem with chain precedence constraints ⋮ Hybridized evolutionary local search algorithm for the team orienteering problem with time windows ⋮ A Memetic-GRASP Algorithm for the Solution of the Orienteering Problem ⋮ The hazardous orienteering problem ⋮ A computational study of solution approaches for the resource constrained elementary shortest path problem ⋮ A simulated annealing heuristic for the team orienteering problem with time windows ⋮ A unified matheuristic for solving multi-constrained traveling salesman problems with profits ⋮ Branch-and-Bound for Bi-objective Integer Programming ⋮ Route relaxations on GPU for vehicle routing problems ⋮ An iterative three-component heuristic for the team orienteering problem with time windows ⋮ A column generation algorithm for the vehicle routing problem with soft time windows ⋮ An efficient column-generation-based algorithm for solving a pickup-and-delivery problem ⋮ A path relinking approach for the team orienteering problem ⋮ Multi-period orienteering with uncertain adoption likelihood and waiting at customers ⋮ Heuristics for the multi-period orienteering problem with multiple time windows ⋮ A survey of resource constrained shortest path problems: Exact solution approaches ⋮ A Pricing Algorithm for the Vehicle Routing Problem with Soft Time Windows ⋮ The orienteering problem with time windows applied to robotic melon harvesting

Cites Work

• Unnamed Item
• The traveling salesman problem: An overview of exact and approximate algorithms
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• An exact algorithm for team orienteering problems
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• New dynamic programming algorithms for the resource constrained elementary shortest path problem
• The orienteering problem
• An algorithm for the resource constrained shortest path problem
• State-space relaxation procedures for the computation of bounds to routing problems
• The Orienteering Problem with Time Windows
• An Optimal Algorithm for the Orienteering Tour Problem
• A tabu search heuristic for periodic and multi-depot vehicle routing problems
• Solving the Orienteering Problem through Branch-and-Cut
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• Shortest Path Problems with Resource Constraints
• Algorithms - ESA 2003