A New Solution Approach For the Three-Dimensional Loading Capacitated Vehicle Routing Problem


Küçük M., Yıldız Ş. A.

41. Yöneylem Araştırması ve Endüstri Mühendisliği Ulusal Kongresi 2022, Denizli, Turkey, 26 - 28 October 2022, pp.4

  • Publication Type: Conference Paper / Summary Text
  • City: Denizli
  • Country: Turkey
  • Page Numbers: pp.4
  • Dokuz Eylül University Affiliated: Yes

Abstract

This study focuses on the Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP). The problem is of practical relevance in the distribution of goods because of its numerous real-world transport applications. The 3L-CVRP is one of the variants of the CVRP in which the goods to be shipped to customers are rectangular boxes of a certain size and loaded into the same rectangular loading spaces of the vehicles with three-dimensional loading space and weight capacity. Therefore, the problem solution includes a set of routes and a loading plan for each vehicle. Moreover, each loading plan has to meet some constraints; All the goods a customer needs must be placed in the same vehicle. The total weight of the items loaded in the vehicle must not exceed the vehicle weight capacity and satisfy the specific loading constraints before it is shipped.

Despite its practical relevance in freight distribution, the literature on this problem is limited due to its high combinatorial complexity. The 3L-CVRP generalizes two of the best-known problems in combinatorial optimization, the Vehicle Routing Problem, and the Three-Dimensional Bin Packing Problem. In this study, we have proposed a new solution approach based on the Evolutionary Algorithm using a new variable elitist strategy based on strength in the form of a sine wave. The algorithm combines two different heuristic information measures, routing and loading. In the computational study, all publicly available test instances have been solved. According to the computational results, the proposed approach has been found effective and has been observed to improve most of the best solutions that have already been reported.