Coincidencia espacio-temporal en línea en dominios dinámicos y estocásticos

Resumen

Coincidencia espacio-temporal en línea de servidores y servicios a los clientes es un problema que se presenta a gran escala en muchos dominios asociados con transporte compartido (por ejemplo, taxis, compartir viaje, super lanzaderas, etc.) y servicios (por ejemplo, alimentos, equipo, ropa, combustible casero, etcetera). Una característica clave de estos problemas es que la coincidencia de servidores y servicios a los clientes en una etapa tiene un impacto directo en la búsqueda de la siguiente etapa. Por ejemplo, es eficaz para los taxis a recoger clientes más cerca al punto del cliente de la entrega de la primera etapa de juego. Tradicionalmente, se han adoptado enfoques codicioso/miope para resolver dichos problemas de juego en línea a gran escala. Aunque ofrecen soluciones de manera escalable, debido a su carácter miope, puede mejorarse significativamente la calidad de juego obtenidos (demostrado en nuestros resultados experimentales). En este trabajo, presentamos una formulación de optimización estocástica multietapa para considerar posibles escenarios de demanda futura (obtenidos de los últimos datos). Nosotros proveeremos una mejora para los problemas de gran escala más eficaz y eficiente en línea. También ofrecemos los peores límites teóricos sobre el funcionamiento de los diferentes enfoques. Finalmente, demostramos la mejora significativa proporcionada por nuestras técnicas enfoques miopes y dos otros enfoques de varias etapas de la literatura (formulación programación dinámica aproximada y híbrido estocástico de etapas múltiples de la optimización) en tres conjuntos de datos de taxis del mundo real.