Published September 30, 2011 | Version v1
Publication Open

UMA NOVA ABORDAGEM HEURÍSTICA PARA A RESOLUÇÃO DO PROBLEMA DO ROTEAMENTO DE VEÍCULOS CAPACITADOS

Creators

  • 1. Universidade Federal do Paraná

Description

Este trabalho apresenta uma nova abordagem heurística para a resolução do Problema do Roteamento de Veículos Capacitados (PRVC). O método emprega uma estratégia em dois estágios, que consiste primeiramente em agrupar os clientes de acordo com a demanda e, posteriormente, construir as rotas para os grupos formados. Para o primeiro estágio, desenvolveu-se uma heurística de ajuste para o algoritmo clássico de agrupamento proposto por Teitz e Bart (1968). No segundo estágio, as rotas iniciais são geradas pela heurística de inserção mais econômica e refinadas pelas heurísticas de melhoria 2-opt e 3-opt. A abordagem proposta foi testada para instâncias clássicas da literatura, e comparadas com o desempenho de procedimentos exatos e heurísticos existentes, produzindo resultados interessantes, tanto em termos de eficácia quanto de eficiência.

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

Translated Description (Arabic)

تقدم هذه الورقة نهجًا إرشاديًا جديدًا لحل مشكلة توجيه المركبات المدربة (PRVC). تستخدم الطريقة استراتيجية من مرحلتين، والتي تتكون أولاً من تجميع العملاء حسب الطلب ثم بناء الطرق للمجموعات المشكلة. بالنسبة للمرحلة الأولى، تم تطوير استدلال ضبط لخوارزمية التجميع الكلاسيكية التي اقترحها تيتز وبارت (1968). في المرحلة الثانية، يتم إنشاء المسارات الأولية من خلال الاستدلال الأكثر اقتصادا للإدخال ويتم تحسينها من خلال الاستدلال التحسيني ثنائي وثلاثي الخيارات. تم اختبار النهج المقترح بحثًا عن الأمثلة الكلاسيكية للأدبيات، ومقارنته بأداء الإجراءات الدقيقة والإرشادية الحالية، مما أسفر عن نتائج مثيرة للاهتمام، من حيث الفعالية والكفاءة.

Translated Description (English)

This paper presents a new heuristic approach to solving the Trained Vehicle Routing Problem (PRVC). The method employs a two-stage strategy, which consists first of grouping customers according to demand and then building the routes for the formed groups. For the first stage, an adjustment heuristic was developed for the classical clustering algorithm proposed by Teitz and Bart (1968). In the second stage, the initial routes are generated by the most economical insertion heuristic and refined by the 2-opt and 3-opt improvement heuristics. The proposed approach was tested for classical instances of the literature, and compared with the performance of existing exact and heuristic procedures, yielding interesting results, both in terms of effectiveness and efficiency.

Translated Description (French)

Cet article présente une nouvelle approche heuristique pour résoudre le problème de routage des véhicules entraînés (PRVC). La méthode utilise une stratégie en deux étapes, qui consiste d'abord à regrouper les clients en fonction de la demande, puis à construire les itinéraires pour les groupes formés. Pour la première étape, une heuristique d'ajustement a été développée pour l'algorithme de clustering classique proposé par Teitz et Bart (1968). Dans la deuxième étape, les routes initiales sont générées par l'heuristique d'insertion la plus économique et affinées par les heuristiques d'amélioration 2-opt et 3-opt. L'approche proposée a été testée pour des instances classiques de la littérature, et comparée à la performance des procédures exactes et heuristiques existantes, donnant des résultats intéressants, à la fois en termes d'efficacité et d'efficience.

Translated Description (Spanish)

Este documento presenta un nuevo enfoque heurístico para resolver el problema de enrutamiento de vehículos entrenados (PRVC). El método emplea una estrategia de dos etapas, que consiste primero en agrupar a los clientes según la demanda y luego construir las rutas para los grupos formados. Para la primera etapa, se desarrolló una heurística de ajuste para el algoritmo de agrupamiento clásico propuesto por Teitz y Bart (1968). En la segunda etapa, las rutas iniciales son generadas por la heurística de inserción más económica y refinadas por la heurística de mejora de 2-opt y 3-opt. El enfoque propuesto se probó para casos clásicos de la literatura y se comparó con el rendimiento de los procedimientos exactos y heurísticos existentes, lo que arrojó resultados interesantes, tanto en términos de efectividad como de eficiencia.

Files

708.pdf

Files (1.9 MB)

⚠️ 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:f3877591e71aa353b8c0fa77d4764c14
1.9 MB
Preview Download

Additional details

Additional titles

Translated title (Arabic)
نهج إرشادي جديد لحل مشكلة توجيه المركبات الممكّنة
Translated title (English)
A NEW HEURISTIC APPROACH TO SOLVING THE PROBLEM OF ROUTING EMPOWERED VEHICLES
Translated title (French)
UNE NOUVELLE APPROCHE HEURISTIQUE POUR RÉSOUDRE LE PROBLÈME DE L'ACHEMINEMENT DES VÉHICULES AUTONOMES
Translated title (Spanish)
UN NUEVO ENFOQUE HEURÍSTICO PARA RESOLVER EL PROBLEMA DEL ENRUTAMIENTO DE VEHÍCULOS HABILITADOS

Identifiers

Other
https://openalex.org/W2082967702
DOI
10.3895/s1808-04482011000300007

Is supplement to
https://openalex.org/W54078636 (Other)
https://openalex.org/W3148032049 (Other)
https://openalex.org/W3105167352 (Other)
https://openalex.org/W3084825885 (Other)
https://openalex.org/W2954470139 (Other)
https://openalex.org/W2935759653 (Other)
https://openalex.org/W2902782467 (Other)
https://openalex.org/W2748952813 (Other)
https://openalex.org/W2298861036 (Other)
https://openalex.org/W1501425562 (Other)

GreSIS Basics Section

Is Global South Knowledge
Yes
Country
Brazil