摘  要： 针对目前出租车“一人一乘”的租赁模式导致空载率较高的问题，对现有的车辆合乘模式予以改进，以提高出租车在城市公共运输系统的辅助效应。通过构建一种适合国内大中型城市出行分布特征的出租车合乘模式，对出租车运营路径按各节点已确定乘载需求以决策树求解，对运行过程中的临时乘载需求，以动态规范算法计算调整路径的插入可行性，实现整体的动态规划调度。模拟程序实验结果表明，随着乘载量的提高，车辆运载效率也随着提高。
关键词： 动态规划算法；出租车合乘；运行路径

    随着全球环保意识不断提高，以公共交通为主导的城市交通发展战略，因其具有明显的低碳特征，已成为城市交通发展的趋势，通过发展公共运输来实现城市交通的节能减排已逐渐成为各国政府的主要施政方向。但公共交通的公交基础设施建设进度通常落后于城市区域扩张，同时公共交通也无法解决私人交通需求的“最后一公里”问题，在一定程度上影响到市区公共交通的服务水平。相比之下，出租车作为一种介于私人运输与公共运输之间的辅助性运输工具，既具有公共运输服务的特征，又兼具私人运输的高自主性，可以成为城市公共运输系统的有益补充[1]。
    出租车虽然是公共交通的已有资源，但目前 “一人一乘”的租赁模式造成空载率较高。以长沙市为例，2009年全市共有7 000余辆出租车，里程空载率为36.1%[2]，其运载能力还有提升空间。如果有效提供出租车合乘服务，可在短距离运输、偏远路线以及交通高峰期弥补公共运输的不足。引导出行人群采用出租车合乘服务而减少私家车使用频率，不仅能降低公共交通成本，同时也可以配合政府的节能减排政策，使城市整体交通状况得到明显改善。由于出租车的运输方式属于“点对点的最短路径运输”，如果要提供合乘服务，必须通过绕路来完成接载多位乘客的任务，因此如何建立有效路径算法，使有限的出租车辆实现载客量极大化成为需要研究的课题。
1 模型建立及求解
    “车辆合乘”在广义上包含“车辆共有”与“车辆共用”两种情况。2003年Matthew Barth等人对车辆合乘提出了3种模式，即邻居模式、站车模式和多点复合模式[3]。邻居模式是在城市多处设置专用停车场，使用者在约定的时间与地点取用车辆，完毕后再停放到专用停车场，此模式要求城区内设置足够多的专用停车场。站车模式是合乘车辆仅行驶于城市至郊区的指定路段，由合乘者分摊交通成本，以减少不必要的交通拥堵与燃油消耗，多适用于地广人稀但城市交通拥堵的区域。多点复合模式与邻居模式类似，区别在于租借和归还不限于同一取车点，回程也可选择其他交通工具，但服务商需每天进行车辆重置以维持各停车场有足够车辆可提供服务。
1.1 出租车合乘模式建模
    我国已进入城镇化、汽车化的加速发展阶段，国内各大城市普遍存在居民出行强度增加、对机动车出行依赖逐渐增加的情况。以长沙市为例，2009年家庭居民人均出行次数为2.40次/日，机动车出行占比从2007年的9.7%上升到11.2%。居民出行目的以通勤出行为主（含上班、上学、公务、回家），占比达74.2%，出行高峰集中在7:00～8:00、17:20～18:20时段，高峰系数分别达到18.1%、13.9%。出行空间分布具有较强的中心集聚性，以五一广场、芙蓉广场为中心，呈“T”字形向外扩张[2]。
    邻居模式对城区停车区域占用较多不切实际，而单独运用站车模式或多点复合模式均无法满足需求。本文结合以上模式的优点设计适合国内城市的出租车合乘模式，对主要集聚地(如车站、商圈、居民区)设置为聚集站点，在站点周边一定距离内提供约车接送服务；设置主要客运车站为中心站点，其他聚集小区为途径站点，通过各小区汇聚机动车出行的需求，实现各小区之间点对点的出租车合乘服务，从而扩大合乘服务范围，更好地发挥出租车的公共交通辅助效应。其示意图如图1所示。

1.2 模型求解
    本文设计的模型以出租车合乘为研究对象，其问题类型与旅行销售员问题TSP（Traveling Salesman Problem）或车辆路线问题VRP（Vehicle Routing Problem）类同，属于网络最优求解问题。由于出租车实际运营中只会做单向运输，途经两个或更多的聚集小区，其路径规划归纳为对复杂情况的一对多情形组合，属于NP类问题。对VRP问题通常可使用穷举法，但效率偏低，应用动态规划法作为最短路径求解是更好的方法[4]。考虑到出租车服务的实际市场需求，对合乘容量、车辆运行时间、候车时间也将纳入计算因素[5]，在求解规划上主要考虑各途径站点到中心站点的调度较优化，这是本模型求解与传统TSP或VRP问题的最大不同，具体说明如下：
    对所有途径小区依据其空间位置划分为多个阶段，在每个阶段的起点做全体路径选择的决策判断，选择本阶段的最优路径。重复以上步骤直到完成整体规划，则所选择路径形成一棵决策树。对该决策树从终点站出发以逆向求解，考虑所有节点设置不同人数组合成为一个观察点，搜寻途径的各节点直到回到起点站为止，从而得到本路径下对于各途径站点不同人数状况的最佳化路径规划。
  
2 模拟实验及结果
    依据本文所建立的出租车合乘模式，以及针对该模式的求解算法，设计实例对所架构的模型与算法进行模拟实验，求证模型的逻辑正确性。设计两个中心站点对6个途径小区站点提供合乘服务，其空间关系示意图如图3所示，各小区站点的坐标初始化赋值情况如表1所示。假定各小区之间为点对点的直线距离，以坐标网格边距1 000 m估算。

    目前出租车容量为限乘载4人，为避免乘客在合乘时有过多身体接触，对每台合乘车辆的容量限制调整为3人。由于出租车对乘客感知上属于高便利性的交通方式，对候车时间限制拟定为10 min为上限[6]，对合乘出租车的乘客最大可接受运行时间设定为30 min。关于对各站点服务半径参数设置，以居民步行可接受距离900 m估算[7]，则每个站点的服务半径不低于900 m。按市区内公共交通日均运行速率19.86 km/h估算，考虑候车时间的10 min限制，则每个站点的最大服务半径不高于3.31 km。
    结合各小区需求人数的不同组合，对路径规划的全集如图4所示。各圆圈符号表示小区编号以及候车人数，图中为完成以3人为单位的分组后情况。由于各小区人数都按3人为单位进行分组，因此出租车抵达后续小区的容量应只考虑一人或两人的组合。

    以每小时需求50人、100人来进行模拟测试，并设定需求随机在一小时内各时间点在各途经小区内出现。对每类需求各模拟30次，结果表明，当每小时需求50人时，该模式的乘载率为0.83；当每小时需求提高到100人时，乘载率提高到0.92。对比传统的出租车运营情况，模拟实验数据表明了合乘模式下应用动态规划算法将具有较好的效益。
    通过发展公共运输来改善城市交通状况已成为我国政府需要面对的重要问题，然而由于公共交通设施建设在城市化进程的滞后性，以及公共运输对个人出行需求存在“最后一公里”的限制，如何运用其他形态的运输方式（如出租车）来弥补公共交通的不足成为公共运输发展中需要研究的课题。本文通过构建一种出租车合乘模式，并运用动态规划算法进行合乘路径规划，以简例设计以及模拟程序实验的方式，证明了模型的可行性。对于合乘模式下回程车辆运载效率的提高，以及同一路径下通过多车组队的方式提高运载效率是后续研究需要关注的问题。
参考文献
[1] 郑秀妙，许建华.城市出租汽车供需平衡影响因素分析[J].经营管理者，2011(2)：54.
[2] 长沙市规划信息服务中心.2009长沙市城市交通状况年度报告[R].长沙，2009.
[3] BARTH M，SHAHEEN S.Shared-use vehicle systems：a framework for classifying carsharing，station cars，and combined approaches[J].Transportation Research Record，2003，1792：105-112.
[4] LI J Q，MIRCHANDANI P B，BORENSTEIN D.Real-time vehicle rerouting problems with time windows[J].European Journal of Operational Research，2009，194(3)：711-727.
[5] HUNSAKER B，SAVELSBERGH M.Efficient feasibility testing for dial-a-ride problems[J].Operations Research Letters，2002，30(3)：169-173.
[6] 郭雅玥，李妮杨，秋萍.公共交通系统优化与推广——以成都市公交系统为例[J].经营管理者，2011(4)：50.
[7] 杨晓飞，马健霄，仲小飞.公交服务半径及服务水平研究[J].森林工程，2011，27(1)：61-64.