What is your default_statistics_target and how accurate is that estimate of 5668 rows? What is random_page_cost set to by the way?
More importantly, what is the better plan that you'd like the planner to use with your existing indexes? It would seem logical to me to scan for the matching shipment_import_id if the estimate is saying 5868 out of 29 million should match and then sort and only get the smallest ID. Doing an index scan on ID and looking up in the table to see if shipment_import_id matches when the planner expects that to be about a .0001 chance... I can't imagine that plan performing well at all.
Certainly a composite index would be very helpful here. Using explain analyze and sharing the output would give more info to go on.
