近年来，移动支付的快速发展以及城市规模的不断扩大，使得网约车迅速兴起，以其预约便捷、支付方便、可达性较强、服务多样和营业时间长等特性在城市交通系统中发挥着重要作用。其中拼车服务以其多人共乘、成本分摊、优惠共享等特性颇受大众喜爱，并以其缓解交通拥堵、减轻能源消耗等优点受到政府大力倡导。
　　然而，在网约拼车场景中，由于诸多复杂因素的影响（如恶劣天气、汽车抛锚、道路修建、交通事故等），路段的通行时间具有高度不确定性，此时的路段通行时间不能精确测量。一方面，对于同一路段，车辆进入该路段时刻的差异可能导致通行时间的不同，如高峰时期和非高峰时期的路段通行时间就有明显差异，即随着道路拥堵程度的不同，路段通行时间也随之动态变化。另一方面，在不同的历史日期中，即使进入路段的时刻相同，该路段的旅行时间也可能不同。如果车辆路径规划是以单天数据为基础而不考虑多天的综合情况，必然会导致规划最短路径偏离实际最短路，增加车辆绕行和空车出行的现象，从而造成车辆载客空间的浪费，加大企业成本并影响调度系统的稳定性，甚至加剧交通拥堵。因此，在现有的交通条件下，如何提供优化路径以提高驾驶员接送乘客的效率和质量，已成为拼车服务信息系统的关键功能部分，也已然成为交通运输领域关注的一个重要科学问题。从企业角度，有效提高企业的服务质量和运营效率的同时最小化运营成本是其核心诉求。
　　基于此，本文开展了在网约拼车场景中，对车辆路径选择的优化研究。基于大量历史出行数据，构建了 0-1 规划模型，目标函数为最小期望费用，同时对复杂模型进行重构，随后用拉格朗日松弛方法松弛模型，然后用改进动态规划算法求解模型，最后利用不同场景的算例分别对模型和算法的有效性进行评估。旨在给车辆提供高鲁棒性的路径选择引导，以保证能够在多位乘客的指定上车时间窗内接上乘客，并且在乘客指定的下车时间窗内分别将乘客送达目的地，最后车辆在行驶时间窗内返回仓库。该研究对提高用户满意度和网约拼车系统运营效率及供需匹配能力具有一定的理论意义和现实价值。本文具体内容详述如下:
　　描述随机时间-空间-状态网络。本文构建了随机时间-空间-状态网络，其中，每一天对应一个时间-空间-状态网络。本文会详细阐述本文研究的网约拼车场景中最小期望车辆路径选择问题。随后本文将用一个简单的算例来对建立的随机时间-空间-状态网络模型进行详细的阐述，然后进一步描述车辆在服务过程中携带乘客的状态以及转换，车辆携带状态的数量。
　　构建随机时间-空间-状态网络车辆最小期望费用路径选择模型。为了更加精确的构建所研究问题的模型，本文在构建的时间-空间-状态网络基础上，增加了相应的虚拟节点和虚拟路段。然后构建了以目标函数为最小期望费用的数学模型。模型约束包括各节点流量守恒约束；每位乘客的乘车请求都要被满足，且仅有一辆车服务的约束；跨不同日期的同一物理路径约束；还有二元变量约束。
　　重构模型。由于本研究考虑了大量的历史出行数据，因此在上述模型中构建了一个跨不同日期的同一物理路经约束，这个约束是基于多个等式的约束，需要对该多等式约束重新构造，使新的约束便于用拉格朗日松弛方法吸收到目标函数中。
　　拉格朗日松弛方法松弛原模型。根据本文所建模型的复杂性，在处理大规模数据集时面临着计算上的挑战。因此，本文引入拉格朗日乘子将复杂的约束松弛到目标函数中，随后将松弛模型分解为一系列单车时变最短路子问题。
　　松弛模型求解算法。本文由于考虑了历史不同日期的数据，因此针对分解后的子问题求解时，需要改进动态规划算法，使其适用于本文模型求解。
　　算例分析。本文对简单网络和现实网络分别构造几种不同场景进行求解，证明所建模型的正确性和算法的有效性。