TSP in spreadsheets--A fast and flexible tool

Rasmus Rasmussen

Omega, 2011, vol. 39, issue 1, 51-63

Abstract: The traveling salesman problem (TSP) is well-known and many specially developed solution procedures have been constructed to solve particular variants of it. This paper considers several different variants of TSP. However, developing tailored solution procedures for each is impractical. These problems are non-deterministic polynomial-time hard (NP hard). Solving them using standard linear programming/mixed integer programming (LP/MIP) solvers has therefore only been regarded to be feasible for very small problems. A careful consideration of the problem formulation may facilitate efficient software utilization, and for real-world problems this can have a considerable impact. Problems that were previously regarded as large and unwieldy are now easily solvable using spreadsheets, thanks to the recent advancement in general optimization software. A comparison of spreadsheet solvers is made with other general purpose optimization tools like the Cplex solver. Here, spreadsheet solvers compete very well. Alternative formulations are implemented that are capable of solving real-world TSP variants that are not suitable for specialized solvers tailored to standard TSP. A performance evaluation is also made between a standard "tight" formulation and a general "wide" formulation. It is found that some solvers are more sensitive to the type of formulation than others.

Keywords: Traveling; salesmen; Assignment; Network; Spreadsheets (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305-0483(10)00026-5
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:39:y:2011:i:1:p:51-63

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().