Optimización de Rutas y Logística: Métodos y Algoritmos de Transporte

Vendedor Viajero (TSP)

Consiste en encontrar la secuencia de puntos que el agente debe visitar, iniciando y regresando al mismo punto, minimizando la distancia o tiempo total. Es parte fundamental de los algoritmos de solución del problema de Ruteo de Vehículos.

Método de Inserción más Cercana

Este procedimiento es de carácter constructivo. A diferencia de otros métodos donde se tiene un camino completo, aquí se generan subtours que van creciendo hasta completar un tour que abarque todos los vértices. Iniciamos con un subtour, al cual llamaremos T, y buscamos insertar el nodo “más cercano” a este para ampliarlo.

El Método de Barrido (Sweep)

Contempla dos fases principales:

• Fase de Asignación de Clientes a Vehículos: Ubicar los clientes y la fuente (planta, almacén) en un mapa.
• Fase de Secuenciación de Rutas: Determinar la secuencia de visita de cada cliente para cada ruta aplicando el concepto de lágrima o un método de solución del problema del Vendedor Viajero.

Método de Agrupar y Rutear (VRP)

Los clientes se consideran como puntos en un plano:

• Fase 1: Se asignan clientes a vehículos en forma polar. Se van sumando clientes en una dirección hasta llenar la capacidad del vehículo. Se puede combinar el barrido polar con zonas.
• Fase 2: Se realiza el ruteo (problema del vendedor viajero).

Ruteo de Vehículos

Se identifican tres tipos básicos de problemas de ruteo:

• a) El origen es diferente al punto destino (caminos más cortos entre puntos).
• b) Múltiples orígenes y destinos (método de transporte y variaciones de este).
• c) El origen y el punto destino son los mismos (TSP, VRP, VRPTW, PDP).

Definiciones Clave

• Agente Viajero: Consiste en encontrar la secuencia de puntos que el agente debe visitar iniciando y regresando al mismo punto, minimizando la distancia o tiempo total.
• Ruteo de Vehículos: Un número de vehículos con capacidad limitada debe servir a un conjunto determinado de consumidores con cierta demanda, satisfaciendo limitaciones. El objetivo es asignar vehículos a consumidores y definir la secuencia de visitas para minimizar costos, distancias o tiempos.
• Recoger y Entregar: Al problema anterior se le incluye la posibilidad de recoger artículos.
• Ruteo e Inventarios: Un almacén central con capacidad ilimitada sirve a un conjunto de detallistas con cierta demanda fija. El objetivo es asignar vehículos y determinar sus cargas para reponer inventarios de los detallistas al mínimo costo de transporte e inventarios.