An analytical methodology for prediction of the platoon arrival profiles and queue length along signalized arterials is proposed. Traffic between successive traffic signals is modeled as a two-step Markov decision process (MDP). Traffic dynamics are modeled with the use of the kinematic wave theory. The MDP formulation allows prediction of the arrival profiles several signals downstream from a known starting flow. This modeling approach can be used to estimate queue lengths and predict travel times, even in cases in which data from loop detectors are unknown, inaccurate, or aggregated. The proposed model was applied to two real-world test sites. The queues estimated with the model are in close agreement with the results from microscopic simulation.