近年来,作为共享经济时代的先行者,网约车平台的发展十分迅速,规模与使用率稳定增长,网约车市场的竞争也随之不断加剧。网约车平台方便快捷的信息交换,大大缓解了传统出租车系统由于乘客和司机之间的时空偏差造成的信息堵塞问题,有效缓解了城市出行打车难的窘境,为居民的出行带来了新的便利。网约车指派策略是网约车平台技术的核心,高效合理的网约车指派方法既可以提升乘客满意度,还可以提升司机接乘效率增加司机侧收入。基于以上分析,本文在考虑乘客实际体验、产品的使用场景与路网的非均质特性后,设计了一种基于车辆运行时间预测的网约车指派算法,以期实现混合订单场景下乘客出行耗时的最小化。本文首先针对路网非均质空间特性,设计了一种基于动态时空图的车辆运行时间预测模型。模型分为空间特征提取模块与时间特征提取模块两部分:空间特征挖掘方面,首先使用LINE的方法对节点的邻接关系进行嵌入以增强数据的空间特征,将谱域图卷积与自注意力机制相结合以挖掘路网局部非均质空间特征,设计了一种虚拟图卷积机制以挖掘路网全局非均质空间特征;时间特征挖掘方面,本文将因果卷积与膨胀卷积结合,设计了一种既有较强历史信息捕获能力又有较小计算复杂度的时间特征提取框架。随后,基于车辆运行时间的预测结果,我们对混合订单场景下的网约车指派问题进行描述与建模,在满足乘客容量与订单数量等约束的前提下,最小化乘客的出行耗时。考虑到研究问题与模型的特点,算法分为两个步骤:订单分组与二分图匹配,根据车辆运行时间的预测结果构建订单拓扑图,设计了一种新的距离函数,参考图聚类的方法对订单进行分组,使用KM算法对二分图进行匹配,从而得到网约车指派结果。最后,我们选取北京市五环内的部分路网作为研究对象,借助出租车GPS数据进行了案例分析。通过对原始GPS数据的处理,得到了指派测试集、训练集与验证集。我们使用训练集与验证集对车辆运行时间预测模型进行训练,再借助训练好的模型得到测试集中各个指派时间窗对应的车辆运行时间预测结果,验证了预测模型在关键指标上表现较好,框架中的各个模块能够较好地发挥作用,可以有效地挖掘路网的非均质特性。基于路径耗时预测结果,完成了相关参数的设置后,我们采用基于图聚类的指派算法进行求解。为了验证本文算法的有效性,将其与贪婪算法进行对比,结果证明,在混合订单的场景下,本文提出的算法在乘客侧指标与司机侧指标的表现均优于比较基线,能够较好地缩短乘客出行时间,提升司机的接送效率。