To investigate highway petrol station replenishment in initiative distribution mode, this paper develops a mixed-integer linear programming (MILP) model with minimal operational costs that includes loading costs, unloading costs, transport costs and the costs caused by unpunctual distribution. Based on discrete representation, the working day is divided into equal time intervals, and the truck distribution process is decomposed into a pair of tasks including driving, standby, rest, loading and unloading. Each truck must execute one task during a single interval, and the currently executing task is closely related to the preceding and subsequent tasks. By accounting for predictive time-varying sales at petrol stations, real-time road congestion and a series of operational constraints, the proposed model produces the optimal truck dispatch, namely, a detailed task assignment for all trucks during each time interval. The model is tested on a real-world case of a replenishment system comprising eight highway petrol stations, one depot, one garage and eight trucks to demonstrate its applicability and accuracy.