ES2644703T3 - Dispositivo y método para optimizar el movimiento de vehículos de guiado automático - Google Patents

Dispositivo y método para optimizar el movimiento de vehículos de guiado automático Download PDF

Info

Publication number
ES2644703T3
ES2644703T3 ES14771380.4T ES14771380T ES2644703T3 ES 2644703 T3 ES2644703 T3 ES 2644703T3 ES 14771380 T ES14771380 T ES 14771380T ES 2644703 T3 ES2644703 T3 ES 2644703T3
Authority
ES
Spain
Prior art keywords
node
vehicles
vehicle
mission
nodes
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
ES14771380.4T
Other languages
English (en)
Inventor
Roberto Olmi
Domenico Di Terlizzi
Fabrizio DABBENE
Federico Della Croce
Marco Ghirardi
Nicola Sacco
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Elett 80 SpA
Elettric 80 SpA
Original Assignee
Elett 80 SpA
Elettric 80 SpA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Elett 80 SpA, Elettric 80 SpA filed Critical Elett 80 SpA
Application granted granted Critical
Publication of ES2644703T3 publication Critical patent/ES2644703T3/es
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0287—Control of position or course in two dimensions specially adapted to land vehicles involving a plurality of land vehicles, e.g. fleet or convoy travelling
    • G05D1/0291—Fleet control
    • G05D1/0297—Fleet control by controlling means in a control room

Landscapes

  • Engineering & Computer Science (AREA)
  • Aviation & Aerospace Engineering (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Automation & Control Theory (AREA)
  • Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
  • Traffic Control Systems (AREA)

Description

5
10
15
20
25
30
35
40
45
DESCRIPCION
Dispositivo y metodo para optimizar el movimiento de vetnculos de guiado automatico Campo tecnico de la invencion
La invencion se refiere a un dispositivo y un metodo para optimizar el movimiento de vetnculos de guiado automatico y similares.
En particular, la presente invencion se refiere a un dispositivo y un metodo que hace posible optimizar el movimiento de vetnculos de guiado automatico utilizados por ejemplo en diferentes tipos de almacenes para transportar artfculos, asf como mejorar las rutas que los vetnculos deben seguir para llegar a las diferentes estaciones, reduciendo los tiempos de transporte de los diferentes artfculos, y evitando la creacion de atascos a lo largo de las propias rutas.
Estado de la tecnica anterior
En varios campos es comun utilizar vetnculos de guiado automatico, denominandose tambien esos vetnculos AGV segun su forma abreviada de las palabras en ingles Automated Guided Vehicle (Vetnculo de Guiado Automatico). Dichos vetnculos se utilizan frecuentemente, por ejemplo, en diferentes tipos de almacenes industriales para transportar artfculos de todo tipo dentro del almacen.
Los artfculos para los que se utilizan los AGVs pueden pertenecer a diferentes campos tal como el campo de la ceramica, el campo de la alimentacion, el denominado campo de las bebidas, es decir, botellas, latas y similares, el denominado campo del papel, es decir, rollos de papel en general y similares, el campo de la mecanica para mover productos semi-trabajados y piezas terminadas, etc.
Dichos vetnculos de guiado automatico pueden ser de varios tipos, y en todos los casos una funcion de gran importancia es la gestion de las rutas que siguen, de modo que ejecuten las misiones asignadas - por ejemplo, transportar artfculos entre las varias estaciones - con eficiencia y velocidad.
Dispositivos conocidos para gestionar las rutas de vetnculos de guiado automaticos comprenden, entre otras cosas, un denominado grafico de conexion, es decir, un esquema de las posibles rutas a traves de las cual deben ser guiados los vetnculos.
El esquema de las rutas consiste en un cierto numero de nodos y segmentos que conectan los nodos entre st
Para preparar las rutas para los vetnculos de guiado automatico, es necesario tomar en consideracion la presencia de ciertas restricciones, la primera de las cuales es que un segmento puede ser asignado a un AGV solo si:
no hay otros vetnculos en el mismo segmento;
no hay otro vetnculo en segmentos con el mismo nodo de destino.
Se debena tambien tener en cuenta que un vetnculo no es un punto, y por tanto debido al volumen del vetnculo puede darse el caso de que un segmento pueda ser incompatible con algunos de los segmentos y nodos cercanos.
En particular, dicha incompatibilidad es verificada calculando - normalmente mediante un programa de CAD - la forma del area que cubre el vetnculo mientras se desplaza sobre cada segmento y se posiciona en cada nodo.
Por tanto, para cada segmento se calcula la totalidad del tamano, es decir, todos los segmentos y nodos para los que la forma calculada intersecta a la forma del segmento considerado.
Estos tamanos, denominados en adelante segmentos y nodos incompatibles, se definen como tamanos de bloque para el segmento considerado.
Por tanto, otras restricciones preven que un segmento predeterminado pueda ser asignado a un vetnculo solo si:
ningun segmento de bloque para el segmento predeterminado ha sido asignado a otro vetnculo;
ningun segmento que termina en un nodo de bloque para el segmento predeterminado ha sido asignado a otro vetnculo;
ningun segmento esta en un nodo de bloque para el segmento predeterminado.
Ademas, cada vez que un vetnculo abandona un nodo es necesario un cierto tiempo para liberar realmente el propio nodo, ya que toda la forma en planta del vetnculo debe abandonar realmente el nodo.
Por tanto, cada segmento tiene un punto de liberacion, que es precisamente el punto del segmento que debe pasar un vetnculo antes de que el nodo pueda ser declarado libre y ocupado por otro vetnculo.
5
10
15
20
25
30
35
40
45
50
Por tanto, una segunda restriccion que se debe asignar es que:
ningun vetnculo esta en un segmento que parte de un nodo de bloque para el segmento predeterminado, pero que no ha pasado su punto de liberacion.
Finalmente, se identifican todas aquellas situaciones en las que los AGVs, aunque no hayan violado ninguna de las restricciones descritas anteriormente, estan situados en posiciones que impiden sus movimientos. Tales situaciones, que claramente ocurren si consideramos segmentos unidireccionales, son generalmente denominadas puntos muertos, es decir, bloqueos de AGV.
Se produce una situacion analoga cuando los vetnculos estan en situaciones en las que solo son posibles movimientos que periodicamente devuelven los AGVs a las mismas posiciones. En este caso, no se impide el movimiento de los AGVs, pero en cualquier caso estan en una situacion punto muerto debido a que, como se ha dicho anteriormente, los AGVs pueden moverse pero periodicamente vuelven a las mismas posiciones. Estas situaciones se denominan puntos muertos moviles.
Sin embargo, los dispositivos y metodos para gestionar las rutas de vetnculos de guiado automatico se limitan simplemente a evitar la interferencia o colision entre los diferentes vetnculos de guiado automatico, pero no aseguran un uso rapido y optimo de los vetnculos, lo que da como resultado perdidas en el tiempo necesario para transportar los artfculos y basicamente provocando tambien una perdida economica.
El artfculo “A distributed route planning method for multiple robots using lagrangian decomposition technique”, de Nishi et al. y relativo a la Conferencia Internacional sobre Robotica y Automatizacion realizada en Taiwan en septiembre de 2003, asf como el artfculo “A modular control system for warehouse automation - algorithms and simulations in USARSim", de Damjan Miklic et al, y relativo a la Conferencia internacional sobre Robotica y Automatizacion realizada en Minnesota en mayo de 2012, describen respectivas soluciones de acuerdo con el estado de la tecnica.
Objetos de la invencion
El objeto de la presente invencion es por tanto proponer un dispositivo y un metodo para optimizar el movimiento de vetnculos de guiado automatico, y similares, que mejore las rutas que los vetnculos deben seguir para llegar a las diferentes estaciones para llevar a cabo las misiones asignadas, asf como disminuir los tiempos necesarios por ejemplo para el transporte de artfculos entre las diferentes estaciones, y evitar la aparicion de interferencias causadas entre los vetnculos de guiado automatico a lo largo de las propias rutas, especialmente en el caso en que se utiliza un gran numero de vetnculos de guiado automatico.
Un objeto particular de la presente invencion es un dispositivo y metodo para optimizar el movimiento de vetnculos de guiado automatico, y similares, que permite disminuir el tiempo de desplazamiento nominal total de todas las rutas seguidas por la totalidad de la flota de vetnculos en una cierto area o almacen, obteniendo asf un ahorro no solo en tiempo, sino tambien economico.
El tiempo de desplazamiento nominal se define como la suma de todos los tiempos de desplazamiento nominales de cada segmento de la ruta, determinados como la relacion entre la longitud y la velocidad nominal del vetnculo en cada segmento.
Este objeto se consigue por medio del dispositivo para optimizar el movimiento de vetnculos de guiado automatico, y similares, de acuerdo con la reivindicacion 1.
Este objeto se consigue tambien mediante el metodo para optimizar el movimiento de vetnculos de guiado automatico, y similares, de acuerdo con la reivindicacion 15.
Otras caractensticas ventajosas se describen en las reivindicaciones dependientes.
Breve descripcion de los dibujos
Las caractensticas de la invencion seran mas claras para cualquier experto en la materia a partir de la siguiente descripcion y de las tablas de dibujos adjuntas, que se proporcionan como un ejemplo no limitante, en las que:
La figura 1 es un esquema del dispositivo para optimizar el movimiento de vetnculos de guiado automatico, y similar, de acuerdo con la presente invencion.
La figura 2 es una vista esquematica de posibles rutas bidireccionales para vetnculos que pueden ser gestionadas mediante el metodo y el dispositivo para optimizar el movimiento de los vetnculos de guiado automatico de acuerdo con la presente invencion.
La figura 3 es una vista esquematica de posibles rutas para vetnculos que pueden ser gestionadas a traves del metodo y el dispositivo para optimizar el movimiento de vetnculos de guiado automatico de acuerdo con la presente invencion.
5
10
15
20
25
30
35
40
45
50
La figura 4 es una vista esquematica de una secuencia de segmentos a traves de los cuales pueden desplazarse dos vetnculos de guiado automatico de acuerdo con la presente invencion.
Realizaciones de la invencion
De acuerdo con lo ilustrado en la figura 1, el dispositivo para optimizar el movimiento de vetnculos de guiado automatico, que se indica con el numero de referencia 20, comprende esencialmente:
un modulo 21 de gestion de trafico que gestiona el movimiento de algunos vetnculos de guiado automatico AGV1, AGV2, AGV3, ..., AGVn;
un modulo 24 de reasignacion de las misiones de los vetnculos de guiado automatico - es decir, para asignar las misiones de recogida y entrega de los artfculos, para cada vetnculo, de acuerdo con un criterio de optimizacion - conectado para comunicarse con el modulo 21 de gestion de trafico y con los vetnculos de guiado automatico AGVn recordando que aqrn el termino optimo u optimizar tiene el significado de encontrar la mejor solucion permitida con respecto de las restricciones impuestas;
un modulo 25 de resolucion que esta conectado a, y esta en comunicacion con, el modulo 21 de gestion de trafico.
En algunos casos, el dispositivo 20 de optimizacion puede opcionalmente comprender un modulo 23 de supervisor de nivel superior, indicado por tanto en la figura 1 con una lmea discontinua. Este modulo supervisor esta a su vez en comunicacion con el modulo 21 de gestion de trafico y con el modulo 25 de resolucion.
Entre las tareas del modulo de supervisor esta la seleccion preliminar, en el termino medio, de las rutas, la asignacion anticipada de rutas a AGVs particulares a traves de criterios de optimizacion, la secuenciacion de las misiones de carga y descarga para “pre-planificar” el trafico.
El dispositivo 20 de optimizacion tambien comprende una memoria 26 en la que esta representada la planta del almacen - el denominado plano - o el area en la que se mueven los vetnculos AGV, y a partir de este plano del almacen es posible entonces obtener el grafico de conexion que esta situado en el modulo 27 de grafico de conexion respectivo, que comprende una grna de las posibles rutas para los vetnculos AGV. El grafico de conexion es entonces utilizado por el modulo 21 de gestion de trafico para mover los vetnculos AGV.
Con mayor detalle, el modulo 21 de gestion de trafico recibe los datos del modulo 27 de grafico de conexion y el estado global del sistema, es decir, la posicion actual de los vetnculos AGV, las misiones que deben llevar a cabo los vetnculos, etc.
El modulo 21 de gestion de trafico calcula entonces para cada AGV un grafico de conexion reducido, es decir, un grafico que esta formado a partir de la porcion general de grafico a la que puede realmente llegar el AGV en un numero predeterminado de pasos, que se denomina aqrn como el marco temporal T.
Esta informacion, es decir, el estado global del sistema y el grafico de conexion reducida para cada vetnculo AGV, se pasa entonces al modulo 25 de resolucion, que la reprocesa a traves de un modelo de programacion lineal entera, que se describe mas adelante, proporcionando una solucion preliminar optimizada de las rutas, en forma de una secuencia de segmentos por los que debe desplazarse cada AGV.
Como la solucion preliminar proporcionada por el modulo 25 de resolucion utilizo un modelo aproximado (que se describe mas adelante), el modulo 21 de gestion de trafico debe comprobar la compatibilidad real de la solucion y por tanto comprobar las asignaciones de los segmentos de ruta a los vetnculos en cuestion.
En el ejemplo ilustrado en la figura 4, el modulo 25 de resolucion proporciona una secuencia de segmentos “b” y “c” para el vetnculo AGV1, mientras que para el vetnculo AGV2 proporciona la secuencia de segmentos “a” y “d”.
Se debena remarcar que dicha solucion puede ser llevada a cabo por el modulo 25 de resolucion debido a que en el primer paso el vetnculo AGV1 se desplaza a lo largo del segmento “b” y el vetnculo AGV2 se desplaza a lo largo del segmento “a” y en el siguiente paso el vetnculo AGV1 se desplaza a lo largo del segmento “c” y el vetnculo AGV2 se desplaza a lo largo del segmento “d”.
A partir del ejemplo indicado anteriormente, se puede apreciar que la solucion propuesta anteriormente es compatible porque, a pesar de que los segmentos de ruta “a” y “c” se cruzan, los dos vetnculos AGV1 y AGV2 se desplazan por estas secciones en momentos diferentes.
En detalle, el dispositivo 21 de acuerdo con la presente invencion lleva a cabo las siguientes actividades:
comprueba periodicamente la posicion actual de los vetnculos de guiado automatico en los diferentes segmentos de la ruta, y cada vez que un vetnculo AGVn dado cambia su segmento actual, comprueba la posibilidad de asignar los otros segmentos a los otros vetnculos AGV1, AGV2, ..., AGVn;
5
10
15
20
25
30
35
40
45
50
asigna un segmento de ruta a cierto vehmulo de guiado automatico en el penodo de tiempo “t1”, solo si todos los segmentos de ruta relativos al penodo de tiempo anterior “t1-1” ya han sido asignados a todos los otros vehmulos, siendo esta regla necesaria para evitar que la solucion aplicada satisfaga la prioridad de paso indicada en la solucion del modelo;
compone un mensaje con los segmentos a asignar a cada vehmulo y lo envfa al gestor 21 de trafico que lo ordena para los vehnculos AGV implicados.
Cada vez que el modulo 25 de resolucion ha procesado una solucion para mover los AGVs, se llama al modulo 24 de reasignacion, que reasigna los AGVs - de entre los que pueden ser reasignados - para activar las misiones.
Los vehnculos AGV que pueden ser reasignados son aquellos que no estan conectados, significando este termino los vehnculos AGV implicados en una mision desde el momento de inicio de recoger una carga de productos hasta el final de la descarga de la carga.
Durante este penodo de tiempo, la carga de los productos con relacion a una mision esta ffsicamente conectada al vehnculo AGV relativo, y por tanto no es posible asignar la realizacion de esa mision a otros vehnculos.
Se debena remarcar que el modulo 24 de reasignacion asigna las misiones a los vehnculos AGV de una manera matematicamente optimizada, es decir, minimizando la suma del tiempo nominal relativo a las rutas mas cortas (es decir, las rutas que permiten alcanzar el destino en el tiempo mas corto posible sin considerar la necesidad de posibles desviaciones para evitar “atascos”) que deben seguir los vehnculos para moverse desde el nodo final del segmento asignado hasta ese momento hasta los respectivos nodos de destino de la mision respectiva.
Con mayor detalle, el modulo 24 de reasignacion reasigna las misiones a los vehnculos AGV, minimizando la suma de los tiempos de desplazamiento de los propios vehnculos hasta que se ha cumplido el objetivo de la mision respectiva.
La funcion objetivo a minimizar es la suma de todos los tiempos de desplazamiento nominales desde el punto final de cada vehnculo AGV, lo que significa el punto en el que los segmentos datos terminan hasta ese momento.
La suma anteriormente mencionada de todas las distancias se suma con antelacion basandose en las rutas predeterminadas, para cada par de nodos, a traves de un algoritmo para calcular las rutas mmimas (como, por ejemplo, el conocido algoritmo Dijkstra).
En la practica, cada nodo del grafico de conexion tiene una matriz asociada que comprende todos los tiempos nominales mmimos hacia los otros nodos, calculados con el algoritmo de calculo de las rutas mmimas.
El modulo 25 de resolucion genera un modelo de programacion lineal entera que utiliza los datos recibidos del modulo 21 de gestion de trafico.
En particular, el modulo 25 de resolucion comprende una memoria en la que los elementos de la programacion lineal entera que definen el sistema son almacenados: variables, coeficientes de la funcion objetivo, matriz de las restricciones; el modulo 25 de resolucion tambien comprende un solucionador lineal.
Como se ha determinado anteriormente, el modulo de resolucion utiliza un modelo lineal aproximado, en el que:
a) se considera que el tiempo de desplazamiento de cada segmento del grafico es conocido y fijo, es decir, cada segmento es recorrido siempre en el mismo tiempo. Esta es la aproximacion mas importante, que evidentemente no es satisfecha por los graficos actuales en los que coexisten segmentos muy cortos y segmentos muy largos. Sin embargo, a partir de la simulacion llevada a cabo, hemos sido capaces de descubrir que, si la relacion entre la longitud de los segmentos mas largos y mas cortos de la ruta esta entre 1,5 y 2, entonces la secuencia optima de pasos de desplazamiento es casi siempre la misma. En realidad, por supuesto, los tiempos de desplazamiento de los segmentos pueden variar, y esta es la razon de la comprobacion de compatibilidad que se lleva a cabo en cada paso por parte del modulo de gestion de trafico;
b) en la actual realizacion de la invencion, se ignoran los puntos de liberacion, es decir, el punto que un vehnculo debe pasar en un cierto segmento antes de que el nodo anterior pueda declararse libre; esta hipotesis se deduce de la consideracion de que el uso de la informacion sobre los puntos de liberacion puede considerarse excesiva si se compara con el tiempo necesario para la comunicacion/decision.
Una buena planificacion asegura que los vehnculos se pueden mover de manera fluida incluso aunque esten muy cerca unos de otros. En la practica, sin embargo, si los tiempos de programacion son demasiado cortos, pueden estar en situaciones diferentes no-ideales. Por supuesto, el modulo 21 de gestion de trafico tiene en cuenta los puntos de liberacion durante la asignacion de segmentos.
Se debena remarcar que la solucion propuesta por el solucionador no puede ser aplicada, o es en la practica imposible de conseguir, solo en el caso de un bucle cerrado de segmentos (figura 3), en el que cada segmento esta
5
10
15
20
25
30
35
40
45
50
bloqueado mientras que el nodo de destino esta todavfa ocupado, pero esta es una situacion a la que es casi imposible llegar, ya que cada vehmulo se desplaza en direccion a su destino y es diffcil que los vehmulos tengan rutas en un bucle cerrado de segmentos. Sin embargo, para evitar la mayona de estas situaciones, se anade una incompatibilidad adicional para cada bucle de 2 segmentos (n1, n2) y (n2, n1), permitiendo la posibilidad de que se produzcan bucles de orden mas alto (tres AGVs para tres segmentos, cuatro AGVs para cuatro segmentos, y asf sucesivamente), cuya probabilidad es despreciable.
Volviendo al modulo del grafico de conexion 27 y como ya se ha establecido anteriormente, en dicho se lleva a cabo modulo el calculo de las distancias mmimas entre cada par de nodos del grafico de conexion. Dicho calculo se lleva a cabo, por ejemplo, a traves del algoritmo Dijkstra, entonces una matriz se asocia a cada nodo del grafico que comprende todas las distancias mmimas en direccion a los otros nodos.
En el modulo del grafico de conexion 27 tambien se verifican, con antelacion, las incompatibilidades de las rutas para los vehmulos AGV identificados mediante el analisis del grafico.
Por ejemplo, haciendo referencia al esquema ilustrado en la figura 2 de un corredor bidireccional, consideremos los segmentos (1, 2) y (4, 3): dichos segmentos no se bloquean entre sf. Sin embargo, si dichos segmentos son asignados uno tras otro a dos vehmulos AGV, los dos vehmulos se veran forzados a parar, es decir, se produce un denominado punto muerto.
Ademas, el par de segmentos (1, 2) y (5, 4) puede tambien tener el mismo problema: despues de la asignacion a dos vehmulos AGV diferentes, el vehmulo en el nodo 4 solo puede desplazarse a lo largo del segmento (4, 3), que es incompatible con el segmento (1, 2). Como resultado, los segmentos (1, 2) y (5, 4) tendran una denominada incompatibilidad estatica, que se describira mas adelante.
El esquema de la figura 3 representa otro ejemplo de incompatibilidad con 3 segmentos.
Si un primer vehmulo AGV1 es enrutado en el segmento (8, 1), un segundo vehmulo AGV2 es enrutado en el segmento (7, 2), y un tercer vehmulo AGV3 es enrutado en el segmento (9, 3), se producira un estado de punto muerto.
En efecto, el segmento (1, 4) para el primer vehmulo es bloqueado por el nodo 2, el segmento (2, 5) para el segundo vehmulo es bloqueado por el nodo 3, y el segmento (3, 6) para el tercer vehmulo es bloqueado por el nodo 1.
La consecuencia es que el conjunto de segmentos incompatibles, definido por la cadena Sincomp = {(8, 1), (7, 2), (9, 3)}, puede anadirse a una lista de segmentos que no se desea asignar a diferentes vehmulos de manera consecutiva. Este conjunto de segmentos sera tenido en cuenta en el modelo resuelto por el modulo 25 de resolucion a traves de algunas restricciones, conocidas como restricciones de “incompatibilidad estatica”.
Las situaciones de segmentos incompatibles deben identificarse con antelacion en la estructura del grafico, es decir, es necesario encontrar todos los segmentos que no pueden ser ocupados simultaneamente.
Para llevar a cabo este analisis, es posible proceder comprobando automaticamente el grafico de conexion, es decir, a traves de un algoritmo adecuado cuyos detalles se proporcionaran mas adelante.
Tambien es posible llevar a cabo sesiones de pruebas experimentales con los vehmulos AGV para encontrar, a traves de simulacion, situaciones de bloqueo o punto muerto.
Una vez se han identificado los grupos de segmentos incompatibles que provocan el bloqueo en una simulacion, se almacenan en una lista y el modulo 25 de resolucion aplicara restricciones adecuadas para evitar que los AGVs se situen en dichos grupos de segmentos incompatibles.
Un caso particular a considerar es el de los segmentos bidireccionales. En general, es mejor evitar que un vehmulo AGV continue moviendose hacia adelante y atras en segmentos bidireccionales: esta situacion es comparable a los puntos muertos moviles anteriormente indicados y, incluso cuando no lleva al sistema a un estado irresoluble, provoca una perdida de tiempo y, por tanto, una cafda del rendimiento.
Por tanto, en el paso de busqueda de incompatibilidades, solo se consideran los movimientos de los AGVs que no vuelven a un segmento ya visto.
Sin embargo, este es un caso particular en el que se desea que el vehmulo AGV vuelva al mismo segmento de ruta.
Este caso se produce cuando un vehmulo AGV entra en el area de carga que tiene asignada, y esta claro que despues el vehmulo tendra que salir de nuevo de dicha area, y este es el unico caso en el que se permite que un vehmulo AGV vuelva al mismo segmento de ruta.
Por supuesto, si no consideramos este caso particular, todos los conjuntos posibles de ultimos segmentos a un nodo de mision podnan ser clasificados como incompatibles.
5
10
15
20
25
30
35
40
45
Finalmente, el ultimo caso a considerar consiste en la definicion de los denominados nodos sin-parada. Por motivos teoricos y tecnologicos, y para limitar el tiempo de resolucion, los modelos de programacion lineales enteros no pueden tener un numero elevado de variables.
Por este motivo, segun se observa, consideramos un marco temporal de T penodos de tiempo - o de un modo equivalente T segmentos asignables, como maximo, para cada vehuculo.
Es ventajoso que el ultimo segmento asignado a un vehuculo no sea tal que su nodo final entorpezca, en el sentido de incompatibilidad entre movimientos, las maniobras de otros AGVS cercanos a los respectivos nodos de mision. De este modo, se asegura que los AGVs que abandonan sus puntos de mision se dirigen hacia su siguiente destino sin necesidad de esperar a que vehfculos entrantes liberen el segmento.
Por este motivo, para cada nodo de mision se determinan a priori todos los nodos que no tienen que ser el punto final del ultimo segmento asignado a un AGV: dichos nodos se denominan nodos sin-parada, ya que no se permite que los AGVs se detengan en dichos nodos. El algoritmo para la identificacion de los nodos sin-parada se describira mas adelante.
Finalmente, en algunas situaciones puede ser ventajoso planificar, al menos de una manera aproximada, secciones de ruta significativamente con antelacion: por ejemplo, para decidir el orden de entrada de los AGVs en un area de la planta. La tarea de planificar con antelacion, “en otro nivel”, el desplazamiento a lo largo de estos corredores puede ser llevado a cabo por el modulo 23 de alto nivel que, en cualquier caso, delega al solucionador 25 objeto de esta invencion la tarea de resolver el problema “local” de seleccionar la ruta de aproximacion al corredor, de asignar segmentos a todos los vehfculos presentes para evitar un punto muerto.
Formulacion del modelo de programacion lineal
Como es conocido, los modelos de optimizacion lineal especifican la relacion entre las variables de decision y los parametros, calculando la optimizacion de una medida representativa y otras variables resultantes.
Las restricciones, por otro lado, establecen limitaciones en el espacio de las posibles decisiones; los valores admisibles de las variables de decision se determinan a traves de una serie de restricciones de igualdad o desigualdad.
Por tanto, es necesario seleccionar los valores de las variables de decision para satisfacer las restricciones de desigualdad y al mismo tiempo maximizar o minimizar el resultado.
El modelo de programacion lineal entera que se utiliza en el modulo 25 de resolucion es definido en una formula matematica que se describe a continuacion. Con relacion a esto, con relacion a las variables de decision y las restricciones, el problema es descrito por las variables de decision binarias X£(t) donde el supenndice v, con v=1, 2, ..., V indica el numero del vehfculo, y el subrndice n indica el nodo actual, y donde t=1, 2, ..., T es el penodo de tiempo actual, siendo T el numero total de penodos de tiempo considerados.
Por tanto, la definicion de la variable de decision es
Xv(t\ — (1 el vehlculo v esta en el nodo n ^
n( ) lo en caso contrario
Con esta notacion, la variable X£(0) representa el estado inicial, representando el estado inicial del sistema.
En lo que respecta a la funcion objetivo, es una funcion de programacion lineal entera definida como
minY,n= i ELi I[=o f(n, v,t)X”(t) (1.1)
donde los coeficientes f(v, n, t) dependen principalmente de la distancia minima entre el nodo n, en el que estana situado el vehuculo v en el momento t, y nodo de mision del vehuculo v. Otros detalles relativos a la funcion objetivo se describiran mas adelante en este documento.
Tambien estan las siguientes restricciones

lnXZ(t) = 1 Vv,t (1.2)

Er*n(£)<1 Vn,t (1.3)

*£(t+1) <En'EF(n)^'(t) Vn,v,t < T (1.4)
que tienen el siguiente significado:
la restriccion (1.2) indica que cada vehuculo debe ocupar uno, y solo un, nodo en cada momento de tiempo; la restriccion (1.3) impone que no puede haber mas de un vehuculo en uno nodo en cada momento de
5
10
15
20
25
30
35
40
45
tiempo;
la restriccion (1.4) impone la estructura del grafico.
En efecto, como V(n) es el conjunto de nodos que pueden alcanzarse a traves de un unico segmento de ruta que sale del nodo n, la restriccion (1.4) asegura que en el momento t+1 el AGV v esta en un nodo que puede ser alcanzado por uno de los nodos n' e V(n), con un unico segmento de ruta.
Otras restricciones tienen en cuenta las dimensiones ffsicas de los AGVs y la incompatibilidad entre segmentos y nodos descrita anteriormente.
Tales restricciones se denominan reglas de bloqueo.
La primera restriccion expresa la situacion “el segmento (n-i, n2) bloquea el segmento (n3, n4)” y puede expresarse de la siguiente forma lineal
*£(0 + *£(* + 1)+ *£(0 + *£(* + 1) < 3
escrita para cada par de vehuculos vi, V2 y para el momento de tiempo t = 0, ..., T-1.
La segunda restriccion expresa la situacion “el nodo k bloquea el segmento (ni, n2)”
2Xvn\(t) + 2X%(t + 1)+ Xvk*(t) + X?(t + 1) < 4
escrita para cada par de vehuculos vi, V2 y para cada momento de tiempo t = 0, ..., T-1.
(15)
(16)
Otra restriccion “estatica” hace que no se permita ninguna posicion de un conjunto de vehuculos que conducina a un punto muerto, es decir, en el estado en el que ningun AGV puede desplazarse sin chocar con otro. Antes de describir dicha restriccion, es importante observar que el conjunto de posiciones no permitidas se determina a priori, una unica vez, a partir del grafico y a partir de las reglas de incompatibilidad segmento/segmento y nodo/segmento que se han descrito a traves del algoritmo ad hoc que se describira en adelante. Las restricciones de este tipo se denominan restricciones estaticas debido a que se calculan a priori y no dependen del tipo de mision de los AGVS o del estado relativo conectado o desconectado.
El principio expresado por esta restriccion asegura que, en un conjunto Ss dado de un numero de s segmentos incompatibles, por ejemplo el conjunto S2 de dos segmentos que son incompatibles entre sf, el conjunto S3 de tres segmentos que son incompatibles entre sf, y asf sucesivamente, no se asigna ningun subconjunto de s vehuculos a los segmentos de Ss.
Se debena remarcar que el numero s de segmentos incompatibles corresponde al numero s de vehuculos que se tienen en cuenta.
Por ejemplo, no se asignan dos vehuculos a dos segmentos que corresponden a un elemento de S2, no se asignan tres vehuculos a tres segmentos que corresponden a uno de los elementos de S3, y asf sucesivamente.
En particular, en el caso de incompatibilidad entre los dos segmentos (n1, n2), por los que podna desplazarse AGV1(v1), y (n3, n4), por los que podna desplazarse AGV2 (v2), la restriccion se convierte en
*::(ti)+EL£l+i^(t)+^(t2)+EL£2+i*;;:(t) <2(T+i)-t1-t2-i
(1.7)
escrito para cada par de vehuculos v1 v2, con v1 t v2, y para cada par de momentos de tiempo t1 = 0, ..., T-1 y t2 = 0, ..., T-1.
Se debena mencionar que el segundo miembro es una constante que expresa el numero de variables presente en el primer miembro, decrementado en 1.
En caso de que k vetuculos respectivamente se desplacen a lo largo de los arcos (ns1, nd1), i = 1, 2, ... k, y puedan bloquearse uno al otro, mientras que k-1 vehuculos todavfa tendnan la posibilidad de desplazarse a lo largo de las respectivas rutas, la restriccion adopta la forma
I1f=1(xvnli(ti)+Ill=ti+1Xvntdi(t)) < k(T + 1) -Z?=1t, - 1
(18)
donde nsi y ndi representan el nodo inicial y final del i-esimo AGV, i = 1, 2, ..., k. La restriccion (1.8) esta escrita para cada par de s y para cada par de momentos de tiempo ti = 0, ..., T-1.
Un segundo tipo de restriccion considerada gestiona los nodos sin-parada, que impone que nx no puede ser asignado a un vehuculo, por ejemplo el vehuculo v2, como el ultimo nodo, si otro vehuculo, por ejemplo v1, ya se ha desplazado a lo largo de un segmento particular, por ejemplo (ns, nd).
5
10
15
20
25
30
35
40
45
En este caso, la restriccion expresada en forma analttica es
*£(0+zr=tl+i +K2x(j) <T-t1 +1
(1.9)
escrita para cada par de vetuculos v1, v2, con v1 t V2, y para cada par de momentos de tiempo ti = 0, ..., T-1 y t2 = 0, ..., T-1.
Se debena remarcar que tanto las restricciones estaticas como las restricciones de nodo sin-parada introducen comprobaciones del tipo “el ultimo segmento por el que se ha desplazado el vetuculo ...”.
Como no es posible conocer a priori en que franja de tiempo se asignara el ultimo segmento, dichas restricciones requieren la generacion de T restricciones, una para cada penodo de tiempo desde 0 hasta T-1.
Finalmente, se debena remarcar que los nodos considerados en el paso de optimizacion son solo aquellos que puede alcanzar un vetuculo determinado v dentro del penodo de tiempo T, partiendo del nodo ocupado en el penodo de tiempo 0.
En lo que respecta a la funcion objetiva a minimizar, los coeficientes f(n, v, t) anteriormente mencionados son diferentes para los vetuculos con o sin una mision.
Para vehteulos con misiones, el termino f(n, v, t) es:
f(n, v, t) = B(n) + M(t) + D(n, v)
(1.11)
donde B(n) es un parametro adicional diferente de cero si el nodo “n” no es un nodo de mision, D(n, v) es el tiempo de desplazamiento nominal de la ruta minima entre el nodo “n” y el nodo de mision del AGV “v” y
M(t) = &t-i)
si t <T sit =T
(1.12)
si un cierto vetuculo AGV no tiene una mision, el modulo de reasignacion de las misiones 24 lo redirecciona hacia una posicion denominada posicion de origen. El nodo mas cercano al AGV de entre aquellos que pertenecen a un conjunto predefinido (almacenado en el modulo 27) y no ocupado por otros AGVs se selecciona como la posicion de origen.
En lo que respecta a los AGVs sin mision, los coeficientes de la funcion objetivo son iguales a 1 para los nodos en los que estan situados los vetuculos, e iguales a 2 para todo el resto de vetuculos. Con esta seleccion, dichos vehfculos “tienden” a mantenerse quietos, a no ser que esten en la ruta de un vehfculo AGV con una mision, o son incompatibles con la misma. En este caso, el coste total aumentado provocado por el movimiento de dichos vetuculos (es decir, 2 para cada nodo desplazado) es despreciable con relacion a la reduccion en coste total debido al acercamiento de los vetuculos con mision a sus respectivos objetivos.
Se puede aplicar facilmente el mismo principio al caso en el que los AGVs sin una mision son dirigidos a las denominadas posiciones de origen. En este caso, tan pronto como un vetuculo AGV llega a la posicion de origen n, el coste del segmento virtual (n, n), que representa el comportamiento “permanecer en el mismo nodo durante un penodo de tiempo” se establece en 1, mientras que el coste del segmento (n, m), con n t m, se establece en 2; con estas elecciones, tambien en este caso un vetuculo sin mision permanece en la posicion inicial a no ser que constituya un obstaculo para los otros vetuculos con misiones asignadas;
como regla adicional, para cada vehfculo sin una mision, consideramos entonces una “fuerza de repulsion” desde los nodos de mision de otros AGVs, de modo que se reduce la interferencia entre los vetuculos con y sin mision. El coste adicional por el cual se multiplican los coeficientes f(n, v, t) del vetuculo v para todos los nodos n que son, o pueden ser, la mision de otros AGVs esta dado por la siguiente formula
MaxRepulsion - minD(v) * CoefRepulsion (1.10)
donde MaxRepulsion y CoefRepulsion son parametros de diseno, y minD(v) es la distancia minima entre el nodo en el que esta situado el vetuculo v sin destino y los nodos de mision del resto.
Las siguientes excepciones tambien afectan a la definicion de funcion de coste:
si n es un nodo de mision, y si el vetuculo v no tiene una mision en el nodo n, entonces f(n, v, t) = MAX_INT, donde MAX_INT es el numero entero mayor que puede ser representado por una calculadora. Esta seleccion evita que un vetuculo sea dirigido en direccion a un nodo de mision diferente del suyo propio;
si desde el ultimo cambio de mision un AGV ha estado en el mismo nodo durante penodos de tiempo TSPuntoMuerto (punto muerto potencial), o ha pasado por el mismo nodo mas de TS_Cuenta veces (punto muerto movil potencial), entonces el coste se hace
5
10
15
20
25
30
35
40
45
F(n, v, t) = B(n) + M(t)*MalusParaPuntoMuerto (1.13)
donde MalusParaPuntoMuerto es un parametro de diseno.
Algoritmos adicionales: restricciones estaticas
Para identificar los conjuntos de segmentos incompatibles que definen las restricciones estaticas, es posible proceder de dos modos:
evaluando las reglas de bloqueo que evitan colisiones entre vetnculos y determinando manualmente cuales son grupos de segmentos incompatibles; este proceso permite identificar casi todos los pares de segmentos incompatibles;
llevando a cabo una simulacion y almacenando como incompatibles todos los grupos de segmentos en los que se producen situaciones de punto muerto; este metodo permite identificar los grupos de mas de dos segmentos que son incompatibles y posiblemente pares que no fueron detectados durante la evaluacion manual de acuerdo con el punto anterior.
Algoritmos adicionales: nodos sin-parada
En este parrafo describiremos el algoritmo utilizado para identificar los denominados NODOS SIN-PARADA.
Con relacion a esto, es importante observar que cada segmento s se caracteriza por un conjunto diferente de NODOS SIN-PARADA, en adelante indicados como NSNs.
El algoritmo preve que:
1. S es el conjunto de segmentos que conectan todos los nodos de las posibles rutas;
2. para cada segmento s en S, todos los nodos que son incompatibles con los que se encuentran despues de s son NODOS SIN-PARADA;
3. si S no esta vado
a. Haber extrafdo un segmento s de S, y eliminado de S, anadir a NSNs todos los nodos que son NODOS SIN-PARADA para aquellos despues de s, excluyendo el segmento inverso (j, i) de s = (i, j), si no es el unico;
b. Si el conjunto NSNs ha cambiado, anadir entonces a S, si no esta presente todavfa, todos los segmentos que preceden a s;
4. anadir a NSNs todos los nodos que son incompatibles con los que estan despues de s;
5. para cada segmento s = (i, j) eliminar los NODOS SIN-PARADA n si
a. n coincide con i, o con j, o es un nodo de mision;
b. La ruta minima entre i y n anadida al parametro umbral NSNJJmbral es menor que la distancia minima entre n y j;
c. la distancia minima entre j y n es mayor que una cierta distancia NSN-RangoMetros.
En este algoritmo, como los puntos 2, 3 y 4 pueden generar muchos NODOS SIN-PARADA para cada segmento s, se utilizan mecanismos de limitacion del conjunto NSNs, de acuerdo con lo que se indica en el punto 5 anterior:
el primer mecanismo 5a de limitacion elimina los nodos de origen y destino de s y los nodos de mision;
el segundo mecanismo 5b de limitacion implementa una regla heunstica dirigida a eliminar del conjunto NSNs algunos nodos que, aunque satisfacen el punto 4 del algoritmo, es decir, son “incompatibles” con los sucesores s, no son verdaderos NODOS SIN-PARADA porque no hay arcos que puedan enrutarse hacia atras hasta s, una condicion expresada mediante la desigualdad entre las distancias;
el tercer mecanismo 5c de limitacion limita el conjunto NSNs a nodos dentro de una cierta distancia (NSNjRangoMetros) de s.
La invencion asf concebida permite obtener importantes ventajas tecnicas.
Una importante ventaja tecnica es que el metodo para optimizar el movimiento de vetnculos de guiado automatico, y similares, permite que las rutas que deben seguir los vetnculos entre estaciones para llevar a cabo las misiones asignadas se optimicen, reduciendo el tiempo necesario para el transporte de artfculos, y asegurando que no
pueden crearse atascos a lo largo de las rutas, incluso en el caso de un elevado numero de vehnculos de guiado automatico. El metodo para optimizar el movimiento de vehnculos de guiado automatico, y similares, tambien permite ahorrar no solo tiempo, sino tambien dinero. Por tanto, se ha visto como la invencion permite conseguir los objetivos propuestos.
5 La presente invencion se ha descrito de acuerdo con realizaciones preferidas, pero pueden disenarse variantes equivalentes sin apartarse del alcance de la proteccion ofrecida por las siguientes reivindicaciones.

Claims (15)

  1. 5
    10
    15
    20
    25
    30
    35
    40
    45
    REIVINDICACIONES
    1. Dispositivo (20) para optimizar el movimiento de vehnculos de guiado automatico, que comprende un modulo (21) de gestion de trafico para gestionar el movimiento de algunos vehnculos de guiado automatico (AGV1, AGV2, AGV3, ..., AGVn) a lo largo de rutas de un grafico definido por segmentos y nodos para conectar los segmentos, estando indicados dichos vehnculos de guiado automatico por un numero v, donde v indica el vehuculo actual, siendo v = 1, 2, ..., V, estando indicados dichos nodos mediante un numero n, donde n indica el nodo actual, siendo n = 1, 2, ..., N, de acuerdo con penodos de tiempo t, y donde t = 1, 2, ., T es el penodo de tiempo actual, donde el dispositivo (20) comprende un modulo (25) de resolucion conectado a, y en comunicacion con, el modulo (21) de gestion de trafico, estando caracterizado el dispositivo por que
    dicho modulo (25) de resolucion ejecuta una solucion optimizada utilizando la siguiente funcion de programacion lineal entera:
    min£%=1 £Li U=of(n, v, t)X% (t) (1.1)
    donde dicha funcion representa la funcion objetivo, y los coeficientes f(n, v, t) indican la distancia minima entre el nodo n en el que el vehfculo v podna estar situado en el momento t, con respecto del nodo de mision del vehfculo v, y donde X£(t) es una decision variable definida como
    Xv(t\ — (1 el vehlculo v esta en el nodo n ^
    n( ) lo en caso contrario
    con las siguientes restricciones
    £n*n(0 = 1 Vv,t
    (12)
    !.vXZ(t)< 1 Vn,t
    (13)
    X£(t + 1) < Zn'EV(n)Xn' (t)
    Vn, v,t<T (14)
    que tienen el siguiente significado:
    la restriccion (1.2) indica que cada vehfculo debe ocupar uno, y solo un nodo, en cada momento de tiempo;
    la restriccion (1.3) impone que no puede haber mas de un vehfculo en un nodo en cada momento de tiempo;
    la restriccion (1.4) impone la estructura del grafico,
    donde V(n) es el conjunto de nodos a los que puede llegarse a traves de un segmento de ruta simple que sale del nodo n.
  2. 2. Dispositivo (20) para optimizar el movimiento de vehfculos de guiado automatico de acuerdo con la reivindicacion 1, que comprende una restriccion que expresa la situacion en la que el segmento (n-i, n2) bloquea el segmento (n3, n4) y esta expresada en la forma lineal
    *£(0 + *£(* + 1)+ *£(0 + *£(* + 1) < 3
    (15)
    escrita para cada par de vehfculos v1, v2 y para cada momento de tiempo t = 0, ..., T-1
  3. 3. Dispositivo (20) para optimizar el movimiento de vehfculos de guiado automatico de acuerdo con la reivindicacion 1 o 2, que comprende una restriccion que expresa la situacion en la que el nodo k bloquea el segmento (n1, n2) y esta expresada en la forma lineal
    2Xvn\(t) + 2X%(t + 1)+ Xvk* (t) + Xv/(t + 1) < 4 (1.6)
    escrita para cada par de vehfculos v1, v2 y para cada momento de tiempo t = 0, ..., T-1
  4. 4. Dispositivo (20) para optimizar el movimiento de vehfculos de guiado automatico de acuerdo con cualquiera de las reivindicaciones anteriores, que comprende una restriccion que asegura que, tomando dos segmentos incompatibles, la totalidad de los ultimos segmentos asignados a cada uno de los vehfculos no es igual que uno de los elementos de S, y se expresa en la forma lineal
    *£(ti) + ZLtl+i*£(0 + ^fe) + ZLt2+i*£(0 <2(T + V)-t1-t2-i
    (1.7)
    escrita para cada par de vehfculos v1, v2 con v1 t v2, y para cada par de momentos de tiempo t1 = 0, ., T-1 y t2 = 0, ., T-1.
    5
    10
    15
    20
    25
    30
    35
    40
    45
  5. 5. Dispositivo (20) para optimizar el movimiento de vetuculos de guiado automatico de acuerdo con cualquiera de las reivindicaciones anteriores, que comprende una restriccion que expresa la situacion en la que s vetuculos pueden bloquearse unos a otros, donde s-1 vetuculos todav^a tendnan la posibilidad de moverse a lo largo de las rutas respectivas, y se expresa en la forma lineal
    Z?=1(x? (t^ + ZL^i^t)) < fc(r + 1) -Zf=1t, - 1
    (1.8)
    donde nsi y ndi representan el nodo inicial y final del i-esimo AGV, con i = 1, 2, ..., k. La restriccion (1.8) se escribe para cada par de conjuntos de s y para cada par de momentos de tiempo ti = 0, ..., T-1.
  6. 6. Dispositivo (20) para optimizar el movimiento de vetuculos de guiado automatico de acuerdo con cualquiera de las reivindicaciones anteriores, que comprende una restriccion que impone que nx no puede asignarse como ultimo nodo a un vetuculo, por ejemplo el vetuculo v2, si otro vetuculo, por ejemplo el vetuculo v1, ya se ha desplazado a lo largo de un segmento particular, por ejemplo (ns, nd), y se expresa en la forma lineal
    *£(ti) + ZLtl+i*£(0 + *£00 <T-t1 +1
    (1.9)
    escrita para cada par de vetuculos v-i, v2 con v1 t v2, y para cada par de momentos de tiempo t-i = 0, ..., T-1 y t2 = 0, ..., T-1.
  7. 7. Dispositivo (20) para optimizar el movimiento de vetuculos de guiado automatico de acuerdo con cualquiera de las reivindicaciones anteriores, donde la funcion f(n, v, t) se determina del siguiente modo:
    f(n, v, t) = B(n) + M(t) + D(n, v)
    (1.11)
    donde B(n) es un parametro adicional diferente de cero si el nodo “n” no es un nodo de mision, D(n, v) es el tiempo de desplazamiento nominal de la ruta minima entre el nodo “n” y el nodo de mision del AGV “v” y
    «(t) = [t‘ct - i)
    si t <T sit =T
    (1.12)
    si n es un nodo de mision, y si el vetuculo v no tiene una mision en el nodo v, entonces f(n, v, t) = MAX_INT, donde MAX_INT es el mayor numero entero que puede ser representado por un ordenador, evitando asf que un vetuculo pueda dirigirse a un nodo de mision diferente del suyo propio;
    si un cierto vetuculo AGV no tiene una mision, el modulo (21) de gestion de trafico lo redirecciona hacia una posicion de origen, denominada posicion de origen n, establecida con antelacion, o lo deja en el ultimo nodo al que ha llegado; tan pronto como el vetuculo (AGVn) llega a la posicion de origen n, bien se queda en el ultimo nodo al que ha llegado, el coste del segmento virtual (n, n), que representa el comportamiento de quedaren el mismo nodo durante un penodo de tiempo, se establece en 1, mientras que el coste del segmento (n, m), con n t m, se establece en 2; de este modo, un cierto vetuculo (AGVn) permanece en la posicion inicial si no constituye un obstaculo para los otros vehuculos con misiones asignadas.
  8. 8. Dispositivo (20) para optimizar el movimiento de vehuculos de guiado automatico de acuerdo con cualquiera de las reivindicaciones precedentes, que comprende una regla de modo que para cada vehuculo (AGVn) sin una mision, se considera una fuerza de repulsion desde los nodos de mision de otros vehuculos (AGV1, AGV2, AGV3, ..., AGVn-1, ..., AGVn+1, ...), de modo que se reducen las interferencias entre los vehuculos con una mision y vehuculos sin una mision; el coste adicional por el cual el coeficiente f(n, v, t) de un nodo sin mision es multiplicado esta dado por la formula
    MaxRepulsion - MinDCoefRepulsion (1.10)
    donde MaxRepulsion y CoefRepulsion son parametros de diseno, y minD es la distancia minima entre el nodo en el que esta situado el vehuculo sin destino y los nodos de mision del resto.
  9. 9. Dispositivo (20) para optimizar el movimiento de vehuculos de guiado automatico de acuerdo con cualquiera de las reivindicaciones anteriores, que comprende una regla de modo que para cada vehuculo (AGVn) con una mision, el coste adicional por el que se multiplica el coeficiente f(n, v, t) es
    f(n, v, t) = BonusDeMision + ModTiempo(t) ■ distancia(n,Mision(v)) (1.11)
    donde BonusDeMision es un parametro adicional diferente de cero si el nodo n no es un nodo de mision y
    ModTiempo(t)=\tt(t - y (1.12)
  10. 10. Dispositivo (20) para optimizar el movimiento de vehuculos de guiado automatico de acuerdo con cualquiera de las reivindicaciones anteriores, que comprende la regla:
    5
    10
    15
    20
    25
    30
    35
    40
    45
    si desde el ultimo cambio de mision un AGV ha estado en el mismo nodo durante penodos de tiempo TSPuntoMuerto (punto muerto potencial), o ha pasado por el mismo nodo mas de TS_Cuenta veces (punto muerto movil potencial), entonces el coste se convierte en
    f(n, v, t) = BonusDeMision + ModTiempo(t)MalusParaPuntoMuerto (1.13)
    donde MalusParaPuntoMuerto es un parametro de diseno.
  11. 11. Dispositivo (20) para optimizar el movimiento de vehuculos de guiado automatico de acuerdo con cualquiera de las reivindicaciones anteriores, que comprende una regla a traves de la cual para cada nodo de mision se determinan todos los nodos que no deben ser el punto final del ultimo segmento asignado a un cierto AGV, definiendose tales nodos como nodos sin-parada, comprendiendo la regla anterior:
    cada segmento s se caracteriza por un conjunto diferente de NODOS SIN-PARADA, indicados por NSNs;
    S es el conjunto de todos los segmentos que conectan todos los nodos de las posibles rutas;
    para cada segmento s en S, todos los nodos que son incompatibles con todos los sucesores de s son NODOS SIN-PARADA;
    si S no esta vado
    haber extrafdo un segmento s de S, y eliminado de S, anadir a NSNs todos los nodos que son NODOS SIN-PARADA para todos los sucesores de s, excluyendo el segmento inverso (j, i) de s = (i, j), si no es el unico;
    si el conjunto NSNs ha cambiado, anadir entonces a S, si no esta presente todavfa, todos los segmentos que preceden a s;
    anadir a NSNs todos los nodos que son incompatibles con los sucesores de s; para cada segmento s = (i, j) eliminar los n-esimos NODOS SIN-PARADA (n) si n coincide con i, o con j, o es un nodo de mision;
    la ruta minima entre i y n anadida al parametro umbral (NSN_Umbral) es menor que la distancia minima entre n y j;
    la distancia minima entre j y n es mayor que una cierta distancia (NSN-RangoMetros).
  12. 12. Dispositivo (20) para optimizar el movimiento de vehfculos de guiado automatico de acuerdo con una de las reivindicaciones anteriores, que comprende un modulo (24) de reasignacion de las misiones de los vehfculos de guiado automatico, estando conectado dicho modulo (24) de reasignacion de modo que se comunica con el nodo (21) de gestion de trafico y con los vehfculos de guiado automatico (AGV1, AGV2, AGV3, ..., AGVn).
  13. 13. Dispositivo (20) para optimizar el movimiento de vehfculos de guiado automatico de acuerdo con cualquiera de las reivindicaciones anteriores, que comprende un modulo (27) de grafico de conexion, que comprende un plano de las posibles rutas para los vehfculos (AGV1, AGV2, AGV3, ..., AGVn).
  14. 14. Dispositivo (20) para optimizar el movimiento de vehfculos de guiado automatico de acuerdo con cualquiera de las reivindicaciones anteriores, donde dicho modulo (25) de resolucion proporciona una solucion aproximada de las asignaciones de las rutas a dichos vehfculos (AGV1, AGV2, AGV3, ..., AGVn), y donde dicho modulo (21) de gestion de trafico debe verificar la compatibilidad real de la solucion y luego comprobar las asignaciones de los segmentos de ruta a dichos vehfculos (AGV1, AGV2, AGV3, ..., AGVn).
  15. 15. Metodo para optimizar el movimiento de vehfculos de guiado automatico (AGV1, AGV2, ..., AGVn), que comprende los pasos de:
    Gestionar el movimiento de algunos vehfculos de guiado automatico (AGV1, AGV2, AGV3, ..., AGVn) en rutas de un grafico definido por segmentos y nodos que conectan los segmentos, estando indicados dichos vehfculos de guiado automatico por un numero v, donde v indica el vehfculo actual, siendo v = 1, 2, ..., V, estando indicados dichos nodos por un numero n, donde n indica el nodo actual, siendo n = 1, 2, ..., N, de acuerdo con penodos de tiempo t, y donde t = 1, 2, ..., T es el periodo de tiempo actual, caracterizado por que comprende un paso de optimizacion de solucion de dicho movimiento de algunos vehfculos de guiado automatico obtenido utilizando la siguiente funcion de programacion lineal entera:
    min£%=1 £Li U=0f(n,v, WZ. (0 (11)
    donde dicha funcion representa la funcion objetivo, y los coeficientes f(n, v, t) indican la distancia minima entre el nodo n en el que el vehfculo v podna estar situado en el momento t, con respecto del nodo de
    mision del vehnculo v, y donde X£(t) es una decision variable binaria definida como
    Xv(t\ — (1 el vehlculo v esta en el nodo n ^
    n( ) lo en caso contrario
    con las siguientes restricciones
    ZnW) = 1 Vv,t (12)
    5
    ZrW)< 1 Vn,t (13)
    X”(t + 1) < En' '£V(n)Xn’ (0 Vn, v,t<T (14)
    que tienen el siguiente significado:
    la restriccion (1.2) indica que cada vehnculo debe ocupar uno, y solo un nodo, en cada momento de tiempo;
    la restriccion (1.3) impone que no puede haber mas de un vehnculo en un nodo en cada momento de 10 tiempo;
    la restriccion (1.4) impone la estructura del grafico,
    donde V(n) es el conjunto de nodos a los que puede llegarse a traves de un segmento de ruta simple que sale del nodo n.
    15
ES14771380.4T 2013-07-26 2014-07-23 Dispositivo y método para optimizar el movimiento de vehículos de guiado automático Active ES2644703T3 (es)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
IT000178A ITVR20130178A1 (it) 2013-07-26 2013-07-26 Dispositivo e metodo per l'ottimizzazione della movimentazione di veicoli a guida automatica, e simili
ITVR20130178 2013-07-26
PCT/IB2014/063349 WO2015011661A2 (en) 2013-07-26 2014-07-23 Device and method for optimising the movement of automated-guided vehicles, and the like

Publications (1)

Publication Number Publication Date
ES2644703T3 true ES2644703T3 (es) 2017-11-30

Family

ID=49263408

Family Applications (1)

Application Number Title Priority Date Filing Date
ES14771380.4T Active ES2644703T3 (es) 2013-07-26 2014-07-23 Dispositivo y método para optimizar el movimiento de vehículos de guiado automático

Country Status (4)

Country Link
EP (1) EP3025206B1 (es)
ES (1) ES2644703T3 (es)
IT (1) ITVR20130178A1 (es)
WO (1) WO2015011661A2 (es)

Families Citing this family (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE102016009255B4 (de) * 2016-07-29 2023-01-26 Kuka Roboter Gmbh Koordinierung von Pfaden mehrerer beweglicher Maschinen
CN107067779A (zh) * 2016-11-30 2017-08-18 英华达（上海）科技有限公司 自动导引运输车交通管制系统及方法
CN110347178B (zh) * 2019-06-21 2021-11-05 东华大学 一种基于空间几何特征的无人机航迹规划方法
DE102020214005A1 (de) 2020-11-08 2022-05-12 Fraunhofer-Gesellschaft zur Förderung der angewandten Forschung eingetragener Verein Methode zur effizienten Routenplanung von Fahrzeugen in einem Sortiersystem
US12124261B2 (en) * 2020-11-20 2024-10-22 Rapyuta Robotics Co., Ltd. Systems and methods for optimizing route plans in an operating environment
CN112783211A (zh) * 2021-01-06 2021-05-11 中国人民解放军陆军装甲兵学院 一种基于剖分理论的无人机与地面装甲编队协同控制方法
EP4095640B1 (en) * 2021-05-26 2025-01-22 Volvo Autonomous Solutions AB Method and system for controlling a plurality of vehicles, in particular autonomous vehicles
EP4113241B1 (en) * 2021-07-01 2023-08-16 Volvo Autonomous Solutions AB Method and system for traffic control of a plurality of vehicles, in particular autonomous vehicles
CN115981264B (zh) * 2023-02-28 2025-06-24 上海交通大学 一种考虑冲突的agv调度与数量联合优化方法
CN117094629B (zh) * 2023-09-18 2024-05-10 兰州交通大学 一种危险品满载配送路径优化和车辆调度方法
EP4664230A1 (en) * 2024-06-10 2025-12-17 Kollmorgen Automation AB Method and system for identifying travel blocking situations

Also Published As

Publication number Publication date
EP3025206A2 (en) 2016-06-01
WO2015011661A3 (en) 2015-07-02
ITVR20130178A1 (it) 2015-01-27
EP3025206B1 (en) 2017-09-06
WO2015011661A2 (en) 2015-01-29
WO2015011661A9 (en) 2015-08-13

Similar Documents

Publication Publication Date Title
ES2644703T3 (es) Dispositivo y método para optimizar el movimiento de vehículos de guiado automático
ES3038372T3 (en) Zone engine for providing context-augmented map layer
Peasgood et al. A complete and scalable strategy for coordinating multiple robots within roadmaps
Zhang et al. Application of Automated Guided Vehicles in Smart Automated Warehouse Systems: A Survey.
US10037029B1 (en) Roadmap segmentation for robotic device coordination
CN110908381B (zh) 机器人调度方法及装置
Skinner et al. Optimisation for job scheduling at automated container terminals using genetic algorithm
KR20200047708A (ko) 물품 핸들링 조율 시스템 및 수송 용기의 재위치결정 방법
Goyal et al. A new approach of path planning for mobile robots
CN118863472A (zh) 一种面向智慧仓储管理的agv叉车协同调度方法及系统
US20210165424A1 (en) An agv system and a method of controlling an agv system
Serpen et al. Automated robotic parking systems: real-time, concurrent and multi-robot path planning in dynamic environments
CN120010487B (zh) 基于深度强化学习的货到人系统多agv路径规划方法
Zhang et al. Conflict-free route planning of automated guided vehicles based on conflict classification
JP7424957B2 (ja) 搬送車制御システム、運行管理装置および搬送経路生成方法
Coltin et al. Optimizing for transfers in a multi-vehicle collection and delivery problem
JP7540505B2 (ja) 移動体システム、ピッキングシステム、および経路決定方法
Huang et al. Optimal control of a hybrid UAV/train parcel delivery system
EP4594829A1 (en) Shared resource management system and method
Dayıoğlu et al. Route planning methods for a modular warehouse system
US11550827B2 (en) Graph enabled location optimization
Vivaldini et al. Automatic routing of forklift robots in warehouse applications
Scerri et al. A decentralized approach to space deconfliction
Datta et al. Prioritized indoor exploration with a dynamic deadline
KR20220167003A (ko) 양방향 자율 이동 장치에서의 이동 경로 제어 방법, 장치 및 시스템