Information Technology Reference
In-Depth Information
An Application of Late Acceptance
Hill-Climbing to the Traveling Purchaser
Problem
Andreas Goerler, Frederik Schulte, and Stefan Voß
Institute of Information Systems (IWI), University of Hamburg, Von-Melle-Park 5,
20146 Hamburg, Germany
a.goerler@gmx.de,
{ frederik.schulte,stefan.voss } @uni-hamburg.de
Abstract. Late Acceptance Hill Climbing (LAHC) is a recent meta-
heuristic in the realm of local search based procedures. The basic idea is
to delay the comparison between neighborhood solutions and to compare
new candidate solutions to a solution having been current several steps
ago. The LAHC was first presented at the PATAT 2008 conference and
successfully tested for exam timetabling, the traveling salesman problem
(TSP) and the magic square problem and the results seemed extraordi-
nary. The purpose of this paper is to analyze the behavior of the method
and to provide some extended understanding about its success and limi-
tations. To do so, we investigate the method for a generalized version of
the TSP, the traveling purchaser problem.
Keywords: Metaheuristic, Late Acceptance Hill-Climbing, Traveling
Purchaser Problem.
1 Introduction
The Traveling Purchaser Problem (TPP) is a well-known generalization of the
Traveling Salesman Problem (TSP) [13,15,17,21] with wide applicability [10,18]
and it occurs in many real-world applications related to routing, warehousing
and scheduling. Starting from home a purchaser can travel to a set of markets
providing different products at different prices. The aim is to fulfill a shopping list
of products while minimizing the sum of traveling and purchasing costs. We apply
a recent metaheuristic to the TPP, namely the Late-Acceptance Hill-Climbing
(LAHC) heuristic. LAHC may be regarded as a simplification or modification
of simulated annealing or threshold accepting. It was originally introduced by
Burke and Bykov [5] and it won the 1st prize in the International Optimization
Competition. LAHC is a one-point iterative search procedure with the general
idea of delaying the comparison between neighborhood solutions. The intention
behind this late acceptance strategy is to avoid the problem of getting stuck
in a local optimum that many greedy search procedures have. The method was
successfully tested for some problems and the purpose of this paper is to examine
if an application of the LAHC to the TPP is also successfully possible.
 
Search WWH ::




Custom Search