Monday, August 22, 2011

Shipping problem

I am starting to work on a problem that looks like a shipping problem I worked on earlier: garments (shirts) are sent from China to stores in the US either directly in a number of packages containing standard contents or through a US warehouse. The cheapest is to send the standard boxes from China but as there are just a few standard configurations, stores will need to be supplied with additional shirts from the US warehouse. Shirts come in different sizes.

image

The basic model looked like:

image

All quantities with bars are parameters (constants). Even though this is a simple model it was not completely trivial to get good solutions:

  • The model as presented is an MINLP. We linearized to make it a MIP.
  • The data set was rather large because of a large number of stores.
  • We could preprocess the demand data as some stores have the same demand; this reduced the size by about a third. We added weights to the objective to represent how many times a demand pattern was used.
  • In practice over-supplying a store was expensive, so we can fix OverShipped(Store,Size)=0.
  • It was not practical to solve this model in one swoop. We found good solutions by first finding a good content for a single standard box, and then (after fixing the content of this first box) finding a good proposal for a second standard box. Adding more standard boxes was not reducing the objective by much.
  • The set sizes can also include other attributes such as color etc.