traveling salesman problem

The combinatorial optimization problem of finding a cheapest closed tour — a cycle that passes through each of n cities once — when the travel cost between every pair of cities is known. Its decision version is NP-completeNP-complete, adj.: Describes problems, such as solving giant Sudokus, where a proposed answer is quick to check but no known method finds one quickly; a fast method for any one of them could be turned into one for all., and the number of distinct tours, (n − 1)!/2 for symmetric costs, rules out brute force beyond a few dozen cities. Exact solvers combine linear-programming relaxations, cutting planes and branch and boundbranch and bound, n.: A method for finding the provably best answer to a hard puzzle: divide the possibilities into groups, quickly estimate the best any group could offer, and throw out every group that cannot beat the best answer already in hand.; the Concorde solver has proved optimal tours through tens of thousands of cities. Heuristics such as 2-opt and Lin–Kernighan local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch., simulated annealingsimulated annealing, n.: An optimization method inspired by slowly cooling metal: early on it sometimes accepts worse solutions, to escape dead ends, and becomes pickier as a 'temperature' setting gradually drops., genetic algorithmsgenetic algorithm, n.: A problem-solving method that copies natural evolution: many candidate solutions compete, the best are 'bred' by mixing and randomly tweaking them, and over many generations the solutions improve. and ant colony optimizationant colony optimization, n.: A method for finding good routes and schedules inspired by how ants find short paths to food: simulated ants leave 'scent' on good paths, which attracts other ants, so the best routes gradually stand out. find near-optimal tours for millions of cities, and Christofides's algorithm guarantees a tour within 1.5 times the optimum when costs obey the triangle inequality. The problem is the classic benchmark for search and metaheuristicsmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one. and, since 2015, for neural combinatorial optimization with attentionattention, n.: A way for an AI model to choose what to focus on. For each word it processes, the model scores how relevant every other word is and draws information mostly from the relevant ones.-based models that learn to construct tours.

Our delivery problem is a traveling salesman problem with time windows, so we use a solver rather than a neural network.