Approximating Capacitated Routing and Delivery Problems
From MaRDI portal
Publication:4268861
DOI10.1137/S0097539795295468zbMath0943.68076MaRDI QIDQ4268861
Prasad Chalasani, Rajeev Motwani
Publication date: 28 October 1999
Published in: SIAM Journal on Computing (Search for Journal in Brave)
NP-hardapproximation algorithmsmatroid intersectioncapacitated vehicle routingtraveling salesperson problemcapacitated deliverymaximum latency problem
Related Items
An algorithm for the one commodity pickup and delivery traveling salesman problem with restricted depot ⋮ Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems ⋮ 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 ⋮ Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder) ⋮ The single line moving target traveling salesman problem with release times ⋮ A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem ⋮ An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem ⋮ Vehicle Routing Algorithms for Radially Escaping Targets ⋮ An unpaired pickup and delivery problem with time dependent assignment costs: application in air cargo transportation ⋮ Polynomial time approximation schemes for the constrained minimum spanning tree problem ⋮ 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 ⋮ The vehicle routing problem with pickups and deliveries on some special graphs ⋮ Heuristics for the mixed swapping problem ⋮ An approximation algorithm for vehicle routing with compatibility constraints ⋮ The multi-commodity pickup-and-delivery traveling salesman problem ⋮ On the one-commodity pickup-and-delivery traveling salesman problem with stochastic demands ⋮ Approximation algorithms for maximum latency and partial cycle cover ⋮ The preemptive swapping problem on a tree ⋮ Cable tree wiring -- benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints ⋮ An improved randomized approximation algorithm for Max TSP ⋮ Better approximations for max TSP ⋮ Approximating the maximum quadratic assignment problem ⋮ Solving the shortest route cut and fill problem using simulated annealing ⋮ A truck scheduling problem arising in intermodal container transportation
