El poliedro del problema de rutas por arcos con capacidades

Abstract

EL PRIMER OBJETIVO DEL TRABAJO ES EL ESTUDIO DEL PILIEDRO ASOCIADO AL CARP PARTIENDO DE UNA FORMULACION "NATURAL" DEL PROBLEMA, PARA UTILIZAR ESTA FORMULACION ES NECESARIO CONSIDERAR UN NUMERO MAXIMO DE VEHICULOS K; LLAMAMOS K-CARP AL PROBLEMA CORRESPONDIENTE. SIN EMBARGO, EL K-CARP ESTA RELACIONADO ESTRECHAMENTE CON EL PROBLEMA DE BIN PACKING, DEBIDO A LA EXISTENCIA DE CARGAS DISTINTAS SOBRE LAS ARISTAS Y A LAS RESTRICCIONES DE CAPACIDAD. ASI, SIMPLEMENTE RESPONDER A LA PREGUNTA DE SI EL POLIEDRO ES NO VACIO ES UN PROBLEMA DE BIN PACKING, ESTO ES, UN PROBLEMA NP-HARD. PARA OBVIAR ESTE PROBLEMA, SE ESTUDIA EL POLIEDRO DEL K-CARP CUANDO TODAS LAS ARISTAS CON CARGA POSITIVA TIENEN LA MISMA CARGA; DENOTAMOS ESTE PROBLEMA COMO K-CARP(Q=0,1). LAS DESIGUALDADES QUE INDUCEN FACETAS DEL POLIEDRO ASOCIADO A ESTE PROBLEMA, SON VALIDAS TAMBIEN PARA EL K-CARP Y, EN DETERMINADAS CONDICIONES, IN DUCEN TAMBIEN FACETAS DEL POLIEDRO ASOCIADO. LA PARTE MAS IMPORTANTE DE ESTE TRABAJO LA CONSTITUYE EL ESTUDIO DEL POLIEDRO ASOCIADO AL K-CARP(Q=0,1), CON LA DETERMINACION DE SU DIMENSION Y EL DESARROLLO DE DESIGUALDADES VALIDAS QUE INDUCEN FACETAS. ESTAS DESIGUALDADES HAN SIDO UTILIZADAS EN UN ALGORITMO TIPICO DE PLANOS DE CORTE, QUE HA SIDO APLICADO MANUALMENTE A UNA SERIE DE EJEMPLOS. A PESAR DE ELLO, EN ESTE TRABAJO SE PRESENTAN ALGUNOS ALGORITMOS DE IDENTIFICACION DE RESTRICCIONES VIOLADAS, PARA CIERTAS CLASES DE DESIGUALDADES.