出租车调度问题是交通运输与智能制造等领域中的重要问题, 其应用场景在生产生活中广泛存在.
出租车调度问题主要研究如何确定一系列从同一个车库出发的出租车的行驶路径, 在每辆车均不超载且在指定时间窗内到达接送订单起点和终点的前提下, 确保各乘客的乘车时间和各车辆的行驶时间分别不超过给定上限, 在此基础上最小化所有车辆的行驶时间之和.
比如网约车平台的派单过程中, 出租车同时能服务的订单数或搭载的乘客人数 (拼车) 有限, 且每个订单的对上下车时间有要求, 网约车平台需要调度出租车用最短的工时完成所有接送订单.
比如芯片代工厂中的物料传送系统的运行过程中, 运输车能够装载的晶圆数量有限, 且上层生产排程系统对每道工序的开工时间有要求, 物料传送系统需要调度运输车用最短的时长完成所有运输任务.
因此, 高效的出租车调度问题的求解算法在理论上与实践上均意义重大.

出租车调度算法训练

问题概述

给定一个有向完全图, 图中包含一个车库节点和若干客户节点.
同时给定一系列乘车请求, 每个请求包含一个上车节点和下车节点, 需由同一辆车分别在对应的时间窗内完成接送 (提前到达可先原地等待), 上下客花费固定的时间.
此外, 每辆车的最大载客量相同且均需从车库出发最后回到车库, 同时任意两点间的最短行驶时间已知.
最后, 每个乘客上车后到下车前的乘车时间与每辆车从车库出发到返回车库的出勤时间分别不得超过给定上限.
请确定使用几辆车参与配送, 并给出每辆车依次访问的有序节点列表, 使得所有车辆的总行驶时间 (不包括停车等待和上下客时间) 最短.

  • 参考文献.
    • [1] T. Gschwind and M. Drexl, “Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem,” Transportation Science, vol. 53, no. 2, pp. 480–491, 2019, doi: 10.1287/trsc.2018.0837.
    • [2] S. C. Ho, W. Y. Szeto, Y. H. Kuo, J. M. Y. Leung, M. Petering, and T. W. H. Tou, “A survey of dial-a-ride problems: Literature review and recent developments,” Transportation Research Part B: Methodological, vol. 111, pp. 395–421, May 2018, doi: 10.1016/j.trb.2018.02.001.
    • [3] Y. Molenbruch, K. Braekers, and A. Caris, “Typology and literature review for dial-a-ride problems,” Annals of Operations Research, vol. 259, no. 1, Art. no. 1, Dec. 2017, doi: 10.1007/s10479-017-2525-0.
    • [4] S. Ropke and D. Pisinger, “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows,” Transportation Science, vol. 40, no. 4, pp. 455–472, 2006, doi: 10.1287/trsc.1050.0135.

命令行参数

请大家编写程序时支持两个命令行参数, 依次为运行时间上限 (单位为秒) 和随机种子 (0-65535).
算例文件已重定向至标准输入 stdin/cin, 标准输出 stdout/cout 已重定向至解文件 (如需打印调试信息, 请使用标准错误输出 stderr/cerr).
例如, 在控制台运行以下命令表示调用可执行文件 darp.exe 在限时 300 秒, 随机种子为 12345 的情况下求解路径为 ../data/pr01.txt 的算例, 解文件输出至 sln.pr01.txt:

1
darp.exe 300 123456 <../data/pr01.txt >sln.pr01.txt

  • 运行时间上限.
    • 超出运行时间上限后测试程序会强行终止算法, 请确保在此之前已输出解 (最好还能自行正常退出).
  • 随机种子设置.
    • 使用 C 语言随机数生成器请用 srand.
    • 使用 C++ 随机数生成器 (如 mt19937) 请在构造时传参或调用 seed() 方法设置.

输入的算例文件格式

所有算例的节点和车辆分别从 0 开始连续编号, 所有节点分布于平面直角坐标系中.
节点 0 为车库, 即车辆的起点和终点, 其服务时间, 乘客数量, 时间窗开始时间均为 0.

第一行给出 5 个由空白字符分隔的整数, 分别表示接送请求数 N, 最大可用车辆数 K, 各车辆的载重量上限 Q, 各车辆最长行驶时间 T, 以及各乘客的最长乘车时间 L.
接下来连续 2N+1 行, 每行包含 6 个由空白字符分隔的数字 (前 2 个为实数, 后 4 个为整数), 第 i 行的 6 个数字依次表示第 i 个节点的 x 坐标, y 坐标, 乘客数量, 最短停留时间 (服务时间), 最早到达时间, 最晚到达时间.
其中编号在 [1, N] 范围内的节点为乘客上车节点, 乘客数量为正数, 每个上车节点 i 的下车节点为 i+N, 乘客数量为其相反数.

例如, 以下算例文件表示有 2 个接送请求 (5 个节点) 和 3 辆车, 每辆车的容量为 10, 车辆最长行驶时间为 25, 乘客最长乘车时间为 15; 其中,
节点 0 的坐标为 (1.234, 5.456), 乘客数量为 0, 最短停留时间为 0, 时间窗开始和结束时间分别为 0 和 30;
节点 1 的坐标为 (2.000, 1.000), 乘客数量为 1, 最短停留时间为 3, 时间窗开始和结束时间分别为 4 和 5;
节点 2 的坐标为 (3.000, 7.000), 乘客数量为 2, 最短停留时间为 4, 时间窗开始和结束时间分别为 5 和 6;
节点 3 的坐标为 (6.000, 8.000), 乘客数量为 -1, 最短停留时间为 5, 时间窗开始和结束时间分别为 6 和 7;
节点 4 的坐标为 (8.000, 8.000), 乘客数量为 -2, 最短停留时间为 6, 时间窗开始和结束时间分别为 7 和 8:

1
2
3
4
5
6
2 3 10 25 15
1.234 5.456 0 0 0 30
2.000 1.000 1 3 4 5
3.000 7.000 2 4 5 6
6.000 8.000 -1 5 6 7
8.000 8.000 -2 6 7 8

注意, 本问题所用算例集中假设行驶时间等于两点间的距离, 目前的距离计算使用截断保留 3 位小数的欧氏距离 ($t = \lfloor 10^3 d \rfloor / 10^3$), 具体计算方式以 SDK 中的代码为准.

输出的解文件格式

输出 V 行整数表示 V 辆车 (V $\le$ K) 的行驶路径, 第 i 行第 j 个整数表示第 i 辆车经过的第 j 个客户节点.

例如, 以下解文件表示 2 辆车的行驶路径; 其中,
车辆 0 从车库 0 出发后依次经过节点 1 和 3, 最后回到车库 0;
车辆 1 从车库 0 出发后依次经过节点 2 和 4, 最后回到车库 0:

1
2
1 3
2 4

提交要求

  • 发送至邮箱 szx@duhe.tech.
  • 邮件标题格式为 “Challenge2023DARP2d-姓名-学校-专业“.
  • 邮件附件为单个压缩包, 文件名为 “姓名-学校-专业“, 其内包含下列文件.
    • 必要 算法的可执行文件 (Windows 平台).
    • 必要 算法源码.
      • 可重入 (可在同一线程内反复调用而不会出现数据初始化错误或内存泄漏).
      • 可并发 (可在同一进程内的多个线程同时运行多个算法求解实例而互不干扰, 满足此要求一般不能有全局的非只读变量).
      • 可伸缩 (数据结构可以根据算例规模动态申请内存, 而非根据预先指定的编译期常量进行内存分配).
    • 可选 算法在各算例上的运行情况概要, 至少包括以下几项信息 (仅在无法成功调用算法输出可通过检查程序的解时作为参考).
      • 算例名.
      • 使用的车辆数.
      • 所有车辆的行驶时长总和.
      • 计算耗时.
    • 可选 算法在各算例上求得的路径总长度最短的解文件 (仅在无法成功调用算法输出可通过检查程序的解时作为参考).
  • 其他所有问题通用的要求见 SmartLab Challenge - ReadMe.

例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
苏宙行-华科-计科.zip
|   darp2d.exe
|   results.csv
|
+---src
|       main.cpp
|       algorithm.cpp
|       algorithm.h
|
+---results
        pr01.n101v25c200.txt
        pr02.n101v25c200.txt
        ...

算例清单

下载地址: https://gitee.com/suzhouxing/npbenchmark.data/tree/data/DARP2d/Instance

pr01.r24v3c6t480l90
pr02.r48v5c6t480l90
pr03.r72v7c6t480l90
pr04.r96v9c6t480l90
pr05.r120v11c6t480l90
pr06.r144v13c6t480l90
pr07.r36v4c6t480l90
pr08.r72v6c6t480l90
pr09.r108v8c6t480l90
pr10.r144v10c6t480l90
pr11.r24v3c6t480l90
pr12.r48v5c6t480l90
pr13.r72v7c6t480l90
pr14.r96v9c6t480l90
pr15.r120v11c6t480l90
pr16.r144v13c6t480l90
pr17.r36v4c6t480l90
pr18.r72v6c6t480l90
pr19.r108v8c6t480l90
pr20.r144v10c6t480l90
a2-16.r16v2c3t480l30
a2-20.r20v2c3t600l30
a2-24.r24v2c3t720l30
a3-18.r18v3c3t360l30
a3-24.r24v3c3t480l30
a3-30.r30v3c3t600l30
a3-36.r36v3c3t720l30
a4-16.r16v4c3t240l30
a4-24.r24v4c3t360l30
a4-32.r32v4c3t480l30
a4-40.r40v4c3t600l30
a4-48.r48v4c3t720l30
a5-40.r40v5c3t480l30
a5-50.r50v5c3t600l30
a5-60.r60v5c3t720l30
a6-48.r48v6c3t480l30
a6-60.r60v6c3t600l30
a6-72.r72v6c3t720l30
a7-56.r56v7c3t480l30
a7-70.r70v7c3t600l30
a7-84.r84v7c3t720l30
a8-64.r64v8c3t480l30
a8-80.r80v8c3t600l30
a8-96.r96v8c3t720l30
b2-16.r16v2c6t480l45
b2-20.r20v2c6t600l45
b2-24.r24v2c6t720l45
b3-18.r18v3c6t360l45
b3-24.r24v3c6t480l45
b3-30.r30v3c6t600l45
b3-36.r36v3c6t720l45
b4-16.r16v4c6t240l45
b4-24.r24v4c6t360l45
b4-32.r32v4c6t480l45
b4-40.r40v4c6t600l45
b4-48.r48v4c6t720l45
b5-40.r40v5c6t480l45
b5-50.r50v5c6t600l45
b5-60.r60v5c6t720l45
b6-48.r48v6c6t480l45
b6-60.r60v6c6t600l45
b6-72.r72v6c6t720l45
b7-56.r56v7c6t480l45
b7-70.r70v7c6t600l45
b7-84.r84v7c6t720l45
b8-64.r64v8c6t480l45
b8-80.r80v8c6t600l45
b8-96.r96v8c6t720l45