Published May 2, 2022 | Version v1
Publication Open

CLUSTERING ALGORITHM FOR A VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

Creators

  • 1. Ho Chi Minh City University of Technology
  • 2. University of Debrecen
  • 3. Vietnam National University Ho Chi Minh City
  • 4. Lappeenranta-Lahti University of Technology
  • 5. University of Johannesburg

Description

The demand for daily food purchases has increased dramatically, especially during the Covid-19 pandemic. This requires suppliers to face a huge and complex problem of delivering products that meet the needs of their customers on a daily basis. It also puts great pressure on managers on how to make day-to-day decisions quickly and efficiently to both satisfy customer requirements and satisfy capacity constraints. This study proposes a combination of the cluster-first –route-second method and k-means clustering algorithm to deal with a large Vehicle Routing Problem with Time Windows (VRPTW) in the logistics and transportation field. The purpose of this research is to assist decision-makers to make quick and efficient decisions, based on optimal costs, the number of vehicles, delivery time, and truck capacity efficiency. A distribution system of perishable goods in Vietnam is used as a case study to illustrate the effectiveness of our mathematical model. In particular, perishable goods include fresh products of fish, chicken, beef, and pork. These products are packed in different sizes and transferred by vehicles with 1000 kg capacity. Besides, they are delivered from a depot to the main 39 customers of the company with arrival times following customers' time window. All of the data are collected from a logistics company in Ho Chi Minh city (Vietnam). The result shows that the application of the clustering algorithm reduces the time for finding the optimal solutions. Especially, it only takes an average of 0.36 s to provide an optimal solution to a large Vehicle Routing Problem (VRP) with 39 nodes. In addition, the number of trucks, their operating costs, and their utilization are also shown fully. The logistics company needs 11 trucks to deliver their products to 39 customers. The utilization of each truck is more than 70%. This operation takes the total costs of 6586215.32 VND (Vietnamese Dong), of which, the transportation cost is 1086215.32 VND. This research mainly contributes an effective method for enterprises to quickly find the optimal solution to the problem of product supply.

⚠️ This is an automatic machine translation with an accuracy of 90-95%

Translated Description (Arabic)

زاد الطلب على المشتريات الغذائية اليومية بشكل كبير، خاصة خلال جائحة كوفيد-19. وهذا يتطلب من الموردين مواجهة مشكلة ضخمة ومعقدة تتمثل في تسليم المنتجات التي تلبي احتياجات عملائهم بشكل يومي. كما أنه يضع ضغطًا كبيرًا على المديرين حول كيفية اتخاذ القرارات اليومية بسرعة وكفاءة لتلبية متطلبات العملاء وتلبية قيود القدرات. تقترح هذه الدراسة مزيجًا من طريقة المجموعة الأولى - المسار الثاني وخوارزمية التجميع k - means للتعامل مع مشكلة كبيرة في توجيه المركبات مع نوافذ الوقت (VRPTW) في مجال اللوجستيات والنقل. الغرض من هذا البحث هو مساعدة صانعي القرار على اتخاذ قرارات سريعة وفعالة، بناءً على التكاليف المثلى وعدد المركبات ووقت التسليم وكفاءة سعة الشاحنة. يستخدم نظام توزيع السلع القابلة للتلف في فيتنام كدراسة حالة لتوضيح فعالية نموذجنا الرياضي. على وجه الخصوص، تشمل السلع القابلة للتلف المنتجات الطازجة من الأسماك والدجاج ولحم البقر ولحم الخنزير. يتم تعبئة هذه المنتجات بأحجام مختلفة ونقلها بواسطة مركبات بسعة 1000 كجم. إلى جانب ذلك، يتم تسليمها من مستودع إلى 39 عميلًا رئيسيًا للشركة مع أوقات وصول تتبع الإطار الزمني للعملاء. يتم جمع جميع البيانات من شركة لوجستية في مدينة هوشي منه (فيتنام). تظهر النتيجة أن تطبيق خوارزمية التجميع يقلل من الوقت اللازم لإيجاد الحلول المثلى. على وجه الخصوص، لا يستغرق الأمر سوى 0.36 ثانية في المتوسط لتوفير الحل الأمثل لمشكلة توجيه المركبات الكبيرة (VRP) مع 39 عقدة. بالإضافة إلى ذلك، يتم أيضًا عرض عدد الشاحنات وتكاليف تشغيلها واستخدامها بشكل كامل. تحتاج شركة الخدمات اللوجستية إلى 11 شاحنة لتوصيل منتجاتها إلى 39 عميلاً. استخدام كل شاحنة أكثر من 70 ٪. تبلغ التكاليف الإجمالية لهذه العملية 6586215.32 دونغ فيتنامي (VND)، منها تكلفة النقل 1086215.32 دونغ فيتنامي (VND). يساهم هذا البحث بشكل أساسي في طريقة فعالة للمؤسسات لإيجاد الحل الأمثل لمشكلة توريد المنتجات بسرعة.

Translated Description (French)

La demande d'achats alimentaires quotidiens a considérablement augmenté, en particulier pendant la pandémie de Covid-19. Cela oblige les fournisseurs à faire face à un problème énorme et complexe de livraison de produits qui répondent aux besoins de leurs clients au quotidien. Cela met également une grande pression sur les gestionnaires sur la façon de prendre des décisions quotidiennes rapidement et efficacement pour satisfaire à la fois les exigences des clients et les contraintes de capacité. Cette étude propose une combinaison de la méthode cluster-first -route-second et de l'algorithme de clustering k-means pour traiter un grand problème de routage de véhicule avec des fenêtres temporelles (VRPTW) dans le domaine de la logistique et du transport. Le but de cette recherche est d'aider les décideurs à prendre des décisions rapides et efficaces, en fonction des coûts optimaux, du nombre de véhicules, du délai de livraison et de l'efficacité de la capacité des camions. Un système de distribution de marchandises périssables au Vietnam est utilisé comme étude de cas pour illustrer l'efficacité de notre modèle mathématique. En particulier, les produits périssables comprennent les produits frais de poisson, de poulet, de bœuf et de porc. Ces produits sont emballés dans différentes tailles et transférés par des véhicules d'une capacité de 1000 kg. En outre, ils sont livrés à partir d'un dépôt aux 39 principaux clients de l'entreprise avec des heures d'arrivée suivant la fenêtre de temps des clients. Toutes les données sont collectées auprès d'une entreprise de logistique à Ho Chi Minh-Ville (Vietnam). Le résultat montre que l'application de l'algorithme de clustering réduit le temps de recherche des solutions optimales. En particulier, il ne faut qu'une moyenne de 0,36 s pour fournir une solution optimale à un gros problème de routage de véhicule (VRP) avec 39 nœuds. En outre, le nombre de camions, leurs coûts d'exploitation et leur utilisation sont également entièrement indiqués. La société de logistique a besoin de 11 camions pour livrer ses produits à 39 clients. L'utilisation de chaque camion est supérieure à 70%. Cette opération prend le coût total de 6586215.32 VND (Dong vietnamien), dont le coût de transport est de 1086215.32 VND. Cette recherche contribue principalement à une méthode efficace permettant aux entreprises de trouver rapidement la solution optimale au problème de l'approvisionnement en produits.

Translated Description (Spanish)

La demanda de compras diarias de alimentos ha aumentado drásticamente, especialmente durante la pandemia de Covid-19. Esto requiere que los proveedores se enfrenten a un problema enorme y complejo de entregar productos que satisfagan las necesidades de sus clientes a diario. También ejerce una gran presión sobre los gerentes sobre cómo tomar decisiones cotidianas de manera rápida y eficiente para satisfacer los requisitos del cliente y las limitaciones de capacidad. Este estudio propone una combinación del método cluster-first -route-second y el algoritmo de agrupamiento k-means para hacer frente a un gran problema de enrutamiento de vehículos con ventanas de tiempo (VRPTW) en el campo de la logística y el transporte. El propósito de esta investigación es ayudar a los responsables de la toma de decisiones a tomar decisiones rápidas y eficientes, basadas en los costos óptimos, el número de vehículos, el tiempo de entrega y la eficiencia de la capacidad de los camiones. Se utiliza un sistema de distribución de productos perecederos en Vietnam como estudio de caso para ilustrar la efectividad de nuestro modelo matemático. En particular, los productos perecederos incluyen productos frescos de pescado, pollo, carne de res y cerdo. Estos productos se envasan en diferentes tamaños y se transportan en vehículos con una capacidad de 1000 kg. Además, se entregan desde un depósito a los 39 principales clientes de la empresa con tiempos de llegada siguiendo la ventana de tiempo de los clientes. Todos los datos se recogen de una empresa de logística en la ciudad de Ho Chi Minh (Vietnam). El resultado muestra que la aplicación del algoritmo de agrupamiento reduce el tiempo para encontrar las soluciones óptimas. Especialmente, solo se necesita una media de 0,36 s para proporcionar una solución óptima a un gran problema de enrutamiento de vehículos (VRP) con 39 nodos. Además, también se muestra en su totalidad el número de camiones, sus costes operativos y su utilización. La empresa de logística necesita 11 camiones para entregar sus productos a 39 clientes. La utilización de cada camión es superior al 70%. Esta operación tiene los costes totales de 6586215.32 VND (Dong vietnamita), de los cuales, el coste de transporte es de 1086215.32 VND. Esta investigación contribuye principalmente a un método eficaz para que las empresas encuentren rápidamente la solución óptima al problema del suministro de productos.

Files

11147.pdf

Files (418.2 kB)

⚠️ Please wait a few minutes before your translated files are ready ⚠️ Note: Some files might be protected thus translations might not work.
Name Size Download all
md5:586fbb735da32db4da7343d269264b06
418.2 kB
Preview Download

Additional details

Additional titles

Translated title (Arabic)
خوارزمية التجميع لمشكلة توجيه السيارة مع الوقت ويندوز
Translated title (French)
ALGORITHME DE CLUSTERING POUR UN PROBLÈME D'ACHEMINEMENT DE VÉHICULE AVEC DES FENÊTRES TEMPORELLES
Translated title (Spanish)
ALGORITMO DE AGRUPAMIENTO PARA UN PROBLEMA DE ENRUTAMIENTO DE VEHÍCULOS CON TIEMPO WINDOWS

Identifiers

Other
https://openalex.org/W4225413397
DOI
10.3846/transport.2022.16850

Is supplement to
https://openalex.org/W630632068 (Other)
https://openalex.org/W602275442 (Other)
https://openalex.org/W587064707 (Other)
https://openalex.org/W561646759 (Other)
https://openalex.org/W4205159025 (Other)
https://openalex.org/W3122052772 (Other)
https://openalex.org/W2214078930 (Other)
https://openalex.org/W2151768624 (Other)
https://openalex.org/W1983537108 (Other)
https://openalex.org/W1974098980 (Other)

GreSIS Basics Section

Is Global South Knowledge
Yes
Country
Vietnam

References

  • https://openalex.org/W1997127736
  • https://openalex.org/W2023470442
  • https://openalex.org/W2040140158
  • https://openalex.org/W2040390778
  • https://openalex.org/W2142458924
  • https://openalex.org/W2558438166
  • https://openalex.org/W2588307798
  • https://openalex.org/W2593161461
  • https://openalex.org/W2735355336
  • https://openalex.org/W2898358851
  • https://openalex.org/W2913960250
  • https://openalex.org/W2916746825
  • https://openalex.org/W2924220803
  • https://openalex.org/W2944803716
  • https://openalex.org/W2974466578
  • https://openalex.org/W3010792765
  • https://openalex.org/W3011563267
  • https://openalex.org/W3016743293
  • https://openalex.org/W3020901135
  • https://openalex.org/W3024456852
  • https://openalex.org/W3119949694
  • https://openalex.org/W3165821132
  • https://openalex.org/W3195015486
  • https://openalex.org/W4238432342
  • https://openalex.org/W4240581593
  • https://openalex.org/W4252801674