**Adjusted 0-1 Knapsack Problem in Cargo Flow by Using Artificial Bee Colony Algorithm**
\*\*This is a Double-blind review, please do not include authors information in this version \*\*
Received Date: \*date
Accepted Date: \*date
Published Date: \*date
**HIGHLIGHTS**
- Knapsack is the problem of optimisation used to illustrate the problem and the solution in which each set of items has its own specific value and weight.
- Artificial bee colony algorithm is used to determine the minimum total cost of 30 shipments.
- Based on the flow of all 30 shipments results, the total cost is obtained.
ABSTRACT
*This study describes the problem with the knapsack that occurred in the cargo flow. The problem of the knapsack is the problem of optimisation used to illustrate the problem and the solution in which each set of items has its own specific value and weight. With its total value as much as possible, the number of items that may become less or at least equal to or equal to the limit. Therefore, the aim of this study is to determine the minimum total cost of 30 shipments based on volume by using Artificial Bee Colony (ABC) algorithm in order to achieving the highest profit. ABC algorithm was derived from the bee colony which consists of four phases of initialisation, employed bees, onlooker bees and scout bees. Based on the result obtained, the total cost of the shipment is 402.377 tons per km which starting from the Shipment 25 with 2 560 000 tons per year for 0.111 tons per km and ends with Shipment 21with 2 250 000 tons per year for 0.129 tons per km.*
*Keywords: knapsack problem, flow volume, total cost, ABC algorithm*
# INTRODUCTION
The first survey of the Knapsack Problem was conducted in the 1897s by Tobias Dantzig. Knapsack is made of canvas or leather, similar to those used by hikers and soldiers. It is commonly used to carry items, equipment and supplies on the back. The problem with the knapsack is the optimisation problem used to illustrate the problem and the solution in which each set of items has its own specific value and weight. With its total value as much as possible, the number of items that may be included in the collection shall be determined in such a way that the total weight becomes less or (at least) equal to the limit. Knapsack problems, or also known as rusksack problems, have more than one constraint: weight limits and volume limits; this means that the amount and weight of each item are not related.
The 0-1 Knapsack Problem (0-1 KP) is one of several types of knapsack problems. It has only one item to select from each set for 0-1 KP, which means there will only be two options for a given item. Choose it (1) or do not select it (0). According to Lin, Liu, Lin, Wu, Wang and Liu (2017), the 0-1 knapsack problem is the combination optimisation problem that is most widely studied. The study modelled the 0-1 knapsack problem using a greedy algorithm to adjust the cargo flow, and noted that the unbounded knapsack problem was a non-deterministic polynomial-time hard (NP-hard) problem. It is known that this very problem arises in a number of other fields, including cargo loading, information encryption and decision-making in engineering projects.
The general model for the 0-1 knapsack problem is follows:
(1)
Subject to:
(2)
(3)
where will determine whether the item of type is included in the knapsack. Given that a set of *n* types of items without quantity restriction. Meanwhile *c* denotes as capacity.
From factory loading, cargo loading, stock-cutting problems, to transport, such as trains, taxis and buses, the problem of knapsack is a normal occurrence in our daily lives. Companies are striving to solve this problem in the hope of achieving the highest profit at the lowest cost. However, the main objectives have not been achieved due to the inefficiency of the company in solving the problem of knapsack. The primary objective is to select a subset of items that bring maximum profit while at the same time presenting minimum costs, thus requiring a company to act on the problem and call the best shot or otherwise suffer losses.
Using the Artificial Bee Colony (ABC) algorithm, the total distance to travel by a salesman can be minimised, as indicated in previous studies. The ABC algorithm was proposed in the study by which iterations reduced the degree of disturbance to which the change of the degree solution as well as the generation of its adjacent solution. The proposed algorithm has proved its effectiveness over another proclaimed approach in the final results of this study (Pandiri and Singh, 2019).
The Set-Union Knapsack Problem (SUKP) resolution study using the Artificial Bee Colony (ABC) algorithm was conducted by He, Xie, Wong, and Wang (2018). It turns out that it is easy to solve this particular problem by developing an evolutionary algorithm for the mathematical model Set-Union Knapsack Problem (SUKP) plus the innovative Binary Artificial Bee Colony (BABC) projection. The study proposed greedy preparation as well as optimisation algorithms.
In addition, the Artificial Bee Colony algorithm is used to solve the Optimal Power Flow (OPF). The aim of the study is to minimise the total cost of thermal units while complying with the limitations of the system such as generator capacity limits, power balance, line flow limits and transformer tap settings limits. The proposed algorithm was tested on the IEEE 30-bus, 57-bus and 118-bus systems. The numerical result has shown that the proposed algorithm can find a high-quality solution to the problem quickly through comparisons of results with other literature methods (Dinh, Ngoc & Vasant, 2013).
Therefore, Artificial Bee Colony (ABC) algorithm is used to determine the minimum cost based on the flow of the shipment obtained.
# METHODOLOGY
On this study, a secondary data was adopted from Lin et al. (2017) which consists of volume of cargo flow and its generalized transport costs as in Table 1 below. In this dataset, there are 30 shipments from China.
Table 1: Dataset of 30 Shipments
| 1 |
1200 |
0.137 |
| 2 |
1210 |
0.11 |
| 3 |
460 |
0.146 |
| 4 |
1790 |
0.135 |
| 5 |
650 |
0.108 |
| 6 |
2310 |
0.115 |
| 7 |
1540 |
0.126 |
| 8 |
1760 |
0.112 |
| 9 |
230 |
0.14 |
| 10 |
1260 |
0.143 |
| 11 |
2800 |
0.137 |
| 12 |
190 |
0.132 |
| 13 |
200 |
0.125 |
| 14 |
610 |
0.129 |
| 15 |
960 |
0.144 |
| 16 |
1560 |
0.141 |
| 17 |
720 |
0.107 |
| 18 |
690 |
0.132 |
| 19 |
750 |
0.15 |
| 20 |
370 |
0.114 |
| 21 |
2250 |
0.129 |
| 22 |
660 |
0.126 |
| 23 |
190 |
0.131 |
| 24 |
2320 |
0.144 |
| 25 |
2560 |
0.111 |
| 26 |
310 |
0.118 |
| 27 |
2580 |
0.133 |
| 28 |
110 |
0.146 |
| 29 |
1360 |
0.118 |
| 30 |
580 |
0.143 |
To execute the optimum total cost from the dataset, the mathematical model from Lin et al. (2017) is used. This model is a flow adjustment model which based on 0-1 knapsack problem.
Since the problem in the previous study included the adjustment of the shipment between parallel paths, the study presents the in-depth railway cargo Flow Adjustment Problem (FAP) with changing freight capacity. The primary objective of the research is to adjust the freight flows between their shortest paths and non-shortest paths based on the knapsack issue.
(4)
Subject to:
(5)
(6)
where, is for the generalized transportation cost, and refer to the length of the path B path A respectively, represents as shipment is adjusted to path A, is the numerical value of shipment *k* traveling along path B, and n is the total number of shipments.
In general, Eq. (4) will determine the maximum the overall cost saving, while Eq. (5) will ensure the total volume of adjusted shipment is smaller the capacity. The value of will be equal to 1 if the shipment is adjusted to path A and 0 if otherwise.
**Artificial Bee Colony Algorithm**
The foraging behaviour of the honey bees illustrates the optimisation technique known as the Artificial Bee Colony (ABC) algorithm. Many practical problems have been successfully addressed by the ABC, as it belonged to the group of swarm intelligence algorithms proposed by Karaboga in 2005. Akay and Karaboga (2012) explained that the idea of the ABC algorithm was derived from the honey bee colony, which consists of three groups of bees, namely bees employing bees, onlooker bees and scouting bees – a minimal model of swarm-intelligent forage selection. Both the employed bees and the onlooker bees make up half of each colony. The employed bees are tasked with exploring previous nectar sources and then providing information on the quality of the site’s food source back to the onlooker bees, also known as the waiting bees. From the information received from the employed bees, the onlooker bees who stayed in the hive will determine which food source to target.
In the meantime, the scout’s bee would look for new food by looking randomly at the environment. Throughout the initial phase of the foraging process, bees will spontaneously explore the environment in order to find a source of food. A bee becomes an employed forger when it discovers a source of food and uses it for nectar. The nectar is being brought back to be emptied. The working bee would either return to its identified source site after unloading the previous nectar, or would be able to inform the other bees of the source site by presenting a dance. The bee returns to being a scout when its source site has run out and it has to go to search for a new source. Back in the hive, the onlooker bees only wait and watch the employed bees’ dances used to inform them of valuable resources. The onlooker bees will then rate the dances based on their corresponding source value and identify the best source sites.
The illustration of ABC algorithm is demonstrated as in Figure 1 below:
Figure 1: Flowchart of ABC Algorithm
(Source: Gou, Li, X., Tang and Li, J., 2016)
***Phase 1: Initialisation Phase***
In this phase, a possible solution, is randomly produced by a group of food sources where is the population size of bees.
(7)
where, , . D denotes as problem size, rand(0,1) is a uniformly distributed random number in \[0,1\], and and are the lower and upper bound of the jth factor.
Then, after possible solution, is obtained, the fitness value and solution of objective value are evaluated.
(8)
where, and are the values of fitness and the solution of the objective value respectively.
***Phase 2: Employed Bee Phase***
In this step, employed bee will search for food sources throughout the room. Every food source, is allocated to only one employed bee and according the following term, a new food source, is created in the vicinity of the food sources, and .
(9)
Where and are randomly selected indexes and is a uniformly distributed random number like \[ -1,1\].
***Phase 3: Onlooker Bee Phase***
The onlooker bees should choose a food source with a probability proportionate to its nectar quantity such as the fitness quality of that food source, by assessing the nectar information received from all employed bees. The *ith* food source's choice likelihood, is calculated by the following formula:
(10)
Based on the result obtained, the greater quantity of nectar that one source of food provides, the greater the likelihood that onlooker bees will choose it.
***
***
***Phase 4: Scout Bee Phase***
The number of scout bee in the colony is not defined in advance of time. Whether abandoned or not, a scout bee is produced depending on the food source situation where the employed bee will be switched to the scout bee if the bee fails to find a new food source for a specified number of tests (determined by a monitoring variable named “limit”). Then, the scout bee will randomly search through the previous equation for a new solution as in Eq. (9), which will then be transformed into an employed bee.
The phase from 2 until phase 4 will be repeating until the termination criterion is satisfied.
**FINDINGS**
The results for the flow of the shipment are generated through MATLAB as in Table 2. The arrangement of the shipment is based on the minimized total cost. The result of the arrangement of the shipment start with Shipment 25 and end with Shipment 21.
> Table 2: The Flow of 30 Shipments
| 1 |
25 |
2560 |
| 2 |
24 |
2320 |
| 3 |
26 |
310 |
| 4 |
20 |
370 |
| 5 |
15 |
960 |
| 6 |
28 |
110 |
| 7 |
17 |
720 |
| 8 |
11 |
2800 |
| 9 |
16 |
1560 |
| 10 |
10 |
1260 |
| 11 |
19 |
750 |
| 12 |
12 |
190 |
| 13 |
6 |
2310 |
| 14 |
14 |
610 |
| 15 |
9 |
230 |
| 16 |
23 |
1960 |
| 17 |
27 |
2580 |
| 18 |
30 |
580 |
| 19 |
3 |
460 |
| 20 |
7 |
1540 |
| 21 |
5 |
650 |
| 22 |
13 |
200 |
| 23 |
18 |
690 |
| 24 |
4 |
1790 |
| 25 |
1 |
1200 |
| 26 |
22 |
660 |
| 27 |
29 |
1360 |
| 28 |
2 |
1210 |
| 29 |
8 |
1760 |
| 30 |
21 |
2250 |
Based on the flow of 30 shipments obtained, the total cost of the arrangement is 402.377 tons per km.
**CONCLUSION**
In this study, the knapsack problem that occur in the cargo flow is being concerned because it commonly used to carry items, equipment and suppliers. The problem with the knapsack is the optimization problem used to illustrate the problem and the solution in which each set of items has own specific. The main objective for this research is to determine the arrangement of the shipment and to determine the total cost based on arrangement of the shipment. A dataset of 30 shipments which consist of cost and flow volume are used. Through the ABC algorithm, it consists of four steps where the steps are initialization, employed bee, onlooker bee and scout bee. The first step is initialization, the initial nectar sources. The next step is employed bees, where this employed bee is associated with a particular source of nectar and its quantity of nectar is determined. Next is onlooker bees’ phase. In this phase, the probability value of the nectar sources of nectar sources with which they are preferred by the onlooker bees will be calculate. And then they will stop the exploitation process of sources abandoned by the bees. For the scout bee phase, send the scouts into the search area or discovering new nectar sources and then memorize the best nectar source found so far. If the requirements are not achieved the bees will go back to employee bee phase and will go through for the next phase.
Based on the results obtained, the shipments are starting with Shipment 25 where the flow volume is 2 560 000 tons per year with 0.111 tons per km and end with Shipment 21 where the flow volume is 2 250 00 tons per year with 0.129 tons per km. Therefore, the total cost for the 30 shipments is 402.377 tons per km.
**REFERENCES**
Akay, B., & Karaboga, D. (2012). A modified artificial bee colony algorithm for real-parameter optimization. *Information sciences*, *192*, 120-142.
Guo, Y., Li, X, Tang, Y., & Li, J. (2017). Heuristic artificial bee colony algorithm for uncovering community in complex networks. *Mathematical Problems in Engineering, 2017.*
He, Y., Xie, H., Wong, T. L., & Wang, X. (2018). A novel binary artificial bee colony algorithm for the set-union knapsack problem. *Future Generation Computer Systems*, *78*, 77-86.
Le Dinh, L., Vo Ngoc, D., & Vasant, P. (2013). Artificial bee colony algorithm for solving optimal power flow problem. *the scientific world journal*, *2013*.
Lin, B., Liu, S., Lin, R., Wu, J., Wang, J., & Liu, C. (2017). Modeling the 0-1 Knapsack Problem in Cargo Flow Adjustment. *Symmetry*, *9*(7), 118.
Pandiri, V., & Singh, A. (2019). An artificial bee colony algorithm with variable degree of perturbation for the generalized covering traveling salesman problem. *Applied Soft Computing*, *78*, 481-495.