2017 年湖南省研究生数学建模竞赛题目
A 题：出租车合乘业务系统设计
出租车合乘业务是指路线相同或相近的两位或多位乘客共同乘坐同一辆出租车出行，系统根据合乘人数、乘车时间、实际路线等因素，分别计算出每位乘客的车费（通常低于各自独乘时的车费）。司机收入则为所有乘客支付的车费总和。该业务可以在不增加运营车辆总数的情况下提高运力，有助于缓解打车难，而且能够降低乘客出行成本，同时提高司机收入。因此，相当一部分乘客、司机愿意接受该业务，特别是在打车的高峰时段。
某出租车公司拟开展合乘业务。通过调研发现，其他城市或公司的合乘业务主要有以下两种模式。
1. 相同起点模式。合乘乘客必须在同一地点上车，顺路去往相同或不同的目的地。合乘乘客各支付共同路段车费的a%（两人合乘时，50 < a < 100，如北京 60，烟台 70，重庆 80）。不允许一人先上车，中途再招揽其他乘客。该模式只需要改造计价器，不需要其他软件支持，并且计费原则简单明了。但该模式构成合乘的条件较严格，合乘比例偏低。
2. “一口价”模式。利用网上调度系统和手机打车软件，在同意合乘的前提下，乘客通过手机软件提交打车请求（起始位置等信息），系统根据历史数据预估车费，显示为“一口价”，即乘客若接受该报价，则无论实际乘车过程中是否有合乘，均按此一口价结算。该价格一般低于正常的车费。系统针对当前打车需求信息，动态调度合乘路线。该模式对乘客友好，便于控制乘车费用，而且合乘条件低，合乘方案灵活，可以提高合乘比例。但该模式可能出现绕行，引发乘客不满。若全程无法构成合乘，影响司机收入，引发司机不满。
请尝试设计新的合乘模式，充分调动乘客、司机等各方参与合乘的积极性（假设不需要考虑对公司现有调度平台和手机打车软件的改造难度）。请完成以下任务：
1. 请设计高效的合乘方案及其相应算法，使乘客等待时间尽量短，所需出租车数量尽量少。
2. 请设计与合乘方案相应的合理的车费计算方法。
3. 假设某城市的路网为正方形网格，网格边长 500 米，道路均可双向行驶。附件 1 是该城市某日某时刻之前 3 分钟内的打车需求数据，附件 2 是当前空驰出租车的位置信息，请按照你们设计的合乘方案给出具体的计算结果，并按附件 3 中指定的格式输出结果。假设，附件 2 中未涉及的出租车在计算合乘方案时不可用（非空驰，不考虑），并且合乘方案不要求用到附件 2 中的全部出租车，即，允许部分出租车仍保持空驰状态。乘客等待时间均以当前时刻为 0 时刻开始计时，即，不考虑之前 3 分钟内已经等待的时间。
附件 1：某市打车数据
requests.csv 文件中给出该城市某日某时刻 3 分钟内的打车需求数据。假设打车客户均为 1 人。文件以英文逗号“,”分隔，共有 5 列数据，分别为：
person_ID: 客户编号
pickup_x: 上车地点 x 坐标（单位：km）
pickup_y: 上车地点 y 坐标
dropoff_x: 下车地点 x 坐标
dropoff_y: 下车地点 y 坐标
附件 2：当前空车信息
taxi.csv 文件中给出当前的空车位置信息。假设出租车均为 4 座车，即，除司机外，至多可搭乘 3 位客人。文件以英文逗号“,”分隔，共有 3 列数据，分别为：
taxi_ID: 车辆编号
now_x: 当前位置 x 坐标
now_y: 当前位置 y 坐标
附件 3：输出文件格式
• 合乘方案的计算结果必须按以下格式输出
• 与费用相关的计算结果，自行设计输出文件格式
• 合乘方案计算结果的文件名格式为“队号-plan.txt”，如“201718001001-plan.txt”。
• 如果有多个计算结果（比如，不同算法或不同参数值对应的计算结果），则顺序编号，如“201718001001-plan-01.txt”、“201718001001-plan-02.txt”
等，并且务必请在正文中说明输出文件与所用算法或参数值的对应关系。
合乘方案输出文件格式如下：
N
taxi_1, p1u, p2u, p1d, p2d
taxi_2, p3u, p4u, p4d, p3d, p5u, p5d
…
taxi_N, pau, pbu, pbd, pad
第一行整数 N 表示合乘调度方案实际使用到的出租车数量，之后 N 行每一行表示一
辆出租车的接送客顺序，整个文件共 N+1 行。taxi_x 为车辆编号，应与 taxi.csv 中的车辆编号吻合。p1u 中 p1 表示第一位乘客的 person_ID，u 表示上车，d 表示下车。比如第二行“taxi_1, p1u, p2u, p1d, p2d”表示出租车 taxi_1 先接 p1 上车，再接 p2 上车，再送 p1
到目的地下车，再送 p2 到目的地下车。其中，person_ID 应与 requests.csv 中的 person_ID 吻合。具体格式请参考 sample-plan.txt 文件。
