We present a manifestly nonnegative integral expansion for the cohomology class of the permutahedral variety in terms of Schubert classes. This is thus a contribution to the Schubert calculus of the flag variety, which we will recall. In addition, we introduce algebraic and combinatorial objects of independent interest. In particular we present a new basis of the polynomial ring that refines Schubert polynomials. We then use it to give a combinatorial interpretation of the coefficients in the above expansion in terms of a novel parking procedure. This is joint work with Vasu Tewari.