Algoritmo más o menos para problemas de transporte de carga fija

Algoritmo más o menos para problemas de transporte de carga fija

El fenómeno de más o menos (MFL) en los problemas de distribución ocurre cuando es posible enviar más bienes totales por un costo total menor (o igual), mientras se envía la misma cantidad o más desde cada origen a cada destino. Esta paradoja ocurre a menudo en problemas de transporte de carga fija (FCTP, por sus siglas en inglés), y un análisis posterior podría traer una reducción significativa en los costos. El fenómeno de MFL para FCTP ha recibido una atención mínima en la literatura a pesar del hecho de que los algoritmos analíticos existentes, tales como la ramificación y el límite, están limitados a pequeños problemas debido al excesivo esfuerzo computacional. En este documento, desarrollamos un algoritmo heurístico simple para identificar los destinos de demanda y los puntos de suministro para enviar MFL en FCTP. El método propuesto se basa en cualquier solución factible básica existente. Es fácil de implementar y puede servir como una herramienta efectiva para que los gerentes resuelvan la paradoja más o menos para grandes problemas de distribución.

1. Introducción

El costo de transporte en muchos problemas de distribución consiste en costos fijos, que son independientes de la cantidad transportada, y costos variables, que son proporcionales al monto enviado. Por ejemplo, las compañías de ferrocarriles y camiones utilizan invariablemente tasas de flete que comprenden tanto costos fijos, como tarifas de permisos e impuestos a la propiedad, y costos variables, como el uso directo de equipos y personal. Cuando los costos de envío no son negativos, el fenómeno de más por menos (MFL) en problemas de transporte clásicos (TP) y problemas de transporte de carga fija (FCTP) ocurre cuando es posible enviar más bienes totales por menos (o igual) total costo, mientras envía la misma cantidad o más desde cada origen y a cada destino. La ocurrencia de MFL en problemas de distribución no es inusual, y la literatura existente ha demostrado la practicidad de identificar los casos donde existe esta situación paradójica [1]. Charnes y Klingman [2] y Charnes et al. [3] han cubierto la paradoja MFL en TP clásicos desde un punto de vista teórico. Robb [4] proporcionó una explicación intuitiva de la ocurrencia de la paradoja. Las características de MFL también son discutidas por muchos otros autores [5] usando la metodología de escalonamiento (SS). En la práctica, sin embargo, el método SS encuentra muchos obstáculos [6]. Además, las preguntas sobre cuántos envíos adicionales son óptimos y cómo distribuir estas unidades adicionales quedan a juicio de estos autores. Arsham [6] desarrolló un enfoque para los análisis de postoptimidad de los TP mediante el uso de análisis de perturbaciones. Adlakha y Kowalski [1] introdujeron una teoría de puntos absolutos para resolver un TP y utilizaron estos puntos para buscar oportunidades de enviar más por menos en TP. Más tarde ofrecen una mejora en este procedimiento sugerido y sugiere un algoritmo mejorado para MFL en un TP [7]. Aunque son efectivos, sin embargo, estos métodos requieren una mayor sofisticación matemática y no son eficientes para problemas grandes.

La aparición de MFL es aún más común en los FCTP que en los TP clásicos. Esto se debe a la estructura especial de la formulación FCTP que surge de la presencia de costos fijos. La existencia de una situación de MFL es información útil para que un gerente decida qué capacidades de la planta se incrementarán y en qué mercados vale la pena realizar esfuerzos para aumentar la demanda. Debido a que requieren un esfuerzo computacional excesivo, los algoritmos analíticos existentes para resolver FCTP tales como la ramificación y el límite son útiles solo para pequeños problemas. Adlakha y Kowalski [8, 9] han hecho un intento pionero sobre este problema utilizando conceptos de puntos absolutos y un fenómeno descubierto por Balinski [10] que el valor de la FCTP sigue de cerca el valor de su correspondiente TP reducido (RTP). Como MFL se identifica fácilmente para RTP, propone obtener una solución MFL de un FCTP simplemente ubicando puntos absolutos de su RTP correspondiente. Sin embargo, los puntos absolutos pueden no estar presentes en muchos problemas y el proceso se vuelve engorroso a medida que aumenta el tamaño del problema. Adlakha y Kowalski [9] presentan una técnica heurística para MFL para el TPs clásico con una extensión a FCTP utilizando el RTP correspondiente. La técnica se basa en la solución óptima del RTP y se basa en prueba y error. Aunque la técnica propuesta puede proporcionar una solución MFL en algunos casos con poco esfuerzo, ni proponen un procedimiento para identificar la existencia de MFL ni aseguran que se encontrará una solución en un FCTP.

En este trabajo desarrollamos una heurística analítica sencilla pero poderosa para MFL en FCTP. Nuestro método se basa en un análisis simple para identificar destinos de mercado y puntos de suministro para enviar más unidades a un costo reducido. Para mejorar la comprensión del algoritmo MFL propuesto para FCTP, primero presentamos y explicamos un algoritmo MFL para TPs clásico y luego extendimos el algoritmo al análisis MFL en el FCTP. A diferencia del método propuesto anteriormente para MFL en la FCTP [9] que se basa en una solución óptima, nuestro algoritmo puede proporcionar MFL para cualquier solución factible básica existente. Es fácil de aplicar y puede servir como una herramienta efectiva para los gerentes en la solución de la paradoja MFL para los principales problemas de transporte. El propósito de este documento es hacer que la teoría MFL en TPs y FCTP sea fácilmente comprensible para los gerentes que carecen de una base matemática sólida.

1. Análisis más por menos (MFL) para TPs

Deje ai representar el suministro dado de bienes en la i-ésima planta y bj representa la demanda que debe satisfacerse en el j-ésimo mercado. Deje que cij sea el costo unitario de transporte desde la i-ésima planta al j-ésimo mercado. Entonces la formulación de MFL para el TP clásico es la siguiente:

[pic 1]

El objetivo es minimizar el costo total de transporte a la vez que se satisfacen las restricciones de oferta y demanda.

1. The MODI method

El método de distribución modificada (MODI) requiere que definamos ui de precio doble para cada restricción de oferta y vj de precio dual para cada restricción de demanda. La computación de estos ui y vj requiere que el coeficiente de costo para cada celda básica cij = ui + vj. Configurando cualquiera ui = 0 o vj = 0, uno puede resolver el sistema de ecuaciones para todos los valores restantes de ui y vj. Para cada celda no básica cij - (ui + vj), el índice de evaluación neto, proporciona el cambio en el costo total por unidad que se obtendrá asignando una unidad de flujo a la celda correspondiente. Usamos el término índice Modi para (ui + vj) y lo presentamos como una tabla Modi.

...