Infeasibility error when planning shipments through Show Routing Options

 We had this happen on 2 orders that built a total of 5 shipments. All 5 shipments had the same error. The orders were all planned using “Show Routing Options”. The 5 shipments were eventually deleted and the orders replanned using Bulk Plan. Everything worked fine that time.
Steps:
When attempting to change the service provider on shipment ID 18415, performed the following:

1.        Selected Actions >> Change Service Provider

2.       Chose the service provider

3.       Clicked OK

4.       Received the following error:

insert into shipment_feasibility (shipment_gid,feasibility_code_gid,domain_name) values (?,?,?) at [NCI.18415,null, NCI]
Cannot insert the SHIPMENT-INFEASIBILITY record. FEASIBILTY_CODE_GID must be set.