Operations Research · 1983 · 127 citations · 6 references
ComputingComputer ScienceIndustrial EngineeringAlgorithmsOptimizationSchedulingBranch And BoundCombinatorial OptimizationShortest Path AlgorithmsTransportation ProblemsBoundingBounding TechniquesDisjunctive Graph RepresentationHeuristic AlgorithmsTraveling Salesman ProblemTraveling Salesperson Problem
The time‑constrained traveling salesman problem extends the classic TSP by adding time‑window constraints on city visits, and its dual formulation is a disjunctive graph model familiar from scheduling theory. This note provides a concise formulation of the time‑constrained traveling salesman problem. The model assumes symmetric distances satisfying the triangle inequality, permits waiting at cities for time windows, and uses a longest‑path algorithm to generate bounds for a branch‑and‑bound solver. Computational experiments on small to moderate‑size instances demonstrate the algorithm’s performance.
The time-constrained traveling salesman problem is a variation of the familiar traveling salesman problem that includes time window constraints on the time a particular city, or cities, may be visited. This note presents a concise formulation of the time-constrained traveling salesman problem. The model assumes that the distances of the problem are symmetrical and that the triangle inequality holds. Additionally, the model allows the salesman to wait at a city, if necessary, for a time window to open. The dual of the formulation is shown to be a disjunctive graph model, which is well known from scheduling theory. A longest path algorithm is used to obtain bounding information for subproblems in a branch and bound solution procedure. Computational results are presented for several small to moderate size problems.
6