To address the issues of insufficient distribution network capacity in highways and the mismatch between renewable energy output and service area energy loads, utilizing mobile energy storage vehicles (MESVs) for energy mutual support between service areas can enhance renewable energy consumption. To enhance the real-time response capability of mobile energy storage, this paper proposes an MESV dispatch optimization strategy that considers traffic state, under the constraint of the average loss rate for electric vehicle (EV) battery swap services. First, leveraging the characteristics of free-flow traffic on highways, vehicle travel speed is modeled as a random variable following a truncated normal distribution and discretized into multiple speed intervals to represent different traffic states and their probabilities. Concurrently, considering the randomness of EV battery swap demand, a multi-state Bernoulli distribution is adopted to describe the swap demand within each time slot, establishing a transportation time cost model for MESVs and an energy state update model for battery swap stations (BSSs). Second, a Markov chain is constructed based on the traffic states between service areas and the energy states of BSSs to characterize the one-step transition probabilities of the system state. Building on this, a constrained Markov decision-making optimization model is then formulated, aiming to minimize the long-term average transportation time cost for mobile energy storage, subject to the constraints of the average loss rate for battery swap services. The model is solved to obtain optimal dispatch parameters and steady-state probability distributions. Simulations based on the actual operational parameters of NIO’s fourth-generation EV BSSs were conducted for validation. The results show that the proposed strategy exhibits a dual-threshold structure based on traffic condition and energy state, allowing adaptive adjustment of MESV dispatch frequency according to traffic conditions between service areas and the energy reserve levels of BSSs. Compared with greedy strategy and Q-learning method, the average transportation time cost was reduced by 17.23% and 8.89%, respectively, achieving an optimal trade-off between transportation cost and battery swap service performance while meeting service quality constraints.