Uno de los objetivos de DoorDash es poner a disposición de los consumidores una amplia gama de tiendas que puedan entregarse rápidamente en la dirección indicada. Este proceso implica calcular con precisión las distancias por carretera para cada par tienda-consumidor en nuestro proceso de búsqueda en tiempo real. Nuestra anterior entrada de blog sobre recomendaciones para la búsqueda se centra principalmente en el componente de clasificación de la búsqueda en DoorDash. Esta entrada describe cómo hemos diseñado nuestro sistema de búsqueda utilizando tecnologías de código abierto para ayudar a determinar la selección del consumidor.
Problema y motivación
Calcular con precisión la distancia en coche en tiempo real es fundamental para la selección que ve un consumidor de DoorDash. Una mera distancia en línea recta basada en un círculo podría ser inexacta y daría lugar a tiempos de conducción de Dasher muy largos, especialmente cuando la topología de la región presenta desniveles debidos a barreras como montañas, lagos, puentes, parques, etc.
La figura 1 muestraun círculo de nueve millas de radio alrededor de una dirección en el sur de California. Si un consumidor hace un pedido en una tienda situada en el borde de este círculo, el Dasher tardará al menos media hora (como muestra la figura2) en llegar de la tienda al consumidor.
Definiciones básicas
Antes de entrar en la arquitectura del sistema, definamos algunos términos:
- Latitud, Longitud: Un punto de localización único en el planeta, abreviado como (lat, lng.)
- Geohash: Un sistema de codificación jerárquica para subdividir el espacio en estructuras similares a cuadrículas.
- Isochrone: Curva de igual tiempo de viaje, representada como un ¬†GeoJSON.¬†La figura3 ¬†muestrauna isocrona en San Francisco que representa las zonas a las que se puede llegar en 10 (región interior) y 20 (región exterior) minutos andando.¬†La figura4 es una representación geojson de una isocrona.
Arquitectura
El siguiente diagrama describe la arquitectura general para determinar si una tienda se encuentra en la dirección de entrega del consumidor para determinar su selección.
Componente fuera de línea:
El componente fuera de línea incluye un servicio de isocronas responsable de calcular isocronas para una ubicación determinada (lat y lng, que se convierte en un geohash de nivel siete) y parámetros (por ejemplo: tiempo de viaje).
Para calcular las isocronas, utilizamos nuestro fork personalizado de †Galton, un proyecto de código abierto. Galton se basa en †OSRM, un motor de enrutamiento de código abierto, y †concaveman, una implementación rápida de un algoritmo de casco cóncavo. Galton genera primero una cuadrícula de coordenadas de tamaño y granularidad configurables en torno a la coordenada de entrada. A continuación, OSRM calcula los tiempos de viaje desde la coordenada de entrada hasta cada una de las coordenadas de la cuadrícula. Las coordenadas de la cuadrícula con tiempos de viaje superiores al tiempo de viaje de entrada se filtran. Finalmente, el algoritmo de casco cóncavo genera un contorno de las coordenadas restantes, produciendo la isocrona apropiada como se muestra en la Figura6, que es la isocrona de nueve millas para la misma dirección en la Figura1.
El servicio almacena en caché las isocronas en DynamoDB, como simples búsquedas de valores clave para una rápida recuperación. Además, tecleamos por geohash, precisión 7, en lugar de por coordenada exacta, para reducir el número de entradas que necesitamos almacenar. Las geofichas de precisión 7 tienen un error de ¬±0,076 km; las isocronas de coordenadas dentro de estos límites no variarán drásticamente. Almacenamos isocronas del orden de millones y con un tiempo de búsqueda inferior a diez milisegundos.
Para cada solicitud, el servicio consulta DynamoDB: si la isocrona está presente, se devuelve. Si la isocrona no está presente, se inicia un trabajo asíncrono para generarla y almacenarla, devolviendo una respuesta nula. En posteriores peticiones para esa dirección y parámetros, se devolverá la isocrona generada. Cuando lanzamos un nuevo mercado, lo arrancamos ejecutando una secuencia de comandos para rellenar previamente las entradas de isocronas para todos los geohashes del mercado, con el fin de que el mercado esté preparado para una selección precisa por adelantado.
Componente en línea:
- Los clientes de DoorDash llaman a la API de backend de búsqueda para el específico (lat, lng)
- El módulo de búsqueda llama al servicio de isocronas con (lat, lng) y parámetros como el tiempo de viaje para obtener la isocrona correspondiente. Estos parámetros son específicos de cada distrito y configurables, por lo que podemos realizar experimentos para comprobar los cambios de conversión en función de la selección. Si la isocrona está ausente (como en el caso en que la isocrona está ausente en dynamodb), volvemos a los cálculos ingenuos de distancia en línea recta (con un radio más ajustado). Persistimos en la lógica de selección (isocrona o línea recta junto con los parámetros) a nivel de sesión en el módulo de búsqueda backend para proporcionar una noción consistente de selección a través de las sesiones de navegación para el consumidor.
- El módulo de búsqueda, al obtener la isocrona de esa dirección, se codifica como una †geoforma poligonal†paraconstruir una†consultade geoforma†paraElasticsearch.
- Los almacenes indexados en Elasticsearch tienen la ubicación codificada en formato"geopunto". Elasticsearch construye unaestructura de árbolde prefijosentiempo de índice para admitir consultas geográficas rápidas en tiempo de ejecución. Elasticsearch ejecuta la consulta ES geoshape del paso 3 para calcular una intersección del polígono con almacenes en el índice para su recuperación.
- Los resultados de la tienda se deserializan y se devuelven al cliente para esa dirección.
Conclusión
Nuestra implementación actual tiene en cuenta la topología de la región a través de la distancia de conducción, abordando el problema de selección imprecisa de la figura 1 mediante la selección isocrónica, como se muestra en la figura 6. Además, esta arquitectura permite configurar y controlar la lógica de selección en función de la regionalidad, cambiar dinámicamente la lógica de selección en función de las curvas de oferta y demanda y realizar experimentos de selección.
Algunas de las áreas en las que trabajaremos en el futuro son la introducción en el sistema de actualizaciones más precisas y en tiempo real sobre el tráfico y el estado de las carreteras.
Si te apasiona resolver problemas desafiantes en este espacio, estamos contratando para nuestro equipo de Búsqueda y Relevancia y nuestro equipo de Infraestructura de Datos. Si estás interesado en trabajar en otras áreas de DoorDash, visita nuestra página de empleo. Háganos saber cualquier comentario o sugerencia.
