The problem of vehicle-cargo matching is a key issue in highway freight logistics transportation, and many investigations have been achieved for this problem. However, current research is limited to ideal environment, small dataset, static matching, and low matching efficiency, etc. Aimed at this, a vehicle-cargo matching algorithm based on improved dynamic Bayesian network is proposed (IDBN) in this paper. First, we define the vehicle-cargo matching degree as two parts, attribute matching degree and environmental influence degree, and quantify the importance of both by AHP (Analytic Hierarchy Process) method. Secondly, we construct the static Bayesian network and the dynamic Bayesian network through mapping vehicles, cargoes, matching combinations and time into Bayesian network nodes. Thirdly, we design an algorithm for the solution of IDBN, where the matching process of each vehicle is viewed as a state and the matching of two adjacent vehicles is switched by state. Fourthly, the model and the algorithm are verified through abundant experiments. It is found that the average success rate of vehicle matching in a single time slice can basically reach more than 80%, and the average success rate of rematching for the failed vehicles can reach 90%, and the matching success rate of vehicles is the highest when the number of cargoes is in the majority. This not only improves the efficiency of vehicle and cargo matching, but also effectively optimizes the subsequent matching process of vehicles that is failed to match. Therefore, theoretical reference can be provided by the proposed IDBN algorithm for the vehicle and cargo matching in small and medium-sized logistics enterprises.