Abstract
Interactive methods for vehicle routing axe appealing because they integrate the insight and experience of the user and the power and precision of heuristics in an interactive environment. Although best known results for benchmark problems are attributed to tabu search, interactive methods give results within about 3% of these solutions, whilst retaining the advantage of user control. A new interactive construction method using GRASP will be presented. The method allows vehicles to make all their deliveries, and then make pick-ups before returning to the depot. A Windows implementation allows the user to control the solution process by selecting initial outline routes of one or more deliveries followed by pick-ups. The user can also try to improve the solution, especially if it is infeasible, using interactive tools. Results will be shown for benchmark problems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
B.M. Baker. Further Improvements to Vehicle Routing Heuristics. JORS, 43:1009–1012, 1992.
P. Festa and M. Resende. GRASP: An Annotated Bibliography. In: Essays and Surveys on Metaheuristics, P. Hansen and C.C. Ribeiro, editors, Kluwer, 2001 (this volume).
M. Fisher and R. Jaikumar. A Generalised Assignment Heuristic for Vehicle Routing. Networks, 11:109–124, 1981.
M. Gendreau, A. Hertz, and G. Laporte. The Traveling Salesman Problem with Backhauls. Computers and Operations Research, 23:501–508, 1996.
M. Goetschalckx and C. Jacobs-Blecha. The Vehicle Routing Problem with Backhauls. European Journal of Operational Research, 42:39–51, 1998.
C.A. Hjorring. The Vehicle Routing Problem and Local Search Metaheuristics. PhD Thesis, University of Auckland, 1995.
G. Kontoravdis and A.J.F. Bard. A GRASP for the Vehicle Routing Problem with Time Windows. ORSA Journal on Computing, 7:10–23, 1995.
N. Mladenovic and P. Hansen. Variable Neighborhood Search. Computers and Operations Research, 24:1097–1100, 1997.
M.G.C. Resende. Greedy Randomized Adaptive Search Procedures (GRASP). To appear in: Encyclopedia of Optimization, C. Floudas and P.M. Pardalos, editors, Kluwer.
P. Toth and D. Vigo. A Heuristic Algorithm for the Symmetric and Asymmetric Vehicle Routing Problems With Backhauls. EJOR European Journal of Operational Research, 113:528–543, 1999.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer Science+Business Media New York
About this chapter
Cite this chapter
Carreto, C., Baker, B. (2002). A Grasp Interactive Approach to the Vehicle Routing Problem with Backhauls. In: Essays and Surveys in Metaheuristics. Operations Research/Computer Science Interfaces Series, vol 15. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-1507-4_9
Download citation
DOI: https://doi.org/10.1007/978-1-4615-1507-4_9
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4613-5588-5
Online ISBN: 978-1-4615-1507-4
eBook Packages: Springer Book Archive