Joint Replenishment Problem with Capacity Constraints

---

This project presents a comprehensive implementation and analysis of the Joint Replenishment Problem (JRP), a fundamental challenge in inventory management and supply chain optimization. The study is based on the enhanced JRP formulation by Hoque (2006), which extends classical inventory models to incorporate real-world business constraints that are often overlooked in theoretical assessments.

---

Problem Definition

The Joint Replenishment Problem arises when a retailer, distributor, or manufacturer needs to coordinate the ordering of several items from a single supplier. This scenario is common in real-world operations:

• Retail chains ordering multiple products from distributors
• Manufacturing companies procuring raw materials and components
• Hospitals ordering medical supplies and pharmaceuticals
• Restaurants sourcing ingredients from food suppliers

The fundamental challenge lies in balancing the economic trade-offs between various cost components while considering operational limitations. The decision needs to be made on the frequency of replenishment of each item in order to minimize the cost of joint ordering.

Assumptions

1. Demand is deterministic and constant over an infinitive time horizon.
2. There is no quantity discount.
3. Lead time is zero.
4. Shortages are not allowed.
5. Transportation times are insignificant.
6. The reorder interval time of an item is an integer multiple of the basic cycle time.

Decision Variables

• $T_0$ = Basic cycle time
• $T_j$ = Reorder interval time for item j$

But since $T_j$ is integer multiple of $T_0$, we can introduce $k_j$ as second decision variable which is a positive integer such that: $T_j = k_j \cdot T_0$

Parameters

$n$: number of items
$S_0$: major ordering cost
$S_j$: minor ordering cost for item j
$D_j$: annual demand rate for item j
$h_j$: unit inventory holding cost per unit per year for item j
$w_j$: weight per unit for item j
$t$: transportation cost per full truck load
$W$: maximum weight capacity of the transportation equipment
$g_j$: storage capacity for item j
$c_j$: unit cost (investment) for item j
$C_j$: budget constraint for item j

Cost Structure and Objective Function

The JRP consists several interrelated cost components:

• Ordering Cost $$\frac{S_0}{T_0} + \sum_{j=1}^{n} \frac{S_j}{k_j T_0}$$
• Holding Cost $${T_0}\sum_{j=1}^{n} H_j k_j$$

where $H_j = \frac {h_j D_j} {2} $

• Transportation Cost $$\sum_{j=1}^{n} \frac{w_j D_j t}{W}$$

The aim in this problem is to minimize total cost. Therefore, the objective function is as following:

$$\text{minimize} \text{ Total Cost} = \text{Ordering Cost} + \text{Holding Cost} + \text{Transportation Cost}$$

where $\mathbf{k} = [k_1, k_2, \ldots, k_n] $

Constraints

1. Storage Capacity

$$T_0 k_j D_j \leq g_j, \quad \forall j = 1, 2, \ldots, n$$

2. Budget Capacity

$$T_0 k_j D_j c_j \leq C_j, \quad \forall j = 1, 2, \ldots, n$$

3. Non-negativity and Integer Constraints

$$T_0 > 0$$

$$k_j \in \mathbb{Z}^{+}, \quad \forall j = 1, 2, \ldots, n$$

Solution Approach

This project implements and compares two distinct solution approaches:

1. Mathematical Model:

• Formulates the JRP as a Mixed-Integer Nonlinear Programming (MINLP) problem
• Leverages commercial optimization solver (Gurobi) capabilities
• Provides optimality guarantees and sensitivity analysis
• Serves as a benchmark for validating heuristic solutions

2. Heuristic:

• Iterative improvement method designed specifically for the constrained JRP
• Uses shadow pricing to guide the search for better solutions
• Computationally efficient with proven convergence properties
• Particularly suitable for large-scale industrial applications

Benchmark

7-item dataset from Hoque (2006) is used for benchmark. Moreover, the other datasets mentioned in the article are also tested. Please note that, these datasets are belongs to previous JRP models and they do not have parameter data related with storage, budget and transportation constraints. Therefore, artificial parameters are introduced by the method loose_restriction_on_constraints() for these datasets.

---

Results

For the benchmark data (hoque7), the comparison for two approaches can be seen in the following table. The optimum values for $T_0$ and total cost are same for both approach as well as the given values in the article (Hoque, 2006). The main difference is in runtime, where heuristic algorithm is considerably faster.

Algorithm	T₀	Total Cost	Runtime
JRPGurobi	0.052	2773.05	0.25456
JRPHeuristic	0.052	2773.05	0.00078

Moreover, the following table demonstrates the optimum values of $k_j$ for each item as well as the corresponding $T_j$ and $Q_j$. Again, the optimum values for $k_j$ are same, but there is a minor discrepancy in $Q_j$ values. It indicates that the optimum values in two methodologies differ after a certain number of decimal points.

Item	kⱼ (JRPGurobi)	kⱼ (JRPHeuristic)	Tⱼ (JRPGurobi)	Tⱼ (JRPHeuristic)	Qⱼ (JRPGurobi)	Qⱼ (JRPHeuristic)
1	1	1	0.052	0.052	237.3	237.4
2	1	1	0.052	0.052	537.4	537.6
3	1	1	0.052	0.052	519.3	519.4
4	2	2	0.104	0.104	913.9	914.2
5	2	2	0.104	0.104	276.3	276.3
6	2	2	0.104	0.104	415.4	415.5
7	2	2	0.104	0.104	1017.8	1018.0

For the other datasets given in the article, the outputs are summarized in the following table. Note that, for v20 data, JRPGurobipy algorithm could not find an optimum value without giving a time limit. (It killed itself after 13 hours of running.)

Data	Algorithm	T₀	kⱼ	Total Cost	Runtime
AE2	JRPGurobi	0.1686	[3 2]	505.96	0.11252
AE2	JRPHeuristic	0.1687	[3 2]	505.96	0.00008
G10	JRPGurobi	0.0416	[1 1 1 1 1 1 3 2 1]	5955.17	0.22699
G10	JRPHeuristic	0.0416	[1 1 1 1 1 1 3 2 1]	5955.17	0.00015
G15	JRPGurobi	0.0214	[4 2 2 2 2 2 1 1 1 1 1 1 1]	11449.76	0.92464
G15	JRPHeuristic	0.0214	[4 2 2 2 2 2 1 1 1 1 1 1 1]	11449.76	0.00022
G20	JRPGurobi	0.0491	[1 1 1 1 1 1 1 1 1 1 2 2 2 3]	7472.84	7.5224
G20	JRPHeuristic	0.0491	[1 1 1 1 1 1 1 1 1 1 2 2 2 3]	7472.84	0.00052
V20	JRPGurobi	0.0326	[3 3 2 2 2 2 2 2 1 1 1 4 2 2 3 2 2]	23195.80	181.24957
V20	JRPHeuristic	0.0326	[3 3 2 2 2 2 2 2 1 1 1 4 2 2 3 2 2]	23195.80	0.00128

---

Insights

Real-World Application

Traditional JRP models often assume unlimited resources and perfect flexibility. Real-life challenges like as transportation capacity usage, capital investment limitations, and storage capacity constraints are often ignored. However, buyers may choose to limit their investment in individual items in a joint replenishment group. When transporting products in a group, there are usually several transports available; nevertheless, transportation restrictions may dictate that the cost of a transport must be the same whether it is completely or half filled. In a store, storage space for each item is restricted, so the quantity of items in an order must also be limited. Thus, due to the related constraints, the model introduced in Hoque (2006) is more realistic compared to previous traditional JRP models.

Gurobi vs. Heuristic

When evaluating solution quality, one might conclude that heuristic algorithm is nearly optimal if the differences are ignored after a few decimal points. On the other hand, when compared to computational effort, gurobi is much slower and, even in some cases cannot find the solution and terminate itself.

Random Data Generation

Since with the given datasets, the heuristic algorithm has always found the optimum solution, there is a possibly that for the given datasets, local optimum can be global optimum. Therefore, I would like to try generate data randomly and solve with the two approach. As may already be seen the method in the base class, when any data is not given as input, it generates automatically random data based on the given parameter intervals which are selected based on the intervals in Silver (1946). For reproducibility, seed can also be given as input (default seed is 42). After running for different seeds, the comparison of two approaches is given in the following:

Data Seed	Algorithm	T₀	kⱼ	Total Cost	Runtime
42 (Default)	JRPGurobi	0.0026	[3, 1, 12, 1, 2, 3, 4, 2, 6, 2, 4]	75908.82	0.00886
42 (Default)	JRPHeuristic	0.0022	[2, 2, 7, 1, 1, 2, 2, 1, 3, 1, 3]	77681.98	0.00186
2407	JRPGurobi	0.0016	[2, 2, 2, 11, 6, 3, 5, 6, 3, 5, 6, 10, 1, 1, 34, 9, 9, 1, 11, 3, 14, 4, 14, 2, 3, 4]	145636.41	9.07642
2407	JRPHeuristic	0.0016	[1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 6, 2, 2, 1, 2, 1, 3, 1, 2, 1, 1, 1]	165756.93	0.00474
1705	JRPGurobi	0.0014	[6, 6, 6, 5, 8, 1, 9, 2, 4, 6, 8, 14, 4, 2, 17, 4, 3, 4, 4, 10, 8, 5, 2, 5, 6, 7]	91032.26	181.01072
1705	JRPHeuristic	0.0014	[3, 2, 2, 5, 2, 1, 2, 1, 1, 2, 2, 4, 1, 1, 4, 1, 2, 1, 1, 3, 2, 1, 1, 2, 2, 2]	101562.72	0.00817
3789	JRPGurobi	0.0034	[5, 2, 1, 2, 1, 6, 3, 3, 1, 2, 1, 3, 2, 2, 1, 1, 1, 2, 2, 2, 5, 2, 1, 22, 2, 1, 1]	48398.65	1.86129
3789	JRPHeuristic	0.0034	[2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 10, 1, 1, 1]	51790.79	0.00490
1107	JRPGurobi	0.0015	[4, 9, 16, 12, 1, 3, 3, 7, 21, 2, 7, 4, 3, 11, 1, 1, 6, 8, 1, 4, 2]	65552.31	1.73336
1107	JRPHeuristic	0.0016	[1, 2, 4, 3, 1, 1, 1, 2, 5, 1, 2, 1, 1, 3, 1, 1, 3, 2, 1, 1, 1]	71671.36	0.00471
2045	JRPGurobi	0.0011	[5, 6, 9, 3, 34, 8, 7, 7, 5, 6, 8, 12, 8, 3, 6, 3, 1, 9, 4, 12, 4, 5, 17, 16, 3, 1, 3, 8]	99176.22	135.99705
2045	JRPHeuristic	0.0011	[2, 2, 3, 1, 9, 3, 2, 3, 3, 2, 2, 4, 3, 1, 2, 1, 1, 2, 1, 3, 1, 1, 5, 4, 2, 1, 2, 2]	114894.49	0.00886

As observed, the optimum values for $T_0$ are mostly identical across algorithms, however, this consistency does not extend to the total cost and optimal $k_j$ values. In the best case, the relative difference in total cost is only 2.34% for random seed 42, whereas the worst case, it reaches 15.85% for random seed 2405. As expected, the local optimum coincides with the global optimum for the datasets used in the referenced article. However, when tested on randomly generated datasets, the algorithm often fails to find the global optimum, being trapped in local optimum. In future studies, heuristic or metaheuristic algorithms could be explored to overcome this issue and improve solution quality.

---

References

• Andrews, G. C., & Emmons, H. (1976). On the optimal packaging frequency of jointly replenished items. Management Science, 22(10), 1165–1166.
• Goyal, S. K. (1973). Determination of Economic Packaging Frequency for Items Jointly Replenished. Management Science, 20 (2), 232–235.
• Goyal, S. K. (1974a). Determination of Optimum Packaging Frequency of Items Jointly Replenished. Management Science, 21(4), 436–443.
• Goyal, S. K. (1974b). Optimum Ordering Policy for a Multi Item Single Supplier System. Operational Research Quarterly, 25(2), 293–298.
• Hoque, M. A. (2006). An optimal solution technique for the joint replenishment problem with storage and transport capacities and budget constraints. European Journal of Operational Research, 175, 1033–1042.
• Kaspi, M., & Rosenblatt, M. J. (1983). An improvement of SilverÕs algorithm for the joint replenishment problem. IIE Transactions, 15(4), 264–269.
• Silver, E. A. (1976). A simple method of determining order quantities in joint replenishments under deterministic demand. Management Science, 22(12), 1351–1361.
• Viswanathan, S. (2002). On Optimal Algorithms for the Joint Replenishment Problem. Journal of the Operational Research Society, 53(11), 1286–1290