Optimización para la formación de grupos mediante algoritmos evolutivos

Abstract

[ES] En esta memoria se pretende explicar el diseño y uso de un algoritmo genético para la generación automática de grupos en el entorno de viajes mediante vehículos. Se propone un modelo para la asignación de viajes a una determinada formación de grupos de viajeros. El modelo está implementado mediante un algoritmo genético desarrollado en Java, ayudandonos de la librería de algoritmos genéticos JGAP. Los parámetros del modelo son, por parte de los viajeros, el lugar de salida del viajero, la lista de ciudades que no quiere visitar y su presupuesto disponible. Por otro lado, los parámetros del viaje son, el mínimo de asientos disponibles en el vehículo, el máximo asientos disponibles en el vehículo, el lugar de salida del vehículo que va a realizar el viaje, el destino del viaje y el coste de dicho viaje. Los resultados muestran soluciones válidas que cumplen con todas las restricciones del problema en todos los escenarios propuestos, mejorando considerablemente el tiempo de ejecución de otras aproximaciones basadas en programación lineal.

[EN] In this specification we go to explain the design and use of a genetic algorithm for an automatic generation of groups in the vehicle travel environment.This paper proposes a model for group formation of trips to a certain formation of groups of travelers. The model is implemented using a genetic algorithm developed in Java, helping us from the library of genetic algorithms JGAP. The parameters of the model are, by the travelers, the place of departure of the traveler, the list of cities that do not want to visit and its budget available. On the other hand, the parameters of the trip are the minimum of seats available in the vehicle, the maximum seats available in the vehicle, the place of departure of the vehicle to be traveled, the destination of the trip and the cost of said trip. The results show valid solutions that satisfy all constraints of the problem in all the proposed scenarios. This algorithm considerably improves the execution time of other approaches based on linear programming.