SOUP: Spatial-T emporal Demand Forecasting and Competitive Supply in Transportation

交通运输市场空间需求预测与竞争供给

Abstract:

分两步解决了时空需求预测和竞争供应(SOUP)问题。

首先，我们构建一个粒度模型(ST-GCSL模型)，提供请求的时空预测。

其次，我们提供路由代理来请求起源的方法，同时避免代理之间的竞争。

1 INTRODUCTION

打车软件引入

开发一种数据驱动解决方案

解决两个子问题：

1.Dynamic request patterns

动态请求

2.Competition among agents

平衡竞争

离线组件：时空图卷积顺序学习(ST-GCSL)

在线组件：需求感知路由规划(DROP)算法

2 PRELIMINARIES

2.1 设置

1.道路网络

被定义为一个加权有向图G

2.移动代理

每个ai在路网中都有一个原始位置li，并标记为空。代理的数量在整个操作过程中是固定的，并且具有基数

3.请求

由 o d t0 t*组成，分别代表起始o，目的地d，引入时间t0，最大生命周期t*

分配给该请求的条件：

1)代理为空。

2. agent是离请求最近的代理。

3)从代理到请求的最短传输时间使代理能够在请求过期前到达请求。

描述了一下代理和请求的互动关系

4.空闲时间

略

为了减少为空闲代理规划搜索路径时的空闲时间，我们建立了一个精确的请求数据模型，供分配机构用于决策。数据模型是一个与所有代理共享的软件模块，用于表示请求模式和预测未来的请求。

2.2 问题重述

(1)时空需求预测;(2)竞争供应

2.3 框架概述

略

3 SPATIAL TEMPORAL REQUEST FORECASTING

3.1 Spatial-Temporal Partitioning

把路线网络分为六边形网格

将一天划分为M个 time slot 并且用T{t1,tn}表示

对于在ri区域中和时间槽tj中发生的请求数的表示：

从而获取了一个请求序列

3.2 Region Correlation Graph

区域之间的空间依赖关系可以通过拓扑结构而不是欧几里得空间[5]准确地描述

所以将请求预测问题转化为图节点预测问题

在介绍ST-GCSL的细节之前，我们首先解释如何基于历史请求数据集构建两个区域相关图

根据已有研究可以推导

1：地理区域相关图

2：语义相关图

邻接矩阵存储

Ageo是一个0-1矩阵，相邻的为1

用Pearson相关系数[4]来量化区域之间的请求模式相似度。相关系数大于某个阈值的话设为1

3.3 ST-GCSL Model

两个并行链分别处理历史请求序列和上下文特征序列。

上链由h个最近的历史请求序列构成，由两个Spatial-
Temporal Gated Blocks处理

下链，输入是相关上下文特征序列，采用Toeplitz逆协方差聚类(TICC)[15]和二维卷积(Conv2d)进行处理。

TICC的解释：多元时间序列聚类：KDD2017 论文《Toeplitz Inverse Covariance-Based Clustering of Multivariate Time Series Data》精读 - 知乎 (zhihu.com)

二维卷积：详述Deep Learning中的各种卷积（一） - 知乎 (zhihu.com)

两条链连接起来并缠绕在一起，以在下一个时间步骤返回预测的结果

3.3.1 Spatial-Temporal Gated Block (ST-Gated Block)

多重时空卷积模块(MSTCM)和时空卷积模块(STCM)。

1. MSTCM由多个stcm(我们称之为inter- stcm)叠加，用于捕获短期时空依赖关系。

2. STCM用于捕获长期时空依赖关系。为了区别于MSTCM中的stcm，我们称其为外stcm。

3.3.2 Clustering Context Feature Sequence

请求可用性模式和额外特性之间的强相关性

4 DEMAND-AWARE ROUTE PLANNING

计算加权分数，衡量受欢迎程度

4.1 Supply-Demand Analysis

COMSET2模拟器 可视化

2016年6月1日的纽约TLC行程记录YELLOW Data3作为模拟数据

尽可能地分散代理

4.2 Computing Region Weighted Scores

区域加权分数的计算方法 公式

4.3 Route Planning

Candidate Regions Generation

为减小搜索空间 仅仅考虑 L-order

Destination Region Determination

候选区域的数量取决于实时的供需状态，而实时的供需状态由agent的闲置率表示。

由加权抽样算法得到

5 EXPERIMENTAL STUDY

5.1 Experimental Settings

三个数据集

为验证，比较了ST-GCSL和其他几种方法的区别。

损失函数

比较路径选择算法和其它四种的区别

5.2 Request Forecasting Performance Evaluation