Un algoritmo basado en backtracking para un problema de packing en tres dimensiones

En este trabajo consideramos el siguiente problema de packing en tres dimensiones, que surge en el contexto del transporte de productos medicinales refrigerados. Los datos de entrada están dados por un conjunto de productos y un conjunto de tipos de contenedores. Cada producto consiste de una cierta...

Descripción completa

Detalles Bibliográficos
Autores principales:	Addisi, Lucas, Barriopedro, Ricardo, Carlos Di Masi, Carlos, Koch, Ivo, Marenco, Javier, Mydlarz, Marcelo, Tacchini, Lautaro, Vitale, Leonel
Formato:	Objeto de conferencia Resumen
Lenguaje:	Español
Publicado:	2021
Materias:	Ciencias Informáticas Packing Backtracking
Acceso en línea:	http://sedici.unlp.edu.ar/handle/10915/141765 http://50jaiio.sadio.org.ar/pdfs/siiio/SIIIO-15.pdf
Aporte de:	SEDICI (UNLP) de Universidad Nacional de La Plata

id	I19-R120-10915-141765
record_format	dspace
institution	Universidad Nacional de La Plata
institution_str	I-19
repository_str	R-120
collection	SEDICI (UNLP)
language	Español
topic	Ciencias Informáticas Packing Backtracking
spellingShingle	Ciencias Informáticas Packing Backtracking Addisi, Lucas Barriopedro, Ricardo Carlos Di Masi, Carlos Koch, Ivo Marenco, Javier Mydlarz, Marcelo Tacchini, Lautaro Vitale, Leonel Un algoritmo basado en backtracking para un problema de packing en tres dimensiones
topic_facet	Ciencias Informáticas Packing Backtracking
description	En este trabajo consideramos el siguiente problema de packing en tres dimensiones, que surge en el contexto del transporte de productos medicinales refrigerados. Los datos de entrada están dados por un conjunto de productos y un conjunto de tipos de contenedores. Cada producto consiste de una cierta cantidad de cajas, especificadas por su ancho, altura y profundidad. Cada contenedor está especificado por su ancho, altura y profundidad internos, y además tiene asociados un costo y un porcentaje máximo de volumen que se puede ocupar. El problema consiste en ubicar los productos en contenedores minimizando el costo total de los contenedores utilizados, de modo tal que (a) cada producto se ubique en forma vertical en cada contenedor, (b) no haya superposiciones entre los productos, (c) cada producto o bien se ubique sobre el piso del contenedor o bien al menos el 70% de su base esté apoyada sobre otros productos, (d) no se supere el porcentaje máximo de volumen ocupado en ningún contenedor y (e) cada producto aparezca con productos distintos en a lo sumo un contenedor. No hay límite a la cantidad de contenedores que se pueden usar. Presentamos un algoritmo heurístico para este problema. Se utiliza como sub-rutina un algoritmo de programación dinámica para la resolución del problema mono-contenedor y mono-producto (sobre la base de algoritmos similares para el pallet loading problem'). A partir de la generación de todas las combinaciones posibles de contenedores mono-producto, se utiliza un algoritmo basado en backtracking para completar la asignación de las cantidades restantes de cada producto. Presentamos experimentos computacionales intensivos, que muestran que los tiempos de resolución sobre instancias prácticas son aceptables y que las soluciones generadas por el algoritmo son adecuadas.
format	Objeto de conferencia Resumen
author	Addisi, Lucas Barriopedro, Ricardo Carlos Di Masi, Carlos Koch, Ivo Marenco, Javier Mydlarz, Marcelo Tacchini, Lautaro Vitale, Leonel
author_facet	Addisi, Lucas Barriopedro, Ricardo Carlos Di Masi, Carlos Koch, Ivo Marenco, Javier Mydlarz, Marcelo Tacchini, Lautaro Vitale, Leonel
author_sort	Addisi, Lucas
title	Un algoritmo basado en backtracking para un problema de packing en tres dimensiones
title_short	Un algoritmo basado en backtracking para un problema de packing en tres dimensiones
title_full	Un algoritmo basado en backtracking para un problema de packing en tres dimensiones
title_fullStr	Un algoritmo basado en backtracking para un problema de packing en tres dimensiones
title_full_unstemmed	Un algoritmo basado en backtracking para un problema de packing en tres dimensiones
title_sort	un algoritmo basado en backtracking para un problema de packing en tres dimensiones
publishDate	2021
url	http://sedici.unlp.edu.ar/handle/10915/141765 http://50jaiio.sadio.org.ar/pdfs/siiio/SIIIO-15.pdf
work_keys_str_mv	AT addisilucas unalgoritmobasadoenbacktrackingparaunproblemadepackingentresdimensiones AT barriopedroricardo unalgoritmobasadoenbacktrackingparaunproblemadepackingentresdimensiones AT carlosdimasicarlos unalgoritmobasadoenbacktrackingparaunproblemadepackingentresdimensiones AT kochivo unalgoritmobasadoenbacktrackingparaunproblemadepackingentresdimensiones AT marencojavier unalgoritmobasadoenbacktrackingparaunproblemadepackingentresdimensiones AT mydlarzmarcelo unalgoritmobasadoenbacktrackingparaunproblemadepackingentresdimensiones AT tacchinilautaro unalgoritmobasadoenbacktrackingparaunproblemadepackingentresdimensiones AT vitaleleonel unalgoritmobasadoenbacktrackingparaunproblemadepackingentresdimensiones
bdutipo_str	Repositorios
_version_	1764820459730239489

Un algoritmo basado en backtracking para un problema de packing en tres dimensiones

Ejemplares similares