INFOR Information Systems and Operational Research · 1994 · 52 citations · 0 references
Natural SciencesTransportation PlanningAlgorithmsOptimizationTransportationBranch And BoundCombinatorial OptimizationDynamic ProgrammingHeuristic OptimizationHeuristic SearchTransportation ProblemsBoundingDial-a-ride ProblemDial-a-ride SchedulingHamiltonian Path AlgorithmsHamiltonian Path ProblemHeuristic AlgorithmsTraveling Salesman ProblemTraveling Salesperson Problem
The Traveling Salesman Problem with Precedence Constraints is to find an hamiltonian tour of minimum cost in a graph G = (X,A) of n vertices, starting from vertex 1, visiting every vertex that must precede i before i (i = 2,3,..., n) and returning to vertex 1. This problem is NP-hard and arises in practical transportation and sequencing problems. In this paper we describe a new bounding procedure and a new optimal algorithm, based on dynamic programming. Computational results are given for randomly generated test problems, including the dial-a-ride problem with the classical TSP objective function.