A tabu search algorithm for the single vehicle routing allocation problem

L Vogt, C A Poojari and John Beasley
Additional contact information
L Vogt: EPFL-SB-IMA
C A Poojari: Brunel University

Journal of the Operational Research Society, 2007, vol. 58, issue 4, 467-480

Abstract: Abstract In the single vehicle routing allocation problem (SVRAP) we have a single vehicle, together with a set of customers, and the problem is one of deciding a route for the vehicle (starting and ending at given locations) such that it visits some of the customers. Customers not visited by the vehicle can either be allocated to a customer on the vehicle route, or they can be isolated. The objective is to minimize a weighted sum of routing, allocation and isolation costs. One special case of the general SVRAP is the median cycle problem, also known as the ring star problem, where no isolated vertices are allowed. Other special cases include the covering tour problem, the covering salesman problem and the shortest covering path problem. In this paper, we present a tabu search algorithm for the SVRAP. Our tabu search algorithm includes aspiration, path relinking and frequency-based diversification. Computational results are presented for test problems used previously in the literature and our algorithm is compared with the results obtained by other researchers. We also report results for much larger problems than have been considered by others.

Keywords: tabu search; median cycle problem; ring star problem; covering tour problem; covering salesman problem; shortest covering path problem (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2602165 Abstract (text/html)
Access to full text is restricted to subscribers.

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:pal:jorsoc:v:58:y:2007:i:4:d:10.1057_palgrave.jors.2602165

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2602165

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().