Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Assignment Problem
Asymmetric Traveling Salesman Problem
Branch and Bound Algorithm
Exact Solution
Large Scale
Branch and Bound
Decision Tree
Related Publications
(3)
TSP Cuts Which Do Not Conform to the Template Paradigm
Exact Solution of Large Asymmetric Traveling Salesman Problems
A selforganizing neural network for the traveling salesman problem that is competitive with simulated annealing
Subscribe
Academic
Publications
Exact solution of largescale, asymmetric traveling salesman problems
Exact solution of largescale, asymmetric traveling salesman problems,10.1145/212066.212081,ACM Transactions on Mathematical Software,Giorgio Carpanet
Edit
Exact solution of largescale, asymmetric traveling salesman problems
(
Citations: 47
)
BibTex

RIS

RefWorks
Download
Giorgio Carpaneto
,
Mauro Dell' Amico
,
Paolo Toth
A lowestfirst, branchandbound algorithm for the
Asymmetric Traveling Salesman Problem
is presented. The method is based on the
Assignment Problem
relaxation and on a subtour elimination branching scheme. The effectiveness of the algorithm derives from reduction procedures and parametric solution of the relaxed problems associated with the nodes of the branchdecision tree. Largesize, uniformly, randomly generated instances of complete digraphs with up to 2000 vertices are solved on a DECstation 5000/240 computer in less than 3 minutes of CPU time. In addition, we solved on a PC 486/33 no wait flow shop problems with up to 1000 jobs in less than 11 minutes and realworld stacker crane problems with up to 443 movements in less than 6 seconds.
Journal:
ACM Transactions on Mathematical Software  TOMS
, vol. 21, no. 4, pp. 394409, 1995
DOI:
10.1145/212066.212081
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
portal.acm.org
)
(
portal.acm.org
)
More »
Citation Context
(19)
...Later, Carpaneto et al. extended their method for largescale (up to 2000 vertices) problems [
23
]...
Jani Boutellier
,
et al.
A Lowoverhead Scheduling Methodology for Finegrained Acceleration of...
...The following is a brief outline of the optimization algorithms provided in this toolbox: • shortest path shortest path, • minimum weighting tree min weight tree, • knapsack problem knapsack[17], • salesman problem salesman[
18
], • minimum linear constraint cost flow min lcost cflow using Busacker and Gowen (Roy) algorithm, • minimum linear cost flow min lcost flow1, • outofkilter algorithm min lcost flow2 using D. Bertsekas relaxation ...
Michael Baudin
,
et al.
Optimization with Scilab, present and future
...An effective branching rule for the ATSP with the AP relaxation is introduced in
Carpaneto and Toth (1980)
...
...The algorithms apply the subtour elimination scheme from
Carpaneto and Toth (1980)
, and the reduction procedure from Carpaneto et al. (1995) is used at the top node of the search tree to determine which arcs will never appear in an optimal solution...
Marcel Turkensteen
,
et al.
Tolerancebased Branch and Bound algorithms for the ATSP
...An exact solution can be found using the algorithm described in [
7
]...
Bjorn De Sutter
,
et al.
Placementandroutingbased register allocation for coarsegrained rec...
...Later, Carpaneto et al. extended their method for largescale (up to 2000 vertices) problems [
4
]...
Jani Boutellier
,
et al.
LowOverhead RunTime Scheduling for FineGrained Acceleration of Sign...
References
(14)
A Patching Algorithm for the Nonsymmetric TravelingSalesman Problem
(
Citations: 85
)
Richard M. Karp
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 8, no. 4, pp. 561573, 1979
Algorithm 750; CDT: a subroutine for the exact solution of largescale, asymmetric traveling salesman problems
(
Citations: 13
)
Giorgio Carpaneto
,
Mauro Dell' Amico
,
Paolo Toth
Journal:
ACM Transactions on Mathematical Software  TOMS
, vol. 21, no. 4, pp. 410415, 1995
Efficient Algorithms for Shortest Paths in Sparse Networks
(
Citations: 240
)
Donald B. Johnson
Journal:
Journal of The ACM  JACM
, vol. 24, no. 1, pp. 113, 1977
A restricted lagrangean approach to the travelling salesman problem
(
Citations: 28
)
E. Balas
,
N. Christofides
Journal:
Mathematical Programming
, 1981
Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
(
Citations: 46
)
Giorgio Carpaneto
,
Paolo Toth
Journal:
Management Science  MANAGE SCI
, vol. 26, no. 7, pp. 736743, 1980
Sort by:
Citations
(47)
A concise guide to the Traveling Salesman Problem
(
Citations: 3
)
Gilbert Laporte
Journal:
Journal of The Operational Research Society  J OPER RES SOC
, vol. 61, no. 1, pp. 3540, 2010
A Lowoverhead Scheduling Methodology for Finegrained Acceleration of Signal Processing Systems
(
Citations: 3
)
Jani Boutellier
,
Shuvra S. Bhattacharyya
,
Olli Silvén
Journal:
Journal of Signal Processing Systems  JSPS
, vol. 60, no. 3, pp. 333343, 2010
Production setupsequencing and lotsizing at an animal nutrition plant through atsp subtour elimination and patching
(
Citations: 1
)
Alistair R. Clark
,
Reinaldo Morabito
,
Eli A. V. Toso
Journal:
Journal of Scheduling  SCHEDULING
, vol. 13, no. 2, pp. 111121, 2010
A heuristic based on multiexchange techniques for a regional fleet assignment locationrouting problem
(
Citations: 6
)
Daniela Ambrosino
,
Anna Sciomachen
,
Maria Grazia Scutellà
Journal:
Computers & Operations Research  CoR
, vol. 36, no. 2, pp. 442460, 2009
Optimization with Scilab, present and future
Michael Baudin
,
Serge Steer
Conference:
IEEE International Workshop on Opensource Software for Scientific Computation  OSSC
, 2009