Resumen

En este trabajo se estudia un problema de enrutamiento de arco capacitado dinámico para la sustitución de baterías en un sistema de e-bike sharing, en el que los trabajadores sustituyen las baterías de las e-bikes con poca potencia a lo largo de segmentos de calle de forma dinámica. El objetivo es reemplazar tantas baterías como sea posible y minimizar los fallos en la recogida. La dependencia temporal de las decisiones de ruta, el conflicto de las operaciones de los trabajadores y la naturaleza estocástica y dinámica de las demandas de los usuarios hacen que este problema sea difícil. Para hacer frente a estas dificultades, se adopta un marco de solución de dos niveles "Partición primero, ruta después" para describir el problema en dos escalas temporales diferentes. En la escala temporal grande, se propone un método de partición espaciotemporal que divide la red de carreteras en subzonas no solapadas para descomponer el problema. A pequeña escala temporal, este artículo modela el proceso de decisión de ruta de un trabajador individual como un proceso de decisión de Markov. Adoptamos una política lookahead que simula información y decisiones futuras en algunos horizontes para evaluar la influencia a largo plazo de las decisiones factibles actuales. También se utiliza un algoritmo de búsqueda en árbol Monte Carlo para mejorar la eficacia de la simulación. Mediante la realización de experimentos de cálculo numérico en un caso de estudio y la comparación con algunas políticas de referencia, demostramos la eficacia y eficiencia del método propuesto.

• Materias:Infraestructura de transportes Ingeniería del transporte Accidentes de transito Seguridad del transporte Planificación de ruta
• Subjects:Transport infrastructure Transport engineering Traffic accidents Transport safety Path planning
• Palabras claves:algoritmo de búsqueda en árbol monte carlo, proceso de decisión de markov, problema de enrutamiento en arco, sistema de bicicletas compartidas, decisiones factibles actuales, diferentes escalas de tiempo, gran escala de tiempo, marco de solución de nivel, experimentos de cálculo numérico, proceso de decisión de enrutamiento
• Keywords:monte carlo tree search algorithm, markov decision process, arc routing problem, bike sharing system, current feasible decisions, different time scales, large time scale, level solution framework, numerical computation experiments, routing decision process