Midterm Project: Logistic Problem in Alibaba
In the Alibaba company, we have one big warehouse, and customers need the products on
time. Based on the coming online shopping, I need to send the products to them from the
warehouse (seen in Figure 1). However, I have limited capacity in the warehouse and which
products I need to store there. The question is here which products need to be in the
warehouse before sending to customers. I will store and deliver my products dynamically.
This problem is an actual use case of the Knapsack Problem, and we store and deliver the
products dynamically. We need to understand the knapsack problem and dynamic
programming (shared as an extra file).
Knapsack Problem algorithm is a very helpful problem in combinatorics. In the warehouse
there are n packages the package i has weight (Wi) and value (Vi). The company cannot store
the products if the total products weights are greater than capacity. The problem to be solved
here is: which packages will the company deliver to get the highest value?
Project Definition:
The Problem here we have 300 instances (trials). For each instance, we have C, Vi, and Wi for
the problem.
Capacity will be generated by using normal distribution as mean: 130 and standard deviation:
30. It means that we will generate the capacity between 100 and 160 for each instance. We
shared all values and weights in the datasets for the project. For each instance, which item we
need to select for getting more value and using less capacity.
Which items should Alibaba put in Warehouse to maximize value?
Simple Examples for Knapsack Problem
Let me explain Knapsack problem with examples.
Note: Instance here is the trial or combinations of items. For each knapsack instance,
For this example, we generated the capacity as 7 then we would like to optimize the total
values. We need to select the items that have minimum weights and maximum values. I will
add each item dynamically and check my instance capacity. When we select;
Item 1 (V:10, W:2) + Item 2 (V:10, W:3) + Item 4 (V:2, W:1) = Total V:22, W:6 so, Wwith 22 values.
Item 2 (V:10, W:3) + Item 3 (V:12, W:4) = Total V:22, W:7 so, WThen, we will store [Item 1 and Item 2] or [Item 2 and Item 3] for this instance.
What we will do in the Project:
In the Project:
• 300 Warehouse (Knapsack) Instances
• For each instance, we need to define C in Normal Distribution[Mean:130, Standard
Deviation:30]
• Only find out C once you choose which items to put in the warehouse (knapsack)
• If you go over C, then you get nothing for that instance
We generated 300 C for 300 instances. For example, let’s say that we generated 125 lbs, for
Instance 1. It means that we store the items based on this capacity. As seen below, total space
consumption cannot pass 125, for Instance 1.
Here is how we’ll give you the knapsack instances:
How to Submit the Project
You need to define 0 or 1 in this CSV file. 1 means that Alibaba do store this item on the
warehouse asseen below. For example, for instance 1, we selected item 1 and item 2 and total
space consumption is 30+63=93. This 93 is less than 125. As a reward, we earned 18.12 + 35.2
dollars. So, we need to assign these 0s and 1s for earning more by using less capacity.
In the evaluation.ipynb file, you will show that how much you are earned. Moreover, you will
show all assignments in this CSV files for submission.
After defined all packages (items) to warehouse, we need to find the optimum way by
using monte carlo simulation. It means that we will use the average of all values for
showing.
Conservative Approach
Assume the size of the knapsack is 100 for all instances
– This way you will never go over
• Find best way to pack knapsack.
– Develop a few heuristics.
– For each instance of the knapsack problem, pass the instance to each heuristic and then pick
the best.
If I assume all knapsacks have size 100, I might be leaving points on the table.
– Use Monte Carlo to find a good mix of knapsack sizes.
– Start by assuming all knapsacks are the same size.
Output: In this project, we need to show the best way to pack the warehouse (knapsack).
For example, we have 300 instances (trials). Please show which instance is the best and how
much we will earn.
Note: You need to use Monte Carlo Simulation for this part.
Grading
• 27 points total
7 points towards how good your solution is
• Top Three Place (among all groups across sessions) – 7 points
• Rest of top 33% - 5 points
• Middle 33% - 3 points
• Bottom 33% - 2 point
20 points towards the fact your code actually runs.
• Your code needs to pass the auto-grader and provides a nonnegative value.