Me gustaría preguntar qué es un problema de vrp y qué es un problema de tsp.

Problema del vendedor ambulante (TSP)

La comprensión literal de este problema es: hay un vendedor que quiere vender productos en n ciudades. Quiere encontrar un anillo que contenga todo. n ciudades con la distancia más corta.

TSP tiene una larga historia. La descripción más antigua es el problema del viaje del caballo estudiado por Euler en 1759, es decir, para las 64 casillas del tablero de ajedrez, visitar las 64 casillas una vez y solo una vez, y finalmente. Regreso al punto de partida.

TSP fue introducido por la empresa estadounidense RAND en 1948. La reputación de la empresa y la aparición del nuevo método de programación lineal hicieron de TSP un problema muy conocido y popular.

2. El problema del cartero chino (CPP)

Hay otra forma de describir el mismo problema en China: un cartero parte de la oficina de correos y entrega el correo en la calle bajo su jurisdicción. , y finalmente regresa a la oficina de correos. Si debe visitar cada calle bajo su jurisdicción al menos una vez, ¿cómo debe elegir la ruta de entrega para recorrer la distancia más corta? Esta descripción se denomina problema del cartero chino porque el erudito chino Profesor Guan Meigugu planteó este problema en 1962 y dio una solución.

3. Problema de "Dibujar por una línea" (Dibujar por una línea)

También existe un método de descripción que usa el lenguaje de teoría de grafos: hay n puntos en el plano, use el línea más corta para dibujar Conecta todos los puntos. Se llama el problema de "un golpe".

4. Ruta de Distribución

La descripción del problema TSP en logística es que corresponde a una empresa de distribución logística que quiere entregar todos los pedidos de n clientes por la ruta más corta . llegar. Cómo determinar la ruta más corta.

La solución más sencilla al problema de TSP es el método de enumeración. Su solución es un espacio de solución complejo, extremo, multidimensional y multilocal que tiende al infinito. ¡El espacio de búsqueda es el conjunto de todas las disposiciones de n puntos, con un tamaño de (n-1)! . El espacio de solución se puede visualizar como un área montañosa infinita, y la altura de cada pico o valle es el valor extremo del problema. Resolver TSP es un proceso de escalada en esta interminable zona montañosa para llegar a la cima de la montaña o al fondo del valle.

5. Problema de rutas de vehículos (VRP)

La explicación del problema del transporte de bucles múltiples en logística es diseñar rutas apropiadas para una serie de puntos de demanda de los clientes, de modo que los vehículos pasen por ellos de manera ordenada y lograr ciertos objetivos de optimización, como el kilometraje, bajo ciertas restricciones, como la demanda de carga, el volumen de entrega, el tiempo de entrega, el límite de carga del vehículo, el límite de kilometraje, el límite de tiempo, etc. El costo más corto, el menor costo, el menor tiempo , tamaño de flota más pequeño y alta tasa de utilización de vehículos.

La diferencia entre el problema de VRP y el problema de TSP es que la cantidad de grupos de clientes es grande y solo un vehículo o una ruta no pueden satisfacer las necesidades de los clientes. Debe haber dos problemas: varios vehículos y. la secuencia de conducción de los vehículos. En comparación con el problema de TSP, el problema de VRP es más complejo y difícil de resolver, pero también está más cerca de la situación real.

6. Problema de los viajantes múltiples (Multiple TSP)

Debido al aumento de las restricciones, del problema de los TSP se puede derivar el Problema de los viajantes múltiples (MTSP), que es un punto de partida , m El TSP de un viajante de comercio significa que los clientes visitados no tienen necesidades y los vehículos no tienen restricciones de carga. El objetivo de optimización es recorrer a todos los clientes y lograr el kilometraje total más corto.

El problema VRP es una generalización del problema MTSP cuando la demanda del cliente no es sólo el acceso, sino la carga y descarga de mercancías con un determinado volumen y peso, implicando diferentes tipos y modelos o diferentes capacidades de carga. Al determinar la estrategia de programación de vehículos, el problema MTSP se convierte en un problema VRP.

7. Vecino más cercano

Este es un algoritmo heurístico utilizado para resolver problemas de TSP. El método es simple, pero la solución obtenida no es muy ideal y puede usarse como solución inicial para una mayor optimización. El proceso de solución consta de uno a cuatro pasos: primero comience desde el punto cero como punto de partida de todo el bucle, luego busque el nodo más cercano al nodo anterior que acaba de agregar al bucle y agréguelo al bucle. Repita el paso anterior hasta que se agreguen todos los nodos al bucle. Finalmente, conecte el último nodo agregado al punto de partida para formar una solución al problema de TSP.

8. Inserción más cercana

La inserción más cercana es otro método para resolver problemas de TSP. Su proceso de solución también consta de 4 pasos: primero comenzar desde un nodo, encontrar el nodo más cercano para formar un subbucle de ida y vuelta entre los nodos restantes, encontrar el nodo más cercano a un determinado nodo en el bucle de iones y luego encontrar el; nodo más cercano en el subbucle Encuentre un arco en el arco de modo que la suma de las distancias desde los dos nodos finales del arco hasta el nodo más cercano recién encontrado menos la longitud del arco sea la más pequeña. nodo encontrado al subbucle para minimizar el aumento de distancia. Este nodo se agrega al subbucle. Repita el proceso anterior hasta que se agreguen todos los nodos al subcircuito. El método de inserción más cercano es más complicado que el método del vecino más cercano, pero puede obtener una solución relativamente satisfactoria.

9. Algoritmo de ahorro

El algoritmo de ahorro es el algoritmo heurístico más famoso utilizado para resolver el problema VRP con un número incierto de vehículos de transporte. Su idea central es fusionar los dos bucles del problema de transporte en un bucle en secuencia, y cada vez que la distancia total de transporte después de la fusión se reduce al máximo, hasta que se alcanza el límite de carga de un vehículo, luego el siguiente vehículo. es la optimización. El proceso de optimización se divide en dos tipos: modo paralelo y modo serie.

10. Algoritmo de barrido

También es un algoritmo heurístico para resolver problemas de VRP con un número ilimitado de vehículos. El proceso de solución también consta de 4 pasos: establecer un sistema de coordenadas polares con el punto inicial como origen, luego crear un grupo a partir de los dos clientes con el ángulo más pequeño y agregar clientes al grupo uno por uno en sentido antihorario hasta que La demanda total de los clientes supera la capacidad de carga del vehículo. Luego cree un nuevo grupo y continúe el proceso hasta que todos los clientes se agreguen al grupo