# Optimization of Chosen Transport Task by Using Generic Algorithms

Anna Burduk, Kamil Musial

<figure><img src="image_1.png" /></figure>

## To cite this version:

Anna Burduk, Kamil Musial. Optimization of Chosen Transport Task by Using Generic Algorithms. 15th IFIP International Conference on Computer Information Systems and Industrial Management (CISIM), Sep 2016, Vilnius, Lithuania. pp.197-205, 10.1007/978-3-319-45378-1_18 . hal-01637504

HAL Id: hal-01637504

https://inria.hal.science/hal-01637504

Submitted on 17 Nov 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# Optimization of chosen transport task by using generic algorithms

Anna Burduk¹ and Kamil Musiał²

¹,²Wrocław University of Technology, Mechanical Department, Wrocław, Poland
anna.burduk@pwr.wroc.pl
kamil.musial@student.pwr.wroc.pl

**Abstract.** The paper presents genetic algorithms, their properties and capabilities in solving computational problems. Using a genetic algorithm an optimization task of transportation - production regard to the transport and processing of milk will be investigated. For the network of collection centers and processing plants (factories) the cost-optimal transportation plan regarding to raw materials to the relevant factories will be established. It is assumed that the functions defining the costs of processing are polynomials of the second degree. To solve the problem the program that uses genetic algorithms written in MATLAB will be used.

**Keywords:** optimization of production systems, generic algorithms

## 1 Introduction

The main purpose of transportation in a company is the system organization and synchronization of physical flow of materials from manufacturers or wholesalers to consumers through all phases of the process, in accordance with the principles of logistics management [1,6,7,12].

Expenditure on transport a large part of total costs, which make the difference between the cost of goods producing and price paid by the consumer. In addition, some of the goods should be transported as quickly as possible due to the limited period of validity. These reasons tend to pay attention to the problem of transport optimizing [11]. At the same time the continuous technological and information advances guarantees the emergence of new methods that can be successfully used in solving transport problem. Transport issues are most often used to [6, 10]:

* optimal products transport planning, taking into account the minimization of costs, or time of execution

* optimization of production factors distribution in order to maximize production value, profit or income.

adfa, p. 1, 2011.

© Springer-Verlag Berlin Heidelberg 2011
Genetic algorithms belong to group of stochastic algorithms. The basic principle of their functioning is based on the imitation of biological processes, namely the pro- cesses of natural selection and heredity. Genetic algorithms are gaining more and more areas of applications in the scientific, engineering and even in business circles, as an effective tool for efficient searching [1,5]. The reason for this is obvious: genet- ic algorithms are a simple and at the same time powerful tool to search for better solu- tions. In addition, they are free from the essential constraints imposed by the strong assumptions about the search space, ie. continuity, existence of derivatives, modality of the objective function, etc.. A typical problem solved by genetic algorithm consists of [2,4,6,9]:

* optimization problem - finding the best solution of all allowable,

* a set of allowable solutions - the set of all possible solutions to the task (not only the optimal),

* the evaluation function (adjustment) - the function that determines the quality of each possible solution. It establishes an ordinal relationship on the set of feasible solutions. In other words, because this function, one can sort all the solutions from best to worst solution of the problem,

* coding method - a function that represents each acceptable solution in the form of string code, which is in the form of a chromosome. Basically, more interesting should be the inverse function. This is a function that, on the basis of chromosome, creates a new feasible solution. In fact, to solve the task the only basic function is required, analogous to nature. Nature has complicated 'knowledge' on how to cre- ate an adult from an embryo. I would be enough that each of the individuals will be stored in the memory of genotype, on the basis of which he was created.

## 2 The mathematical model of transport – production task

In the following example optimization of transport - production tasks for the pro- cessing of milk will be considered. For network of collection points and processing plants, according to its algorithm, the cost-optimal distribution of transport tasks has been determined. It is assumed that the functions defining the costs of conversion are polynomials of the second degree. To solve the problem a program written in MATLAB based on the genetic algorithm, equalizing marginal costs is used.

Enterprise processing a uniform material has m collection points and n plants pro- cessing this material. Additional information should be known:

* unit cost of transportation from any collection point to individual processing plants,

* amount of material collected at each point of supply,

* functions defining the cost of the material processing at each plant, depending on the size of the processing.

Features defining the costs of conversion are convex and square functions. They take into account only the variable costs, which depend on the size of production. The entire acquired material must be transported to the plant and converted there. It is
assumed that plants are able to process the supplied amount of material (the possibility of processing by plants are known). This increases the production capacity of plants, but also results in an increase in the unit cost of production. Rising costs of conversion are a natural limitation of the size of production of each establishment.

It is needed to establish a plan of material supplies to individual plants and processing of raw materials in these plants, so the total costs of transport and processing were minimal. The following designations have been adopted:

i - the number of the collection (supplier number),

j - number of the processing plant (recipient number),

$x_{ij}$ - the amount of raw material transferred from the i-th supplier to the j-th recipient,

$x_j$ - the amount of raw material processed by the j-th recipient,

$a_i$ - the amount of raw material, which must be send by i-th supplier,

$c_{ij}$ - the unit cost of transport from the i-th supplier to the j-th recipient,

$f_j(x_j)$ - the cost of processing $x_j$ units of raw material in the j-th plant (at j-th recipient).

Furthermore assumed that the convex cost function $f_i$ is a second degree polynomial of the form:

$$f_j(x_j) = c_j x_j + e_j x_j^2, \quad c_j, e_j > 0 \quad (1)$$

where:

$c_j$ - describes the minimum unit cost of processing,

$e_j$ - determines the growth rate of unit cost.

The first derivative of this function is determined by the marginal cost of processing:

$$F_j'(X_j) = C_j + 2 E_j X_j \quad (2)$$

while the second derivative - the rate of increase in the marginal cost:

$$F_j''(X_j) = 2 E_j \quad (3)$$

The average cost of processing the j-th plant is determined by the formula:

$$K_j^P(X_j) = C_j + E_j X_j \quad (4)$$

The problem of determining the optimal supply plan of raw material and its processing can be presented in the form of a non-linear decision task.

Variables $x_{ij}$ and $x_j$ are sought that:

$$\sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} + \sum_{j=1}^{n} f_j(x_j) \rightarrow \min. \quad (5)$$
By the conditions:

$$ \sum_{j=1}^{n} x_{ij} = a_i; (i = 1, \dots, m), \qquad (6) $$

$$ \sum_{i=1}^{m} x_{ij} = x_j; (j = 1, \dots, n) \qquad (7) $$

$$ x_{ij}, x_j \ge 0; (i = 1, \dots, n) \qquad (8) $$

The objective function (5) minimizes the total cost of transport and processing. Condition (6) provides that each supplier will send all owned raw material. Condition (7) forces the processing in the j-th plant of all the raw material to which it is delivered. Task (5 - 7) is the task of quadratic programming with a special - transport structure. It can be solved by using an algorithm equalizing the marginal cost, which is based on genetic algorithm.

Marginal cost, the cost of which the manufacturer incurs due to the increased size of production of the good by one unit. It is the increase in total costs associated with producing an additional unit of a good. If the plant increases its production by one unit, then the total cost of production will increase. The difference in the size of the costs manufacturer incur earlier and costs incurred after the increase in production is a marginal cost. It is, therefore, the cost of producing an additional unit of a good.

The concept of marginal cost can also be formulated in relation to the consumer and is then taken as the cost of acquiring an additional unit of a good. The marginal cost is an important micro-economic category. It was observed that for typical business processes marginal costs initially decrease with the increase in production until the technological minimum is reached. Further increase of production over a minimum of technology, however, increases the unit cost of further increases in production and thus rising marginal costs. This observation is important in microeconomic analysis of the behavior of the manufacturer and determining the optimal level of production. According to economic theory, marginal cost cannot be negative. This means that the increase in production may entail reducing the total cost.

Method of equalizing the marginal cost based on genetic algorithm consists of:

* determination of the best possible, an acceptable solution output,

* improvement of new solutions X¹, X², ..., by offset equalizing marginal costs.

A string of new obtained solutions X¹, X², ..., Xⁿ, ..., does not need to be finished. It is therefore interrupted at some point of calculations. It is important, however, that the final solution does not deviate too far away (in terms of objective function value) from the optimum solution. JCC algorithm comes down to the following steps:

1. Determine the initial solution:

a) for the i-th supplier (i = 1, ..., m) the route with minimal marginal cost is set,

b) on the selected route an entire supply of i-th supplier is located,

c) update the marginal costs in the column of the selected route.
Then move on to the next vendor, and repeating steps (a) - (c) until the supply is disposed for all suppliers.

2. Make sure the current solution $X_r$ meets the criterion of optimality. If so, the final solution is optimal. If not- return to step 3.

3. Make sure the solution $X_r$ is $\varepsilon$- accurate. If so, finish the calculations. If not, go to step 4.

4. Improving the solution by shifting equalizing marginal costs and return to step 2.

Having designated solution $X_r$ and the matrix of marginal costs $K_r$ for each supplier, lets settle the differences between the maximum realized cost and the minimal cost.

### 3 Solving the problem of transport and production using a genetic algorithm

The study involved the delivery of milk (about 2 000 m³/month). The task was formulated as follows:

Six suppliers (in 6 cities): $D1, D2, D3, D4, D5, D6$ supplies milk to two factories: $S1, S2$, with restrictions:

$S1$: can accept and process 700 or 1000 m³ of milk,

$S2$: can accept and process 1 500 m³ of milk.

Data are summarized in Table 1 below and include:

unit transportation costs (in PLN per km),
offered monthly deliveries $A_i$ (m³),
monthly demand of factories $B_j$ (m³).

<table><caption>**Table 1.** Unit transportation costs, supply and demand</caption><thead><tr><th rowspan="3">Suppliers</th><th rowspan="3">Supply A<sub>j</sub><br>[m<sup>3</sup>]</th><th colspan="4">Factories</th></tr><tr><th colspan="2">Variant v1</th><th colspan="2">Variant v2</th></tr><tr><th>S1</th><th>S2</th><th>S1</th><th>S2</th></tr></thead><tbody><tr><td>D1</td><td>400</td><td>5</td><td>60</td><td>5</td><td>60</td></tr><tr><td>D2</td><td>70</td><td>40</td><td>60</td><td>40</td><td>60</td></tr><tr><td>D3</td><td>100</td><td>70</td><td>15</td><td>70</td><td>15</td></tr><tr><td>D4</td><td>300</td><td>70</td><td>5</td><td>70</td><td>5</td></tr><tr><td>D5</td><td>420</td><td>100</td><td>50</td><td>100</td><td>50</td></tr><tr><td>D6</td><td>200</td><td>100</td><td>80</td><td>80</td><td>100</td></tr><tr><td>Demand B<sub>j</sub> [m<sup>3</sup>]</td><td>700</td><td>1500</td><td>1000</td><td>1500</td><td></td></tr></tbody></table>

The task is solved with the help of developed in MATLAB genetic algorithm equipped with a graphic interface GUI. The aim of the task is to determine the opti-
mal marginal cost of "material processed" transport from any supplies, to one of two factories, taking into account its processing capacity.

## 3.1 Solving the transport- production problem of in the general scheme of genetic algorithm

### Population.

The first step is to number all suppliers. Created chromosome has a length such as the number of suppliers. In the following genes another supplier is saved. For example, if the gene number 1 "represents" city X and gen number 2 city Y it means that the provider moves from town X to Y. In this way, genes in the chromosome are arranged exactly as the city cycle. For a sample of six cities connected with road, a sample chromosome mapping cycle may look like this:

[1 4 6 2 3 5]

### The evaluation function (cost).

The function of evaluation is the total minimum cost of transport and processing.

### Selection.

Simulation using the roulette wheel assigns the probability of choosing each individual directly on the basis of a single evaluation function. The sum of the probabilities assigned to each chromosome is equal to 1, which means that if the area of a circle is the sum of the values of the objective function of population individuals, then each of them is associated with a circle section. In the current example, it six fields exist.

### Crossover.

One-point crossover. Individuals are combined sequentially in pairs:

<table><tr><td>5.39</td><td>5.8</td></tr><tr><td>5.8</td><td>6.51</td></tr></table>

Parent 1: [3 4 6 2 1 5]

Parent 2: [4 1 5 3 2 6]
Among the offspring duplicates of existing individuals may appear. Duplicates do not bring anything to the database all the genes are subjected to forced mutation.

## Mutation.

After giving birth to offspring, approx. 50% of generation mutates.

## 3.2 Solution to the problem in MATLAB

After entering all necessary data, information about the correct solution of the problem is obtained (Fig.1). On the y-axis the accuracy of the solution (in %), and on the x-axis the number of iterations (max = 5) is given.

<figure><img src="image_3.png" /><figcaption>Fig. 1. The dialog box of the program - the relationship of the accuracy and the number of iterations</figcaption></figure>

If the solution is optimal- accurate results in a table showing the following information:

* amount of processing at the individual plants,

* the total cost of the transportation and processing of milk,

* the cost of transport,

* the cost of processing,

* average costs,
* marginal costs,

* way of the deployment of milk.

<figure><img src="image_4.png" /><figcaption>Fig. 2. Terms of the calculation in the program for variant v1</figcaption></figure>

The calculations examined several variants, the supply of milk did not change but both demand (processing capacity), and processing costs (description of function) were variable. For example, variant v1 adopted by Table 1 the following demand: for factory S1 - 700 m³ / month, and for the factory S2 - 1500 m³ / month.

Also, based on studies carried out it was assumed that the processing functions have the following form:

$$f_1(x_1) = 15x_1 + 0,2 x_1^2 \text{ and } f_2(x_2) = 15x_2 + 0,1x_1^2$$

In the case of variant V2 (data according to Table 1) adopted the demand: for factory S1 - 1 000 m³ / month and for the factory S2 - 1500 m³ / month. Processing functions have the form:

$$f_1(x_1) = 10x_1 + 0,2 x_1^2 \text{ and } f_2(x_2) = 10x_2 + 0,1x_1^2$$

## 3.3 Summary of results

Collective summary of results is shown in Table 2. There is placed sample of simulation results conducted for several variants, which are varied in parameters of processing function, transportation costs, the possibility of processing by individual factory. Statement contains the best results.
<table><caption>Table 2. Results for the task</caption><thead><tr><th rowspan="2">Suppliers</th><th colspan="2">Factories</th></tr><tr><th>Variant v1</th><th>Variant v2</th></tr></thead><tbody><tr><td>Solution</td><td colspan="2">S1: 0.2x<sup>2</sup> + 15x</td></tr><tr><td></td><td colspan="2">S2 0.1x<sup>2</sup> + 15x</td></tr><tr><td>Processing [m<sup>3</sup>]</td><td>580</td><td>1 020</td><td>880</td><td>720</td></tr><tr><td>Stock of processing [m<sup>3</sup>]</td><td>120</td><td>480</td><td>120</td><td>780</td></tr><tr><td>Transport costs [PLN]</td><td colspan="2">40 700</td><td colspan="2">40 700</td></tr><tr><td>Processing costs [PLN]</td><td colspan="2">226 720</td><td colspan="2">195 320</td></tr><tr><td>Total costs of transport and processing [PLN]</td><td colspan="2">267 420</td><td colspan="2">236 020</td></tr><tr><td>Average costs [PLN / m<sup>3</sup>]</td><td>186</td><td>82</td><td>131</td><td>117</td></tr><tr><td>Marginal costs [PLN/ m<sup>3</sup>]</td><td>362</td><td>362</td><td>247</td><td>219</td></tr><tr><td>The way of transport divisions</td><td colspan="4"></td></tr><tr><td>D1</td><td>500</td><td>0</td><td>500</td><td>0</td></tr><tr><td>D2</td><td>80</td><td>0</td><td>80</td><td>0</td></tr><tr><td>D3</td><td>0</td><td>200</td><td>0</td><td>200</td></tr><tr><td>D4</td><td>0</td><td>400</td><td>0</td><td>400</td></tr><tr><td>D5</td><td>0</td><td>120</td><td>0</td><td>120</td></tr><tr><td>D6</td><td>0</td><td>300</td><td>300</td><td>0</td></tr></tbody></table>

The chart shows that the total cost of the task for variant v1 is 267 420 PLN and it is more than 40 000 PLN higher than the costs of the variant v2. This difference is primarily due to the fact that for small factories processing costs are higher than for larger ones.

## 4 Summary

The study shows that the effective use of resources spent on process management is only possible through system logistics solutions that will be effective in terms of technical information and simultaneously optimized in terms of financial outlay.

The proposed work approach using solving the problem of production and transport costs with convex function should facilitate decision-making processes of transport and production management. Genetic algorithms fully confirmed its effectiveness for the problem, minimizing total costs of transport and processing.
Unlikely the classic optimizing methods that give determined outcome, the Genetic Algorithms do not guarantee finding the best solution. An efficient GA using is complex because of mutation- random component. Executing the same algorithm for the same task a few times may obtain various results.

The relationship of the accuracy and the number of iterations (Figure 1) has been obtained and showed to find out how many iterations should be performed to achieve adequate (not random) results. Task become more complex when computing time is also significant and it is necessary to guarantee find the optimum between result accuracy and computing time or when it is required to clearly determinate if obtained solution is the best one.

## 5 References

1. Ayoough A., Zandieh M., Farsijani H.: GA and ICA approaches to job rotation scheduling problem: considering employee's boredom. In: International Journal of Advanced Manufacturing Technology, Vol. 60, pp.651-666, (2012).

2. Burduk A.: Artificial neural networks as tools for controlling production system and ensuring their stability. Computer Information Systems and Industrial Management. Lecture Notes in Computer Science, Vol. 8104, pp. 487-498, (2013).

3. Chodak G., Kwaśnicki W.: Genetic Algorithms in seasonal demand forecasting. In: Information Systems Architecture and Technology'2000, Wrocław University of Technology, pp. 91-98, (2000).

4. Govindan K., Jha P.C., Garg K.: Product recovery optimization in closed-loop supply chain to improve sustainability in manufacturing. In: International Journal of Production Research, Vol. 54, No. 5, pp. 1463-1486, (2016).

5. Guvenir H. A., Erel E: Multicriteria inventory classification using a genetic algorithm. European Journal of Operational Research. Vol. 105 (1), pp.29-37, (1998).

6. Jachimowski R. Kłodawski M.: Simulated annealing algorithm for the multi-level vehicle routing problem, Logistyka 4, (3013).

7. Krenczyk D., Kalinowski K., Grabowik C.: Integration Production Planning and Scheduling Systems for Determination of Transitional Phases in Repetitive Production, Hybrid Artificial Intelligent Systems, Vol. 7209, Springer, Berlin Heidelberg, pp. 274-283 (2012).

8. Krenczyk D., Skołud B.: Production preparation and order verification systems integration using method based on data transformation and data mapping. Lecture Notes in Computer Science, vol. 6697, 297-404, (2011).

9. Nissen V.: Evolutionary algorithms in management science. An overview and list of references. Papers on Economics & Evolution, Report No. 9303, European Study Group for Evolutionary Economics, (1993).

10. Sahu A, Tapadar R.: Solving the assignment problem using genetic algorithm and simulated annealing. In: International Journal of Applied Mathematics, Vol. 36(1), (2007).

11. Yusoff M, Ariffin J, Mohamed A.: Solving vehicle assignment problem using evolutionary computation. In: Lecture Notes in Computer Science, Vol. 6145, pp. 523-532, (2010).

12. Zegordi S.H., Beheshti Nia M.A.: A multi-population genetic algorithm for transportation scheduling. Transportation Research Part E: Logistics and Transportation Review, Vol. 45(6), pp.946-959, (2009).