TSP Solver 3.05 · Guía de usuario

Desde los primeros puntos hasta la ruta final. Conoce el espacio de trabajo, los algoritmos, los ajustes y las opciones de exportación de TSP Solver.

Ing. Robert Polák (RoboPol)robopol@gmail.com

Introducción

TSP Solver busca un recorrido lo más corto posible que pase una sola vez por cada punto y vuelva al inicio. Es el problema del viajante de comercio (TSP), con aplicaciones en logística, planificación de rutas, perforación de circuitos impresos, mecanizado CNC, corte láser, robótica y trayectorias para drones en 2D y 3D.

La aplicación incluye LKH, Robopol Refined y un método híbrido. Permite calcular distancias en línea recta y distancias sobre una red de carreteras real.

Inicio rápido

  1. Elige línea recta (AIR) para coordenadas o carretera (ROAD) para direcciones.
  2. Añade puntos en el lienzo o importa coordenadas desde un archivo .txt. En el modo carretera, escribe una dirección por línea y geocodifícalas.
  3. Selecciona un algoritmo y un perfil según la rapidez y la calidad que necesites.
  4. Inicia el cálculo para dibujar la ruta.
  5. Exporta los puntos, una imagen o un SVG. Guarda el proyecto completo en .json.

Espacio de trabajo

La barra lateral izquierda contiene las herramientas del proyecto, de datos y del sistema. En el centro está el lienzo. El panel derecho reúne el selector de algoritmos, el botón de cálculo y el resumen y los detalles de la ruta.

Espacio de trabajo con una ruta AIR calculada
Espacio de trabajo con una ruta AIR calculada

El contador suma coordenadas únicas. Antes del cálculo, el marcador dorado señala el primer punto introducido. Después, señala el inicio y el fin de la ruta o el depósito común en mTSP. Los detalles incluyen las coordenadas, los duplicados eliminados y el tiempo de cálculo. Puedes copiar, borrar o exportar su contenido.

Las filas de entrada duplicadas no aumentan el número de puntos únicos.

Diseño y pantalla completa

En pantallas estrechas, los resultados aparecen debajo del lienzo y puedes usar el botón de menú para abrir la navegación. El icono de la esquina superior derecha del lienzo activa o desactiva la pantalla completa. Las herramientas siguen disponibles en el menú.

Con conjuntos de datos grandes, puedes omitir el dibujo desde los ajustes de apariencia del lienzo. El cálculo continúa mientras se suspende el dibujo de puntos y líneas.

AIR 3D (x, y, z)

Activa Air 3D para calcular distancias tridimensionales. Para añadir puntos a mano, ajusta la altura z de −1000 a 1000. También puedes importar coordenadas x y z o generar puntos aleatorios con una altura fija o uniforme dentro de un intervalo.

Después del cálculo, abre la vista 3D. Arrastra con el ratón para girar y usa la rueda para hacer zoom. Cerrar la vista 3D no cambia el modo de cálculo. La exportación TXT incluye Z si está activo el modo 3D o si algún punto tiene una Z distinta de cero. Consulta los formatos de importación y exportación para ver los separadores admitidos.

Ruta calculada en el visor 3D integrado
Ruta calculada en el visor 3D integrado

Botones de funciones

Las acciones rápidas permiten añadir y eliminar puntos, quitar las líneas dibujadas y borrar todo el contenido. El botón de cálculo está en el panel derecho. Las herramientas para gestionar archivos y datos están a la izquierda.

Algoritmos

LKH-3.0.10

Un algoritmo consolidado para rutas en línea recta, por carretera y con varios vehículos. Para las rutas AIR, prueba varios valores de CANDIDATE_SET_TYPE. El resultado depende de la distribución de los puntos.

EUC_2D / EUC_3D redondea la distancia euclidiana de cada tramo a unidades enteras. EXACT_2D / EXACT_3D emplea mayor precisión.

LKH + Robopol Refined

Un método híbrido que da prioridad a la calidad en rutas AIR exigentes y que puede tardar más en calcularlas.

Robopol Refined

El optimizador de RoboPol cuenta con tres perfiles. Fast prioriza la rapidez, Balanced equilibra rapidez y calidad, y Heavy da prioridad a la calidad.

Elige EXACT_2D / EXACT_3D cuando sea importante obtener una distancia total precisa. Empieza con los perfiles incluidos. Fast favorece cálculos más cortos, Balanced es adecuado para el trabajo general y Heavy o LKH + Robopol Refined priorizan la calidad de la ruta. El primer cálculo puede incluir una inicialización única.

Los perfiles aparecen en la interfaz en español como Rápido (Fast), Equilibrado (Balanced) e Intensivo (Heavy).

Rendimiento

El tiempo de cálculo depende de la cantidad y distribución de los puntos, del algoritmo, del perfil y del equipo. Si la ruta es crítica para tu trabajo, compara los resultados de varios perfiles. Con muchos puntos, puedes suspender el dibujo en el lienzo para facilitar el uso de la interfaz.

Fast prioriza la rapidez, Balanced ofrece el equilibrio predeterminado y Heavy prioriza la calidad. Ningún perfil es el mejor para todos los conjuntos de datos. Se admiten 2D y 3D con visualización interactiva, además de rutas sobre redes viales reales que se pueden exportar a Google Maps. Fuente: página de TSP Solver de RoboPol.

Elección de métodos y perfiles

  • Respuesta rápida con Robopol Refined y Fast.
  • Uso general con Robopol Refined y Balanced.
  • Calidad de la ruta AIR con Heavy o LKH + Robopol Refined.
  • Carretera y varios vehículos con LKH-3.0.10.

Empieza con los perfiles incluidos. Cambiar valores avanzados puede incrementar el tiempo de cálculo, la carga del procesador y el uso de memoria. El efecto sobre la ruta depende de los datos.

Los perfiles incluidos ofrecen niveles probados de velocidad y calidad sin ajustes manuales. Las modificaciones avanzadas están dirigidas a usuarios experimentados. Un valor mayor no garantiza una mejor ruta para un conjunto de datos concreto.

Operaciones con archivos

Crear un proyecto nuevo limpia el lienzo y la salida, y conserva los ajustes. Guarda los proyectos AIR como tsp_air_data.json y los de carretera como tsp_road_data.json. Puedes volver a abrir los proyectos guardados en TSP Solver.

Importa una imagen como plantilla o exporta la vista actual como imagen. El formato SVG conserva la ruta y los puntos como gráficos vectoriales escalables.

Los proyectos guardados usan la extensión .json y los gráficos vectoriales, .svg. Guardar como abre un diálogo para elegir el nombre del archivo.

Importación y exportación de datos

Todos los formatos de coordenadas admitidos

  • x y o x y z
  • x, y o x, y, z
  • x; y o x; y; z
  • n) x y o n) x y z
  • n: x y o n: x y z
  • n, x y o n, x y z

La numeración solo se reconoce si tiene un delimitador explícito, como ), : o ,. Esto permite conservar una primera coordenada entera en los archivos 3D válidos. Los decimales usan punto (.).

Antes del cálculo se resalta la primera fila. Después, el marcador dorado sigue el orden real de la ruta. Las coordenadas repetidas se cuentan una sola vez. La exportación TXT guarda los puntos de la ruta. Usa x y si el modo 3D está desactivado y todos los valores Z son cero. En los demás casos usa x y z. Después de generar puntos aleatorios, pulsa Calcular para resolver la ruta.

La exportación mTSP estructurada está pensada para máquinas y herramientas. Sus metadatos usan esta sintaxis:

# TSP_SOLVER_TXT 1
# mode: air
# depot: 1
# vehicles: k
# objective: MINSUM|MINMAX|MINMAX_SIZE
POINTS
id x y [z]
ROUTES
V <vehicle_id> cost=<cost> stops: id id id ...

Para ROAD, el modo es # mode: road y el formato de los puntos es id lat lon "address". Los identificadores son 1..n en el orden del archivo. Las rutas hacen referencia a esos identificadores.

La exportación TXT conserva, cuando es posible, el separador de coordenadas (espacio, coma o punto y coma) y el estilo de numeración. En el generador de puntos aleatorios, selecciona una distribución y calcula la ruta después de generar los puntos.

Apariencia y ajustes del algoritmo

Opciones de apariencia en detalle

Abre Sistema → Apariencia o Configuración en el lienzo. La pestaña Lienzo incluye el tema, los colores del fondo, de los puntos y de las líneas, el tamaño de los puntos, el grosor de las líneas, la cuadrícula tenue y Omitir dibujo. La pestaña Interfaz permite ajustar los colores de la página, la barra lateral, los paneles, el acento, el acento oscuro, el texto, los bordes y los campos. Restablecer colores de página recupera los colores predeterminados.

Con conjuntos muy grandes, de decenas de miles a millones de puntos, omitir el dibujo puede mantener la aplicación más ágil. El solucionador sigue calculando mientras se suspende la representación de los puntos y de la ruta.

Perfiles y esfuerzo de búsqueda

La configuración del algoritmo tiene las pestañas Rutas, Robopol Refined y LKH. Confirma los cambios con Aplicar ajustes. Empieza con un perfil incluido. Modifica valores individuales cuando las mediciones de tu caso de uso justifiquen el cambio. El método seleccionado gestiona algunos valores automáticamente.

Robopol Refined ofrece controles previsibles del esfuerzo de búsqueda. El perfil gestiona los parámetros internos sensibles. Sus interacciones son no lineales y modificarlos por separado puede reducir el trabajo útil de optimización o empeorar la calidad de la ruta.

  • Perfil carga una configuración completa y probada de velocidad y calidad.
  • Ejecuciones determina el número de intentos de optimización independientes. Se conserva el mejor resultado.
  • Presupuesto de búsqueda por ejecución limita el trabajo de búsqueda de cada intento.
  • Amplitud de búsqueda determina cuántas alternativas prometedoras se conservan simultáneamente.
  • Variantes por ciclo determina cuántas alternativas se evalúan en cada ciclo.
  • Los valores personalizados se guardan en el navegador por separado para Fast, Balanced y Heavy, y se recuperan al volver al perfil.
  • Restablecer el perfil actual elimina únicamente sus valores personalizados y recupera sus valores predeterminados.

Un esfuerzo mayor suele requerir más tiempo y puede mejorar la consistencia. La optimización estocástica no garantiza que cada cálculo individual supere a un perfil de menor esfuerzo.

Todos los campos de mTSP

  • Tipo de problema permite elegir TSP con una ruta o mTSP para varios vehículos.
  • Vehículos (vehicles) establece el número de vehículos o rutas.
  • Objetivo (mtsp_objective): MINSUM minimiza la suma de las distancias o tiempos. MINMAX minimiza la ruta individual más larga. MINMAX_SIZE minimiza el mayor número de paradas por vehículo para equilibrar la carga de trabajo, sin optimizar directamente la distancia.
  • Índice del depósito (1..n) (depot_index) fija el inicio y final comunes. 1 corresponde al primer punto. En ROAD cuenta el orden de las direcciones geocodificadas correctamente. Las líneas fallidas se omiten.
  • Paradas mínimas por vehículo (mtsp_min_size) evita repartos como 1 frente a 99 paradas. Excluye el depósito.
  • Paradas máximas por vehículo (mtsp_max_size) limita la carga de trabajo. Excluye el depósito.
  • Optimizar carretera por (road_objective) permite elegir distancia en kilómetros o tiempo en segundos.

La aplicación desactiva o gestiona automáticamente las opciones avanzadas de LKH que no corresponden al método elegido. Aumentar RUNS y MAX_TRIALS suele aumentar el tiempo de ejecución. Cambia otras opciones avanzadas únicamente a partir de una prueba validada o una recomendación de soporte. Los valores más altos no garantizan mejores resultados. mTSP requiere la edición Professional. Consulta la exportación TXT por vehículo en Importación y exportación de datos.

Ajustes de apariencia del lienzo
Ajustes de apariencia del lienzo
Configuración del algoritmo Robopol Refined
Configuración del algoritmo Robopol Refined
Ajustes de rutas para varios vehículos
Ajustes de rutas para varios vehículos

mTSP utiliza LKH-3.0.10 y está pensado principalmente para AIR 2D y ROAD. Comprueba AIR 3D con tareas pequeñas antes de iniciar cálculos grandes.

Edición y cálculo

Haz clic en el lienzo para añadir un punto. Activa el modo de eliminación para quitar puntos individuales. Puedes quitar las líneas dibujadas o borrar todos los puntos, rutas e imágenes de fondo. El cálculo requiere al menos dos puntos únicos.

Al añadir puntos se resalta el primero. Después del cálculo, el marcador indica el inicio y final reales de la ruta. En el modo de eliminación, pulsa sobre un punto para quitarlo.

Arte TSP

La aplicación de escritorio convierte imágenes en puntos. En la versión en línea puedes importar coordenadas preparadas y calcular una ruta continua a partir de ellas.

En la aplicación de escritorio, usa el menú de datos para elegir una imagen e indicar la cantidad de puntos. Empieza con unos miles de puntos para obtener una vista previa rápida. Para un cálculo rápido con LKH puedes probar DELAUNAY, RUNS = 1, MAX_TRIALS = 1, MOVE_TYPE = 3 y ambos parámetros de patching en 0. Ajusta los colores y el grosor de la línea y exporta el resultado.

Los ejemplos usan entre 50 000 y 100 000 puntos. Los tiempos dependen de los datos, de los ajustes y del equipo.

John Wick: arte TSP con 100 000 puntos únicos, calculado con LKH
John Wick: arte TSP con 100 000 puntos únicos, calculado con LKH
Tigre: arte TSP con 100 000 puntos únicos en la interfaz clara
Tigre: arte TSP con 100 000 puntos únicos en la interfaz clara
Rosa: arte TSP con 50 000 puntos únicos en la interfaz oscura
Rosa: arte TSP con 50 000 puntos únicos en la interfaz oscura

Imágenes de referencia: John Wick · WildCats Conservation Alliance · Liam Nguyen / Unsplash

En la aplicación de escritorio, abre Conjunto de datos → Generar arte TSP, selecciona una imagen e introduce el número de puntos. Más puntos aportan más detalle y aumentan el tiempo de conversión y cálculo. Selecciona LKH-3.0.10, abre Ajustes del algoritmo → LKH y ajusta los valores indicados. Pulsa Aplicar ajustes y después Calcular. En Apariencia → Lienzo, ajusta los colores del fondo, de los puntos y de la ruta. Exporta la imagen, los puntos o el SVG según necesites.

Las capturas proporcionadas por el autor muestran la interfaz completa de la versión 3.05, con el algoritmo seleccionado y el resultado. John Wick tiene 100 000 puntos únicos calculados con LKH, el tigre tiene 100 000 puntos en la interfaz clara y la rosa tiene 50 000 puntos en la interfaz oscura. Los ejemplos son ilustrativos y no garantizan un tiempo de ejecución en otros equipos o conjuntos de datos.

Ejemplos y capturas de pantalla

Cada captura muestra la ventana completa de la versión 3.05. Pulsa una imagen para abrirla y elige 1:1 para ver su tamaño original.

Pasos para una imagen de fondo

  1. Abre Archivo → Importar imagen.
  2. Añade puntos sobre la imagen, elige un algoritmo y pulsa Calcular.
  3. Exporta la imagen, los puntos o el SVG y conserva el proyecto con Guardar como.

Pasos para coordenadas TXT

  1. Prepara las coordenadas con un delimitador admitido.
  2. Abre Conjunto de datos → Importar puntos y calcula la ruta.
  3. Compara el número de puntos únicos con los detalles de la ruta y exporta el resultado.

Rutas por carretera

En mTSP, todos los vehículos salen del depósito común y vuelven a él. depot_index empieza en 1 y sigue el orden de las direcciones geocodificadas correctamente. Las direcciones que fallen se omiten. La geocodificación y el cálculo por carretera dependen de servicios externos.

El modo de carretera combina geocodificación y cálculo de rutas sobre redes viales reales. Activa mTSP desde Ajustes del algoritmo → Rutas y establece vehículos, objetivo, depósito y límites de paradas. La misma función admite AIR 2D. Prueba AIR 3D primero con tareas pequeñas.

Selecciona ROAD, introduce una dirección por línea, geocodifica la lista y calcula la ruta. Mostrar mapa abre una vista previa interactiva. La exportación a Google Maps permite navegar y enviar la ruta al teléfono. Se requiere conexión a internet. Las solicitudes a servicios externos pueden ralentizar el cálculo.

Entrada de direcciones con un destino por línea
Entrada de direcciones con un destino por línea
Ruta por carretera calculada en el mapa
Ruta por carretera calculada en el mapa

Licencia y ediciones

Las ediciones se diferencian por los límites de puntos, los permisos de importación y exportación y las funciones de carretera. Activa las funciones adquiridas en Información → Clave de licencia. Demo permite evaluar la aplicación con puntos y funciones limitados. Basic es adecuada para proyectos pequeños y planificación de viajes. Professional ofrece todas las funciones con límites ampliados. El tamaño práctico de los datos depende del hardware, la memoria y el modo elegido.

Requisitos del navegador

Necesitas un navegador moderno y conexión a internet. El visor 3D requiere WebGL. Los cálculos se ejecutan en el servidor.

El cálculo en línea no requiere instalar el solucionador de escritorio.

Notas y consejos

  • Para facilitar la geocodificación, incluye calle, número, código postal, ciudad y país.
  • Con conjuntos AIR grandes, empieza con Fast y omite el dibujo si hace falta.
  • Exporta a SVG para editar los trazados en programas de gráficos vectoriales y usa el punto decimal en los archivos de coordenadas.

SVG permite ampliar la imagen con nitidez y editarla como vectores, por ejemplo en Inkscape o Illustrator.

El selector de idioma cambia la interfaz dentro del área de trabajo abierta. Conserva los puntos, las rutas, las direcciones, los diálogos abiertos y los cálculos en curso.