Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries

DOI<654::AID-NAV4>3.0.CO;2-A 10.1002/(SICI)1520-6750(199909)46:6<654::AID-NAV4>3.0.CO;2-AzbMath0940.90051OpenAlexW2046876986MaRDI QIDQ4700651

Shoshana Anily, Julien Bramel

Publication date: 27 July 2000

Full work available at URL: https://doi.org/10.1002/(sici)1520-6750(199909)46:6<654::aid-nav4>3.0.co;2-a

zbMATH Keywords

worst-case boundspolynomial-time approximation algorithmscapacitated traveling salesman problem

Mathematics Subject Classification ID

Operations research and management science (90B99)

Related Items

An algorithm for the one commodity pickup and delivery traveling salesman problem with restricted depot, Mathematical formulations for a 1-full-truckload pickup-and-delivery problem, A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem, Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery, Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder), Heuristic algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem, A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem, An unpaired pickup and delivery problem with time dependent assignment costs: application in air cargo transportation, Balancing the stations of a self service “bike hire” system, Polynomially solvable cases of the bipartite traveling salesman problem, A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem, A branch‐and‐cut algorithm for the nonpreemptive swapping problem, Approximation results for min-max path cover problems in vehicle routing, The multi-commodity pickup-and-delivery traveling salesman problem, On the one-commodity pickup-and-delivery traveling salesman problem with stochastic demands, Solving the shortest route cut and fill problem using simulated annealing, A truck scheduling problem arising in intermodal container transportation

Cites Work

• Unnamed Item
• Unnamed Item
• The traveling salesman problem with delivery and backhauls
• Technical Note—Heuristics for Delivery Problems with Constant Error Guarantees
• Bounds and Heuristics for Capacitated Routing Problems
• The swapping problem
• Worst-Case Analysis of Heuristics for Multidepot Capacitated Vehicle Routing Problems
• Restricted delivery problems on a network