链上镖师 / Chain Biaoshi
CIE|乘客—包裹共载请求：兼容约束下的异构车队路径优化
把请求级冲突、时间分离与容量限制纳入同一套共载调度框架
论文面向预约制、集中式乘客—货运共载服务，将请求级不兼容、异构车队、时间窗和分舱约束纳入利润最大化路径规划，并用定制ALNS支持大规模求解。
- 01：研究对象：乘客与包裹共享车辆时的请求分配、路径、时序和装载决策。
- 02：核心方法：混合整数线性规划与带兼容性破坏—修复机制的自适应大邻域搜索。
- 03：主要发现：不可兼容率约超过30%、紧急请求比例超过50%后，服务可行性明显下降。
乘客与包裹共载的调度难点
乘客—包裹共载能够提高车辆利用率，适用于预约制、需求响应式和低密度区域交通服务。车辆需要同时满足乘客的准时服务、最大乘坐时间与绕行容忍度，以及包裹的装卸、容量、时间窗和分舱要求。请求之间的冲突还会随空间分布、紧急程度和需求构成变化，直接影响可行路线、服务率、车辆数量和系统利润。
01乘客请求：强调独立上下车、服务时间窗和最大乘坐时间。
02包裹请求：允许在乘客站点之间插入，受货运容量、装卸时间和分舱规则约束。
03系统目标：最大化已服务请求收入，扣除车辆固定雇佣成本与距离相关运营成本。
论文将兼容性细化到请求对层级：两个请求可被同车分配时，服务区间需要满足相应的时间关系；不兼容请求允许共用车辆的条件是服务时段严格分离。
请求级兼容性建模：从配对矩阵到时间分离
模型在有向路网上同时决定车辆行驶弧、请求分配、到达时间、乘客流和货物流。二元兼容矩阵π记录请求对是否允许并行服务。对于同车分配的不兼容请求，辅助二元变量决定先后顺序，配合大M时间约束保证一个请求完成后另一个请求才能开始；请求分配、取送先后、时间窗、乘客乘坐时间和车辆服务时段共同限定可行解。
Fig. 1：请求兼容时的可行服务顺序与时间关系。
1建立乘客请求、包裹请求、车辆和取送节点集合。
2用π记录请求对兼容状态，用时间变量描述服务先后。
3对不兼容请求启用先后顺序变量，强制服务区间不重叠。
4用容量流、时间窗和最大乘坐时间检验路线可行性。
请求级时间分离让模型能够识别具体请求之间的冲突，适配乘客与包裹混合流、异构车辆和独立货舱等运营条件。
ALNS求解框架：破坏、插入与冲突修复
精确MILP适合小规模实例，需求规模扩大后求解难度快速上升。论文据此设计兼容性感知的ALNS：每轮先移除部分请求，再以自适应插入算子重建路线，并通过模拟退火接受规则保留具有潜力的候选解。算法评价函数同时计算利润与容量、服务时长、时间窗、乘客乘坐时间和兼容性惩罚。
Algorithm 1：面向乘客—货运共载问题的自适应大邻域搜索流程。
阶段 1 初始化：按增量目标与约束可行性构造路线。
阶段 2 破坏：优先移除造成兼容性冲突的请求。
阶段 3 修复：兼容性惩罚插入，降低潜在重叠位置的选择概率。
阶段 4 后处理：通过交换或重新定位消除不兼容请求的时序重叠。
阶段 5 更新：依据新最优、改进解和接受解的表现调整算子权重。
专用不兼容修复算子扫描每条路线，识别请求取件点位于另一请求取件与送达之间的重叠结构。算法优先尝试交换送达点与取件点，随后尝试将冲突请求移至下一个可行位置。每次移动都需要重新满足取送先后、时间窗和容量约束。
合成算例中的算法基准比较
实验覆盖散点—散点、散点—聚类、聚类—散点和聚类—聚类四种空间布局，请求规模从10扩展到100，配置10辆异构车辆、30%不可兼容率和1∶1乘客—包裹构成。ALNS与模拟退火使用相同随机种子、迭代预算和退火参数，Gurobi以7200秒作为精确求解时限，比较利润、最优差距、运行时间和多次运行稳定性。
Table 7：SS场景下Gurobi、SA与ALNS的性能比较。
Fig. 5：不同不可兼容水平下的车辆路线结构。
小规模实例
ALNS达到接近最优解
大规模实例
ALNS持续优于模拟退火基线
结果显示，空间聚类能够提升路线效率与系统利润；不可兼容性增加会压缩合法请求配对，促使路线重组并增加服务成本。
云林康复巴士案例：从实验参数到区域验证
真实案例来自台湾云林县康复巴士服务，重点分析第3至第6区。实例依据历史预约节奏生成请求，起点采样自居民区，目的地根据医疗设施和返程需求的经验权重确定，行驶时间来自经过裁剪的OpenStreetMap网络最短时间路径。车辆类型与不可兼容关系编码轮椅、空间和服务约束，第6区用于体现高龄人口占比较高区域的服务压力。
Fig. 10：云林县11个区域及重点分析的第3至第6区。
Table 21：云林第3至第6区实例参数的统计范围。
案例参数覆盖不同请求规模、乘客—包裹构成、不可兼容率、收入、车辆成本、时间窗和容量。部分精确参数因运营方数据保密协议未披露，论文提供了范围与均值，并在附录中说明预约时间分布、目的地采样和拟合检验过程。
Table 26：云林第3至第6区30%不可兼容率下ALNS与SA的比较。
敏感性结果：冲突、紧急程度与需求构成
场景分析揭示三类灵活性损失。不可兼容率提高会逐步减少合法配对，利润和服务率随之下降；紧急请求比例提高会压缩时间可行域，超过50%后服务率下降更加明显；包裹占比变化会改变乘客与货运请求的服务平衡，极端构成带来更高的调度低效。空间聚类能够改善路线组织，缓解部分距离与成本压力。
Fig. 6：紧急程度对服务水平与经济指标的影响。
Table 15：包裹请求占比对服务结果的影响。
不可兼容率
约超过30%后服务可行性明显下降
紧急请求比例
超过50%后服务率出现明显压力
云林案例从0%提升至完全不兼容时，服务请求率下降16—21个百分点，利润下降15%—42%，行驶距离增加28%—57%。
运营策略：拒单与部分外包如何缓冲约束压力
论文进一步比较拒单、部分外包和定价敏感性。允许拒绝不可行请求能够减少路线拥堵、车辆投入和总行驶距离，并改善利润目标下的路线组织。部分外包将ALNS无法承接的请求交由外部服务商处理，在不增加内部车辆资源的情况下恢复约50%的未服务请求，平均总成本相对基准增加11.5%。外包比例与价格参数需要结合需求规模和服务成本校准。
Fig. 7：部分外包策略对路线配置的影响。
✓以不可兼容率和紧急请求比例作为容量预警指标。
✓在高约束时段保留拒单机制，避免强制履约造成路线拥堵。
✓用部分外包承接难以内部服务的请求，持续监测成本增幅。
✓根据乘客—包裹需求构成调整车辆、分舱和时间窗配置。
研究结果支持分层服务策略：核心请求优先由内部车队承接，冲突请求通过拒单、重排或外包进行调节，运营方以利润、服务率、距离和车辆使用量共同评估策略效果。
模型适用条件与研究边界
模型面向集中式、静态、提前一天规划的预约制服务，运行在已知行驶时间的有向网络上。服务时长按固定值建模，乘客请求受到最大乘坐时间与时间窗约束，包裹请求使用更宽时间窗并承担装卸和容量限制。论文明确指出，部分云林参数因数据保密仅提供范围和均值。
- 适用对象：需求响应式交通、康复巴士和具备灵活路线的乘客—货运共载服务。
- 关键条件：请求级兼容关系、异构车辆、独立分舱、取送先后和时间窗可被量化。
- 外推范围：论文未报告固定班次公交、动态实时订单、随机行驶时间或超出案例参数范围的系统表现。
论文：Combined passenger-and-parcel delivery problem with request incompatibility
作者：C.S. Shui，Yu-Syuan Chang
期刊：Computers & Industrial Engineering
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
