Vehicle Routing Optimization Using Multiple Local Search Improvements (CROSBI ID 195246)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Fosin, Juraj ; Carić, Tonči ; Ivanjko, Edouard
engleski
Vehicle Routing Optimization Using Multiple Local Search Improvements
Combinatorial optimization problems on graphs arise in many practical applications. One of the most studied practical combinatorial optimization problem is the Vehicle Routing Problem (VRP). When coupled with modern in-car navigation and fleet management software, real world applications of VRP optimization result in significant cost savings. In this paper novel multiple improvements pivoting rule for Capacitated VRP (CVRP) is proposed. Its application significantly reduces computational time needed for CVRP optimization. A novel pivoting rule is implemented as part of the search step selection mechanism in the iterated local search algorithm. Augmented iterated local search algorithm is tested on 4 large scale real- world problems in Croatia with up to 7065 customers and 236 vehicles and on standard CVRP benchmark sets. Real-world problem data was obtained from a large Croatian logistics company. Comparison of well known first and best pivoting rules with proposed novel multiple improvements pivoting rule regarding travel distance, number of search moves and computational time is given. Achieved computational speed-ups are up to 29 times compared to the first and 9 times compared to the best improvement pivoting rule, without any substantial degradation in quality of the obtained solution.
VRP ; CVRP ; iterated local search ; multiple improvements
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o izdanju
55 (2)
2014.
124-132
objavljeno
0005-1144
1848-3380
10.7305/automatika.2014.01.580
Povezanost rada
Elektrotehnika, Računarstvo, Tehnologija prometa i transport