THE PRECEDENCE CONSTRAINED TRAVELING SALESMAN PROBLEM

スポンサーリンク

概要

• 論文の詳細を見る

• We consider a generalization of the classical traveling salesman problem (TSP) called the precedence constrained traveling salesman problem (PCTSP), i.e. given a directed complete graph G(V, E), a distance D_<ij> on each arc (i,j) ∈ E, precedence constraints ≺ on V, we want to find a minimum distance tour that starts node 1 ∈ V, visits all the nodes in V - {1}, and returns node 1 again so that node i is visited before node j when i ≺ j. We present a branch and bound algorithm for the exact solutions to the PCTSP incorporating lower bounds computed from the Lagrangean relaxation. Our lower bounding procedure is a generalization of the restricted Lagrangean method that has been successfully adapted to the TSP by Balas and Christofides [2]. Our branch and bound algorithm also incorporates several heuristics and variable reduction tests. The computational results with up to 49 nodes b-how that our algorithm computes exact solutions to several classes of precedence constraints within acceptable computational requirements.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Kubo Mikio

  Waseda University

• Kasugai Hiroshi

  Waseda University

関連論文

• HEURISTIC ALGORITHMS FOR THE SINGLE VEHICLE DIAL-A-RIDE PROBLEM
• A LAGRANGEAN APPROACH TO THE FACILITY LOCATION PROBLEM WITH CONCAVE COSTS
• THE PRECEDENCE CONSTRAINED TRAVELING SALESMAN PROBLEM
• ON THE CORE OF THE NETWORK DESIGN GAME
• THE PROBABILISTIC NETWORK DESIGN PROBLEM
• RANDOMIZED DECISION STRATEGY FOR THE HIERARCHICAL OPTIMIZATION PROBLEMS

スポンサーリンク