A neural network algorithm for the traveling salesman problem with backhauls

A neural network algorithm for the traveling salesman problem with backhauls

0.00 Avg rating0 Votes
Article ID: iaor20031637
Country: Netherlands
Volume: 44
Issue: 2
Start Page Number: 267
End Page Number: 281
Publication Date: Feb 2003
Journal: Computers & Industrial Engineering
Authors: ,
Keywords: statistics: data envelopment analysis
Abstract:

This paper introduces a new heuristic based on Kohonen's self-organizing feature map for the traveling salesman problem with backhauls (TSPB). The TSPB is an extension of the traveling salesman problem in which a set of customers is partitioned into a set of linehaul customers to be visited contiguously at the beginning of the route and a set of backhaul customers to be visited once all linehaul customers have been visited. The major innovation of the proposed heuristic is based on the design of a new network architecture, which consists of two separate chains of neurons. The network evolves into a feasible TSPB tour using four types of interactions: (1) the first chain interacts with the linehaul customers, (2) the second chain interacts with the backhaul customers, (3) the tails of the chains interact together, and (4) the heads of the two chains interact with the depot. The generated tour is then improved using the 2-opt procedure. The new heuristic is compared to the best available TSPB heuristics in the literature on medium to large-sized instances up to 1000 customers. The computational results demonstrate that the proposed approach is comparable in terms of solution quality and computational requirements.

Reviews

Required fields are marked *. Your email address will not be published.