# Shortest path problem with boxes

A company sells seven types of boxes, ranging in volume from 17 to 33 cubic feet. The demand and size of each box is given in the following table. The variable cost (in dollars) of producing each box is equal to the box's volume. A fixed cost of \$1,000 is incurred to produce any of a particular box. If the company desires, demand for a box may be satisfied by a box of larger size. Formulate and solve a shortest-path problem whose solution will minimize the cost of meeting the demand for boxes. $$\begin{array}{lr}\hline&&&&\text{Box}\\\hline&1&2&3&4&5&6&7\\\hline\text{Size}&33&30&26&24&19&18&17\\\text{Demand}&400&300&500&700&200&400&200\\\hline\end{array}$$ I'm trying to understand this exercise from W.L Winston's Operations Research: Algorithms and Applications. What I don't get is: 1) What does "if the company desires, demand for a box may be satisfied by a box of larger size" mean? 2) Is the demand for the quantity of that particular box( the box which is shown above that demand)? If so, isn't the problem nonsensical? We need to produce as many boxes as the demand requests, and there is no way of creating the shortest path problem? i.e we produce 400 of 33 cubic feet boxes, 300 of 30 cubic feet boxes, etc. ## 2 Answers 1) What does "if the company desires, demand for a box may be satisfied by a box of larger size". It means that if you don't have a box size $$x$$, you can satisfy it with a box of size $$y$$ where $$y>x$$. For example, satisfy the demand of box 30 with 33 if you don't have boxes of size 30. 2) Is the demand for the quantity of that particular box which is show above that demand? ... Yes, the demand for each box is given below the size. But on top of your variable cost (related to the volume of the box), you have a fixed cost of producing any particular box of a given size. • Well then if they demand$d_i$quantity of the$x_i$type of box, then, to fulfill the demand, we need to deliver exactly$d_i$amount of the$x_i$type of box. What can we minimize here? – The Poor Jew Dec 26 '19 at 2:12 • You're minimizing the total cost including variable costs and fixed costs (if you produce a certain type of box). If you formulate the problem, maybe you find out that it's better to produce more of box size$y$and not any box size$x$. I could eyeball one. Take a look at your biggest boxes. What if rather than producing both 30 and 33 and pay two fixed costs, you only produce 33 to satisfy both demands and pay one fixed cost? – EhsanK Dec 26 '19 at 3:00 • Okay, now I see! thanks! – The Poor Jew Dec 26 '19 at 5:35 EhsanK's answer clearly explains your questions. My input is to give you a quick way to resolve this issue. Just think about the marginal cost of "up-sizing" each box demand. If this costs less than the$1000 fixed cost, it is worthwhile.

Looking at the No. 3 boxes, the marginal cost is 4 dollars per box to up-size to No. 2 and you need 500 No. 3 boxes, which would cost 2000 dollars total to up-size. So, it is cheaper to just produce the #3 boxes at size 26.

For box #6, there is a 1 dollar cost to up-size to #5, and you need 400 #6s. So, this would only cost 400 dollars to up-size, and should be a candidate for doing so.

Note that this process is iterative, as you might up-size a box 2 or 3 sizes if the costs are lower.