Abstract

Contents

Introduction

Many industrial processes nowadays are optimized using intelligent methods to solve various problems. One of such tasks is the loading of goods in the vehicle. A problem to place the goods in a way to consume the least amount of space occurs during the loading. In other words, we are facing the aim with the optimized stacking also known as the 3-dimensional knapsack problem. It reduces the cost of transporting goods due to a more compact distribution.

1. Timeliness of the topic

Packing boxes in the container body of the vehicle or pallet is one of the most difficult problems of the stacking.[10] This is a NP-hard complete problem and its optimal solution is a classical challenge in combinatorial optimization. All the exact algorithms use blind search of all possible solutions. Therefore, even with a small amount of goods, the program will run for an unacceptably large amount of time. The same problem is to set additional restrictions that must be satisfied during the load arrangement within a given volume. Thus, the creation of approximate algorithms is a crucial task.

2. The purpose and objectives of the research, expected results

Objective: Improvement of the effectiveness of cargo delivery to consumers at the expense of its efficient placement within the vehicle.

The main objectives of the study:

1. Analysis of technologies and methods used to solve the transportation problem, formulation of the buildup for the issue with placing the goods inside the vehicle ;

2. Development of a mathematical model for placing the goods under the confinement conditions;

3. Development of the upgradable genetic algorithm to optimize the placement of cargo in the vehicle;

4. Verification of the effectiveness of the algorithm.

The object of research is the process of loading the goods in the vehicle.

The subject of the study is determination of the goods’ optimal placement within a given volume of the vehicle.

3. Review of Research and Development

The analysis of works devoted to the creation of models and algorithms for three-dimensional packaging determined that heuristic approaches are mainly used for resolving such tasks. The most frequently mentioned heuristics in the literature are: Iterative Local Search, (ILS); Guided Local Search (GLS); Variable Neighborhood Search (VNS); Greedy Randomized Adaptive Search Procedure (GRASP); Evolutionary Algorithm, (EA); Genetic Algorithms (GA); Ant Colony Optimization (ACO); Simulated Annealing (SA); Tabu Search (TS). [9] In comparison with the number of all kinds of heuristics, the number of accurate algorithms for solving three-dimensional case packing problem is limited. One of the reasons for this is the complexity of packaging and the imposition of limitation from real-world problems. Even if this method of solution is found, there is a difficulty in formulating solutions, which are often huge due to the number of boxes and containers. [10]

3.1 Review of international sources

The resolution of the issue with goods’ placing inside the vehicle is commonly met along with the problem of constructing routes (the so-called traveling salesman problem) in the foreign authors' works. 2L-CVRP and 3L-CVRP are decollated during solving the transportation problem. 2LCVRP class problem considers two-dimensional arrangement of objects, while 3L-CVRP (Three-Dimensional Loading Capacitated Vehicle Routing Problem), respectively, a three-dimensional one.

For example, in [4] and [5] a hybrid algorithm for solving 3L-CVRP is used. It consists of a tabu search algorithm for the vehicle routing and subordinate tree search algorithm to load the boxes of all customers in the cargo space of the car.

4. Analysis of similar systems

An analysis of existing computerized systems was conducted. One of the most popular solutions of optimal goods’ loading is the online service «packer3d». The basis of the algorithms used in the program for the calculation of the optimal loading plan different types of goods is laid in the theoretical and applied researches by Victor Psiola [2] The service allows you to calculate the optimal loading plan for different types of boxes, cylinders, and pallets into containers, trucks, and cars. The service works with many restrictions on loading.

A similar functionality is seen in the service of calculating the load on site www.searates.com. This portal is dedicated to maritime transport. It has a load calculator that allows you to approximate the optimal location inside the cargo container.

5. The mathematical formulation of the three-dimensional packing problem

A region with width W, length L and height H is given. It is a container. The container has a rear opening part dimensions H × W for loading and unloading goods. The container has a carrying capacity of D. Given a set of blocks is N. The entire set of blocks divided into many types of T. Each type determines the geometric parameters, weight, value and a number of other parameters of the blocks. It is required to calculate the exact position of the blocks in a specified volume so that its filling is acceptable and effective. That is done so that the total amount of placed blocks is maximal. The moment when all blocks packed within a given volume and they do not overlap and rest on the bottom and walls of the other blocks is considered a valid block position.

pic1

Figure 1 - Load in a 3 dimensional space
(Animation : 7 frames , repetition cycles - 12 , size 39 KB )

The following packing constraints are involved:

1. The total amount of the elements shall not exceed the volume of the vehicle.

2. Neither element is to be beyond the predetermined volume.

3. The occupied weight cannot exceed the carrying capacity of the vehicle.

4. Boxes can only be placed so that their edges are parallel to the walls of the container.

5. Boxes should not cut each other.

The objective function:

F = (xmax - xmin) * (ymax - ymin) * (zmax - zmin) , F →min,

where point (xmin, ymin, zmin) и (xmax, ymax, zmax) – the defining points of describing the blocks.

Considering the problem of placement of goods in a vehicle, we introduce the rules of loading of the vehicle, which must be considered in the implementation of the algorithm:

1. The blocks may have only parallelepiped form.

2. Volume filling of the vehicle with blocks comes from the far wall to the neighbor.

3. Only those blocks, which go through the vehicle’s opening door ( the parameters of which are: width W1 and height H1 ) can be packed.

4. Only those blocks that completely fit in the container can be packed.

It is possible to add additional restrictions, which will seem inconsiderable on one hand, but on the other hand, can seriously affect the loading plan of goods in the vehicle:

- Restriction on the fragility of items: non-fragile items cannot be placed on top of fragile ones;

- The restrictions on boxes’ orientation and rotations;

- Each box should be entirely on a flat surface that is fully supported by the container or another box.

To achieve this objective during the analysis a modified genetic algorithm was selected.

Conclusions

As a result of the research work, we have collected and studied materials on the issues related to the theme of the master's work. We investigated the applied methods and algorithms to optimize the loading of cargo in vehicles. We have identified the advantages and disadvantages of existing computer systems, optimization methods, which belong to different classes. We chose the direction of our own research in the field of cargo placement in the vehicle based on the analysis results.

Comments

At the time of writing this essay, master's work is not completed yet. Estimated completion date: May 2017. The full text of work and materials on the topic can be obtained from the author or his manager after that date.

Список источников

  1. Корчевская О.В. Информационные модели и методы решения задач ортогонального раскроя-упаковки на основе конструктивных и нейросетевых подходов, Диссертация // СГТУ, 2009г. – 147с.
  2. Псиола. В.В. Об одном приближении плотной упаковки, Диссертация // МГУ имени М.В. Ломоносова, 2011г. -143с.
  3. Курейчик В.В., Заруба Д.В., Запорожец Д.Ю. Применение генетического алгоритма решения задачи трехмерной упаковки // Известия ЮФУ. Технические науки, 2012г. - 264с.
  4. Andreas Bortfeldt A hybrid algorithm for the capacitated vehicle routing problem with threeв dimensional loading constraints // — Режим доступа:ftp.fernuni-hagen.de/pub/fachb/wiwi/winf/forschng/publi/DBFakWiWI460.pdf
  5. Qingfang RUAN, Qi RUO , Kevin Woghiren, Lixin MIAO A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints //  — Режим доступа: ntl.bts.gov/lib/37000/37900/37921/A_hybrid_genetic_algorithm_for_the_vehicle_routing_problem_with_three-dimensional_loading_constraints.pdf
  6. Сайт компании Packer3d // — Режим доступа: packer3d.ru
  7. Сайт компании Searates // — Режим доступа: searates.com
  8. Трубачев Д. С. Система формирования динамического расписания рейсов, с учетом воздушных ресурсов авиакомпании // — Режим доступа: masters.donntu.ru/2013/fknt/trubachev/
  9. Кощеев И.С. Оптимизация доставки груза потребителям с учетом его размещения внутри транспортных средств на основе эвристических методов. Диссертация // — Режим доступа: www.ugatu.ac.ru/assets/files/documents/dissov/03/2014/KoshcheevIS/diss.pdf
  10. Юдаков П.В. Задача о трехмерной упаковке и методы ее решения. Обзор // Инженерный вестник № 06, июнь 2015
  11. Лобкова А.А., Секирин А.И. Алгоритмы оптимизации загрузки транспортных средств // Международная научно-техническая конференция студентов и молодых учёных Компьютерная и программная инженерия