An exact parallel algorithm for the resource constrained traveling salesman problem with application to scheduling with an aggregate deadline

ABSTRACT

The Resource Constrained Traveling Salesman Problem (RCTSP) is introduced and an optimal algorithm for its solution is presented. The RCTSP is shown to subsume the Prize Collecting TSP and Orienteering Problem. Computational results are presented for sequential and parallel computations for problems containing up to 200 cities. The RCTSP algorithm is used to optimally schedule a processing facility involving sequence dependent transition costs and an aggregate due date on all job completion times. A penalty is incurred for each job not completed by the aggregate due date.

REFERENCES

• 1: E. Balas, "The Prize Collecting Traveling Salesman Problem," Management Science Research Report No. MSRR-539, 1987.
• 2: M. Fischetti and P. Toth, "An Additive Approach for the Optimal Solution of the Prize-Collecting Traveling Salesman Problem," Research Report OR/87/4, 1987.
• 3: J.E. Beasley and N. Christofides, "'An Algorithm for the Resource Constrained Shortest Path Problem," Networks, vol. 19, pp. 379-394, 1989.
• 4: L F. Pekny, D. L. Miller, and G. J. McRae, "An Exact Parallel Algorithm for Scheduling When Production Costs Depend on Consecutive System States," Computers and Chemical Engineering, 1989. submitted
• 5: B.L. Golden. L. Levy, and R. Vohra, "The Orienteering Problem," Naval Research Logistics, vol. 34, pp. 307- 318, 1987.
• 6: T. Tsiligirides, "Heuristic Methods Applied to Orienteering," J. Operational Research Society, vol. 35, no. 9, pp. 797-809, 1984.
• 7: G.B. Dantzig, D. R. Fulkerson, and S. M. Johnson, "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, vol. 2, p. 393, 1954.
• 8: G. B. Dantzig, D. R. Fulkerson, and S. M. Johnson, "On a Linear-Programming, Combinatorial Approach to the Traveling-Salesman Problem," Operations Research, vol. 7, p. 58, 1959.
• 9: E. L. Lawler, J. K. Lenstra, A. H. G. R~mooy Kan, and D. B. Shmoys, The Traveling Salesman Problem A Guided Tour of Combinatorial Optimization, Wiley, New York, 1985.
• 10: D.L. Miller and J. F. Pekny, "Results From A Parallel Branch and Bound Algorithm For Solving Large Asymmetric Traveling Salesman Problems," Operations Research Letters, vol. 8, pp. 129-135, 1989.
• 11: J.F. Pekny and D. L. Miller, "A Parallel Branch and Bound Algorithm For Solving Large Asymmetric Traveling Salesman Problems," EDRC Report 05-27-88, Carnegie Mellon University, Pittsburgh, PA, 1988.
• 12: S. Martello and P. Toth, "Linear Assignment Problems," Annals of Discrete Mathematics, vol. 31, pp. 259-282, 1987.
• 13: M.L. Fisher, "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, vol. 27, no. 1, 1981.
• 14: E. Balas and P. Toth, "Branch and Bound Methods," in The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, ed. E. L. Lawler, J. K. Lenstra, A. H. G. Rirmooy Kan, D. B. Shmoys, John Wiley & Sons, New York, 1985.
• 15: M. Bellrnore and J. C. Malone, "Pathology of Traveling Salesman Subtour-Elimination Algorithms," Operations Research, vol. 19, pp. 278-307, 1971.
• 16: K.G. Murty, "An Algorithm For Ranking All the Assignments in Order of Increasing Cost," Operations Research, vol. 16, pp. 682-687, 1968.
• 17: T.H.C. Smith, V. Srinivasan, and G. L, Thompson, "Computational Performance of Three Subtour Elimination Algorithms for Solving Asymmetric Traveling Salesman Problems," Annals of Discrete Mathematics, vol. 1, pp. 495-506, 1977.
• 18: G. Carpaneto and P. Toth, "Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem," Management Science, vol. 26, no. 7, pp. 736-743, 1980.
• 19: M.S. Bazaraa and C. M. Shetty, Nonlinear Programming Theory and Algorithms, Wiley, New York, 1979.
• 20: R. M. Karl3, "A Patching Algorithm for the Nonsynmaetrie Traveling Salesman Problem," SlAM J. Computing, vol. 8, pp. 561-573, 1984.
• 21: Randall Rettberg , Robert Thomas, Contention is no obstacle to shared-memory multiprocessing, Communications of the ACM, v.29 n.12, p.1202-1212, Dec. 1986 [doi>10.1145/7902.7905]
• 22: G. Li and B. W. Wah, "Computational Efficiency of Parallel Approximate Branch-and-Bound Algorithms," International Conference on Parallel Processing, pp. 473-480, 1984.
• 23: Ten-Hwang Lai , Sartaj Sahni, Anomalies in parallel branch-and-bound algorithms, Communications of the ACM, v.27 n.6, p.594-602, June 1984 [doi>10.1145/358080.358103]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Theory