Heuristics for unequal weight delivery problems with a fixed error guarantee |
| |
| Institution: | 1. Department of Ecology and Environmental Science, Umeå University, SE 90187 Umeå, Sweden;2. Department of Physics, Umeå University, SE 90187 Umeå, Sweden;3. Department of Chemistry, Umeå University, SE 90187 Umeå, Sweden;4. Department of Wildlife, Fish, and Environmental Studies, SLU, Umeå, Sweden;5. School of Marine Studies, The University of the South Pacific, Laucala Bay Road, Suva, Fiji |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
