It takes 93 moves to solve, per this paper by Collette, Raskin, and Servais. I tried it and got nowhere.
You can think of the space of all possible configurations of vehicles as, well, a configuration space, not unlike the configuration spaces of disks in a box. But here there is a bit less topology; the space is just a graph, with two configurations made adjacent if one can be reached from the other by making a single move. The connected component of configuration space containing the “hardest case” shown here has 24,132 vertices.
I wonder what this graph looks like? What does the path of the cars look like as you traverse the 93-step path; do most of the cars traverse most of their range? How many of the possible configurations of the 13 vehicles (constrained to stay in the given rows and columns, and in the same linear order when two share a row or column) are actually contained in this component? Maybe Matt Kahle knows. By the way, another Matt Kahle-like fact is that among the list of the hardest configurations are some which are not so dense at all, like this one with only 9 cars. It looks like it should be easy, but apparently it takes 83 moves to solve!