Wyniki wyszukiwania - BazTech

1

A combination K-means clustering and 2-opt algorithm for solving the two echelon e-commerce logistic distribution

Zuhanda Muhammad Khahfi, Suwilo Saib, Sitompul Opim, Mardiningsih Mardiningsih

LogForum

|

2022

|

Vol. 18, no. 2

213--225

EN

Background: The rise of e-commerce in the community makes competition between logistics companies increasingly tight. Every e-commerce application offers the convenience and choices needed by the community. The Two-Echelon Vehicle Routing Problem (2E-VRP) model has been widely developed in recent years. 2E-VRP makes it possible for customers to combine shipments from several different stores due to satellites in their distribution stream. The aim of this paper is to optimize a two-echelon logistics distribution network for package delivery on e-commerce platforms, where vans operate in the first echelon and motorcycles operate in the second echelon. The problem is formulated as 2E-VRP, where total travel costs and fuel consumption are minimized. This optimization is based on determining the flow in each echelon and choosing the optimal routing solution for vans and motorcycles. Methods: This paper proposes a combination of the K-means Clustering Algorithm and the 2-opt Algorithm to solve the optimization problem. Many previous studies have used the K-means algorithm to help streamline the search for solutions. In the solution series, clustering is carried out between the satellite and the customer in the first echelon using the K-means algorithm. To determine the optimal k-cluster, we analyzed it using the silhouette, gap statistic, and elbow methods. Furthermore, the routing at each echelon is solved by the 2-opt heuristic method. At the end of the article, we present testing of several instances with the different number of clusters. The study results indicate an influence on the determination of the number of clusters in minimizing the objective function. Results: This paper looks at 100 customers, 10 satellites, and 1 depot. By working in two stages, the first stage is the resolution of satellite and customer problems, and the second stage is the resolution of problems between the satellite and the depots. We compare distance and cost solutions with a different number of k-clusters. From the test results, the number of k-clusters shows an effect of number and distance on the solution. Conclusions: In the 2E-VRP model, determining the location of the cluster between the satellite and the customer is very important in preparing the delivery schedule in logistics distribution within the city. The benefit is that the vehicle can divide the destination according to the location characteristics of the satellite and the customer, although setting the how many clusters do not guarantee obtaining the optimal distance. And the test results also show that the more satellites there are, the higher the shipping costs. For further research, we will try to complete the model with the metaheuristic genetic algorithm method and compare it with the 2-opt heuristic method.

2

A logistic optimization for the vehicle routing problem through a case study in the food industry

Akpinar Muhammet Enes

LogForum

|

2021

|

Vol. 17, no. 3

387--397

EN

Background: In this study, the food delivery problem faced by a food company is discussed. There are seven different regions where the company serves food and a certain number of customers in each region. The time of requesting food for each customer varies according to the shift situation. This type of problem is referred to as a vehicle routing problem with time windows in the literature and the main aim of the study is to minimize the total travel distance of the vehicles. The second aim is to determine which vehicle will follow which route in the region by using the least amount of vehicle according to the desired mealtime. Methods: In this study, genetic algorithm methodology is used for the solution of the problem. Metaheuristic algorithms are used for problems that contain multiple combinations and cannot be solved in a reasonable time. Thus in this study, a solution to this problem in a reasonable time is obtained by using the genetic algorithm method. The advantage of this method is to find the most appropriate solution by trying possible solutions with a certain number of populations. Results: Different population sizes are considered in the study. 1000 iterations are made for each population. According to the genetic algorithm results, the best result is obtained in the lowest population size. The total distance has been shortened by about 14% with this method. Besides, the number of vehicles in each region and which vehicle will serve to whom has also been determined. This study, which is a real-life application, has provided serious profitability to the food company even from this region alone. Besides, there have been improvements at different rates in each of the seven regions. Customers' ability to receive service at any time has maximized customer satisfaction and increased the ability to work in the long term. Conclusions: The method and results used in the study were positive for the food company. However, the metaheuristic algorithm used in this study does not guarantee an optimal result. Therefore, mathematical models or simulation models can be considered in terms of future studies. Besides, in addition to the time windows problem, the pickup problem can also be taken into account and different solution proposals can be developed.

3

Improving unloading time prediction for vehicle routing problem based on GPS data

Žunić Emir, Kuric Amar, Delalić Sead

Annals of Computer Science and Information Systems

|

2020

|

Vol. 22

45--49

EN

The problem of transport optimization is of great importance for the successful operation of distribution companies. To successfully find routes, it is necessary to provide accurate input data on orders, customer location, vehicle fleet, depots, and delivery restrictions. Most of the input data can be provided through the order creation process or the use of various online services. One of the most important inputs is an estimate of the unloading time of the goods for each customer. The number of customers that the vehicle serves during the day directly depends on the time of unloading. This estimate depends on the number of items, weight and volume of orders, but also on the specifics of customers, such as the proximity of parking or crowds at the unloading location. Customers repeat over time, and unloading time can be calculated from GPS data history. The paper describes the innovative application of machine learning techniques and delivery history obtained through a GPS vehicle tracking system for a more accurate estimate of unloading time. The application of techniques gave quality results and significantly improved the accuracy of unloading time data by 83.27% compared to previously used methods. The proposed method has been implemented for some of the largest distribution companies in Bosnia and Herzegovina.

4

Innovative modular approach based on vehicle routing problem and ant colony optimization for order splitting in real warehouses

Žunić Emir, Delalić Sead, Tucaković Zlatan, Hodžić Kerim, Beširević Admir

Annals of Computer Science and Information Systems

|

2019

|

Vol. 20

125--129

EN

A crucial part to any warehouse workflow is the process of order picking. Orders can significantly vary in the number of items, mass, volume and the total path needed to collect all the items. Some orders can be picked by just one worker, while others are required to be split up and shrunk down, so that they can be assigned to multiple workers. This paper describes the complete process of optimal order splitting. The process consists of evaluating if a given order requires to be split, determining the number of orders it needs to be split into, assigning items for every worker and optimizing the order picking routes. The complete order splitting process can be used both with and without the logistic data (mass and volume), but having logistic data improves the accuracy. Final step of the algorithm is reduction to Vehicle Routing Problem where the total number of vehicles is known beforehand. The process described in this paper is implemented in some of the largest warehouses in Bosnia and Herzegovina.

5

Multicriteria vehicle routing problem solved by artificial immune system

Mrówczyńska B.

Transport Problems

|

2015

|

T. 10, z. 3

141--152

EN

Vehicles route planning in large transportation companies, where drivers are workers, usually takes place on the basis of experience or intuition of the employees. Because of the cost and environmental protection, it is important to save fuel, thus planning routes in an optimal way. In this article an example of the problem is presented solving delivery vans route planning taking into account the distance and travel time within the constraints of vehicle capacities, restrictions on working time of drivers and having varying degrees of movement. An artificial immune system was used for the calculations.

PL

Planowanie tras samochodów dostawczych w dużych firmach transportowych, w których kierowcy są pracownikami najemnymi, najczęściej odbywa się na podstawie doświadczeń lub intuicji pracowników. Ze względu na koszty i na ochronę środowiska ważne jest oszczędzanie paliwa, a więc układanie tras w sposób optymalny. W artykule rozwiązano przykładowy problem planowania trasy samochodów dostawczych ze względu na długość drogi i czas przejazdu przy ograniczeniach ładowności pojazdów, ograniczeniach czasu pracy kierowców i przy uwzględnieniu zmiennego natężenia ruchu. W obliczeniach zastosowano sztuczny system immunologiczny.

6

Zastosowanie algorytmu przeszukiwania rozproszonego do problemu marszrutyzacji z ograniczeniem pojemności środków transportu

Głuszek A., Rudziński F.

Logistyka

|

2015

|

nr 4

3417--3425, CD2

PL

Niniejszy artykuł prezentuje wyniki zastosowania algorytmu przeszukiwania rozproszonego do problemu marszrutyzacji z ograniczeniem pojemności pojazdów. Przeszukiwanie rozproszone zaliczane jest do obszaru algorytmów ewolucyjnych i znajduje wiele zastosowań w optymalizacji problemów o charakterze zarówno ciągłym jak i dyskretnym. Problem marszrutyzacji stanowi zagadnienie należące do zadań optymalizacji kombinatorycznej, a w szerszym zakresie – do badań operacyjnych. Ze względu na jego duże znaczenie praktyczne, zwłaszcza w obszarze zarządzania transportem, wciąż trwają intensywne badania w zakresie poszukiwania nowych i udoskonalania już istniejących algorytmów, umożliwiających jego efektywne rozwiązywanie. W rozdziale pierwszym niniejszego artykułu przedstawiono formalnie zadanie marszrutyzacji z ograniczeniem pojemności pojazdów. Rozdział drugi prezentuje zasadę działania algorytmu przeszukiwania rozproszonego. Rozdział trzeci przedstawia zestaw problemów testowych wykorzystywanych w niniejszej pracy oraz wyniki przeprowadzonych eksperymentów numerycznych. Rezultaty działania algorytmu przeszukiwania rozproszonego porównano z wynikami uzyskanymi przy zastosowaniu dwóch innych metod ewolucyjnych (algorytm genetyczny i strategia ewolucyjna) oraz zaawansowanego dwufazowego algorytmu heurystycznego, wykorzystującego zmodyfikowany algorytm wspinaczkowy.

EN

The paper presents application of scatter search to capacitated vehicle routing problem. Scatter search belongs to the area of evolutionary computations and it has numerous applications in continuous and discrete optimization problems. Vehicle routing problem is an important combinatorial optimization task that is related to operations research. It has great practical relevance, especially in the fields of transport management, distribution and logistics. Development of the algorithms for efficient solving of the vehicle routing problem is still very intensive. In the first section of the paper capacitated vehicle routing problem is formally presented. Next section describes in outline the scatter search algorithm. The third section presents a set of test examples, used in this study and the results of performed experiments. Proposed approach is also compared with two alternative evolutionary algorithms (genetic algorithm and evolutionary strategy) and advanced two-phase heuristic method, based on modified hill climbing algorithm.

7

Algorytm Clarke’a-Wrighta jako źródło początkowego rozwiązania dla algorytmu symulowanego wyżarzania w problemie marszrutyzacji

Oszelska-Mierzejewska J., Misztalska E.

Logistyka

|

2015

|

nr 4

5080--5088, CD 2

PL

W prezentowanym artykule skupiono się na przedstawieniu rozwiązania problemu marszrutyzacji. Zaproponowano tutaj zastosowanie zmodyfikowanego algorytmu Clarke'a-Wrighta jako mechanizmu generowania pierwszego rozwiązania dla algorytmu symulowanego wyżarzania, w celu znalezienia optymalnego rozwiązania dla zadanego problemu. Opisano również przeprowadzone badania symulacyjne ukazujące skuteczność proponowanego rozwiązania wykorzystując zestawy danych o różnym charakterze, a także przedyskutowano otrzymane wyniki z badania doświadczalnego z wykorzystaniem rzeczywistych danych z firmy dystrybucyjnej. Wykazano, że zaproponowane podejście do generowania pierwszego rozwiązania dla metaheurystyki powala uzyskać lepsze wyniki w akceptowalnym czasie, co zostało potwierdzone w badaniu doświadczalnym.

EN

This paper presents a solution to the vehicle routing problem. A modified Clarke-Wright algorithm has been proposed as a mechanism for generating an initial solution for the simulated annealing algorithm, which is then used to find the optimal solution. The effectiveness of the proposed method is examined by means of a simulation study using data sets of various types. The results of an experimental study using real data from a selected distribution company are also discussed. The comparison of the results indicates that the proposed approach to generating the first (initial) solution for metaheuristics is able to produce better results within an acceptable time.

8

Scale free distribution of nodes in Euclidean graphs

Dominik A., Walczak Z., Wojciechowski J., Wojciechowski J.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2006

|

z. 156

107-115

EN

In the paper we propose a new model of spatial distribution of nodes in graphs which can be represented in the Euclidean space. Such graphs appear in many areas of computer science, for instance wireless networks design, Traveling Salesman and Vehicle Routing Problems. We show analogies between scale-free and Euclidean graphs. Although the distribution of node's degrees in Euclidean graphs is not scale-free, the spatial distribution of node's follows the power law. We analyze distribution of population density in different continents, propose a model to generate such distributions and provide numerical experiments concerning its quality. Finally, the impact of our model on different NP-complete problems in Euclidean graphs is analyzed.

9

Analysis of distance between vehicle routing problem solutions generated by memetic algorithms

Kubiak M.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2006

|

z. 156

223-236

EN

This paper focuses on analysis of distance between solutions of the capacitated vehicle routing problem generated by memetic algorithms with different crossover operators. The goal of the analysis is to see what are relative positions of such solutions in search spaces and if different algorithms explore different parts of these spaces. In the described memetic algorithms five different crossover operators are used. The conducted computational experiment shows that solutions generated by the algorithms have very similar, very good quality. From the distance analysis it appears that there are two types of instances of the considered problem: 10 instances have very similar solutions, concentrated in small regions of spaces ('big valleys'), while other 12 have good solutions which reside in different parts of search spaces, implying wide and flat regions of good solutions.