Pennant Sportswear is a performance sportswear distributor located in New Hampshire. Pennant is partnered with FedEx to ship their products to customers and charges their customers for the shipping rates that they pay to FedEx. Recently, the FedEx’s pricing model changed: they now charge their customers a baseline “dimensional weight” if the weight of the package being shipped does not exceed the baseline. This change in pricing presented a problem to Pennant sportswear where they could not accurately estimate the cost of shipping for their customers, and often ended up paying more than they charged for shipping. The goal of this project was to design an algorithm to direct employees to optimally pack shipments for Pennant in order to reduce and more accurately estimate shipping costs.

We used the Simplex algorithm to solve a linear program that we formulated to fit our problem.  The objective function minimizes the difference between the actual weight of the shipment and the dimensional weight, while also keeping the value positive. This ensures that Pennant will pay for the actual weight of the box while also making sure the shipment is as light as possible (to reduce cost). The first constraint ensures that all of the items placed into a box will fit, and the final two constraints ensure that each item is only placed in a box once. The final constraint also makes sure that the dummy variables that were created to account for weight (volume accounted for in first set of variables), match up according to each item.

However, we were not sure if implementing the LP in excel would be possible. We ran into some issues with the maximum function in our original LP when trying to implement it in excel. We originally had a maximum function that would return whichever value was higher: the dimensional weight or the actual weight of the package. The original goal of the LP was to minimize this function. However, solver continued to give errors saying that the problem was not linear. However, we were able to find a helpful trick that added more dummy variables, but eliminated the problem. This method introduced a new variable, tj, where tj was greater than the difference between the two, but also greater than 0.

Once we were able to implement the LP, we were faced with the challenge of making it dynamic. Following advice from Professor Min, we implemented the excel LP using minimal “items to pack” and minimal “box size options.” In order to fully relate the LP to the real-world problem, it needed to be implemented dynamically. Within the python code, depending on the number of items that the order starts with, the number of available boxes is updated. From there, the LP is arranged with the set of constraints that was updated based on inputs. This allows for the LP to be fully dynamic yet also linear.

When small scale testing was being done, checking results by hand using the simplex method was very easy/manageable. On the small scale, all solutions that were obtained through the excel implementation or the dynamic programming with python matched the solutions that were computed by hand. This would lead us to believe that this algorithm does produce an optimal solution. However, as the testing was scaled up, the “checking” of the solution became more difficult.

The results of the testing can be found in an attachment to this document. These results include the inputs for each test and the output of the algorithm. As the number of items got to be over 100, the time it took for a result to be produced increased significantly (to around 5 minutes). While this should not really be much an issue for packing the boxes because these solutions could be computed over night, this extended time has the potential to cause issues if the website was to include a final price during checkout.

A major issue that came up during the process was “worst case” scenarios. There is always the possibility of an order of one shirt, that is too small and light for any box to not get over its dimensional weight. These orders were categorized separately and put into a bag. FedEx offers small bags for shipping that do not have the same dimensional weight pricing model as boxes. These are perfect for smaller shipments where the difference between the weight that needs to get shipped and the smallest dimensional weight is still very large. Some test cases resulted in a “bag” output which accounts for this worst case scenario.

The final algorithm output is very complex currently (see appendix 4). However, some next steps would be to implement this algorithm on the pennant website for use by customers. Tieing the algorithm into the back end of the Pennant website with a simplified output would make instructions for the box-packing employees very simple. Additionally, another element that could be added to this problem is the dimensions of each item. As stated in the discussion section below, we made the assumption that all items were malleable and therefore could be packed in any shape (we still accounted for volume). As a result, another aspect of this program that could be improved is taking into account dimensionality of products so that it is guaranteed that they can stay flat and avoid wrinkling.