reformulate_ATSP_as_TSP: Reformulate a ATSP as a symmetric TSP

Description Usage Arguments Details Value Author(s) References See Also Examples

View source: R/reformulare_ATSP_as_TSP.R

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

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

Arguments

x

an ATSP.

infeasible

value for infeasible connections.

cheap

value for distance between a city and its corresponding dummy city.

Details

To reformulate the 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 negative or very small distance with value cheap is used. This makes sure that each cities always occurs in the solution together with its dummy city. 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 makes the infeasible.

Value

a TSP 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

ATSP, TSP.

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
data("USCA50")

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

## reformulate as a TSP
tsp <- reformulate_ATSP_as_TSP(atsp)
labels(tsp)

## create tour (now you could use Concorde or LK)
tour_atsp <- solve_TSP(tsp, method="nn")
head(labels(tour_atsp), n = 10)
tour_atsp
## Note that the tour has a lenght of -Inf since the reformulation created
## some -Inf distances

## filter out the dummy cities (we specify tsp so the tour lenght is 
## recalculated)
tour <- TOUR(tour_atsp[tour_atsp <= n_of_cities(atsp)], tsp = atsp)
tour

Example output

  [1] "Abilene, TX"        "Akron, OH"          "Albany, NY"        
  [4] "Albuquerque, NM"    "Alert, NT"          "Allentown, PA"     
  [7] "Amarillo, TX"       "Anchorage, AK"      "Ann Arbor, MI"     
 [10] "Asheville, NC"      "Ashland, KY"        "Atlanta, GA"       
 [13] "Atlantic City, NJ"  "Augusta, GA"        "Augusta, ME"       
 [16] "Austin, TX"         "Bakersfield, CA"    "Baltimore, MD"     
 [19] "Bangor, ME"         "Baton Rouge, LA"    "Battle Creek, MI"  
 [22] "Bay City, MI"       "Beaumont, TX"       "Belleville, ON"    
 [25] "Bellingham, WA"     "Berkeley, CA"       "Billings, MT"      
 [28] "Biloxi, MS"         "Binghamtom, NY"     "Birmingham, AL"    
 [31] "Bismarck, ND"       "Bloomington, IL"    "Boise, ID"         
 [34] "Boston, MA"         "Bowling Green, KY"  "Brandon, MB"       
 [37] "Brantford, ON"      "Brattleboro, VT"    "Bridgeport, CT"    
 [40] "Brockton, MA"       "Buffalo, NY"        "Burlington, ONT"   
 [43] "Burlington, VT"     "Butte, MT"          "Calgary, AB"       
 [46] "Cambridge, MA"      "Canton, OH"         "Carson City, NV"   
 [49] "Cedar Rapids, IA"   "Central Islip, NY"  "Abilene, TX*"      
 [52] "Akron, OH*"         "Albany, NY*"        "Albuquerque, NM*"  
 [55] "Alert, NT*"         "Allentown, PA*"     "Amarillo, TX*"     
 [58] "Anchorage, AK*"     "Ann Arbor, MI*"     "Asheville, NC*"    
 [61] "Ashland, KY*"       "Atlanta, GA*"       "Atlantic City, NJ*"
 [64] "Augusta, GA*"       "Augusta, ME*"       "Austin, TX*"       
 [67] "Bakersfield, CA*"   "Baltimore, MD*"     "Bangor, ME*"       
 [70] "Baton Rouge, LA*"   "Battle Creek, MI*"  "Bay City, MI*"     
 [73] "Beaumont, TX*"      "Belleville, ON*"    "Bellingham, WA*"   
 [76] "Berkeley, CA*"      "Billings, MT*"      "Biloxi, MS*"       
 [79] "Binghamtom, NY*"    "Birmingham, AL*"    "Bismarck, ND*"     
 [82] "Bloomington, IL*"   "Boise, ID*"         "Boston, MA*"       
 [85] "Bowling Green, KY*" "Brandon, MB*"       "Brantford, ON*"    
 [88] "Brattleboro, VT*"   "Bridgeport, CT*"    "Brockton, MA*"     
 [91] "Buffalo, NY*"       "Burlington, ONT*"   "Burlington, VT*"   
 [94] "Butte, MT*"         "Calgary, AB*"       "Cambridge, MA*"    
 [97] "Canton, OH*"        "Carson City, NV*"   "Cedar Rapids, IA*" 
[100] "Central Islip, NY*"
 [1] "Brantford, ON*"   "Brantford, ON"    "Burlington, ONT*" "Burlington, ONT" 
 [5] "Buffalo, NY*"     "Buffalo, NY"      "Belleville, ON*"  "Belleville, ON"  
 [9] "Binghamtom, NY*"  "Binghamtom, NY"  
object of class 'TOUR' 
result of method 'nn' for 100 cities
tour length: -Inf 
object of class 'TOUR' 
result of method 'NA' for 50 cities
tour length: 20114 

TSP documentation built on May 23, 2019, 1:03 a.m.