Heuristics for unequal weight delivery problems with a fixed error guarantee
type: Item
instance of: scholarly article
title: Heuristics for unequal weight delivery problems with a fixed error guarantee
zbMATH Open document ID: 0632.90083
DOI: 10.1016/0167-6377(87)90012-5
author: Kemal Altinkemer
author: Bezalel Gavish
published in: Operations Research Letters
publication date: 1987-01-01T00:00:00Z
review text: This paper presents heuristics that are based on optimal partitioning of a travelling salesman tour, for solving the unequal weight delivery problem. The worst case error performance is given as a bound on the worst case ratio of the cost of the heuristic solution to the cost of the optimal solution. A fully polynomial procedure which consists of applying the optimal partitioning to a travelling salesman tour generated by Christofides' heuristic has a worst case error bound of 3.5-3/Q where Q is the capacity limit of the vehicles. When optimal partitioning is applied to an optimal travelling salesman tour, the worst case error bound becomes 3-2/Q.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4029296
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: optimal partitioning of a travelling salesman tour
zbMATH Keywords: unequal weight delivery problem
zbMATH Keywords: worst case error performance
zbMATH Keywords: fully polynomial procedure
zbMATH Keywords: heuristic
describes a project that uses: VRP
MaRDI profile type: Publication
full work available at URL: 0167-6377(87)90012-5
OpenAlex ID: W2017372614
cites work: Technical Note—Heuristics for Delivery Problems with Constant Error Guarantees
cites work: Heuristics with Constant Error Guarantees for the Design of Tree Networks
cites work: Tight bounds for christofides' traveling salesman heuristic
cites work: Q4744064
cites work: Q4184789
cites work: Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
cites work: A vehicle routing improvement algorithm comparison of a ''greedy'' and a matching implementation for inventory routing
cites work: Topological design of centralized computer networks—formulations and algorithms
cites work: An approach for solving a class of transportation scheduling problems
cites work: Bounds and Heuristics for Capacitated Routing Problems
description: scientific article; zbMATH DE number 4029296