Optimizing Parcel Package Selection Using an Enhanced Multiple Knapsack Problem Approach with Greedy Dynamic Programming - Santoso, Dewi Agustini; Rizqa, Ifan; Aqmala, Diana; Alzami, Farrikh (Universitas Ibn Khladun Bogor, 2024)
This study introduces an enhanced algorithm for solving the Multiple Knapsack Problem to optimize parcel package selection, particularly focusing on balancing value maximization with price and weight constraints. Due to Dynamic Programming requires significant memory, The proposed method employs a heuristic approach such as greedy algorithm, initially sorting items by their value-to-weight ratio and iteratively filling each knapsack to maximize total value while adhering to constraints. The algorithm demonstrates high computational efficiency, solving instances within 0.07 seconds, and achieves a total value of 122.00 across multiple knapsacks. However, the analysis reveals a significant underutilization of weight capacity (44.74%) compared to price capacity (98.92%), highlighting the need for more sophisticated constraint handling. Limitations such as the simplistic heuristic approach and single-objective focus are discussed. Future work will explore the integration of advanced optimization techniques, dynamic constraints, and multi-objective frameworks to improve solution quality and applicability in real-world scenarios. This research contributes to the field by providing a foundation for further exploration of Multiple Knapsack Problem in logistics and resource allocation contexts.