Optimization and Machine Learning. Patrick Siarry

3L-CVRP with backhaul

      The combination of VRP with backhauls and loading constraints is a recently studied problem. Bortfeldt et al. (2015) proposed a large neighborhood search and a variable neighborhood search (LNS-VNS) for solving the 3D VRP with backhaul in both routing and a packing procedure in addition, a tree search heuristic (TSH) is considered for loading items. Koch et al. (2018) addressed the CVRP with time windows and 3D loading constraints (3L-VRPSDPTW). They used a large neighborhood search to solve the problem. Reil et al. (2018) extended the last approach proposed by Bortfeldt et al. (2015) for the VRPBTW with 3D loading constraints by considering various types of backhauls. Koch et al. (2020) proposed a TS for the routing problem and a set of loading heuristics for the loading problem for solving the 3L-CVRP with mixed backhauls (3L-VRPMB).

      1.3.3.3. 3L-CVRP with pickup and delivery

Bartok and Imreh (2011) used a simple local search method for solving the 3L-VRPPD. Mannel and Bortfeldt (2016) discussed several 3L-VRPPD variants and hybrid approaches based on LNS and tree search heuristics are proposed for packing boxes.

      1.3.3.4. 3L-CVRP with split delivery

      Yi and Bortfeldt (2016) addressed the 3L-SDVRP with the same packing constraints as the 3L-CVRP in Gendreau formulation. Only inevitable splits are allowed, that is serving a customer in two or more routes is only permitted if not all boxes can be packed into a single loading space. A hybrid heuristic is developed that can be considered as a preliminary variant of the algorithm presented here.

      Li et al. (2018) proposed a novel data-driven three-layer search algorithm to solve the 3L-SDVRP. They minimize the number of vehicles used as a first priority and the total travel distance as a second priority.

      Bortfeldt and Yi (2020) studied two variants of the 3L-SDVRP. In the first, a delivery is only split if the customer demand cannot be carried by a single vehicle. In the second, splitting customer deliveries can be done any number of times. The authors proposed a hybrid algorithm consisting of an LS and a GA to solve the two variants.

      Table 1.2 presents a comparative study of the existing literature on 3L-CVRP.

      1.3.4. Computational analysis

      The set of instances used for the 3L-CVRP is available at http://www.or.deis.unibo.it/research.html and was introduced by Gendreau et al. (2006). There are in total 27 3L-CVRP instances available on the web which provide an interesting test bed for the comparison of different heuristic and metaheuristic solutions. The vehicle characteristics are W = 25, H = 30 and L = 60, respectively. The demand of each customer is between 1 and 3. The capacity of vehicles is 0.75.

Table 1.2. Comparative study of the 3L-CVRP

Author	Problem	Routing problem	Loading problem
		Solution methods	Solution methods
Gendreau et al. (2006) Apile et al. (2007) Tarantilis et al. (2009) Fuellerer et al. (2010) Ren et al. (2011) Massen et al. (2012) Bortfeldt (2012) Wisniewski et al. (2011) Zhu et al. (2012) Miao et al. (2012) Ruan et al. (2013) Bortfeldt and Homberger-2013 Tao and Wang (2015) Junqueira etal. (2013) Hokima et al. (2016) Vega et al. (2020) Moura (2008) Moura and Oliveira (2009) Zhang et al. (2017) Moura et al. (2019) Vega et al. (2019) Ceschia etal. (2013) Pace etal. (2015) Pollaris et al. (2017) Bortfeldt et al. (2015) Koch et al. (2018) Reil et al. (2018) Koch et al. (2020) Bartok and Imreh (2011) Mannel and Bortfeldt (2016) Yi and Bortfeldt (2016) Li et al. (2018) Bortfeldt and Yi (2020)	3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRP 3L-CVRPTW 3L-CVRPTW 3L-CVRPTW 3L-CVRPTW 3L-CVRPTW 3L-HCVRP 3L-HFCVRPTW CVRP with pallet loading and axle weight constraints 3L-VRPB 3L-VRPBTW 3L-VRPBTW 3L-VRPMB 3L-VRPPD 3L-VRPD 3L-SDVRP 3L-SDVRP 3L-SDVRP	TS SA LS-GLS ACO Branch-and- bound black box algorithm TS TS TS GA HBMO P1R2 TS integer linear programming model Branch-and-Cut GRASP-CWS GA LS, GRASP TS-ABC MILP NLMIP LNS ILS and SA ILS LNS/VNS LNS TS TS LS LNS TS Data-driven 3-layer GA-LS	TS SA LS-GLS ACO Branch-and-bound black box algorithm TRSA bottom-left Deepest-Bottom-Left-Fill heuristic and the Maximum Touching Area TS six heuristics P1R2 least waste algorithm Branch-and-Cut GRASP-CWS GA LS, GRASP TS-ABC MILP NLMIP LNS ILS and SA ILS TSH LNS TS TS LS TSH TS Data-driven 3-layer GA-LS

1.4. Perspectives on future research

In this review, the last decade of publications related to the combination VRP with 2/3D loading problems with additional variants and constraints has been surveyed. A comparative study of the existing optimization methods such as exact, heuristic and metaheuristic is described. These promising research areas give the opportunity for solving real-world problems in transportation. Given the importance of this problem, it still remains a challenge. However, future research could extend on the 2L-CVRP with multi-objective optimization. In addition, the 2L-VRP has been studied on the static case in which all information is known at the time of the planning routes. However, in most real-life applications, new customer requests can happen over time and thus trouble the optimal routing schedule that was originally invented. Therefore, the problem can be studied in the dynamic case.

1.5. References

      Aprile, D., Egeblad, J., Garavelli, A.C., Lisi, S., Pisinger, D (2007). Logistics optimization: Vehicle routing with loading constraints. In Proceedings of the 19th International Conference on Production Research. Informs, Valparaiso, Chile.

      Araujo, L.J., Ozcan, E., Atkin, J.A., Baumers, M. (2019). Analysis of irregular three-dimensional packing problems in additive manufacturing: A new taxonomy and dataset. International Journal of Production Research, 57(18), 5920–5934.

      Attanasio A., Fuduli A., Ghiani, G., Triki, C. (2007). Integrated shipment dispatching and packing problems: A case study. Journal of Mathematical Modelling