Método del vendedor viajero
Clasificado en Economía
Escrito el en 
español con un tamaño de 4,11 KB
Vendedor 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.
Es parte fundamental de algoritmos de solución del problema de Ruteo de Vehículos.
Método de Inserción más Cercana
Este procedimiento es también constructivo, pero en contraste con el anterior, en el cual se tiene un camino, y sólo al final se completa un tour, aquí tenemos
subtours, los cuales van creciendo hasta completar un tour que abarque todos los vértices. Iniciemos con un subtour, al cual llamaremos T, queremos ahora insertar el nodo “más cercano” a este subtour para ampliarlo.
El Método de Barrido (Sweep)
Contempla 2 fases: La asignación de clientes a vehículos y luego la definición de la secuencia para visitar cada cliente de cada ruta.
Fase de Asignación de Clientes a Vehículos: Ubicar los clientes y fuente (planta, almacén) en 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 barrido polar con zonas.
Fase 2: Se rutea (problema del vendedor viajero).
Ruteo de Vehículos
Se identifican 3 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 éste)
c) el origen y el punto destino son los mismos. (TSP , VRP, VRPTW, PDP)
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 un conjunto determinado de consumidores con cierta demanda y satisfaciendo limitaciones. El objetivo es el de 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 un conjunto de detallistas con cierta demanda fija. El objetivo es el de asignar vehículos y determinar sus cargas para reponer inventarios de los detallistas al mínimo costo de transporte e inventarios.
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 algoritmos de solución del problema de Ruteo de Vehículos.
Método de Inserción más Cercana
Este procedimiento es también constructivo, pero en contraste con el anterior, en el cual se tiene un camino, y sólo al final se completa un tour, aquí tenemos
subtours, los cuales van creciendo hasta completar un tour que abarque todos los vértices. Iniciemos con un subtour, al cual llamaremos T, queremos ahora insertar el nodo “más cercano” a este subtour para ampliarlo.
El Método de Barrido (Sweep)
Contempla 2 fases: La asignación de clientes a vehículos y luego la definición de la secuencia para visitar cada cliente de cada ruta.
Fase de Asignación de Clientes a Vehículos: Ubicar los clientes y fuente (planta, almacén) en 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 barrido polar con zonas.
Fase 2: Se rutea (problema del vendedor viajero).
Ruteo de Vehículos
Se identifican 3 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 éste)
c) el origen y el punto destino son los mismos. (TSP , VRP, VRPTW, PDP)
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 un conjunto determinado de consumidores con cierta demanda y satisfaciendo limitaciones. El objetivo es el de 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 un conjunto de detallistas con cierta demanda fija. El objetivo es el de asignar vehículos y determinar sus cargas para reponer inventarios de los detallistas al mínimo costo de transporte e inventarios.