6533b825fe1ef96bd12831a5

RESEARCH PRODUCT

Efficient Local Search Limitation Strategies for Vehicle Routing Problems

Yuichi NagataOlli Bräysy

subject

Set (abstract data type)Mathematical optimizationbusiness.industryComputer scienceMultipath routingVehicle routing problemBenchmark (computing)Memetic algorithmContext (language use)Local search (optimization)Destination-Sequenced Distance Vector routingbusiness

description

In this paper we examine five different strategies for limiting the local search neighborhoods in the context of vehicle routing problems. The vehicle routing problem deals with the assignment of a set of transportation orders to a fleet of vehicles, and the sequencing of stops for each vehicle to minimize transportation costs. The examined strategies are applied to three standard neighborhoods and implemented in a recently suggested powerful memetic algorithm. Experimental results on 26 well-known benchmark problems indicate significant speedups of almost 80% without worsening the solution quality. On the contrary, in 12 cases new best solutions were obtained.

yearjournalcountryeditionlanguage
2008-01-01
https://doi.org/10.1007/978-3-540-78604-7_5