出租车合乘能够提高出租车的利用率,从而实现在不增加出租车投放量的前提下,一定程度上缓解当前中国大中城市打车难的问题,然而目前尚未有较为科学的模式,能够保证合乘路线的合理性并保障合乘中各方面的利益。另一方面,近年来出租车电召服务进入人们视野,并逐渐培养着人们预约打车的习惯。预约打车模式在用户需求收集方面具有先天优势,为通过优化方法实现车辆调度提供了平台与支撑。因此,研究在预约打车的背景下,根据用户出行需求,实现乘客合乘线路的优化,从而提高出租车利用率,缓解道路拥堵并减少环境污染具有一定的现实意义。本文根据出租车合乘系统的成本结构,建立了车辆合乘路径优化的数学模型,并设计了求解该模型的改进遗传算法,通过matlab对算法进行实现,分析了该模型在提高车辆利用率,降低系统成本方面的优化效果。从研究出租车预约服务模式入手,分析出租车预约用户和车辆的行为特点,研究可行的出租车预约合乘模式。分析该模式下系统的成本结构,提出了单位里程成本与载客量的三种关系模型,并根据出租车运营的实际情况确定了各个参数的取值范围,建立了带有混合时间窗的车辆路径模型用于优化合乘系统中电召车的服务路径。对比分析求解车辆路径问题的各类相关算法,确定了采用遗传算法求解该模型的思路。同时根据问题特点,设计了相应的交叉、变异等遗传操作,并将禁忌搜索算法与遗传算法混合,改进了算法的全局优化特性。处理哈尔滨市出租车GPS实际数据,通过出租车路径的起讫点识别生成用户出行需求点对,建立了优化效果测试集。通过matlab对算法进行编程,分别对比了合乘与非合乘情况下的路径优化效果,以及三种不同里程成本结构模型对优化结果的影响,最后分析了模型的参数敏感性。