This is a famous puzzle
[See : http://en.wikipedia.org/wiki/Beatles_Concert_Puzzle]

I think the optimal solution is :

TIME xxxxxx MOVEMENT
0+2xxxxxxxxxSoldier and Gunman move to opposite side.
2+1xxxxxxxxxSoldier comes back.
3+10xxxxxxxxKing and Queen move to opposite side.
13+2xxxxxxxxGunman comes back.
15+2xxxxxxxxSoldier and Gunman move to opposite side.
17xxxxxxxxxxAll have crossed safely

So, minimum time to cross is 17 mins