Within the cross-dock facility, suppliers transport goods on pallets; however, there are instances when the received amount does not align with the allocation demand, resulting in either surplus or shortage. This situation raises the challenge of determining the appropriate customer to handle the excess or shortfall while also addressing any potential penalties. In the case of frozen deliveries, time sensitivity is of utmost importance, necessitating swift and efficient procedures. However, Ho Chi Minh City's dynamic environment poses challenges when delivery schedules deviate, making it necessary to accept such variations. The problem also involves optimizing vehicle allocation and managing early or late deliveries, along with over-deliveries or under-deliveries. The objective of this study is to create an enhanced schedule and strategy for vehicle allocation that effectively reduces three cost components: transportation expenses, penalties associated with untimely deliveries, and fines for inaccuracies in product quantities. A robust model will be introduced to balance these costs effectively, providing valuable insights for frozen product distribution. The model was initially tested on a sample problem using the Trial-and-Error method with CPLEX. Given the large data set and time constraints in real-world scenarios, Simulated Annealing is used to optimize the solution faster, making it more practical for implementation.