###### Abstract  
In practical logistic distributions, uncertainties may exist in each distribution process, and sometimes suppliers have to take undesirable measures to deal with the subsequent schedule variances. In light of the uncertainty of customers in logistics distribution and the widely applied two-dimensional loading patterns in transportation, we propose and formulate a two-dimensional loading-constrained vehicle routing problem with stochastic customers (2L-VRPSC), where each customer has a known probability of presence and customers' demands are a set of non-stackable items. A stochastic modeling platform of 2L-VRPSC is established based on a Monte Carlo simulation and scenario analysis to minimize the expected total transportation cost. To achieve this, an enhanced adaptive tabu search (EATS) algorithm incorporating the multi-order bottom-fill-skyline (MOBFS) packing heuristic is proposed, where the EATS algorithm searches for the optimal routing combination and the MOBFS checks the feasibility of each route and guides the EATS to search for feasible solutions. The widely used two-dimensional loading-constrained vehicle routing problem (2L-VRP) benchmarks under different loading configurations considering items' sequential and rotation constraints are applied for experiments, which demonstrates the comparable efficiency of the proposed EATS-MOBFS for solving 2L-VRP. Furthermore, the results and analysis of experiments based on the new 2L-VRPSC instances verify the versatility of the proposed solving approach, which is capable of providing more practical solutions to some real-life scenarios with customers' uncertain information. adaptive tabu search; customer uncertainty; loading constraints; vehicle routing; scenario simulation 2023151741.11.11.11.11.11.11.11.11.11.11.11.11.11.11.11.11.11.11.1.11.  
method was proposed for solving small-scale 2L-VRP instances. Thereafter, a large number of research attempts have been devoted to designing efficient two-dimensional packing heuristics and routing optimization methods in order to improve the solving efficiency for the large-scale problem. In [4], the authors first proposed a heuristic approach that combined Tabu search with a Touching-Perimeter-rule-based packing algorithm, which solved large-scale instances with up to 255 customers. Other heuristic methods, such as genetic algorithm [5; 6], extended guided Tabu search [7], promise routing memory packing [8] and variable neighborhood search algorithm [9], have been presented to efficiently solve 2L-VRP. In these pieces of work, only the unrestricted and sequential loading configurations of 2L-VRP were studied. However, allowing items to rotate during the packing process has many practical applications. Lately, the authors in [10] proposed a biased-randomized algorithm to solve the unrestricted 2L-VRP with and without item rotations, while the two-dimensional sequential loading configuration was not studied. In [11], the authors studied four classes of 2L-VRP, including item rotation and sequential loading, and a saving-based ant colony optimization (ACO) algorithm was designed to solve the problem. This is the first published research that deals with the four classes of 2L-VRP, namely, unrestricted oriented loading (2|UO|L), unrestricted rotation-allowed loading (2|UR|L), sequential oriented loading (2|SO|L) and sequential rotation-allowed loading (2|SR|L). Recently, a simulated annealing method [12] was proposed for solving four classes of 2L-VRP, which improved loads of best-known solutions. Thus far, a large number of extended 2L-VRPs have received research attention, e.g., 2L-VRP with back-hauls [13], 2L-VRP with heterogeneous fleet [14; 15], 2L-VRP with split delivery [16] and three-dimensional constrained vehicle routing problem [17; 18; 19]. Nevertheless, the above research generally considers that the geographic location, demand, central depot, vehicle driving status and other information of customers are known in advance and do not change.