Читать книгу Optimization and Machine Learning - Patrick Siarry - Страница 13

Although the vehicle routing problem (VRP) is the most studied combinatorial optimization problem, the challenge still remains to achieve the most optimal and effective results (Sbai et al. 2020a). The VRP aims to minimize total traveling cost in cases where a fleet of identical vehicles is used to visit a set of customers. The VRP is used in many real-world applications, for example: pharmaceutical distribution, food distribution, the urban bus problem and garbage collection. The basic version of the VRP is known as the capacitated VRP (CVRP); each vehicle has a fixed capacity which must be respected and must not be exceeded when loading items. It is aimed at minimizing the total cost of serving all the customers. The CVRP can be extended to the VRP with time windows (VRPTW) by adding time windows to define the overall traveling time for a vehicle. It can also be extended to the VRP with pickups and deliveries (VRPPD) where orders may be picked up and delivered. Another variant of the basic CVRP is the VRP with backhauls (VRPB). Here, pickups and deliveries may be combined in a single route; all delivery requests therefore need to be performed before the empty vehicle can collect goods from customer locations. Two surveys, conducted by Cordeau et al. (2002) and Laporte (2009), provide further details.

Loading and transporting items from the depot to different customers are practical problems that are regularly encountered within the logistics industry. The loading problem can be extended to the BBP. When taking into account the number of dimensions that are relevant to the problem, packing problems are classified into 2D and 3D problems. The first related problem is the 2D-BPP (Zang et al. 2017; Wei et al. 2018; Sbai and Krichen 2019) where both items and bins are rectangular and the aim is to pack all items, without overlap, into the minimum number of bins. The second one is the 3D-BPP (Araujo et al. 2019; Pugliese et al. 2019); this consists of finding an efficient and accurate way to place 3D rectangular goods into the minimum number of 3D containers (bins), while ensuring goods are housed completely within the containers.

In recent years, some researchers have focused on the combined routing and loading problem. The combinatorial problem includes the 2D loading VRP, denoted as 2L-CVRP and the 3D loading VRP, denoted as 3L-CVRP. The purpose of addressing these problems is to minimize the overall travel costs associated with all the routes that serve each of the customers, as well as to satisfy all the constraints of the loading dimensions. The two problems are solved by exact and metaheuristic algorithms which are reviewed in detail in the sections that follow. For further information, we refer the reader to Pollaris et al. (2015) and Iori and Martello (2010), wherein detailed surveys are presented in relation to vehicle routing with packing problems.

This chapter is organized as follows: section 1.2 provides an overview of the literature concerning VRPs in combination with 2D loading problems and the existing variants and constraints. Section 1.3 focuses on VRPs with 3D loading problems and the existing variants and constraints. Finally, in section 1.4, we close with conclusions and opportunities for further research.