Cross-docking cargo delivery routing for guaranteed minimum period

Abstract

Стаття присвячена проблемі успішного застосування кросс-докінгу, як технології доставки вантажів за підвищених вимог до термінів, що дозволяє розв’язувати суперечності між забезпеченням гарантованих термінів доставки і ефективності використання наявного парку вантажівок. Процес організації доставки розглядається як упорядкування на транспортній мережі множини дискретних вантажопотоків у вигляді його фаз. Якщо від фази до фази з потоком не відбуваються якісні, і/або кількісні зміни, то такт такого потоку є сталим. Проте вантажопотоки при кросс-докінгу змінюють за переміщення розмір гурту. Вантажі можна переміщати за призначенням довільним гуртом, розміри якого, однак, є обмежені максимальним та мінімальним значенням розмірів гурту. Розроблено двостадійний алгоритм розв’язання задачі. Транспортна мережа представлена у вигляді графа. Зміст задачі пошуку маршрутів є оптимізаційним, оскільки полягає у множинному виборі з початкового графа дуг при наявності обмежень на вхідні і вихідні потоки. Потрібно кожне ребро графа замінити на дугу прямого або зворотного напряму, або видалити це ребро. Критерій оптимальності розв’язку задачі, який застосовано – мінімальна гарантована тривалість доставки вантажів по усій сукупності заданих вантажопотоків. На першій стадії алгоритму виконано пошук найкоротших шляхів у графі, по яких може проходити кожен із заданих вантажопотоків. Перша стадія оптимізації є лінійною задачею цілочислового програмування, розмірність не є надто великою. Початковими даними для другої стадії є матриця вантажопотоків, яка отримана в результаті оптимізації на першій стадії. Зміст другої стадії алгоритму – це розв’язок рівняння балансу дискретних вантажопотоків. Рівняння балансу означає, що усі потоки, які входять у кожну вершину, включно із джерелами вантажопотоків даної вершини, мають середню інтенсивність, яка дорівнює інтенсивності вихідних вантажопотоків з кожної вихідної вершини, включно зі стоками. Завдяки дослідженим залежностям між окремими фазами процесу доставки на прикладі вантажного перевізника на транспортній мережі України, сформульованим обмеженням і крайовим умовам отримано можливість гарантованого точного розв’язання комплексної проблеми. При цьому знайдено найкоротші маршрути, визначено пункти перевантаження, а також часові параметри експлуатації і ступінь завантаження автомобілів. За результатами проведених досліджень отримано трикратне підвищення продуктивності використання парку автопоїздів із зниженням термінів гарантованої тривалості доставки на 30 %The article is devoted to the problem of effective use of cross-docking as a technology of cargo delivery with increased time requirements, which allows to resolve the contradictions of guaranteed delivery time ensuring and the efficiency of the existing fleet of trucks. The process of delivery organization is considered as the ordering on the transport network of many discrete freight flows in the form of their phases. If qualitative and / or quantitative changes do not occur from phase to phase with the flow, then the tact of such flow is constant. However, crossdocking flows change the size of the band of moving goods. Cargo can be moved as intended by any group size, which, however, is limited by the maximum and minimum values. A two-stage algorithm for solving the problem has been developed. The transport network is represented as a graph. The content of the route search problem is optimization, as it consists of multiple selections from the initial graph of arcs in the presence of restrictions on input and output flows. One needs to replace every each edge of the graph with an arc of the forward or reverse direction, or remove this edge. The criterion for the optimal solution of the problem, which is applied, is the minimum guaranteed duration of delivery of goods throughout the set of specified freight flows. At the first stage of the algorithm, the search for the shortest paths in the graph is performed, along which every given cargo flow can pass. The first stage of optimization is a linear problem of integer programming, the dimension of which is not too large. The initial data of the second stage is freight flows matrix, which is obtained as a result of optimization in the first stage. The content of the second stage of the algorithm is the solution of the equation of the balance of discrete goods flows. The balance equation means that all flows entering each peak including the sources of cargo flows of this peak have an average intensity equal to the intensity of the outgoing cargo flows from each source peak, including runoff. Due to the studied dependencies between the individual phases of the delivery process on the example of a cargo carrier on the transport network of Ukraine, the formulated restrictions and boundary conditions, the possibility of guaranteed accurate solution of a complex problem is obtained. At the same time, the shortest routes were found, reloading points were identified as well as time parameters of operation and the degree of loading of cars. According to the results of the research, a threefold increase in the productivity of the fleet of road trains with a reduction in the guaranteed delivery time by 30 %