城市化进程不断推进,城市居住人口不断增加,进而导致个人出行活动也不断增加,这使得资源紧张的交通运输系统在当下仍面临着严峻的交通拥堵问题。单独出行是现如今社会存在的普遍现象,单独出行占用了大量的交通资源,造成了车辆使用效率低下,并且加剧了交通拥堵。而优化的、协调的共享出行的交通方式,可以有效利用有限的车辆资源、司机资源,并同时满足对时间敏感的起、终点的运输服务请求。基于手机APP的共享出行方式正日益流行,越来越受到大众的青睐。该方式可以让乘客提前几分钟通过手机就能轻松发出乘车请求,无需长时间等待。通过优化共享出行过程中服务车辆的行驶路径,可让共享出行车辆的运营费用降低,同时又能够满足乘客的出行需求,给乘客提供良好的出行体验,提高乘客的满意度等。还可以为共享出行方式的可持续发展和节约资源以及缓解城市交通拥堵现状做出重要贡献。共享出行中的服务车辆路径规划问题的研究,可以用车辆路径问题来进行解决。车辆路径问题自Dantzig和Ramser 1959年首次提出以来受到国内外专家学者的密切关注。国内外专家学者从模型本身和求解算法方面都在该领域做出了大量的贡献,并且延伸出了多种不同的变本。车辆路径问题可以优化车辆的行驶路径,可以使得车辆行驶成本最小化和服务公司收益最大化。并且该问题的研究可以为高效利用现有交通资源,缓解交通压力带来良好的效果。在车辆路径问题中考虑动态的路段行驶时间和服务车辆接、送乘客的时间窗,能够使得研究更加贴合现实中的共享出行情况,从而能够更加精确地模拟现实中合乘车辆的路径规划问题。车辆路径问题是组合优化问题,并且是NP难问题,一般构建的模型为整数规划或者混合整数规划问题,模型的目标可以为使得车辆的总行驶距离最短或者总行驶费用最小,一般用分支定界法、割平面法或者启发式算法进行求解。本文将研究状态-空间-时间网络表示方法下带时间窗的共享出行车辆路径问题,并用拉格朗日松弛求解框架进行求解。本文构建了状态-空间-时间网络模型,该模型在二维的空间-时间网络模型基础上增加了车辆在网络中的载客状态维度,该网络可以精确表示共享出行服务车辆在任何时间点的载客状态和载客状态的转换问题。基于建立的状态-空间-时间网络,本文针对研究的具体内容建立了多商品网络流模型。本文建立的模型所具有的复杂性,使得在处理大规模数据集时面临着计算上的挑战。因此,本文引入拉格朗日乘子将一个复杂的约束松弛到目标函数中,得到拉格朗日松弛函数来重新对该问题进行求解。拉格朗日松弛的基本思想是把难处理的约束通过引入拉格朗日乘子移动到目标函数中去,并且使目标函数仍保持线性,从而得到原问题的一个易于求解的松弛问题,而最优的松弛问题则可以通过以拉格朗日乘子作为变量的拉格朗日对偶问题来求得。然后对于拉格朗日对偶问题,应用拉格朗日分解,将问题转化为一系列单车最短路径子问题进行求解。针对具有时变路段费用的最短路问题,本文中将使用时变的动态规划算法来解决。解决拉格朗日对偶问题时将使用次梯度算法来更新拉格朗日乘子。拉格朗日松弛算法包含两部分内容,一是提供待求解问题的下界,二是演变为拉朗日松弛启发式算法。最后,文中还给出了一些有效的可以缩减搜索空间的规则以加快求解时的计算速度。然后,在GAMS建模系统中对简单场景和复杂场景的算例进行建模并求解,来测试算法的有效性。