Problema de entrega de mercancías con ventana de tiempo
Desde que Danting y Rasmer [2] propusieron por primera vez el problema de rutas de vehículos (VRP) en 1959, este problema ha sido el foco de muchos investigadores. Los problemas de rutas de vehículos con ventana de tiempo (VRPTW) es una extensión del problema de rutas de vehículos generales. Su descripción simple es la siguiente: varios vehículos utilizados para el servicio parten del sitio y están ubicados en diferentes ubicaciones geográficas y tienen todos los clientes con carga diferente. Se atienden necesidades y diferentes períodos de tiempo de servicio, y luego se regresa al sitio donde se atiende a cada cliente solo una vez. El objetivo es minimizar la suma del tiempo de viaje del vehículo y el tiempo de espera al brindar servicios a los clientes dentro de la ventana de tiempo.
Dependiendo de si las restricciones de tiempo son estrictas o no, VRPTW se divide en dos categorías: ventana de tiempo suave VRP y ventana de tiempo difícil VRP. Ventana de tiempo flexible VRP requiere la llegada y el acceso dentro de la ventana de tiempo tanto como sea posible; de lo contrario, se impondrá una cierta penalización, es decir, cuando el vehículo llega antes de la hora de llegada más temprana a la ubicación solicitada, el costo se pierde cuando debe esperar en el punto de tarea o el vehículo deben estar a la hora mínima de llegada requerida. La penalización impuesta al llegar después de la hora de llegada tardía VRP requiere que el acceso debe llegar dentro de la ventana de tiempo; de lo contrario, se denegará el servicio; Este artículo analiza el problema de las rutas de vehículos con ventana de tiempo difícil.
2 Modelo matemático y su prueba
2.1. Establecimiento del modelo matemático
Basado en las necesidades de problemas específicos, este artículo parte de los siguientes supuestos básicos:
(1) Solo hay un sitio
(2) Se conocen las coordenadas de ubicación del sitio y el punto del cliente
(3) La demanda; se conoce el punto del cliente;
(4) El vehículo no debe exceder su masa de carga nominal durante el proceso de entrega
(5) Se deben satisfacer las necesidades de entrega de cada cliente;
(6) El vehículo es del mismo tipo y se conoce la capacidad
(7) Cada cliente debe y sólo puede ser visitado una vez
;(8) Se conoce la ventana de tiempo requerida por cada cliente.
Las variables de decisión y parámetros del modelo matemático se definen de la siguiente manera:
I representa el conjunto de sitios y clientes, es decir, 0 representa el sitio
; p>J representa el conjunto del cliente, es decir;
K representa el conjunto de vehículos, es decir;
C representa la masa de carga nominal del vehículo
representa la demanda del cliente i
es una variable de decisión, cuando el vehículo k va de i a j, se necesita 1 , de lo contrario, toma 0;
es una variable de decisión, cuando el vehículo k atiende al cliente j, toma 1; de lo contrario, toma 0
representa el momento más temprano en que el cliente i recibe; servicio Cuando i=0, representa la hora de salida del vehículo desde la estación;
representa la última hora para recibir el servicio del cliente, cuando i=n+1, representa la última hora para el vehículo. para regresar al sitio;
representa la hora de inicio del vehículo k que atiende al cliente i, y se requiere que esté dentro del intervalo tanto como sea posible;
Representa el tiempo requerido para completar la tarea en el punto i
Representa el tiempo de conducción del vehículo desde el cliente i al cliente j
Según la descripción del problema, establezca un problema de ruta del vehículo con una ventana de tiempo; El modelo matemático es el siguiente:
Min (2-1)
(2-2)
(2-3)
( 2-4)
(2-5)
(2-6)
(2-7)
( 2- 8)
(2-9)
(2-10)
La fórmula (2-1) es la función objetivo, que representa la clásica El valor mínimo del costo de entrega (distancia total de entrega). La fórmula (2-2) indica que un cliente solo puede ser atendido por un vehículo (2-3), (2-4) y (2-5) indican que el vehículo parte del sitio 0 y finalmente regresa al sitio después; sirviendo a todos los clientes estación n+1; la ecuación (2-6) significa que si un vehículo está en camino del cliente i al cliente j, no puede llegar al cliente j antes del tiempo. se cumple el límite de masa de carga de cada vehículo; la ecuación (2-8) (2-9) son restricciones de 0 y 1 (2-10) son restricciones de ventana de tiempo.
2.2 Prueba del modelo matemático
Este artículo utiliza el software Ling10.0 para probar el modelo matemático anterior. Los datos adoptan los datos de prueba de problemas similares en la Literatura 3, como se muestra en la Tabla 1 y la Tabla 2. El número de vehículos es 3, la masa de carga nominal de cada vehículo es 8 y la velocidad de operación es 50. En el cálculo, Se supone que el costo de transporte entre cada punto de cliente es igual a la distancia.
Tabla 1 Distancias entre puntos y sitios de clientes
0 1 2 3 4 5 6 7 8
0 0 40 60 75 90 200 100 160 80
1 40 0 65 40 100 50 75 110 100
2 60 65 0 75 100 100 75 75 75
3 75 40 75 0 100 50 90 90 150
4 90 100 100 100 0 100 75 75 100
5 200 50 100 50 100 0 70 90 75
6 100 75 75 90 75 70 0 70 100
7 160 110 75 90 75 90 70 0 100
8 80 100 75 150 100 75 100 100 0Tabla 2 Demanda y tiempo de atención requerido para cada punto de cliente
p>
Tarea i 1 2 3 4 5 6 7 8
2 1,5 4,5 3 1,5 4 2,5 3
[ ]
[ 1, 4 ] [4,6] [1,2] [4,7] [3,5.5] [2,5] [5,8] [1.5,4]
Si 1 2 1 3 2 2.5 3 0.8
Explicación: di es el volumen de carga de cada tarea, [ ] es el rango de tiempo en el que cada tarea comienza a ejecutarse y Si es el tiempo de servicio.
Los resultados de usar Lingo para calcular el modelo matemático anterior son:
Ruta uno: 0, 8, 5, 7, 0
Ruta dos: 0, 6 , 4, 0;
Ruta 3: 0, 3, 1, 2, 0;
El costo total de la función objetivo es 910, lo cual es consistente con el Los resultados proporcionados en la literatura [3] muestran la exactitud del modelo matemático en este artículo.
3. Método de resolución de problemas VRP basado en el método genético
3.1 Introducción al algoritmo genético [3]
El algoritmo genético fue desarrollado por el profesor John Holland de la Universidad. de Michigan en Estados Unidos en 20 Creado a finales de los años 1960. Se deriva de la teoría de la evolución de Darwin y de las teorías genéticas de Mendel y Morgan, y construye sistemas artificiales simulando el mecanismo de la evolución biológica. Los algoritmos genéticos se basan principalmente en la ley de "supervivencia del más apto" en la evolución biológica, es decir, los grupos más adecuados para el entorno natural tienden a producir grupos más grandes de descendencia. Tomando el grupo de este ciclo como punto de partida, después de la competencia, un grupo es eliminado y ya no puede ingresar al ciclo, mientras que el otro grupo se convierte en población. La supervivencia del más apto juega un papel muy importante en este proceso. Debido al duro clima natural y a la invasión de enemigos naturales, la tasa de supervivencia de muchos animales en la naturaleza es muy baja. Incluso dentro de un grupo viable, las poblaciones deben generarse mediante la competencia. La población produce nuevos individuos a través del apareamiento y, combinado con los efectos de la mutación, el subgrupo crece hasta convertirse en un nuevo grupo y reemplaza al antiguo grupo. En un nuevo ciclo, el nuevo grupo reemplazará al antiguo y se convertirá en el comienzo del ciclo. .
3.2 Descripción del algoritmo
Paso 1: Inicialización, establezca el tamaño de la población n y utilice el método de números naturales para codificar el cromosoma;
Paso 2: GenN ∶= 0, genere la población inicial Pop (0);
paso 3: para cada cromosoma de la población, calcule el valor de aptitud y registre el valor de la función de aptitud óptima actual;
paso 4: si se cumplen las condiciones de terminación del algoritmo, deténgase y genere el resultado; de lo contrario, vaya al paso 5;
Paso 5: de acuerdo con el método de selección de élite y de selección de ruleta, seleccione Pop (GenN + 1). ) de Pop (GenN), es decir, copiar la siguiente generación de individuos;
paso 6: realizar operaciones de mutación de intercambio y cruce de retención máxima, y recombinar Pop (GenN + 1);
paso 7: GenN ∶= GenN + 1; vaya al paso 3.
El proceso de descripción específico del algoritmo se muestra en la Figura 1.
Sí
No
Figura 1 Proceso del algoritmo genético
3.3 Construir cromosomas y generar poblaciones iniciales [4]
Este artículo adopta el método de codificación de disposición directa por parte de los clientes. Utilice números naturales entre 1 y N para representar a los clientes. Cualquier disposición de estos números naturales es una solución. De acuerdo con las restricciones del problema, cada número (cliente) de la solución se incluye en la ruta de entrega del vehículo. Por ejemplo, 12346789, primero, el cliente 1 se incluye en la primera ruta de entrega y se juzga si se cumplen las restricciones del problema. Si se cumple, se forma la ruta de entrega 0-1-0 y luego el cliente 2. se incluye en esta ruta de entrega, y luego Calcule si se cumplen las restricciones del problema. Si aún se cumple, se forma la ruta de entrega 0-1-2-0, luego se incluye el cliente 3 en esta ruta de entrega. se calcula la restricción. Si no se cumple, explique. Si el cliente 3 no puede ser entregado por la primera ruta de entrega, se iniciará una nueva ruta de entrega 0-3-0. Este proceso se repetirá hasta que todos los clientes estén incluidos en la entrega. ruta.
Aunque este método de codificación no representa la posición genética del punto de división de cada ruta, es beneficioso para futuras operaciones de cruce. No solo elimina la posibilidad de soluciones inviables, sino que también consume menos almacenamiento informático. También más pequeño.
En cuanto a la selección de la población inicial, algunos estudiosos han propuesto el método de utilizar algoritmos heurísticos para seleccionar mejores cromosomas como población inicial. Sin embargo, la selección de semillas tiene ciertos sesgos y carece de representatividad, lo que puede ocurrir. Resulta imposible encontrar la solución óptima para un crecimiento prematuro y prematuro. Para evitar este defecto, este artículo adopta el método de generar aleatoriamente la solución inicial. Solo de esta manera se pueden atravesar todos los estados, por lo que se puede encontrar la solución óptima. generarse en la evolución del algoritmo genético.
3.4 Función de aptitud
Este artículo selecciona la función de aptitud como aptitud ( ) = M-( ), donde M es un valor grande y M es el valor de la función objetivo, que es Un cromosoma, donde i=1,...,m.
3.5 Determinación del operador de selección
Ordena los n cromosomas de cada población de generación según el valor de la función de aptitud y divide. la aptitud Una copia del cromosoma con el valor de función más grande ingresa directamente a la siguiente generación. Los n - 1 cromosomas restantes de la población de la próxima generación se generan mediante el método de selección de la ruleta. De esta manera, puede garantizar en primer lugar que el individuo óptimo pueda sobrevivir hasta la siguiente generación, lo que no sólo da a los individuos con mayor aptitud una mayor probabilidad de pasar a la siguiente generación, sino que también evita la disparidad en las posibilidades de ser seleccionado para la siguiente. generación debido a diferentes valores de aptitud entre individuos.
3.6 Determinación de la probabilidad de cruce y de mutación [5]
En el algoritmo genético, los operadores de cruce y mutación juegan un papel decisivo en su convergencia. En el algoritmo genético existente para resolver VRP, la forma habitual de abordar las probabilidades de cruce y mutación es: la probabilidad de cruce selecciona aleatoriamente un valor mayor, generalmente 0,5 ~ 1,0, mientras que la probabilidad de mutación selecciona un valor más pequeño; Generalmente es 0, 001 ~ 0, 05. Para evitar divergencias o caer en el óptimo local, mantener individuos "buenos" en la población y acelerar el proceso de optimización, este artículo introduce un mecanismo adaptativo para ajustar dinámicamente la suma, es decir, reduciendo el valor de la suma. a través de soluciones para valores de aptitud altos y para soluciones con valores de aptitud bajos se implementan aumentando la suma. Específicamente:
Entre ellos, = 0.5, = 0.05, = 1, = 0.1; es el valor máximo de aptitud en la población, f ′ representa la mayor adaptación de los dos individuos cruzados. value es el valor de aptitud promedio de la población y f es el valor de aptitud del individuo mutado. La probabilidad de cruce disminuye a medida que el valor de aptitud tiende a hacerlo. Cuando el valor de aptitud es igual a , es decir, para la solución con el valor de aptitud más grande, la suma es cero. De esta manera, la mejor solución de la población se copia directamente a. la próxima generación (es decir, selección de élite).
3.7 Determinación del operador de cruce y operador de mutación
Este artículo utiliza el método de cruce de orden [3] (Order Crossover, OX El método de cruce específico es el siguiente:
paso 1: seleccione aleatoriamente una subcadena del primer padre;
paso 2: copie la subcadena en la posición correspondiente de una subcadena vacía para generar un descendiente original;
paso 3: Elimine los clientes existentes en la subcadena del segundo padre para obtener el pedido de otros clientes que necesita la descendencia original;
paso 4: de acuerdo con el orden de este cliente, ubique estos clientes en las posiciones vacantes de la descendencia de superior de izquierda a derecha.
La descripción del proceso se muestra en la Figura 2. Se pueden utilizar los mismos pasos para obtener otra descendencia con el mismo par de padres [7 9 3 4 5 6 1 2 8]. 6 2 8
Padres 1
*
*
4 9 1 3
*
*
* Descendencia original
1 2 3 4 5 6 7 8 9
Padres 2
2 5 4 9 1 3 6 7 8
Descendencia
Figura 2 Proceso de cruce
La elección de este artículo se basa en el método de mutación de 2 intercambios en la mutación por translocación [ 3], es decir:
Aleatorio Seleccione dos genes en la cadena de codificación individual y luego intercambie sus posiciones, como por ejemplo:
12345678 12375648
3.8 Terminación reglas
Determinar el número de iteraciones del algoritmo de antemano. Puede controlar eficazmente el tiempo de ejecución del algoritmo y la precisión de la solución del algoritmo. Por lo tanto, este artículo utiliza la regla de terminación para determinar el número de iteraciones. de antemano, es decir, para determinar si el álgebra de iteración es el álgebra N requerida. Si es así, detenga la evolución y seleccione la ruta correspondiente al cromosoma con el mejor rendimiento, como la solución óptima del problema VRPTW original; no, continúe ejecutando la iteración del bucle.
4. Análisis de ejemplo
Los 56 conjuntos de datos R1, R2, C1, C2, RC1 y RC2 proporcionados en Solomon [6] son datos clásicos para experimentos numéricos de conjuntos de problemas VRPTW. El número de clientes en cada conjunto de datos es 25, 50 y 100. La distancia entre clientes es la distancia euclidiana y satisface la desigualdad del triángulo. Las ubicaciones de los clientes de R1 y R2 están distribuidas aleatoriamente, los clientes de C1 y C2 están en un estado agregado y RC1 y RC2 están en un estado semiagregado. Los conjuntos de datos de tipo R1, C1 y RC1 tienen ventanas de tiempo más cortas, por lo que la cantidad de clientes a los que se les permite atender en cada ruta es menor. R2, C2 y RC2 tienen ventanas de tiempo más largas y la cantidad de clientes a los que se les permite atender en cada ruta; es más pequeño. En los problemas reales, la distribución de clientes está en la mayoría de los casos más cerca del estado aleatorio y semiagregado reflejado en los conjuntos de datos de tipo R y RC. Para estar más cerca de la situación real, este artículo utiliza los datos de 25 conjuntos de clientes en la ventana de tiempo más corta R101 para programar y verificar el algoritmo genético propuesto en este artículo, y lo compara con los resultados de la literatura [1]. .
Tabla 3 Comparación de resultados de ejemplos de cálculo
Algoritmo de la literatura sobre algoritmos [6] Algoritmo de este artículo Algoritmo de este artículo
Número de vehículos utilizados 8 8 10
La distancia total recorrida es 617,1 580,352 563,292
La ruta de solución óptima cuando se utilizan 10 vehículos en la tabla es: 0-7-6-2-0; 15-9-4-1-0; 0-14-22-21-0; 0-12-23-0; 0-16- 0;0-13-0,0-17-0,0-19-0;0-25-0;0-24-0;0-20-0. El tiempo de ejecución es de 0,482 segundos.
La ruta de solución óptima cuando se utilizan 8 vehículos es: 07-11-21-0; 13-14-22-0; 0-24-19-16-6-0; El tiempo de ejecución es de 0,437 segundos.
Después de repetidas comprobaciones, cuando el número de población es inferior a 100, el resultado de la operación siempre tiende al óptimo local; cuando el número de población es 150, se puede omitir el óptimo local, obteniendo así el óptimo global; solución óptima. Cuando el álgebra de iteración es 50, el valor promedio de la solución es 670,4 y el tiempo de ejecución promedio es 0,246 segundos; cuando el álgebra de iteración es 100, la solución promedio es 643,7 y el tiempo de ejecución promedio es 0,532 segundos; El álgebra es 200 Cuando, el valor promedio de la solución es 636,8 y el tiempo de ejecución promedio es 1,021 segundos. Esto muestra que si el álgebra de iteración es mayor que 100, no tendrá un gran impacto en la optimización de la solución, pero el tiempo de ejecución aumentará considerablemente, por lo que el álgebra de iteración en este artículo se establece en 100. Después de la verificación, cuando el número de población es 150 y la generación de iteraciones es 100, y la probabilidad de cruce correspondiente es 0,5 y la probabilidad de mutación es 0,02, se puede obtener la solución optimizada (AMD Athlon (tm) 64) que se muestra en la Tabla 3.
5. Conclusión
En el experimento de este artículo, se realizaron 30 ejecuciones aleatorias y la probabilidad de que apareciera la solución óptima fue del 40%, que fue mejor que la solución óptima en la literatura [1] de 8,7%, y el tiempo de solución es corto, lo que muestra la adaptabilidad del algoritmo genético utilizado en este artículo al problema de generación de rutas de vehículos con ventanas de tiempo difíciles, lo que tiene un valor de referencia importante para futuras investigaciones sobre este problema. .