UAX · Estructura de datos y algoritmos II · algoritmos voraces
¿Qué rider va a qué pedido?
Cuando entra un pedido, lo intuitivo es mandarle el rider más cercano. Es un algoritmo voraz y casi nunca es lo mejor para el conjunto. Aquí se ve paso a paso frente al reparto óptimo, el que hacen Uber, Glovo o RiderExpress: juntar los pedidos de unos segundos y repartirlos todos a la vez.
Escenario
El mapa
rider libre pedido reparto voraz reparto óptimo
Paso 0
Pulsa Ejecutar y avanza solo, o ve paso a paso con Siguiente.
Minutos de espera
–total voraz
–total óptimo
–ahorro
–peor espera (v / ó)
Cada celda, los minutos que tarda ese rider en llegar a ese pedido (una cuadra, un minuto). Es la matriz de costes de un grafo bipartito: riders a un lado, pedidos al otro.