导读
本论文于2022年发表于交通领域顶级期刊《Transportation Research Part B: Methodological》。论文聚焦于拥堵交通环境下城市物流的“富”弧路径问题（RARP），目标是提出一种简洁的时变行程时间表征方法，并将其嵌入至RARP建模过程，从而为现实RARP提供行之有效的解决方案。首先提出一种解析的流体排队模型，用于标定时变的路段行程时间，在此基础上解析推导出车辆路径优化产生的社会影响表达式。论文开发了两种时变行程时间表征方法，包括离散的时间扩展表示方法和非线性多项式表示方法；在此基础上，建立了三种RARP模型；最后，开发了基于拉格朗日松弛和分支定价的两类精确式求解算法；以洒水车路径优化应用为例，基于一系列数值实验证实了所提出方法、模型及算法的有效性。本文开源代码库可以在Github上找到，网址为https://github.com/jiawlu/time-dependent-vrp-bnp
关键词：城市物流；富弧路径问题(RARP)；时间依赖（时变）的行程时间；社会影响；拉格朗日松弛；分支定价
研究背景
高效的城市物流系统有助于降低运营成本、缓解交通拥堵、保护环境、应对气候变化以及提升经济活力。考虑到城市交通拥堵的广泛存在，拥堵交通环境下的“富”弧路径问题（Rich Arc Routing Problems，简称 RARPs）在近些年得到了研究人员的广泛重视。这里的“富”体现在：除了经典ARP中的常规约束（如容量约束和时间窗口约束），建模过程中还需要考虑一些面向特定领域问题的约束。例如，冬季铲雪车路径规划问题中，车辆的行进路线需要考虑车道相关的约束。这些 “富”约束具有重要的现实意义，同时也为建模与求解带来额外的挑战。鉴于此，本文旨在提出能够系统考虑多种“富”特征的RARP建模与求解方法。
交通网络中最重要的一类“富”特征是时变的交通状况，对应规划车辆在服务时经历的时变道路行程时间。早期的车辆路径问题（VRP）和弧路径问题（ARP）研究中，路段上的行程时间通常被视为恒定的或时间独立的。然而，在拥堵的城市网络中，基于恒定行程时间的解决方案可能会严重低估交通延误产生的影响。尽管最近有部分VRP研究利用分段行程时间函数来表征时变的交通状况，但精确表征时变的行程时间仍充满挑战性。需要指出的是，大多数ARP研究将行程时间进行了简化表征或处理。
现有研究主要存在的不足：（1）对时变的交通状况进行了简化或忽略；（2）服务车辆对交通系统的影响未得到充分考虑；（3）针对“富”约束特征缺乏深入调研和比较；（4）聚焦于启发式求解算法，在精确式求解算法方面缺乏针对性探究。
本文的主要创新点和贡献：
在建模过程中系统考虑了城市物流中服务车辆运营成本及其对交通运输系统产生的社会影响
基于流体排队模型，提出了非线性时变行程时间表征方法，同经典的分段线性函数表征方法相比，所提出方法形式更为简洁，也更易标定，同时具有可微性，有利于解析和推导服务车辆对时变交通网络的影响
开发了三种RARP优化模型，针对“富”约束条件对建模复杂度的影响进行了深入分析
以洒水车路径规划问题为RARP的代表性案例，定制开发了基于拉格朗日松弛和基于分支定价的精确式求解算法
研究问题
在拥挤的城市街道网络中，洒水车车队需要沿着城市街道完成洒水与清洗路面任务，建模的目标是为洒水车队确定一组最优路线，在考虑社会影响的同时以最小的总成本完成洒水清洁任务。研究问题本质上属于带时间窗口和容量限制约束的弧路径问题（CARPTW），在此基础上考虑了以下“富”特征：
（1）城市交通网络上时变的交通状况
（2）路口的转向延误
（3）在某些路段上需要完成多次洒水任务
（4）需要在加水站完成加水，以确保有充足的水量能完成任务
给定交通网络 G=(N，L)，其中 N和L 分别表示道路节点和路段的集合。每个路段(i，j)∈L都与一个洒水任务相关联，即路段(i，j)必须在时间窗口[s_i_j，e_i_j]内清洁m_i_j次，其中s_i_j 和e_i_j分别表示最早服务和最晚服务时间。车辆在路段(i，j)上完成一次洒水将消耗w_i_j单位的水量。节点集合N中包含一些加水站节点。
本研究考虑以下假设：(a)洒水车一旦开始清洁路段，必须一次性清洁完成整个路段而不能中途加水再完成剩余路段的清洗；(b) 洒水车加满水所用的时间是固定的；(c) 洒水车从起始节点出发时满容量，且由于假设(a)，每个路段(i，j)的水消耗w_i_j不应超过洒水车最大容量C。若w_i_j大于C，路段(i，j)将被分割成多条短路段。优化的总成本为TOC+ω×TSIC，其中，TOC和TSIC分别代表运营总成本和系统影响总成本，ω是一个用户自定义的权重，用于衡量社会影响在解决方案中的重要性。总运营成本TOC包括洒水车购置成本和总行程时间成本。假设所有洒水车类型相同，且每辆洒水车购置成本为h。本研究假定可用的洒水车数量无限。每辆洒水车的行程时间成本为离开仓库和返回仓库之间的时间差，包括四部分：清洁时间、空驶时间、等待时间和加水时间。空驶意味着洒水车穿过道路路段而不清洁该路段，可能出现两种情形：(a) 路段不需要清洁或已经被清洁；(b) 洒水车用完水正前往加水站。对于每条路段，空驶时间DT(t)和清洁时间CT(t) 通过公式(1)和(2)计算：
其中， w(t)是时变路段延误，在后续小节给出推导公式；LL表示路段长度；v_d和v_c分别表示洒水车在空驶模式和清洁模式下的最快速度。等待时间指洒水车到达路段时刻与其开始服务时刻之差。
图1展示了一个简单的任务网络和洒水车路线示例。网络由17个节点组成，车辆出发点位于节点0，两个加水站分别位于节点11和12。橙色线表示一个示例路径，由实线（车辆处于作业模式）和虚线（车辆处于空驶模式）组成。洒水车从节点0出发，途径作业路段(0,4)，(4,1)，(2,5)，(5,8)，在节点11加水，途径作业路段(16,15)，(15,14)，(14,13)，(13,7)，(7,4)，(4,0)，然后返回节点0。
图1 路网拓扑及洒水车路线示意
RARP建模与求解
3.1 时变行程时间表征与系统拥堵影响建模
路段行程时间通过路段长度除以行程速度获得。行程速度可以由基于经验标定的基本图估计获得。但是，在车辆路径问题中，速度和密度需要嵌入连续交通流模型，以表征拥堵的演化。本研究扩展了Newell提出的具有二次到达率的流体排队模型，满足先入先出（FIFO）条件，同时能精确度量过饱和时段的拥堵影响，从而有效表征时变的路段和路径行程时间。与广泛使用的分段线性行程时间表征函数相比，所提出的表征方法具有以下三个优点：(1)形式简洁；(2)具有FIFO属性；(3)可微分。
3.1.1 时变行程时间
在非拥堵情形下，道路路段上的车辆速度相对稳定，本研究将车辆速度近似为路段自由流速度；在拥堵情形下，车辆行驶受到道路容量限制，当流入路段的交通需求超过路段容量时，会形成排队。在此情形下，车辆的行程时间包括自由流行程时间和排队延误时间。本研究主要关注针对单个拥堵时段的时变行程时间表征函数的标定，而非拥堵时段行程时间的表征采用恒定或分段线性函数形式。为保持行程时间函数的可微分性，可以在多拥堵时段采用本研究所提出的单拥堵时段行程时间函数标定方法。为了描述不同时段车辆到达模式的变化，可采用高阶到达率函数来降低标定误差，但这需要额外的标定工作，有兴趣的读者可以参考Zhou等学者[1]的最新研究。
不失一般性，交通网络上的每个拥堵路段被建模为具有恒定服务率的单一排队系统，该服务率等于最大路段消散率。图2给出了Newell模型[2]的路段排队演化示意图。
图2 在拥堵持续时间p=t3-t0内，在时间t2达到排队长度最大值
图2中，到达率λ(t)用蓝色线表示，出发率μ用红色线表示，t0为排队形成时刻，t2为排队开始消散时刻，t3为排队完全消散时刻，t1为到达率达到最大值的时刻，Q(t)为t时刻的排队长度，定义为：
其中，γ为路段流入需求曲率参数，可根据可观测的空间排队长度或路段行程时间进行标定，感兴趣的读者可以参考Cheng等学者[3]发表的论文。由w(t)=Q(t)/μ可知，时变的路段延误为：
在许多城市物流应用中，只有速度v_obs_t可以采集获得，观测时间间隔t通常为5分钟或15分钟。公式(4)中关键参数μ和γ的标定步骤如下，图解参见图3。
步骤1：在没有观测流量的情形下，可以根据设施类型和速度限制估计道路通行能力c。截断速度（cutoff speed）可以根据交通基本图来确定。
步骤2：拥堵持续时间P可以由t3-t0得到，而t0和t3分别对应截断速度开始下降和截断速度恢复的时间戳。
步骤3：平均消散率μ可以根据拥堵持续时间内的流量-速度曲线和观测速度来估计。μ的默认值用道路通行能力c近似代替。
步骤4：空间平均速度v_obs_t可以转换为公式(4)中的虚拟等待时间w(t)，并使用非线性回归法标定参数γ。或者，当w(t2)=(γ/6μ)(t2-t0)^3时，也可以根据最低速度和转换的最大排队等待时间估计γ。
图3 公式(4)中关键参数的四步标定方法图解
3.1.2 交通系统拥堵影响（社会影响）建模
如前所述，RARP应用中的服务车辆通常为缓慢移动的卡车，因此会对道路周边其他交通用户产生负面影响（降低周边社会车辆的通行效率），在高峰时段尤其如此。鉴于此，本研究基于标定的排队指标来度量服务车辆对整个交通系统的影响。
图4 道路路段边际延误图解[4]
图4中，蓝色和红色实线分别表示某条路段上车辆的累积到达和离去曲线。假设有一辆服务车辆在时间t进入路段。我们需要特别关注拥堵时段，即 t0≤t≤t3。服务车辆带来的边际延误对应蓝色虚线面积区域和灰色面积区域。这里的边际延误包括w(t)和SI(t)。w(t)是服务车辆所经历的延误，而SI(t)表示在t到t3之间到达该路段的社会车辆由于服务车辆在时间t的到达而产生的额外延误，即本文所述的系统影响。根据前文对w(t)的推导，SI(t)计算为：
考虑到服务车辆的行驶速度通常比其他社会通行车辆慢，并且占用更多的道路资源，进一步将式(5)中的SI(t)乘以一个乘用车当量系数PCE，即SI(t)×PCE，来度量服务卡车在时刻t进入路段时对系统造成的影响。
3.2 RARP建模方法
3.2.1节介绍了基于离散时间扩展网络的弧路径模型M1；3.2.2节介绍了基于图转换和弧的节点路径模型M2；3.2.3节介绍了基于图转换和路径的节点路径模型M3。
3.2.1 M1-TEN
目标函数
流量平衡约束
清洁要求满足约束
洒水车水位更新约束
决策变量
公式(6)中的目标函数为完成清洁任务的总成本最小化，总成本包括三个部分：行程时间成本、车辆购置成本和系统影响成本。集合A中除了在节点d建立的等待弧外，所有弧的行程时间成本ct(i,j,t,t')等于t'-t。令节点d的等待弧成本等于0 (i.e., ct(i,i,t,t+1)=0 if i=d)。表达式对x变量的求和表示使用的洒水车数量。通过对每个x(f,i,j,t,t')的三种系数进行积分，可以将公式（6）简化为：
弧(i,j,t,t')表示从顶点(i,t)到顶点(j,t')的时空出行活动，由于时间维度是连续的，将规划时间跨度(0,T)均匀离散为短时间间隔(例如10秒)，从而确保顶点和圆弧的数量是有限的。t和t'表示离散时间区间的索引。用{0,1,2,3,4,...,s}表示离散时间区间的索引集合，其中s为最后一个时间区间的索引， c(i,j,t,t')表示arc(i,j,t,t')的总成本，包括出行时间成本、车辆购置成本和系统影响成本。约束(7)保证在顶点上流入的流量等于流出的流量。注意，本研究没有对起点O(st)和终点D(st)施加这个约束。约束(8)确保按要求清洁路段，而约束(9)用于更新洒水车的水位。最后，约束(10)指定决策变量及其域。其中，x(f,i,j,t,t')为二元变量，q(f,i,t)为上界为C的正连续变量，其中C为洒水车水箱容量。
3.2.2 M2-STD
交叉口扩展网络和时间扩展网络大幅增加了M1-TEN的模型复杂度，使得在大规模实例上求解极具挑战性。在模型M2-STD中，本研究通过将原始弧路径问题转换为节点路径问题，来克服上述问题。
目标函数
清洁要求满足约束
洒水车空间路线约束
洒水车时间路线约束
时间窗约束
洒水车水位更新约束
决策变量
式(12)中的目标函数以总成本最小为目标，其中 O_N表示图G_N中洒水车的起始节点，d_f_N表示图G_N中洒水车f的目标节点d_N的副本。通过为每辆洒水车f创建一个目的车场的虚拟副本d_f_N，洒水车f到达目的车场的时间d_f_N就是洒水车f使用的时间。注意，由于目的车场的服务时间为零，所以到达和离开目的车场的时间是相同的，因此可以在目标函数中使用出发时间t_d_d_f_N来避免定义额外的变量。约束(13)确保每个服务节点只服务一次。约束(14)、(15)和式 (16) -(21)分别制定了洒水车的时空路径约束。约束(18)中， tao_i_p表示在p时隙开始服务时节点 的服务时间。对于服务节点，tao_i_p等于p时隙中相应路段的清洁时间。对于加水站和车厂节点，tao_i_p分别等于加水时间和0。约束(22)确保清洁服务在预设的时间窗口内启动。约束(23)-(25)用于跟踪洒水车的水位更新。最后，约束(26)指定了模型M2-STD中使用的决策变量及其域。
除了基本约束(13)-(26)外，下面进一步构造两组约束来收紧模型M2-STD的线性松弛。约束(30)确保至少需要一辆洒水车来完成清洁任务。注意，由于允许洒水车在行驶过程中补充水，因此我们无法计算使用总水量的最小洒水车数量除以洒水车的水箱容量。虽然约束(27)看起来很松散，但它确实是数值实验部分中许多实例的下界。约束(28)被用来打破模型M2-STD的对称性。
3.2.3 M3-CTR
目标函数
清洁要求满足约束
决策变量
目标函数Eq(11)使所有所选路线的代价最小，其中θ_r为二元变量，表示是否在一个解中选择路线 r; c_r为路线r的成本，包括运行成本和系统影响。
3.2.4 三种模型的时变行程时间表征对比
图5 M1-TEN、M2-STD和M3-CTR三种模型的时变行程时间表征对比
图5显示了三种模型中采用的时变行程时间表征函数(蓝线)。对于M1-TEN模型，时间维度被离散成0.2分钟的时间间隔。因此，路段行程时间和节点到达(离去)时间都近似为0.2分钟的分辨率；对于M2-STD模型，整个时间范围被划分为4个5分钟的时间段，每个时间段的行程时间保持不变；对于M3-CTR模型，使用了原始的多项式行程时间函数。
3.3 模型求解
在实际应用中，模型规模可能非常庞大，使得在合理的时间内难以获得理想解决方案。为此，我们开发了两个精确式求解方法来有效求解所提出的模型。针对M1-TEN模型，提出了一种基于拉格朗日松弛的求解方法，同时还提出了一种基于分支定价的求解方法。
3.3.1 基于拉格朗日松弛(LR)的求解算法
针对M1-TEN模型，本文提出了一种基于拉格朗日松弛的求解方法，通过对决策变量x(f,i,j,t,t')的系数进行重组，可以将目标函数Eq.(32)进一步简化为Eq.(33)。给定λ_i_j的值，松弛问题需要在离散化时间扩展网络上找到代价最小的最短路径，每个洒水车的弧代价为c'(i,j,t,t')，可以用动态规划方法精确求解。
我们采用经典的次梯度方法，利用Eq.(34)和Eq.(35)更新拉格朗日乘子λ_i_j的值，其中λ_k_i_j和 α_k分别表示拉格朗日乘子和步长在迭代k时的值。需要注意的是，由于约束(19)是一个等式约束，拉格朗日乘子可以为正、负或0。一个正的拉格朗日乘数意味着在服务于相应的弧线时额外的惩罚，而负值意味着额外的奖励。当所有环节都满足约束(8)，即在式(34)中没有拉格朗日乘子更新时，拉格朗日迭代停止。
3.3.2 分支定价求解算法
对大规模问题而言，M3-CTR模型中的集合omega中可行路径的数量可能非常庞大，难以通过列举所有路径并使用现有优化器进行求解。为此，我们提出一种基于分支定价的精确式方法来求解模型M3-CTR。该方法由两个模块组成，即列生成(CG)和分支定界(BnB)。将M3-CTR模型表示为主问题(MP)，然后利用CG模块求解线性主问题(LMP)，利用BnB模块根据CG模块的结果得到整数解。在LMP中，我们放松了决策变量θ_r的整数要求，即0≤θ_r≤1。
列生成模块
由于集合Ω的规模很大，LMP仍然很难求解Ω。因此，我们不直接求解LMP，而是迭代求解其对应的受限线性主问题(restricted linear master problem, RLMP)，RLMP的集合Ω‘只包含部分可行路线，并根据需要扩展新的路线。RLMP介绍如下:
清洁要求满足约束
决策变量
本文通过为每个服务节点分配一辆洒水车来生成集合Ω’中的初始路径。需要注意的是，在生成初始路线时，如果某个节点由于违反时间窗口约束或水资源消耗约束而无法完成服务，则原问题不可行。RLMP中的路径集Ω’通过解决所谓的定价问题进行扩展，将成本负降低的路径加入到集合Ω’中。
定价问题
定价问题表示如下
目标函数是使一条可行路径的降低成本最小化，其中Π_j为节点j相关的降低成本。本质上，上述优化问题是一个具有资源约束的初级最短路径问题。
动态规划
在网络中寻找具有资源约束的基本最短路径是一个NP-Hard问题。因此，在大规模实例中，找到上述定价问题的精确解决方案非常耗时。本文采用Martinelli提出的动态规划ng-route算法，并对其进行了一些改进。具体而言，在Martinelli提出的算法中，车辆只需要在其行程中收集货物，因此车辆的负载随着行程不断增加。本研究允许洒水车在行驶过程中补充水，因此洒水车的水位变化不再单调。此外，Martinelli假设需求是离散的，而在本研究中需求是连续的。
图6给出了分支和定价求解方法的伪代码和流程示意图。
（a）
（b）
（c）
（d）
图6 分支定价求解方法的伪代码和流程示意图
案例分析
在本节中，首先遴选华盛顿特区的都市区域的12条走廊来验证所提出的时变行程时间表征方法的适用性；然后基于标定的行程时间函数，设计了三组不同大小的实例，比较了三种模型的性能，并分析了车辆路径优化对系统的影响；最后，对求解方法进行了灵敏度分析。
4.1 时变行程时间表征
图7 用于时间相关行程时间建模评估的走廊
图7展示了为评估所提出的时间相关的旅行时间建模方法而选择的12条走廊，包括1条高速公路走廊、3条高速公路走廊和8条经历不同程度交通拥堵的主干道走廊。表6总结了选定走廊的特征。感兴趣的时间范围设置为6:00–20:00。请注意，交通网络通常会在一天中经历两到三个拥堵时段(上午高峰时段、下午高峰时段以及可能的中午时段)，而4.2中提出的方法适用于单个拥堵时段分析。因此，我们将分析时间范围分为三个时段，包括AM (6:00-10:00)、MD (10:00-14:00)和PM (14:00-20:00)，然后对每个时段依次应用该方法。
表1比较了观测速度和用多项式到达率从流体排队模型标定的速度。总体而言，在具有短拥堵持续时间的走廊上标定精度较高，具有严重拥堵的走廊上标定误差较大，但仍具有令人满意的标定精度。
表1 道路走廊上路段观测速度和标定速度对比
注:MAE-平均绝对误差，MAPE-平均绝对百分比误差
图8 US29 Middle_W走廊上观测速度和模拟速度的热图比较
图9 I395_E走廊上观测速度和模拟速度的热图比较
图8和图9显示了表7中建模精度相对较差的两个走廊(走廊US29 Middle_W和I395_E)上观察到的和标定的行程速度之间的热图比较。总体上，拥堵蔓延的影响能够被较好地捕捉到。
图10 两条路段上的模拟速度和观测速度比较
图10提供了在分析时段内的观测速度和标定速度。拥塞发生在路段32609上的AM和MD时段，而只有AM在路段31948上经历显著的延迟。可以观察到，对于具有单个拥塞时段的路段(link 31948)，标定的速度与观察到的速度非常匹配。然而，对于具有多个拥堵时段的路段(link 32609)，两条线路之间仍然存在明显的偏差，这凸显了在建模复杂和严重情形下交通拥堵的挑战性。
4.2 三种模型的性能评估
如表8所示，设计了三组不同大小的实例来评估本文开发的三个优化模型。实例网络由高速公路、高速公路和干线组成。在12条具有代表性的走廊上校准的行程时间函数根据其道路类型应用于基准实例中的路段。我们的开源代码库可以在Github上找到，网址为https://github.com/jiawlu/time-dependent-vrp-bnp。
表2 三个基准实例集的特征
第一个实例集包括15个小型实例。平均有16条路段需要清理。第一组路段的长度范围为0.07到0.74英里。第二组包含15个中等大小的实例，其中道路路段的数量从28到38不等。最后一组包括13个大型实例，每个实例网络平均需要清理62个路段。对于所有实例，计划跨度为3小时。车辆容量为1200加仑水，假设清洁1英里的道路消耗400加仑水。洒水车在清洁模式和空载模式下的速度限制分别设置为5英里/小时和14英里/小时。我们假设洒水车数量没有限制，但是每个洒水车的购置成本相当于10个行驶时间单位。请注意，在本小节中，由于我们主要关注三个建议模型的效率评估，系统影响成本w的权重设置为0。
表3、表4和表5分别显示了建议模型在三组真实实例(小型、中型和大型)上的结果，包括下界(LB)、上界(UB)、Gap、求解时间(ST)和内存使用(MU)。Gap计算方法为Gap=(UB-LB)/UB×100%。小型实例的解决时间限制设置为15分钟，中型实例为30分钟，大型实例为60分钟。模型M1-TEN的时间离散分辨率设置为0.2分钟。M3-CTR模型中ng集的大小设置为2。
主要结论：
（1）总体而言，在三组实例上，基于所提出精确式求解算法的两个模型（M1-TEN 和 M3-CTR）要优于用MILP求解器求解的模型（M2-STD）。模型M3-CTR的求解质量和求解效率最优。
（2）在15个小型实例中，模型M3-CTR能够在规定时间内生成14个实例的最优解，而模型M1-TEN和M2-STD则无法在所有15个实例中证明最优解。另一方面，虽然模型M1-TEN和M2-STD的Gap高于模型M3-CTR，但前两个模型提供的上界始终与最优解相近，表明这两个模型仍能产生可接受的解，可用于小规模实例的实际应用。在计算速度方面，三种模型在小规模实例上的平均求解时间分别为385秒、900秒和100秒。
（3）对于中等规模的实例，由于实例复杂度的增加，三种模型都出现了较大的Gap和较长的求解时间。在解质量方面，与小型实例的结果类似，模型M3-CTR的性能仍然最好，平均Gap为3.32%。模型M1-TEN的平均Gap为10.84%，而模型M2-STD则超过80%。模型M2-STD的Gap较大的原因在于性能下界较差。模型M2-STD可直接用CPLEX 求解，CPLEX内置线性松弛和分支约束功能。同模型M3-CTR相比，线性松弛的基于路径的模型（M3-CTR）比简单松弛的基于弧的模型（M2-STD）能提供更为严格的下界。
（4）对于大规模实例，模型M2-STD只能在一个实例（L4）上产生可行解，而在所有实例上都能提供较弱的下界，导致平均Gap为99.82%，这凸显了为解决实际生活中的大规模 RARPs而设计定制求解算法的必要性。与平均Gap为4.23%的模型M3-CTR相比，模型M1-TEN的下界和上界相对较差，平均差距为84.65%。
（5）总体而言，模型M1-TEN的内存消耗远低于模型 M2-STD和M3-CTR。即使对于大规模实例，模型M1-TEN的平均内存使用量也只有8.18 GB，这表明模型M1-TEN具有在线计算的潜力。模型M3-CTR比模型M1-TEN消耗更多内存，是由于分支和约束模块使用了并行计算，需要同时处理大量的分支和约束节点。对于模型M2-STD，中型实例的平均内存使用量为43.11 GB。需要注意的是，由于模型M2-STD在达到时间限制时仍处于预求解阶段，因此无法给出大规模实例的内存统计数据。
表3三个推荐模型在小型实例上的性能比较
表4三个推荐模型在中型实例上的性能比较
表5三个推荐模型在大型实例上的性能比较
4.3 社会影响分析
图11 运营成本和系统对实例S5的影响的帕累托曲线，w范围为0.0至1.0
表11显示了w=0和1.0时小型实例的最佳解决方案成本。请注意，为了准确度量不同系统影响权重下的最优运行成本和系统影响的变化，我们只选择具有最优解的实例，因此实例S14不包括在表13中。总体而言，在更加重视车辆路径的边际成本后，系统影响明显降低，而私人运营成本增加。对于每个实例，OCPI (SIPD)表示当w从0.0变化到1.0时，实例的最佳运行成本(系统影响)的增加(减少)百分比。由于所选实例的多样性，OCPI和SIPD可能因实例而异。具体而言，对于S1，当 w从0.0变为1.0时，其运营成本增加了4.23%，而在S4，其运营成本增加了69.35%。
表6不同系统影响权重w下小实例的最优路线成本
总结
在本研究中，我们针对拥挤城市环境下城市物流中RARP问题展开了探索，提出了有效的建模框架和求解方法。具体而言，基于流体排队模型和到达流率的多项式函数假设，解析了与时变路段行程时间以及社会影响。提出了两种时变行程时间表征方法。以洒水车路径规划应用为例，通过考虑时变行程时间和面向特定领域地“富”约束，构建了三个优化模型，包括基于时间扩展网络的弧路径模型M1-TEN、基于图转换和弧的节点路径模型M2-STD和基于图转换和路径的节点路径模型M3-CTR。为有效求解M1-TEN模型和M3-CTR模型，开发了基于拉格朗日松弛和分支定价的精确式求解方法。
利用从华盛顿大都市区收集的真实交通流数据，选取了12条有代表性的走廊来验证所提出的时变路段行程时间表征方法的有效性。结果表明，该方法能够合理捕捉不同交通拥挤程度下的出行时间演化曲线。基于标定的行程时间函数，设计了三组不同规模的SRP实例来检验三种优化模型及其相应的求解算法的性能。总体而言，模型M3-CTR能够在更短的时间内产生高质量的解，而模型M1-TEN能够以更少的内存消耗提供良好的可行解。此外，还系统地分析了不同优先级的路径规划方案对系统产生的拥堵影响。
参考文献
点击下载论文原文
Rich arc routing problem in city logistics Models and solution.pdf
点个在看 你最好看
