I had to solve a similar but simpler problem in the Star Wars : Rebellion tactical game. You had dozens of ships, all flying through space, some going to waypoints, and others following or avoiding other ships.

What I did was a basic approach of the ships attempted to reach a certain point in space each frame. They looked ahead along this course, and if a collision with another ship was imminent ( this was nevery allowed to happen for gameplay reasons ), then the moving ship would detect if it were already slightly above the other ship, if so, it would go up, otherwise if it were below, it would go down, otherwise, the 2 ships would compare unique ids to decide who goes up and who goes down.

I didn't really have acceleration or inertia to worry about, and moving up and down did not require turning the ships, so I never did have collisions occur.

When a ship failed to make any progress towards its goal after a certain time, it would attempt one of several different routes that would temporarily create a new waypoint at an extreme distance away from the action. It would then try to fly there for several seconds, and then try resuming its original route.

This way in dense heavy traffic, a ship could get itself unstuck.