Considering uncertainties in the real-life distribution applications, this paper studies the joint optimization of two-dimensional loading and vehicle routing with cross-docking, and for the first time presents a two-dimensional loading constrained vehicle routing problem with cross-docking and a stochastic travel time(2L-VRPCDSTT). Based on Monte Carlo simulations and a scenario analysis method, a stochastic programming model with recourse(SPR) for the 2L-VRPCDSTT is formulated, aiming to minimize the total transportation cost, fixed cost of vehicles and expected penalty cost of time window. According to the characteristics of the 2L-VRPCDSTT, an improved adaptive tabu search(IATS) algorithm incorporating a tabu-based multi-order best-fit(TSMOBF) packing heuristic is proposed to solve this problem. In the proposed algorithm, an adaptive mechanism is embedded to dynamically select different neighborhood operators, and a diversification mechanism based on the remove-reinsert strategy is proposed to enhance the exploitation capability of the algorithm. Experimental results show that the proposed SPR model and hybrid method can efficiently solve the 2L-VRPCDSTT, and that the adaptive mechanism and diversification mechanism are capable of enhancing the global search capability of the algorithm.