An efficient genetic algorithm for solving open multiple travelling salesman problem with load balancing constraint
- 1. Vellore Institute of Technology University
Description
The multiple travelling salesman problem (MTSP) is one of the widely studied combinatorial optimization problems with various theoretical and practical applications. However, most of the studies intended to deal with classical MTSP, very limited attention has been given to an open multiple travelling salesman problem and its variants. In this paper, an open multiple travelling salesman problem with load balancing constraint (OMTSPLB) is addressed. The OMTSPLB differs from the conventional MTSP, in which all the salesmen start from the central depot and need not come back to it after visiting the given number of cities by accomplishing the load balance constraint, which helps in fairly distributing the task among all salesmen. The problem aims to minimize the overall traversal distance/cost for operating open tours subject to the load balancing constraint. A zero-one integer linear programming (0-1 ILP) model and an efficient metaheuristic genetic algorithm (GA), is established for the OMTSPLB. Since no existing study on OMTSPLB, the proposed GA is tested on the relaxed version of the present model, comparative results are reported. The comparative results show that the proposed GA is competent over the existing algorithms. Furthermore, extensive experiments are carried out on OMTSPLB and the results show that proposed GA can find the global solution effectively.
Translated Descriptions
Translated Description (Arabic)
تعد مشكلة مندوب المبيعات المتنقل المتعدد (MTSP) واحدة من مشاكل التحسين التوافقي المدروسة على نطاق واسع مع العديد من التطبيقات النظرية والعملية. ومع ذلك، فإن معظم الدراسات التي تهدف إلى التعامل مع الخطة الاستراتيجية المتوسطة الأجل الكلاسيكية، تم إيلاء اهتمام محدود للغاية لمشكلة بائع متنقل متعددة مفتوحة ومتغيراتها. في هذه الورقة، يتم تناول مشكلة بائع متنقل متعددة مفتوحة مع قيود موازنة الحمل (OMTSPLB). يختلف OMTSPLB عن الخطة الاستراتيجية المتوسطة الأجل التقليدية، حيث يبدأ جميع البائعين من المستودع المركزي ولا يحتاجون إلى العودة إليه بعد زيارة العدد المحدد من المدن من خلال تحقيق قيود توازن الحمل، مما يساعد في توزيع المهمة بشكل عادل بين جميع البائعين. تهدف المشكلة إلى تقليل المسافة/التكلفة الإجمالية للعبور لتشغيل الجولات المفتوحة الخاضعة لقيود موازنة الحمل. تم إنشاء نموذج البرمجة الخطية لعدد صحيح صفر (0-1 ILP) وخوارزمية وراثية ميتاهورية فعالة (GA) لـ OMTSPLB. نظرًا لعدم وجود دراسة حالية حول OMTSPLB، يتم اختبار الجمعية العامة المقترحة على النسخة المريحة من النموذج الحالي، ويتم الإبلاغ عن النتائج المقارنة. تُظهر النتائج المقارنة أن الجمعية العامة المقترحة مختصة بالخوارزميات الحالية. علاوة على ذلك، يتم إجراء تجارب مكثفة على OMTSPLB وتظهر النتائج أن الجمعية العامة المقترحة يمكن أن تجد الحل العالمي بشكل فعال.Translated Description (French)
Le problème des vendeurs itinérants multiples (MTSP) est l'un des problèmes d'optimisation combinatoire largement étudiés avec diverses applications théoriques et pratiques. Cependant, la plupart des études destinées à traiter du MTSP classique, une attention très limitée a été accordée à un problème ouvert de vendeurs itinérants multiples et à ses variantes. Dans cet article, un problème de vendeur itinérant multiple ouvert avec contrainte d'équilibrage de charge (OMTSPLB) est abordé. L'OMTSPLB diffère du MTSP classique, dans lequel tous les vendeurs partent du dépôt central et n'ont pas besoin d'y revenir après avoir visité le nombre donné de villes en accomplissant la contrainte d'équilibre de charge, ce qui aide à répartir équitablement la tâche entre tous les vendeurs. Le problème vise à minimiser la distance/le coût de parcours global pour l'exploitation de circuits ouverts soumis à la contrainte d'équilibrage de charge. Un modèle de programmation linéaire à zéro-un entier (0-1 ILP) et un algorithme génétique métaheuristique efficace (GA) sont établis pour l'OMTSPLB. Comme aucune étude existante sur l'OMTSPLB, l'AG proposée est testée sur la version assouplie du présent modèle, des résultats comparatifs sont rapportés. Les résultats comparatifs montrent que l'AG proposé est compétent sur les algorithmes existants. En outre, des expériences approfondies sont menées sur OMTSPLB et les résultats montrent que l'AG proposée peut trouver la solution globale efficacement.Translated Description (Spanish)
El problema del viajante múltiple (MTSP) es uno de los problemas de optimización combinatoria ampliamente estudiados con diversas aplicaciones teóricas y prácticas. Sin embargo, la mayoría de los estudios destinados a tratar el plan estratégico de mediano plazo clásico, se ha prestado muy poca atención a un problema abierto de múltiples vendedores ambulantes y sus variantes. En este documento, se aborda un problema abierto de múltiples vendedores ambulantes con restricción de equilibrio de carga (OMTSPLB). El OMTSPLB difiere del MTSP convencional, en el que todos los vendedores parten del depósito central y no necesitan volver a él después de visitar el número dado de ciudades cumpliendo la restricción de equilibrio de carga, lo que ayuda a distribuir la tarea de manera justa entre todos los vendedores. El problema tiene como objetivo minimizar la distancia/costo transversal general para operar recorridos abiertos sujetos a la restricción de equilibrio de carga. Para el OMTSPLB se establece un modelo de programación lineal de cero-uno entero (0-1 ILP) y un algoritmo genético metaheurístico (GA) eficiente. Dado que no existe ningún estudio sobre OMTSPLB, la AG propuesta se prueba en la versión relajada del presente modelo, se informan los resultados comparativos. Los resultados comparativos muestran que el AG propuesto es competente sobre los algoritmos existentes. Además, se llevan a cabo extensos experimentos en OMTSPLB y los resultados muestran que la AG propuesta puede encontrar la solución global de manera efectiva.Additional details
Additional titles
- Translated title (Arabic)
- خوارزمية وراثية فعالة لحل مشكلة البائع المتنقل المتعددة المفتوحة مع قيود موازنة الحمل
- Translated title (French)
- Un algorithme génétique efficace pour résoudre le problème des vendeurs itinérants multiples ouverts avec une contrainte d'équilibrage de charge
- Translated title (Spanish)
- Un algoritmo genético eficiente para resolver el problema de múltiples vendedores ambulantes abiertos con la restricción de equilibrio de carga
Identifiers
- Other
- https://openalex.org/W3191258758
- DOI
- 10.5267/j.dsl.2021.5.003
References
- https://openalex.org/W3191258758