PROBLEMA DEL CARTERO CHINO:

Kwan Mei-Ko publico un artículo en un diario chino referido a optimizar la ruta de un cartero en 1962, debido a su autor, Alan Goldman sugirió llamarlo “problema del cartero chino”. Recientemente se le ha llamado “problema de la ruta de inspección”.

La formulación del problema es la siguiente: Un cartero debe repartir la correspondencia a cada una de las casas de su distrito, siendo la oficina de correos su punto de partida y llegada. Deberemos encontrar una ruta óptima para que el cartero camine la menor distancia posible.

Reformulando el problema en teoría de grafos debemos construir un grafo en el que las calles del barrio son las aristas del grafo que tiene por vértices las intersecciones de las calles.

Ejemplo:

A la izquierda la ruta del cartero y a la derecha el grafo representativo

Por tanto el cartero debe recorrer cada arista del grafo una vez al menos en su recorrido. Aunque hay veces en que el cartero no debe repetir el recorrido de ninguna arista.

A cada arista se le asocia un peso (la longitud del tramo correspondiente) y así el objetivo del problema del cartero sería encontrar un grafo de peso mínimo (longitud mínima).

NOTA: Dentro del problema del cartero chino hay diversas variantes, el grafo puede ser dirigido, no dirigido o mixto con arcos dirigidos y aristas no dirigidas.

Hay muchas aplicaciones distintas del problema del cartero chino, entre ellas podemos destacar las siguientes:

Ø      Diseño de rutas de carteros, autobuses o semejantes.

Ø      Sistema de recogida de basura.

Ø      Metro.