A Multi-Start Simulated Annealing Algorithm for the Vehicle Routing Problem with Time Windows

Vehicle Routing Problems have been analyzed to reduce transportation costs of people and goods. More particularly, the Vehicle Routing Problem with Time Windows (VRPTW) imposes the period of time of customer availability as a constraint, a very common characteristic in real world picking up and deli...

Full description

Saved in:
Bibliographic Details
Main Authors: Oliveira, Humberto Cesar Brandao de, Vasconcelos, Germano Crispim, Alvarenga, Guilherme Bastos
Format: Conference Proceeding
Language:English
Subjects:
Analytical models
Computational modeling
Computer science
Computer simulation
Costs
Informatics
Routing
Simulated annealing
Transportation
Vehicles
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Vehicle Routing Problems have been analyzed to reduce transportation costs of people and goods. More particularly, the Vehicle Routing Problem with Time Windows (VRPTW) imposes the period of time of customer availability as a constraint, a very common characteristic in real world picking up and delivery problems. Using minimization of the total distance as the main objective to be fulfilled, this work implements an efficient hybrid system which associates a nonmonotonic Simulated Annealing technique to a Hill Climbing Strategy with Random Restart (Multi-Start). The algorithm performance is evaluated by comparing the results achieved with the best published works found in the literature of the 56 Solomon instances. The results outperformed or paired the individual best previous results in 36 out of the 56 instances.
ISSN:1522-4899
2375-0235
DOI:10.1109/SBRN.2006.4