‘T’ for Tabu and Time Dependent Travel Time

Johan W. Joubert ()
Additional contact information
Johan W. Joubert: University of Pretoria

A chapter in Operations Research Proceedings 2006, 2007, pp 367-372 from Springer

Abstract: Abstract Even in its most basic form, the Vehicle Routing Problem and its variants are notoriously hard to solve. More often artificially intelligent algorithms are employed to provide near-optimal solutions. To be classified as “intelligent”, however, a solution strategy should be able to first analyze the environment in which the problem occurs, then solve it, and afterwards reflect on the solution process so as to improve future decision-making. Although reference is made to the entire context of the intelligence research project, this paper reports on the Tabu Search algorithm designed that catered for a problem with multiple soft time windows, a heterogeneous fleet, double scheduling, and time dependent travel time. An adaptive memory procedure was employed, initially populated with good initial feasible solutions, and the algorithm was tested on 60 problems based on established benchmark sets. The complex variant of the Vehicle Routing Problem required between 670 and 4762 seconds on a standard laptop computer, which is considered to be reasonable in the proposed application, and was consistent between different runs with an absolute mean deviation of 3.6%. The contribution is significant as it provides an algorithm that efficiently addresses a complex and practical application of the Vehicle Routing Problem. The algorithm can easily be extended to make use of multiple processors so as to reduce computational time.

Keywords: Initial Solution; Vehicle Route Problem; Incumbent Solution; Origin Tour; Feasible Position (search for similar items in EconPapers)
Date: 2007
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:oprchp:978-3-540-69995-8_60

Ordering information: This item can be ordered from
http://www.springer.com/9783540699958

DOI: 10.1007/978-3-540-69995-8_60

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().