Optimization and Machine Learning. Patrick Siarry. Читать онлайн. Newlib. NEWLIB.NET

Автор: Patrick Siarry
Издательство: John Wiley & Sons Limited
Серия:
Жанр произведения: Программы
Год издания: 0
isbn: 9781119902874
Скачать книгу
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

      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.

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

      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