Skip to the main content

Automatika : journal for control, measurement, electronics, computing and communications, Vol. 55 No. 2, 2014.

Original scientific paper

https://doi.org/10.7305/automatika.2014.01.580

Vehicle Routing Optimization Using Multiple Local Search Improvements

Juraj Fosin orcid id orcid.org/0000-0002-3176-5239 ; Department of Intelligent Transportation Systems, Faculty of Transport and Traffic Sciences, University of Zagreb Vukelićeva 4, HR-10000 Zagreb, P.O. Box 170, Croatia
Tonči Carić orcid id orcid.org/0000-0001-8564-4304 ; Department of Intelligent Transportation Systems, Faculty of Transport and Traffic Sciences, University of Zagreb Vukelićeva 4, HR-10000 Zagreb, P.O. Box 170, Croatia
Edouard Ivanjko ; Department of Intelligent Transportation Systems, Faculty of Transport and Traffic Sciences, University of Zagreb Vukelićeva 4, HR-10000 Zagreb, P.O. Box 170, Croatia

Full text: english pdf 821 Kb

page 124-132

downloads: 1.946

cite

Abstract

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 7, 065 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 improvement pivoting rule and 9 times compared to the best improvement pivoting rule, without any substantial degradation in quality of the obtained solution.

Keywords

VRP; CVRP; iterated local search; multiple improvements

Hrčak ID:

125607

URI

https://hrcak.srce.hr/125607

Publication date:

16.7.2014.

Article data in other languages: croatian

Visits: 3.152 *