提升带垫层液位(Pad Levels)约束的加油站补货问题(Petrol Station Replenishment Problem with Pad Levels, PSRPPL)成品油配送效率的研究

《Results in Engineering》：Enhancing Distribution Efficiency of Oil Products in a New Variant of Fuel Replenishment Problems: Petrol Station Replenishment Problem with Pad Levels

　　

摘要：本文研究了一类加油站补品问题(Petrol Station Replenishment Problem, PSRP)的新变体——即带垫层液位(Pad Levels)约束的加油站补货问题(Petrol Station Replenishment Problem with Pad Levels, PSRPPL, 简称PSRPPL)，该问题关注城市区域内成品油配送，其区别于文献中其他PSRP之处在于引入了垫层液位(pad level)限制，要求油罐车各隔舱须按特定固定液位装载且所有隔舱离库时必须满载(非空载)。研究人员探讨并求解了两种PSRPPL情形：即每车次最多访问一站点的PSRPPL-0，以及放宽至常规罐车最多访问两站、超大罐车最多访问三站的PSRPPL-1。研究人员采用改进的自适应大邻域搜索(Adaptive Large Neighborhood Search, ALNS)框架进行求解，与传统ALNS仅依赖破坏-修复算子不同，所提ALNS进一步嵌入局部搜索(Local Search)和多起点(Multi-start)过程。基于140组假设算例及7组真实世界算例，研究人员发现所提启发式算法具显著有效性——在求解时间与解质量上均优于CPLEX，尤其中大规模复杂PSRPPL算例中表现突出。研究人员亦发现多起点(Multi-start)过程对获取更优解有关键作用，从而增强了ALNS启发式的性能。最后，允许每车次访问更多站点(PSRPPL-1)可大幅降低总运营成本，鉴于补货成本占分销业务主要比重，此改进具重要实践价值。

论文解读：

【研究背景与开展情况】

加油站补货问题(Petrol Station Replenishment Problem, PSRP)是下游石油供应链中典型且具挑战性的组合优化问题，属于多隔舱车辆路径问题(Multi-compartment Vehicle Routing Problem, MCVRP)的衍生变体。实践中成品油由炼油厂经异质车队(常规罐车与超大罐车)配送至分散加油站，罐车隔舱无计量仪(debit meter)须整舱卸载(unsplit-tank)，且需同时决策隔舱装载方案与行车路径以最小化运输总成本。现有PSRP文献未涉及"垫层液位(Pad Level)"约束——即因安全防窃考量，泰国某大型炼油企业罐车隔舱只可按若干预设容积刻度(pad level)装载油品，且离库时所有隔舱必须占用(非全空)，致使装载组合复杂度剧增。此外该企业现行政策限定常规罐车单程单站点直发，超大罐车单程最多两邻近站点(相距≤50km)，部分城区站点无法接纳超大罐车，每日通行时段受限(晚7点至早6点)，常规/超大罐车载卸耗时分别为60min与120min。补货成本占成品油物流总成本60%–70%，现有调度方式分区手工制定，难以应对pad level带来的组合爆炸。为此研究人员首次定义带垫层液位的加油站补货问题(Petrol Station Replenishment Problem with Pad Levels, PSRPPL)，建立PSRPPL-0(现行政策)与PSRPPL-1(放宽至多双drop/三drop)的混合整数规划(Mixed Integer Linear Programming, MILP)模型，设计嵌入局部搜索与多起点(Multi-start)的改进自适应大邻域搜索(Adaptive Large Neighborhood Search, ALNS)启发式进行求解，并通过假设算例与真实算例验证算法及多站点拼装策略之效益。该文发表于《Results in Engineering》。

【关键技术方法】

研究人员首先构建PSRPPL-0与PSRPPL-1之MILP数学模型，含节点集合V={炼厂?∪加油站C}，常规罐车集合N(5隔舱，总容15000–20000L)、超大罐车集合M(8隔舱，总容34000–44000L)，各隔舱具离散pad level集合，目标函数为最小化车队固定启用费+行驶费+超量配送惩罚费(excess delivery penalty)。为求解NP-hard之大规模实例，研究人员设计改进ALNS启发式：①初始解由IntGen算法生成——含RandT(随机罐车任务生成)、MultiPS(多站点任务合并)、PadAdj(按最小超量原则指定pad level)、Greedy(最小空闲时间车辆指派)；②破坏算子含Random/Worst/Shaw Removal及2-OPT、3-OPT扰动，并引入两种Multi-start算子——Random Tank Truck Assignment(D?)与Random Trip Assignment(D?，按油站-油品对而非油站生成任务)；③修复算子含Random/Greedy/Regret-2/Regret-3 Insertion；④接受准则采用模拟退火(Simulated Annealing, SA)，权重调整(Weight Adjustment, W-adj)依据算子历史表现更新。参数经标定：初始温度T_start=10?，冷却率r_c=0.99，无改进最大迭代数10000，移除任务数q∈[2,4]，奖励权重δ?=3(新全局最优)、δ?=2(迭代改进)、δ?=1(接受劣解)。算例来源为140组假设算例(5–20站、2–5油品、隔舱2–8个、2 pad levels)及泰国炼油企业7组真实区域算例(约14–16站)，对照基准为CPLEX 12.6.3(时限6小时)。

【研究结果】

Introduction(引言)：综述PSRP及MCVRP相关文献，指出现存研究未考虑pad level约束与异质车队多隔舱非连续装载组合，确立PSRPPL为新变体及本研究创新点，阐明ALNS改进方向与研究贡献。

Problem Description(问题描述)：形式化描述PSRPPL网络——单炼厂、多加油站、异质罐车(常规N/超大M)、多油品P、隔舱K_N(5格)与K_M(8格)、pad level集L_N与L_M、日最大趟次R、时间窗B。明确约束含：需求满足(允许受罚超量)、站储容上限、每隔舱单油品单pad level装载、超大罐车隔舱不得混装不同站油品、所有隔舱离库满置(通过Eq.7–10强制)、时间衔接与归库时限(Eq.11–16)、每趟单/双/三站点访问限制(依PSRPPL-0/PSRPPL-1)、车次顺序性及低编号车辆优先派发(Eq.17–24)、车队启用关联固定费用。给出PSRPPL-1扩展定义——常规车最多两站配对集U、超大车最多三站三元组集V，相应修改访问与隔舱分配变量。

Mathematical Formulation of the PSRPPL-0 / PSRPPL-1(数学模型)：给出PSRPPL-0完整MILP公式含目标函数(式1，三部分成本加权和)及26条约束(需求平衡、储容、隔舱单载、隔舱混装禁止、全隔舱装载、时间窗、访问次数、序列一致性、车队启用)。PSRPPL-1将单站访问变量扩展为配对U与三元组V访问变量，放宽常规车至|U|中配对(≤2站)、超大车至|V|中三元组(≤3站)，其余约束系统类推(附录A详述)。

Solution Methodology(求解方法)：阐述标准ALNS框架后说明改进之处——初始解构造(IntGen四阶段)、七种破坏算子(D?–D?，D?/D?为Multi-start不含修复直接产出完整解)、四种修复算子(R?–R?含Regret-k插入)、SA接受劣解机制(式28指数概率)、W-adj动态权重更新(δ?–δ?)。强调Random Trip Assignment(D?)生成更异构初始解以跳出局部极值。

Computational Results(计算结果)：

• •
  Parameter Tuning(参数调优)：通过小规模算例标定最佳参数为T_start=10?，无改进终止10000 iter，权重(1-2-3即δ?-δ?-δ?)。
• •
  Hypothetical PSRPPL Instances(假设算例)：CPLEX在中小规模(≤100站以下组)可得较优解但耗时长(平均数千秒)，大规模(101–140组)因内存溢出常无解或gap>88%；所提ALNS耗时仅为CPLEX约2%–5%且在中小规模与CPLEX偏差<2.2%，大规模实例ALNS解显著优于CPLEX(Instance 121–140 PSRPPL-0目标值改善-25.85%，PSRPPL-1改善-34.84%)。PSRPPL-1较PSRPPL-0平均降本约2.91%，超量配送降约1.72%，总行驶距降约3.13%。破坏算子统计显示D?(Random Trip Assignment Multi-start)在97%(PSRPPL-0)/96%(PSRPPL-1)算例中为主导算子。
• •
  Real-World Instances(真实算例)：七组真实区域实例CPLEX大多达时限仍留高gap，ALNS平均提速75%–97%且获更优或相当目标值(部分实例改善-20%至-36%)，但因现行订单量大接近单车容量，多drop策略(PSRPPL-1)在真实例中增量效益有限(仅Instance 5显现2.71%降本)，指出若改为小批量订单或VMI(供应商管理库存, Vendor Managed Inventory)模式可放大multi-drop效益。
• •
  ALNS Performance Analysis(ALNS性能分析)：对比不同算子组合，仅含基础破坏(D?–D?)之ALNS平均差CPLEX约4.71%以上，加入D?改善1.45%、加入D?改善4.65%，全七算子效果近含D?版，证实Multi-start尤Random Trip Assignment对PSRPPL问题空间探索至关重要。

【讨论与结论翻译】

研究结论如下：本文首次提出并定义带垫层液位(Pad Levels)约束之加油站补货问题(PSRPPL)及其两种政策——现行单/双drop(PSRPPL-0)与放宽双/三drop(PSRPPL-1)，建立MILP模型并设计嵌入局部搜索与多起点(Multi-start)之改进自适应大邻域搜索(ALNS)启发式。经140组假设算例与7组真实世界算例验证，所提ALNS在计算时间(平均仅为CPLEX之数百分比)与解质量(中小规模偏差<2.2%，大规模明显优于CPLEX最优已知解)上均具优势，多起点过程尤Random Trip Assignment对逃离局部极值起关键作用。允许更高每车次访问数(PSRPPL-1)可降低总运营成本约2.91%均值并减少超量配送与行驶距离，对大型分销商具潜在显著效益。此外该决策支持工具可大幅减轻计划员工作量，并可用于评估订单策略变更(如导入VMI)对补货运营之影响。虽ALNS专为PSRPPL设计，其框架经修改可推广至带计量仪或其他特征之PSRP情形，未来可纳入安全、拥堵、环境排放等因素构建更可持续运输方案。