Published January 22, 2021
| Version v1
Publication
Open
A hybrid metaheuristic for solving asymmetric distance-constrained vehicle routing problem
Description
Abstract The Asymmetric Distance-Constrained Vehicle Routing Problem (ADVRP) is NP-hard as it is a natural extension of the NP-hard Vehicle Routing Problem. In ADVRP problem, each customer is visited exactly once by a vehicle; every tour starts and ends at a depot; and the traveled distance by each vehicle is not allowed to exceed a predetermined limit. We propose a hybrid metaheuristic algorithm combining the Randomized Variable Neighborhood Search (RVNS) and the Tabu Search (TS) to solve the problem. The combination of multiple neighborhoods and tabu mechanism is used for their capacity to escape local optima while exploring the solution space. Furthermore, the intensification and diversification phases are also included to deliver optimized and diversified solutions. Extensive numerical experiments and comparisons with all the state-of-the-art algorithms show that the proposed method is highly competitive in terms of solution quality and computation time, providing new best solutions for a number of instances.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
الملخص مشكلة توجيه المركبات المقيدة للمسافة غير المتماثلة (ADVRP) صعبة NP لأنها امتداد طبيعي لمشكلة توجيه المركبات الصعبة NP. في مشكلة ADVRP، تتم زيارة كل عميل مرة واحدة بالضبط بواسطة مركبة ؛ تبدأ كل جولة وتنتهي في مستودع ؛ ولا يُسمح للمسافة التي تقطعها كل مركبة بتجاوز حد محدد مسبقًا. نقترح خوارزمية ميتاهوريستية هجينة تجمع بين البحث العشوائي عن الجوار المتغير (RVNS) والبحث عن التبو (TS) لحل المشكلة. يتم استخدام مزيج من الأحياء المتعددة وآلية التابو لقدرتها على الهروب من الأمثلية المحلية أثناء استكشاف مساحة الحل. علاوة على ذلك، يتم تضمين مراحل التكثيف والتنويع أيضًا لتقديم حلول محسنة ومتنوعة. تُظهر التجارب العددية الواسعة والمقارنات مع جميع الخوارزميات الحديثة أن الطريقة المقترحة تنافسية للغاية من حيث جودة الحل ووقت الحساب، مما يوفر أفضل الحلول الجديدة لعدد من الحالات.Translated Description (French)
Résumé Le problème d'acheminement des véhicules soumis à des contraintes de distance asymétriques (ADVRP) est NP-difficile car il est une extension naturelle du problème d'acheminement des véhicules NP-difficile. Dans le problème ADVRP, chaque client est visité exactement une fois par un véhicule ; chaque visite commence et se termine dans un dépôt ; et la distance parcourue par chaque véhicule ne doit pas dépasser une limite prédéterminée. Nous proposons un algorithme métaheuristique hybride combinant la Randomized Variable Neighborhood Search (RVNS) et la Tabu Search (TS) pour résoudre le problème. La combinaison de plusieurs quartiers et du mécanisme tabu est utilisée pour leur capacité à échapper aux optima locaux tout en explorant l'espace de solution. En outre, les phases d'intensification et de diversification sont également incluses pour fournir des solutions optimisées et diversifiées. Des expériences numériques approfondies et des comparaisons avec tous les algorithmes de pointe montrent que la méthode proposée est très compétitive en termes de qualité de la solution et de temps de calcul, fournissant de nouvelles meilleures solutions pour un certain nombre d'instances.Translated Description (Spanish)
Resumen El problema de enrutamiento de vehículos con distancia restringida asimétrica (ADVRP) es NP-duro, ya que es una extensión natural del problema de enrutamiento de vehículos NP-duro. En el problema ADVRP, cada cliente es visitado exactamente una vez por un vehículo; cada recorrido comienza y termina en un depósito; y la distancia recorrida por cada vehículo no puede exceder un límite predeterminado. Proponemos un algoritmo metaheurístico híbrido que combina el Randomized Variable Neighborhood Search (RVNS) y el Tabu Search (TS) para resolver el problema. La combinación de múltiples vecindarios y el mecanismo tabú se utiliza por su capacidad para escapar de los óptimos locales mientras exploran el espacio de la solución. Además, también se incluyen las fases de intensificación y diversificación para ofrecer soluciones optimizadas y diversificadas. Amplios experimentos numéricos y comparaciones con todos los algoritmos de última generación muestran que el método propuesto es altamente competitivo en términos de calidad de la solución y tiempo de cálculo, proporcionando nuevas y mejores soluciones para una serie de casos.Files
s40649-020-00084-7.pdf
Files
(1.7 MB)
| Name | Size | Download all |
|---|---|---|
|
md5:af69d7de280a57b2ac51b0f79a022e71
|
1.7 MB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- ما وراء هيوريستيك هجين لحل مشكلة توجيه المركبات غير المتماثلة ذات المسافة الضيقة
- Translated title (French)
- Une métaheuristique hybride pour résoudre les problèmes de routage des véhicules soumis à des contraintes de distance asymétriques
- Translated title (Spanish)
- Una metaheurística híbrida para resolver el problema de enrutamiento asimétrico de vehículos con distancia restringida
Identifiers
- Other
- https://openalex.org/W3118614813
- DOI
- 10.1186/s40649-020-00084-7
References
- https://openalex.org/W1601649239
- https://openalex.org/W1964196426
- https://openalex.org/W2018691209
- https://openalex.org/W2029681015
- https://openalex.org/W2059715080
- https://openalex.org/W2068403188
- https://openalex.org/W2091669670
- https://openalex.org/W2104670598
- https://openalex.org/W2110673691
- https://openalex.org/W2111563176
- https://openalex.org/W2146870367
- https://openalex.org/W2345852648
- https://openalex.org/W2997776631
- https://openalex.org/W4246707514
- https://openalex.org/W4253500057