## Posted By

jerryvig on 10/10/10

# Cost Minimization Algorithm for USPS Flat Rate Boxes

/ Published in: PHP

I have a client who ships fluids in USPS flat rate boxes. If you are unfamiliar with USPS flat rate boxes, they are boxes of a certain volume that ship regardless of weight. Anything that fits in the box, ships for one low price. My client uses two box sizes: the medium flat rate boxes, and the large flat rate boxes. Additionally, my client ships their fluids in the three bottle sizes: 200ml, 375ml, and 750ml. Moreover, due to the shape of the bottles only a certain number of bottles can fit in each box, and due to their shape the cost minimization cannot be detemined using the volume of each box and the bottle volumes. Thus, there are different arrangements of the bottles in each box which can work. For example, a medium box can hold 3 200ml and 2 375ml bottles or it can hold 4 200 ml bottles and 1 375ml bottle, and there are many other possible arrangements depending on the number of each size bottle. The table below, which I will call the allowed_configurations table lists the possible arrangements of each bottle in each size of box. Also, the large box costs \$14.50 and the medium box costs \$10.70 to ship.\r\n\r\nFor example, the first row in the table says 5,0,0 and indicates that the medium box can hold 5 200 ml bottles, and no other bottles. Using the table of the arrangements above, find an algorithm for computing the optimal arrangement with respect to the shipping cost for shipping a set of x 200ml bottles, y 375 ml bottles, and z 750 ml bottles. Your algorithm should not only compute the minimal cost but it should return the optimal arrangment of bottles among the different size boxes. I would be particularly interested in seeing your algorithm expressed in SQL, but solutions in a procedural language such as Java, PHP, or C will definitely be useful also.

`<?php   // the values \$numberOf200mlBottles, \$numberOf375mlBottles, \$numberOf750mlBottles are integers  // function to solve the "Bin Packing Problem" for packing 200 ml bottles, 375 ml bottles, and 750 ml bottles into medium and large USPS flat rate boxe\s. function MinimizeUSPSCost( \$numberOf750mlBottles, \$numberOf375mlBottles, \$numberOf200mlBottles ) {   \$configCosts = array(array(2, 1, 0, 14.5), array(2, 0, 2, 14.5), array(2, 0, 1, 14.5), array(2, 0, 0, 14.5), array(1, 2, 0, 14.5), array(1, 1, 2, 14.5)\, array(1, 1, 1, 14.5), array(1, 1, 0, 14.5), array(1, 0, 4, 14.5), array(1, 0, 3, 14.5), array(1, 0, 2, 14.5), array(1, 0, 1, 14.5), array(1, 0, 0, 14.5\), array(0, 6, 0, 14.5), array(0, 5, 1, 14.5), array(0, 5, 0, 14.5), array(0, 4, 2, 14.5), array(0, 4, 1, 14.5), array(0, 4, 0, 14.5), array(0, 3, 4, 14.\5), array(0, 3, 3, 14.5), array(0, 3, 2, 14.5), array(0, 3, 1, 10.7), array(0, 3, 0, 10.7), array(0, 2, 5, 14.5), array(0, 2, 4, 14.5), array(0, 2, 3, 10\.7), array(0, 2, 2, 10.7), array(0, 2, 1, 10.7), array(0, 2, 0, 10.7), array(0, 1, 5, 14.5), array(0, 1, 4, 10.7), array(0, 1, 3, 10.7), array(0, 1, 2, 1\0.7), array(0, 1, 1, 10.7), array(0, 1, 0, 10.7), array(0, 0, 8, 14.5), array(0, 0, 7, 14.5), array(0, 0, 6, 14.5), array(0, 0, 5, 10.7), array(0, 0, 4, \10.7), array(0, 0, 3, 10.7), array(0, 0, 2, 10.7), array(0, 0, 1, 10.7));   \$allowedConfigurations = array(array(2, 1, 0), array(2, 0, 2), array(2, 0, 1), array(2, 0, 0), array(1, 2, 0), array(1, 1, 2), array(1, 1, 1), array(1,\ 1, 0), array(1, 0, 4), array(1, 0, 3), array(1, 0, 2), array(1, 0, 1), array(1, 0, 0), array(0, 6, 0), array(0, 5, 1), array(0, 5, 0), array(0, 4, 2), a\rray(0, 4, 1), array(0, 4, 0), array(0, 3, 4), array(0, 3, 3), array(0, 3, 2), array(0, 3, 1), array(0, 3, 0), array(0, 2, 5), array(0, 2, 4), array(0, 2\, 3), array(0, 2, 2), array(0, 2, 1), array(0, 2, 0), array(0, 1, 5), array(0, 1, 4), array(0, 1, 3), array(0, 1, 2), array(0, 1, 1), array(0, 1, 0), arr\ay(0, 0, 8), array(0, 0, 7), array(0, 0, 6), array(0, 0, 5), array(0, 0, 4), array(0, 0, 3), array(0, 0, 2), array(0, 0, 1));   //initialze set of boxes to ship with one empty box.  \$boxes = array( array( 0, 0, 0 ) );   //Process the large bottles first.  for ( \$i=\$numberOf750mlBottles; \$i>0; \$i-- ) {    \$configurationIsAllowed = false;    for ( \$j=0; \$j<count(\$boxes); \$j++ ) {     \$nextBox = array( (\$boxes[\$j][0]+1),  \$boxes[\$j][1],  \$boxes[\$j][2] );     for ( \$k=0; \$k<count(\$allowedConfigurations); \$k++ ) {      if ( \$nextBox == \$allowedConfigurations[\$k] ) {        //configuration is allowed        \$boxes[\$j] = \$nextBox;        \$configurationIsAllowed = true;        break;      }    }    if ( \$configurationIsAllowed ) {      break;    }    }    if ( !\$configurationIsAllowed ) {      //configuration is not allowed add to set of boxes.      //open a new box and place 750 ml bottle inside.     array_push( \$boxes, array(1, 0, 0) );   }   }   //Now process medium bottles.  for ( \$i=\$numberOf375mlBottles; \$i>0; \$i-- ) {  \$configurationIsAllowed = false;    for ( \$j=0; \$j<count(\$boxes); \$j++ ) {     \$nextBox = array( \$boxes[\$j][0],  (\$boxes[\$j][1]+1),  \$boxes[\$j][2] );     for ( \$k=0; \$k<count(\$allowedConfigurations); \$k++ ) {      if ( \$nextBox == \$allowedConfigurations[\$k] ) {        //configuration is allowed        \$boxes[\$j] = \$nextBox;        \$configurationIsAllowed = true;        break;      }    }    if ( \$configurationIsAllowed ) {      break;    }    }    if ( !\$configurationIsAllowed ) {      //configuration is not allowed add to set of boxes.      //open a new box and place 375 ml bottle inside.     array_push( \$boxes, array(0, 1, 0) );   }   }   //Now process small bottles.  for ( \$i=\$numberOf200mlBottles; \$i>0; \$i-- ) {    \$configurationIsAllowed = false; for ( \$j=0; \$j<count(\$boxes); \$j++ ) {     \$nextBox = array( \$boxes[\$j][0],  \$boxes[\$j][1],  (\$boxes[\$j][2]+1) );     for ( \$k=0; \$k<count(\$allowedConfigurations); \$k++ ) {      if ( \$nextBox == \$allowedConfigurations[\$k] ) {        //configuration is allowed        \$boxes[\$j] = \$nextBox;        \$configurationIsAllowed = true;        break;      }    }    if ( \$configurationIsAllowed ) {      break;    }    }    if ( !\$configurationIsAllowed ) {      //configuration is not allowed add to set of boxes.      //open a new box and place 750 ml bottle inside.     array_push( \$boxes, array(0, 0, 1) );   }  }   //you need to compute the cost of the configurations.  \$shippingCost = 0.0;  for ( \$i=0; \$i<count(\$boxes); \$i++ ) {    for ( \$j=0; \$j<count(\$configCosts); \$j++ ) {      if ( \$boxes[\$i] == array( \$configCosts[\$j][0], \$configCosts[\$j][1], \$configCosts[\$j][2] ) ) {         \$shippingCost += \$configCosts[\$j][3];          break;      }     }  }   \$resultArray = array( \$boxes, \$shippingCost );  return \$resultArray;  } // now use the function to compute the configuration of a set of z 750 ml, y 375 ml, and x 200 ml bottles.// e.g. 399 750 ml bottles and 121 200 ml bottles. \$boxSet = MinimizeUSPSCost( 399, 0, 121 );  for ( \$i=0; \$i<count(\$boxSet[0]); \$i++ ) {    echo "Box " . (\$i+1) . ": " . \$boxSet[0][\$i][0] . " 750ml bottles, " . \$boxSet[0][\$i][1] . " 375 ml bottles, " . \$boxSet[0][\$i][2] . " 200 ml bottles\.\n"; } echo "Total Shipping cost = " . \$boxSet[1] . "\n"; ?>`