Differential evolution algorithms with local search for the multi-productscapacitated vehicle routing problem with time windows: A case study of the ice industry

Abstract

This research aimsto offer a solution tothe capacitated vehicle routingproblem for multiple products, time windows and a heterogeneous fleet for ice transport. The problem structure isthatthe capacitated vehicle routing problem isone-to-many with multiple products, where each customer has a variety of product types and demands. Also, limited delivery time is considered for each customer. We used a mixed integer linear programming model to give an optimal solution, and propose a differential evolution method with a local search that we have developed. The objective is to sequence the delivery procedures for ice transport to minimize total costs, comprised oftraveling costs, driver wages and a penalty costs. Weobtained various solutions by a comparison ofour proposed solution and the optimal solution of the ice transport case study and differential evolution with local search (DELS)to validate the proposed metaheuristic. The relative improvement between the current practice of the ice transportin thecase study and the differential evolution with a local search was 3.70-25.75%. The differential evolution with alocal search outperformed current practices by an average by 2.29%.

Keywords

• Ice transportation
• Capacitated vehicle routing problem
• Time windows
• Differential evolution algorithm
• Local search