Sign In

Communications of the ACM

ACM TechNews

Improved Approach to the 'Traveling Salesperson Problem' Could Boost Logistics, Transport Sectors

View as: Print Mobile App Share:
A courier checking a parcel for delivery.

The Traveling Salesperson Problem involves a delivery driver who must call at a set number of cities that are connected by highways, all in one journey. The challenge is to find the shortest possible route that calls at each destination once, and to find

Credit: Luis Alvarez

Researchers at the U.K.'s University of Cambridge have developed an enhanced approach to the Traveling Salesperson Problem that yields high-quality solutions at a faster rate than other cutting-edge tools.

The challenge involves finding the shortest possible delivery route for visiting multiple destinations in a single trip.

The researchers' solution integrates a machine learning model supplying information about the previous best routes with a "metaheuristic" tool that draws the new route from this data.

Said Cambridge's Ben Hudson, "Our goal with this research is to improve such methods so that they produce better solutions—solutions that result in lower distances being traveled and therefore lower carbon emissions and reduced impact on the environment."

From University of Cambridge (U.K.)
View Full Article



Abstracts Copyright © 2022 SmithBucklin, Washington, DC, USA


No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account