Читать книгу Optimization and Machine Learning - Patrick Siarry - Страница 14
1.2. The capacitated vehicle routing problem with two-dimensional loading constraints
ОглавлениеThe 2L-CVRP is a variant of the classical CVRP characterized by the two-dimensionality of customer demand. The problem aims to serve a set of customers using a homogeneous fleet of vehicles with minimum total cost. The 2D loading constraints must be respected.
The 2L-CVRP is available in a set of real-life problems (Sbai et al. 2020b), for example household appliances and professional cleaning equipment. Table 1.1 presents a comparative study of the existing literature for the 2L-CVRP, which includes solution methods, variants and constraints.
Table 1.1. Comparative study of the 2L-CVRP
| Author | Problem | Routing problem Solution methods | Loading problem Solution methods |
| lori et al. (2007) Gendreau et al. (2008) Fuellerer et al. (2009) Zachariadis et al. (2009) | 2L-CVRP 2L-CVRP 2L-CVRP 2L-CVRP | Branch-and-cut TS ACO GTS | Branch-and-bound LH2SL, LH2U L LB, Branch and Bound Bottom-Left Fill (L,W axis) Max Touching Perimeter Max Touching Perimeter No Walls Min Area Bottom-Left Fill(L,W axis) Max Touching Perimeter Max Touching Perimeter No Walls Min. Area LBFH GRASP-ELS PRMP |
| Leung et al. (2011) | 2L-CVRP | EGTS | |
| Duhamel et al. (2011) Zachariadis et al. (2013) Wei et al. (2015) Wei et al. (2017) Sbai et al. (2020b) Leung et al. (2013) | 2L-CVRP 2L-CVRP 2L-CVRP 2L-CVRP 2L-CVRP 2L-HFVRP | GRASP-ELS LS VNS SA GA SAHLS | Skyline heuristic Open space based heuristic ALWF Bottom-Left Fill (L,W axis) Max. Touching Perimeter Max. Touching Perimeter No Walls Min. Area Max. fitness value Bottom-Left Fill (L,W axis) Max Touching Perimeter Max. Touching Perimeter No Walls Min. Area Max. fitness value Lower Bound L-cuts MA ALWF ILP GVNS BLH Best-Fit LS VNS VNS LS Bottom-Left Heuristics |
| Sabar et al. (2020) | 2L-HFVRP | MA | |
| Cote et al. (2013) Cote et al. (2020) Khebbache-Hadji et al. (2013) Sbai et al. (2017) Attanasio et al. (2007) Song et al. (2019) Pinto et al. (2015) Dominguez et al. (2016) Zachariadis et al. (2017) Pinto et al. (2017) Pinto et al. (2020) Zachariadis et al. (2016) Malapert et al. (2008) | S2L-CVRP S2L-CVRP 2L-CVRPTW 2L-CVRPTW 2L-CVRPTW 2L-CVRPTW 2L-VRPMB 2L-VRPB 2L-VRPB 2L-SPD 2L-VRPB 2L-VRPMB 2L-SPD 2L-VRPPD | L-Cuts L-Cuts MA GA ILP GVNS Insert-heur LNS Touch-Per LS VNS VNS LS Scheduling based-model |
