Metaheuristics for the traveling salesman problem with pickups, deliveries and handling costs

Metaheuristics for the traveling salesman problem with pickups, deliveries and handling costs

1. Solución Óptima para el TSPPD-H

   • Una ruta hamiltoniana que minimice la suma de los costos de enrutamiento y costos de operación adicionales del proceso.
     • Dos formas de resolver
       • Algoritmo de programación dinámica
         • Dado un tour, con el fin de calcular una solución óptima al problema tenemos que decidir entre colocar los productos de recogida en la parte posterior o en la parte delantera del vehículo en cada ubicación del cliente.
           • El costo de cada decisión se basa en la configuración actual de los productos a bordo.
             • Se utiliza el número de cajas de recogida y entrega como variables de estado.
               • Para ver solución matematica, ver paper
       • Heurística de tiempo lineal
         • Ahora nos centramos en el diseño de nuestra heurística de tiempo lineal basada en un análiisis.
           • Para ver análisis, ver paper

2. Palabras clave:

   • Problema del agente viajero
   • Costo de manipulación
   • Recogida y entrega
   • Metaheurística

3. Autores

   • Gunes - Erdogan
   • Gilbert Laporte c
   • Maria Battarra
   • Daniele Vigo

4. Esencia del Trabajo

   • En este trabajo se estudia el problema del agente viajero con recogos, entregas, y costos de manipulación. El subproblema de minimizar el gasto de de transporte de una ruta fija se analiza en detalle.
     • El Traveling Salesman Problem with Pickups, Deliveries and Handling Costs (TSPPD-H), es una generalizacioón de la Single Vehicle Pickup and Delivery Problem with combined demands (SVPDP–P&D).
       • El objetivo es diseñar un recorrido óptimo a través del depósito y un conjunto de clientes, cada uno de los cuales requiere un servicio de recogido, entrega, o ambos. El vehículo sale del depósito transportando las entregas, visita a cada cliente una vez, y vuelve al depósito, pero sin exceder nunca su capacidad

5. En la TSPPD-H

   • Se determina una gira hamiltoniana en la que los productos a bordo se reorganicen posiblemente a la ubicacion de los clientes clientes.
   • El objetivo es minimizar la suma de Costos de manejo y enrutamiento
   • Combina la complejidad del enrutamiento y toma de decisiones de programación
   • El vehículo sigue un "último en entrar-primero en salir" (LIFO). Al visitar a un cliente, los productos que obstruyen a otros productos de entrega deben ser descargados.

6. Conclusiones

   • Los modelos propuestos pueden ser capaces de resolver el problema del agente viajero con recogos, entregas, y costos de manipulación.
   • Los resultados muestran que el algoritmo de programación dinámica exacta produce los mejores resultados.