Stochastic techniques for vehicle routing problems

Abstract

Vehicle routing problems (VRPs) are resource management problems where the aim is to use the limited number of resources to a large number of jobs so that a maximum number of jobs can be completed with minimum cost. These problems are made complicated by the inclusion of temporal and technological constraints. These problems belong to the class of nondeterministic polynominal-time complete (NP) problems. This paper describes the application of stochastic techniques, namely simulated annealing (SA) and genetic algorithm (GA), to solve VRPs. It is found empirically that SA gives better results than GA for all randomly generated under-, critically- and over-resourced VRPs in almost all cases.

Keywords:

• Vehicle routing problems
• Simulated annealing
• Genetic algorithms
• Resource management
• Temporal constraint
• Technological constraint