reformulate_ATSP_as_TSP: Reformulate a ATSP as a symmetric TSP

In mhahsler/TSP: Traveling Salesperson Problem (TSP)

Reformulate a ATSP as a symmetric TSP

Description

A ATSP can be formulated as a symmetric TSP by doubling the number of cities (Jonker and Volgenant 1983). The solution of the TSP also represents the solution of the original ATSP.

Usage

reformulate_ATSP_as_TSP(x, infeasible = Inf, cheap = -Inf)

filter_ATSP_as_TSP_dummies(tour, atsp)

Arguments

x	an ATSP.
infeasible	value for infeasible connections.
cheap	value for distance between a city and its corresponding dummy city.
tour	a TOUR created for a ATSP reformulated as a TSP.
atsp	the original ATSP.

Details

To reformulate a ATSP as a TSP, for each city a dummy city (e.g, for 'New York' a dummy city 'New York*') is added. Between each city and its corresponding dummy city a very small (or negative) distance with value cheap is used. To ensure that the solver places each cities always occurs in the solution together with its dummy city, this cost has to be much smaller than the distances in the TSP. The original distances are used between the cities and the dummy cities, where each city is responsible for the distance going to the city and the dummy city is responsible for the distance coming from the city. The distances between all cities and the distances between all dummy cities are set to infeasible, a very large value which prevents the solver from using these links. We use infinite values here and solve_TSP() treats them appropriately.

filter_ATSP_as_TSP_dummies() can be used to extract the solution for the original ATSP from the tour found for an ATSP reformulated as a TSP. Note that the symmetric TSP tour does not reveal the direction for the ATSP. The filter function computed the tour length for both directions and returns the shorter tour.

solve_TSP() has a parameter as_TSP which preforms the reformulation and filtering the dummy cities automatically.

Note on performance: Doubling the problem size is a performance issue especially has a negative impact on solution quality for heuristics. It should only be used together with Concorde when the optimal solution is required. Most heuristics can solve ATSPs directly with good solution quality.

Value

reformulate_ATSP_as_TSP() returns a TSP object. filter_ATSP_as_TSP_dummies() returns a TOUR object.

Author(s)

Michael Hahsler

References

Jonker, R. and Volgenant, T. (1983): Transforming asymmetric into symmetric traveling salesman problems, Operations Research Letters, 2, 161–163.

See Also

Other TSP: ATSP(), Concorde, ETSP(), TSPLIB, TSP(), insert_dummy(), solve_TSP()

Examples

data("USCA50")

## set the distances from anywhere to Austin to zero which makes it an ATSP
austin <- which(labels(USCA50) == "Austin, TX")
atsp <- as.ATSP(USCA50)
atsp[, austin] <- 0
atsp

## reformulate as a TSP (by doubling the number of cities with dummy cities marked with *)
tsp <- reformulate_ATSP_as_TSP(atsp)
tsp

## create tour for the TSP. You should use Concorde to find the optimal solution.
# tour_tsp <- solve_TSP(tsp, method = "concorde")
# The standard heuristic is bad for this problem. We use it here because
#   Concord may not be installed.
tour_tsp <- solve_TSP(tsp)
head(labels(tour_tsp), n = 10)
tour_tsp
# The tour length is -Inf since it includes cheap links
#  from a city to its dummy city.

## get the solution for the original ATSP by filtering out the dummy cities.
tour_atsp <- filter_ATSP_as_TSP_dummies(tour_tsp, atsp = atsp)
tour_atsp
head(labels(tour_atsp), n = 10)

## This process can also be done automatically by using as_TSP = TRUE:
# solve_TSP(atsp, method = "concorde", as_TSP = TRUE)

## The default heuristic can directly solve ATSPs with results close to the
#  optimal solution of 12715.
solve_TSP(atsp, control = list(rep = 10))

mhahsler/TSP documentation built on July 29, 2023, 11:12 p.m.