$$\text{PD110-1 MTP REPORT}$$

$$\text{This report was migrated to HackMD by 顧寬証}$$

$$\text{Group Information}$$

$$\text{Group Members}$$

$$\text{Dept.\&Name}$$	$$\text{Student ID}$$
$\text{資管一黃偉翔}$	$\text{B10705006}$
$\text{資管一蔡可亮}$	$\text{B10705010}$
$\text{資管一顧寬証}$	$\text{B10705016}$
$\text{資管一陳禹翰}$	$\text{B10705050}$
$\text{資管一賴旻}$	$\text{B10705055}$

---

$$\text{Midterm Project Information}$$

$$\text{Brief Description}$$

This project is the midterm project of the Program Design course of the semester 110-1.

Students are evenly distributed into several groups and are asked to finish the project together with their teammates.

The main objective of the project is to provide a complete replenishment plan for a retailer given some detailed information regarding the distribution centers and the retail stores.

Students are thus asked to write a program that produces profit-making replenishment plan based on the given input.

Furthermore, there is an online grading system hosted by NTUIM, PDOGS, where students can submit their code 24 hours a day and can see the results immediately after the program finished executing. There is also a real time scoreboard brocasting the rank and score of every team of the course. The score is determined by the profit brought by the replenishment plan provided.

$$\text{References}$$

• PDOGS problem
• NTUIM PD110-1 MTP Instructions

---

$$\text{Results}$$

$$\text{Final Total Profit}$$

We made a total profit of

$65,119,650$

$$\text{Ranking}$$

We ranked 1st among the 33 teams of the class.

---

$$\text{Source Code}$$

GitHub Repo

---

$$\text{Complete Report}$$

$$\text{Notations}$$

These following notations will be used frequently in this report.

$\text{For retail store, }R{S}_i,i\in [1,m]$

• $\text{Position: }(x_i,y_i)$
• $\text{Daily Demand: }{D}_i$
• $\text{Daily Demand Left: }{D_{left}}_i,\text{ initialized to }{D}_i$
• $\text{Daily Operation Cost: }{f}_i$
• $\text{Price of Products per unit: }{p}_i$

$\text{For distribution center, }D{C}_j,j\in [1,n]$

• $\text{Position: }(u_j,v_j)$
• $\text{Capacity: }{K}_j$
• $\text{Inventory: }in{v}_j\text{, initialized to }{K}_j$
• $\text{Daily Operation Cost: }{h}_j$

$\text{For option, }{O}_{ij},i\in [1,n]\wedge j\in [1,m]$

• $\text{Restock Cost per unit per kilometer: }c$
• $\text{Distance between }R{S}_i\text{ and }D{C}_j\text{ involved: }{d}_{ij}=|x_i-u_j|+|y_i-v_j|$
• $\text{Unit Profit: }{M}_{ij}=p_i-c{d}_{ij}$
• $\text{Restock Count: }{x}_{ij}$
• $\text{Total Profit: }{\pi }_{ij}=M_{ij}\cdot x_{ij}$
• $\text{Indices of RS and DC involved: }i,j$
• $i^{\ast },j^{\ast }\text{ denotes the indices of the DC and RS involved in the current best option.}$

---

$$\text{System Design}$$

$\text{A. Stem}$

Firstly, we load the testing data, and initialize a Retailer, a class that wraps up this problem, instance with the testing data. Then, the Retailer instance makes an optimal replenishment plan based on our algorithm. Lastly, it prints out the complete replenishment plan in the required format.

$\text{B. Algorithm}$

We opted to adopt a greedy algorithm in this problem, so our algorithm, in short, is a loop that constantly chooses the best feasible option, which is determined by the sort-key. The loop terminates as soon as the restock count of the current best option reaches 0, meaning there are no profitable options left. We then shutdown deficit retail stores and distribution centers by comparing their revenues and costs. Further details will be covered in the next section.

$\text{C. Flow Chart}$

---

$$\text{Algorithms}$$

$\text{A. Situation 1: Single Sourcing}$

This algorithm focuses on a single

$RS$ for each iteration. In order to maximize final profit, we choose the best

$O$, which is the option with the greatest

$k_1$ for each iteration.

$$k_1={\pi }_{ij}-f_i{\lambda }_{1f}-h_j{\lambda }_{1h}\text{ , where }\lambda \in [0,1]\text{ is a constant.}$$

The amount of the replenishment is determined as follows.

$$x_{i^{\ast }{j}^{\ast }}=min\{D_{i^{\ast }},in{v}_{j^{\ast }}\}$$

Firstly, we create a list of feasible options. We choose the current best

$O$ for each iteration until there is no

$O$ with positive

$k1$. We skip

$R{S}_{i^{\ast }}$ later on because it is only allowed to be replenished by one distribution center. We skip

$D{C}_{j\ast }$ later on if

$in{v}_{j^{\ast }}-x_{i^{\ast }{j}^{\ast }}=0$, meaning it’s out of stock.

$\text{B. Situation 2: Multiple Sourcing}$

This algorithm focuses on a single retail store for each iteration. In order to maximize final profit, we choose the best option, which is the option with the greatest sort key

$k_2$.

$$k_2=M_{ij}-\frac{f_i{\lambda }_{2f}+h_j{\lambda }_{2h}}{x_{ij}}\text{, where }{x}_{i^{\ast }{j}^{\ast }}=min\{{D_{left}}_{i^{\ast }},in{v}_{j^{\ast }}\}$$

$$\lambda \in [0,1]\text{ is a constant}$$

Firstly, we create a list of feasible options. For each iteration, we choose the current best

$O$ until there is no

$O$ with positive

$k_2$. If

${D_{left}}_{i^{\ast }}-x_{i^{\ast }{j}^{\ast }}=0$, we skip

$R{S}_{i^{\ast }}$ later on because it’s completely satisfied. If

$in{v}_{j^{\ast }}-x_{i^{\ast }{j}^{\ast }}=0$, we skip

$D{C}_{j^{\ast }}$ later on because it’s out of stock.

$\text{C. The Advent of the Constant Lambdas}$

There exists, in fact, no constant in our algorithm in the early stages. After several times of testing, observation, organization and some in-depth analyses on the output of our algorithm based on some cases, we attempted to make sense out of the underperformance of our initial algorithm. The following is our crude conclusion.

When

$s=2$, every retail store and distribution center can be paired with multiple distribution centers and retail stores, thus we thought that we might have overestimated the cost of a certain option by taking 100% of

$f_i$ and

$h_j$ into consideration.

We found that there is a considerable number of options with extremely high potential profit left unselected, for their costs were overestimated, resulting in the underestimate of their sort-keys to the extent that some considerably lucrative options have negative sort-keys which prevent them from being selected.

More specifically, there is rarely a distribution center that is only able to restock a single retail store in normally distributed cases, i.e., a distribution center usually makes replenishments to multiple retail stores. Therefore, it’s advisable that we consider the cost of the distribution center proportional to its ratio of the restock count of an option to the total restock count of the distribution center so that we can have an accurate evaluation of the lucrativeness of a certain option.

However, it’s nearly impossible to know the count of the replenishments of a distribution center beforehand. Thus, we alternatively and tentatively adopted a relatively intuitive method.

That is, we gave the cost of the distribution center in the sort-key a weight less than

$1$ in hope of reducing the negative impact of the overestimation on the cost.

Since different retail stores might share the same distribution center,

$h_j$ is likely to be overestimated. Hence, in order to lower its weight, we apply a constant,

$\lambda$, that ranges from

$0.1$ to

$1.0$ with an interval of

$0.1$ to

$h_j$ in our sort key on both

$k_1$ and

$k_2$. The results are as follows.

As the graph indicates, the coefficient of correlation between total profit and the constant, lambda, is about

$0.94$, meaning there is a very high correlation between the two variables. The results showed that this method undoubtedly made a huge enhancement. The results show also that we obtain maximal profit when we set

$\lambda \approx 0.2$. As a consequence, we further tentatively apply different lambdas to

$f_i$ and

$h_j$ on

$k_1$ and

$k_2$ and try to find our best solution for the midterm project.

The method above allows us to find a combination of coefficients that helps us obtain near optimal total profit on average, but it doesn’t guarantee that we reach the highest level on any test cases. Thus, we came up with another solution. That is, by using a simple for loop, we evaluate the performance of every combination of coefficients, and we take the one with the best performance as our final answer so that we can rest assured that we provide an optimal solution based on our algorithm for any test cases.

However, there was a time limit of 1000 milliseconds per test case imposed on PDOGS, so we failed to list and evaluate all possible combinations of coefficients in time, and we couldn’t seem to find a way to optimize our code. Therefore, we decided to manually find the best combination of coefficients for each of the 25 test cases beforehand, and hardcode them into our code.

Though this procedure is somewhat troublesome, this is only to avoid TLE. If our math was correct, it takes about 80 seconds for our code to automatically find the best combination of coefficients and provide a complete replenishment plan given any new test cases with

$(n,m)=(40,1000)$ and faster for test cases with a smaller scale.

Perhaps 80 seconds is not fast at all, but making or finding a replenishment plan is a matter of a company’s revenue, so I think it is worth it.

---

$$\text{The Evolution of Sort-keys}$$

$\text{1.}$

$$M_{ij}=p_i-c{d}_{ij}$$

1 to 2: Sort-key 1 doesn’t consider

$x_{ij}$ , which sometimes lower the profit when

$s=1$.

$\text{2.}$

$${\pi }_{ij}=(p_i-c{d}_{ij})\cdot x_{ij}$$

2 to 3: Sort-key 2 didn’t consider

$f_i$ , which may overestimate each retail stores’ profit.

$\text{3.}$

$${\pi }_{ij}-f_i⟺(p_i-c{d}_{ij})\cdot x_{ij}-f_i$$

3 to 4: Sort-key 3 doesn’t consider

$h_j$, which may overestimate each distribution center’s profit. In order consider

$h_j$ proportionately, we multiply

$h_j$ with a coefficient

$\frac{x_{ij}}{K_j}$.

$\text{4.}$

$${\pi }_{ij}-f_i-x_{ij}\frac{h_j}{K_j}$$

4 to 5: We found that for

$s=1$ and

$s=2$, we should emphasize on different things: For

$s=1$, we emphasize on the total profit of a single option, while for

$s=2$, we emphasize on the unit profit of a single option. So we divided our sort-key into two parts to handle two different situations accordingly.

$\text{5.}$

$$k_1={\pi }_{ij}-f_i-h_j$$

$$k_2=M_{ij}-\frac{f_i+h_j}{x_{ij}}$$

5 to 6: We overestimated the cost of a option by taking 100% of

$f_i$ and

$h_j$ into consideration.

$\text{6.}$

$$k_1={\pi }_{ij}-f_i-h_j{\lambda }_{1h}$$

$$k_2=M_{ij}-\frac{f_i+h_j{\lambda }_{2h}}{x_{ij}}$$

6 to 7: We found that total profit would increase if we also lower the weight of

$f_j$.

$\text{7.}$

$$k_1={\pi }_{ij}-f_i{\lambda }_{1f}-h_j{\lambda }_{1h}$$

$$k_2=M_{ij}-\frac{f_i{\lambda }_{2f}+h_j{\lambda }_{2h}}{x_{ij}}$$

---

$$\text{Segregation of tasks}$$

$\text{A. Project Manager}$

​​​​B10705016 顧寬証

$\text{B. Algorithm Design}$

​​​​All members

$\text{C. System Development}$

​​​​B10705016 顧寬証

$\text{D. Testing Data Design}$

​​B10705006 黃偉翔
​​​​B10705010 蔡可亮
​​​​B10705050 陳禹翰
​​​​B10705055 賴旻

$\text{E. Discussion Room Reservation}$

​​B10705006 黃偉翔
​​​​B10705050 陳禹翰

$\text{F. Report}$

​All members

$\text{G. Food Finder}$

​​​​B10705010 蔡可亮

$\text{H. Report Revision and Formatting}$

​B10705016 顧寬証

---

$$\text{Reflections and thoughts}$$

$\text{A. B10705006 黃偉翔}$

This midterm project is really unforgettable! It is the first time I program with others. In fact, the manager of our team finished almost the entire code right after our first meeting. The most time-consuming job of this project is to improve our algorithm. We decided to apply Greedy Algorithm to this project and came up with four different kinds of algorithms(sort-keys) in the first meeting. The instant when PDOGS allowed us to upload our code, we were very excited, but ended up with a terrible score. It turned out that the execution time exceeded the time limit, so we tried to speed up our code and improve our algorithms. One morning on the way to school, an idea flashed into my mind, and I shared this thought with my teammates immediately. This idea did help improve our performance, but we were still not the first place. Thanks to all my teammates' efforts, we improved again and again, finally winning first place before the deadline. It’s a great experience of doing a project with them.黃偉翔

$\text{B. B10705010 蔡可亮}$

When seeing the question for the first time, I was shocked by these optimization problems. Those notations are too problematic to handle. Also, the constraints are too complicated. After preliminary consideration, I overcame it but still couldn’t know how to cope with it. Thanks to the purpose of this Midterm Project––teamwork, I finally realized the importance of segregation of duties. This is the best experience to learn how to cooperate with other members in my life ever. Every member of our group is 100% constructive because we extremely wanted to gain the best grades. Thus, we came up with several solutions at the very beginning in turn that we had enough time to carry out the unsurpassable “lambdas.” Super proud of my team members, I deeply appreciate every one of them. Thanks a lot. Let's move on to the next stage––Final Project.蔡可亮

$\text{C. B10705016 顧寬証}$

Before I begin my reflections, I would like to express my deepest gratitude and appreciation to my teammates, 偉翔, 可亮, 禹翰 and 賴旻, for being such wonderful co-workers and friends at the same time. I think you all did an amazing job for being highly involved throughout this project and actively attending regular meetings despite having other unfinished tasks. It surely is my pleasure to be a part of this cooperative and lovely team. The championship belongs to us, the whole team. It’s impossible for me to reach such a high level alone without any one of you. There is just too much I learnt and felt during the past few weeks that I can only share a part of it here. The following are some of my reflections.

To begin with, I realized, quite profoundly, that it’s always wiser to lay a complete plan prior to starting a project. When the problem was first released on COOL, we didn’t jump headlong into the coding process. Instead, we immediately arrange our first meeting to share and exchange our understandings and ideas regarding the stem, and then compile our initially scattered ideas into one neat understanding. Any further discussion didn’t start until we made sure everyone fully understood the problem. Then, we started to discuss and exchange ideas on the conceptual algorithm we should adopt for this problem. We had lots of brainstorming and rational debates, and also did some math during the forming of our algorithm. After almost everything was settled, I started to code the basic structure of our problem solving logic, and it didn’t take me that long to produce an effective and neat piece of code thanks to our complete plan written clearly in plain text in advance by other teammates.

Moreover, it dawned on me that having keen perceptions and being observant are really important. We discovered some patterns in the output of our underperforming algorithm in the early stages, and gave them in-depth analyses to clarify the reason behind such happening, making it easier for us to come up with solutions more effectively and efficiently.

Last but not least, we realized that it’s advisable to adopt scientific methods to examine our understandings or ideas, for it is able to either effectively prove the correctness with scientific basis or help us easily realize the mistakes we had made and the misunderstandings we might have. 顧寬証

$\text{D. B10705050 陳禹翰}$

To start with, congrats to the team for our winning the first place in this Midterm Project. I think all of us are overjoyed since our efforts have paid off. We worked hard on this project and as a matter of fact, I enjoyed the vibe from working with my teammates. In our team, everyone was trying their best to improve our algorithm, and no one was being a free rider. What’s more, I love the process of coming up with new thoughts based on others’ thoughts. Whenever we achieve a new high score or encounter a breakthrough, it really feeeeeels right. I’m so excited that I was being helpful when making great improvements on our code.

Here’s a fun fact, our team consists of only freshman students in the IM department. As a consequence, we are dying to take the first place to prove that the champ belongs to the IM department. However, despite the fact that we went to great lengths, we only got second place the night before the deadline. We were exhausted and decided to call it a day. However, when we woke up the next morning, we found that we were in first place! What a surprise!

Last but not least, I genuinely appreciate my teammates for this wonderful experience. I hope we can learn more from each other and get good grades in the Final Project together once again.陳禹翰

$\text{E. B10705055 賴旻}$

I’ve learned lots of things during this month. First, I learned more about the application of struct, class and vector, which greatly enhanced my programming skills. I also realized the importance of program structure. A well-designed structure makes it easier for us to modify our program. Thanks to the good program written by our manager, I found myself able to understand it quickly and write down the procedure easily.

On top of that, the most important lesson I learned was teamwork. I won’t be able to construct such a complex project without my teammates. We came up with different algorithms, coped with many problems, and finished the report together. We were enthusiastic about this project and put in a lot of effort. No one was absent from our regular meetings on Sunday morning every week. Sometimes we even had online meetings until midnight. When we finally won first place, all of our members were proud of ourselves. I enjoy the process of working with them. I hope we can try our best in the final project and also keep our liver healthy.賴旻