考虑临时配送的动态车辆路径规划研究

摘要：文章研究了客户请求的配送车辆呈动态化的车辆路径规划问题，在该问题中，客户请求的动态化可能在配送计划制定时已知，也可能在任一配送时间节点更新；配送车辆的动态化体现在管理配送的公司配备固定的车队进行配送，也有临时的司机通过接单形式提供服务，且临时配送与对应时间窗相关联。文章的研究目的是确定分配成本最小化的分配计划，分配成本由常规车辆成本、支付给接单司机补偿款项和罚款成本共同构成。该问题研究基于大邻域搜索算法和遗传算法设计优化算子，探索处理动态请求并实时调整路径规划的分配计划。通过计算研究与灵敏度分析评估算法性能，确定其解决动态问题的可行性与优势。关键词：动态车辆路径规划；大邻域搜索算法；遗传算法；优化算法電子商务在过去几年经历了指数级增长，对多个行业而言，无疑是一个巨大的商机，但其对管理与满足客户订单相关的运营方面也提出了巨大挑战[1]，尤其聚焦供应链的最后一站。电商的爆发式增长让“最后一公里”交付成为焦点。事实上，客户对送货速度的要求越来越高。一方面，提供“当天送达”或“次日送达”等的服务是增加收入和获取客户忠诚度的绝佳机会[2]。另一方面，送货速度加快意味着减少合并机会和缩短交付计划时间。而在这一过程中，主要风险表现在提供质量差的服务或产生高昂的交付成本。基于此，为“最后一公里”交付寻找创新和高效的解决方案成为了所有电子市场参与者成功的关键手段。亚马逊公司便是该领域的领先创新者之一。它推出的“amazonFlex”，使私人司机可以为亚马逊运送包裹并获得服务补偿。司机提交可用时间和实时位置，亚马逊要求他们必须从亚马逊配送中心取货并交付给最终客户。该服务于2015年在美国开始运营，目前已覆盖100多个城市。针对物流行业存在的相关问题，王缉宪[3]的研究以多层次的社会技术转型理论为基础，建立了促进“最后一公里”城市物流转型的概念框架，确定了该配送形式在改善电子商务时代“最后一公里”配送方面的巨大潜力；韩慧瑜等[4]提出了使用众包工人的“最后一公里”交付选择模型，用于优化成本、时间和工人表现间的权衡。但其更多侧重于从定价策略上进行规划，而没有将其与司机路线联系起来；周林等[5]研究了在旅行时间随时间变化的情况下，使用众包车辆顺路捎带进行城市包裹在线众包配送的问题，侧重于从司机个人角度进行协同配送规划；赵建有等[6]引入了在线众包卡车交付（OCTD）问题，并将其重新表述为“在线双点超匹配”的问题。虽然其从企业的角度进行了算法模拟，但缺少容量、时间窗及解决相关问题路径的研究。可见，现有研究对于众包与传统配送相结合的物流系统的相关研究较少，尤其在涵盖多种现实因素的算法研究较为空缺。因此，本文以此为研究切入点展开了研究探讨。本文从薛桂琴等[7]的两阶段动态车辆调度问题出发，创新引入了临时车辆的規划算法。在徐倩等[8]研究的配送车辆路径规划问题的基础上，探究了一项配送服务方式，即公司需要将包裹送到城市地区的客户手中。该公司配备有一支能力较高的“正式司机”（即由公司雇用并在配送服务中全职工作的司机）车队，该车队在夏小云等[9]研究的带容量限制的车队问题的基础上增加了使用“临时车辆”提供服务，该临时车队由可在特定时间窗口内进行配送服务的临时工作人员构成。在临时车辆执行完一次送货任务时，就会得到相应的报酬。此外，如果一个临时车辆不得不消耗比其自行规定时间更长的时间来交付指定的包裹，则会收到额外的补偿。当开始配送包裹后，出现的新请求将会被作为临时的顾客需求点。因此，公司需要不断调整配送计划以处理新的订单。客户订单与特定时间窗口相关联，便成为该客户选择接收包裹的首选时间。任何违反这个时间窗口的行为都会产生惩罚性费用。如果公司不能为在线客户订单提供服务，且不安排交货，则会被认为订单配送可能会被推迟到后一天。这便会产生罚款成本。而公司的目标是实现总配送成本的最小化。该成本由常规的司机成本、对临时车辆的补偿款项以及对客户延迟或推迟交货的惩罚款项共同构成。基于此，我们将研究临时配送的动态车辆路径规划问题。本研究假设没有关于临时客户的信息，且这种设定与最近在某一地区开始的相关服务情况是一致的。因此，本文不存在关于请求出现的可靠信息。1

动态VRP模型动态VRP作为一种企业实际问题，从公司设计的角度来看，公司必须将货物交付给一组地理上分散的客户。客户的需求可能在配送计划实施前提前获知，也可能在配送过程中在线获得。公司拥有一支固定的常规车辆车队，用于向客户提供配送服务，同时，也配备有临时车辆可用于灵活执行服务。具体而言，每个临时车辆可自行设计服务的时间窗口，且其获得的收益与行进距离成正比。此外，如果未满足客户时间窗口或服务时间超过预先设计的时间窗口，系统将自动生成相应的惩罚。此外，如果因司机原因未能满足客户要求，公司将需要支付未满足需求的成本费用。公司的目标是实现分配成本最小化，而分配成本由支付给临时车辆的补偿款项、与使用常规车辆相关的路线成本和赢得时间的惩罚成本的总和而得。每个客户i都与一个需求di和一个时间窗[ei，li]相关联，确定了为客户提供服务的时间段。在站点（仓库）有一个容量为Q的固定车辆车队F，并由企业司机驾驶。每条常规车辆路线都从仓库s开始，最终又回仓库t。此外，一组临时车辆K可用于执行该服务。每个临时车辆K与时间窗[ek，lk]相关联，用于确定司机可用时间并设置相应惩罚，以及可用的最大容量Qk。此外，每个临时车辆均可指定其在整体范围内的终止节点Vk。A是弧的集合。每个圆弧（i，j）∈A表示从i到j的最短路径。还有两个相关参数与弧（i，j）相关联，分别为成本cij和时间tij。它们都满足三角不等式。本研究假设成本cij代表使用普通车辆从i到j的成本。因此，它包括与车辆使用相关的所有成本（燃料、通行费，以及车辆使用费用）和司机工资；同时，本研究还假设成本与穿过弧线的时间成正比。这意味着最短路径对应于最快路径。每个临时车辆都在与普通车辆相同的原点仓库s出发。研究假设，当临时车辆在仓库S中取货时，会被分配一个“路径计划”，即应该执行交付的顺序。因此，除了常规司机的路线之外，公司还定义了临时车辆的行程路径。每个临时车辆根据可以从站点出发的最早时间和想要到达目的地的最晚时间来定义时间可用性并完成交货。给予每个临时车辆的补偿计算为递送分配给的包裹而遍历的弧的成本cij（从仓库S到最后一个访问的客户遍历的弧乘以补偿参数q），且对所有临时车辆都是统一的。惩罚成本与客户时间窗口违规、临时车辆时间窗口违规和未满足请求相关。特别是，惩罚成本Cs与客户时间窗口违规相关，并且与违规延长时间成正比。因此，把客户时间窗违反情况计算值设置如下。类似地，我们将对临时车辆时间窗口违规的惩罚定义为Ch。设置临时车辆的时间窗口违反情况的计算值如下。最后，Cr是为每个未满足请求支付的罚款。我们假设必须为Cs中的客户提供服务，而原始路径中客户的请求可能会被推迟。这反映了客户在Cs中提前下订单并保证在给定期限内得到服务的情况。此外，我们假设未满足请求支付的罚款与未满足的客户需求成正比。在这种情况下，每个未满足的请求都会支付罚款。设置ri为二进制变量，在客户i的请求未得到满足的情况下，相应值的计算如下。通过这种方式，我们近似于请求根据其“重要性”具有不同优先级的情况。这可能与请求的价值或承运人与客户签订的合同有关。需要注意的是，该模型和解决方法很容易被修改，以考虑不同的惩罚成本设置。研究设置目标为定义总成本最小化的分配计划。总成本由常规司机的路由成本、临时车辆补偿支出、违反客户和临时车辆时间窗口的惩罚成本以及未满足请求的惩罚成本的总和得出。目标函数设置如下。式中，第一项是与车辆相关的运输成本；第二项是临时车辆的补偿成本；后三个多项式分别是客户时间窗口违反成本、临时车辆时间窗口违规成本和未满足请求的惩罚成本。另外，与本文创新设置的临时车辆问题的相关约束条件陈述如表1所示。约束（1）（2）对可用的临时车辆数量和离开车辆的数量进行限制；（3）为计算节点j的到达时间；（4）为临时车辆在ek之后开始行程；（5）为保证每个在线客户最多被访问一次，无论是固定车辆还是临时车辆；（6）为强制要求访问所有静态客户节点。1.1

客户问题的描述静态顾客需求点是指在进行路径规划时已知时间配送距离的点；而临时顾客需求点则是在配送过程中提出的。这种情况在原始路径规划中无法得知足够信息，进而无法进行规划安排，只能由本文研究的动态优化算法实现。针对本文提出的动态客户问题，创建模型。具体模型如图1所示。本文以确定仓库为基础，对图1中时间t为9时出现的临时顾客需求点的相关路线进行了详细探讨。临时顾客需求点4出现时，车辆已从仓库出发向顾客点1行进，且直接执行插入算子形成的路径规划（2）显然不满足成本最小化原则，故需要对此路径进行进一步优化，得到最终可满足目标函数路径（3）。1.2

车辆问题的描述设K为临时车辆总集。司机的行程公告k∈K，指定其目的地。司机k∈K有最早出发时间ek和最晚到达时间lk。驾驶员还指定了最大行程时间Tk，其中tok，dk≤Tk≤lk-ek，出发时间灵活性表示为Fk=lk-ek-tok，dk。除了绕行和出发时间的灵活性，还要考虑到司机可能愿意额外停靠的最大次数。令Qk∈Z+表示驾驶员k的停车意愿。在同一地点多次上车或下车算作一次停靠。因此，停车意愿限制了司机访问不同位置的数量，反映了临时车辆愿意接受的不便程度。一项服务配送任务最多与两个站点相关联：一个在上车地点，一个在下车地点。当司机的出发地与任务的取件地点重合时，便只需多停一站即可完成送货（见图2中的a）。这符合沃尔玛公司配送服务的想法，即让实体店顾客沿着从实体店到家的路线将包裹递送给在线买家。图2中的b显示了一个示例，表示其中驾驶员的来源与任务的上车位置不同。在这种情况下，司机需要额外停靠两次，即一次上车和一次下车。图2中的c中描绘了另一个需要两次额外停靠的示例，表示其中司机在他的起点处拿起两个包裹，然后进行两次下客。为了简化符号，研究假设时间和停止限制比容量限制更严格。理论上，这是一个合理的假设，因为大多数消费品都小到可以轻松放入汽车后备箱（亚马逊86%的包裹重量不到5磅，小到甚至可以用无人机运送）。为了适应运输较大物体（例如家具或白色家电）的环境，我们针对货物体积引入额外的限制。研究将作业p定义为一组任务，且作业可以由单个任务或多个任务组成。集合P为至少在一个可行匹配中的所有作业的集合。假设存在一条可行路线r，使得司机k和工作p之间的匹配（k，p）是可行的。其中，司机从他的起点ok开始，涵盖p中的所有任务，并在他的目的地dk结束。如果满足以上约束条件，则表示路径r是可行的。2

动态优化算法在本节中，研究首先介绍了一种基于简单插入方案的动态车辆路径问题的解决算法。该算法允许处理在线决策和实时调整分配计划。在传统解法（即对计划进行局部调整以适应新的请求）的基础上，提出重新优化策略。其出发点是在给定的連续时间点上反复重新优化路线，且每次重新优化都会重建整个分配计划。尤其值得注意的是，我们假设，每次有一定数量的在线请求被放置，就有一个程序被应用，并试图将搁置请求插入到现有路线的最佳可行位置。然后，我们在每条路线上应用一个重新优化的程序，只考虑仍需执行的那部分路线，即在最后一个请求时段内到达后并执行的那部分。我们之所以提出这个策略，是为了显示重新优化比简单插入算法更占优势，即强调了LNS算法的优势。同时，基于此研究，评估了遗传算法对插入带来的效益，以实现再插入。针对以上两种算法的基础思路，引入多种不同类别的移除与插入算子进行权重改变的重优化，增加系统的动态性与复杂性，使整体程序实现局部最优。2.1

大邻域搜索算法在下文中，基于李珍萍等[10]（2021）提出的改进LNS算法，作进一步优化改进记作DynamicVRP问题。Dynamic代表“动态问题”，该算法是基于上文描述的从客户以及车辆两方面的动态车辆路径规划问题提出的。本研究提供LNS-VRP的一般方案，并参考徐倩[8]等外卖路径规划研究中考虑时间窗及惩罚情况的更多细节，重点讨论DynamicVRP问题，以建立一个可行的解决方案，在不违反时间窗口的情况下访问CS中的所有客户。具体来说，该算法由三个主要阶段组成，分别为初始化、移除和再插入。初始化阶段是通过一个贪婪的插入启发式建立一个初始可行的解决方案（不考虑任何成本及距离问题）；然后在解决方案初步可行的情况下，重新优化并更新融合程序。解决方案被传递到第2和第3阶段进行迭代，直到达到最大迭代次数。特别需要提及的是，要先找出满足时间窗约束和容量约束的所有插入点，再计算上述插入点的距离增量；接着找出上述插入点距离增量最小的那个插入点，并记录其距离增量。通过重新优化阶段得到的解决方案将被传递给LNS。不同的邻域已被明确定义，再由LNS按顺序逐一探索。一个邻域的解决方案只有在改善当前解决方案的情况下才会被接受。当所有邻域都被探索后，LNS就会停止执行。然后，除非达到最大的迭代次数，否则便会对当前的解决方案进行持续更新。具体如表2所示。2.2

优化移除算子本研究从夏小云等[9]解决带容量约束的车辆路径问题（CVRP）时设计的５个移除算子和２个插入算子出发，用相同的思路深入挖掘更符合本研究问题的算子。移除算子设置如下。2.2.1

随机移除算子不考虑任意约束直接进行移除，虽然会给系统迭代次数带来压力，但其跳出局部最优能力较强。2.2.2

节约值最大移除算子仅考虑个体节约值进行移除，较易陷入局部最优，且其仅考虑线路中单一节点数值问题，可将节约值作为移除因子纳入算式进行整体计算移除。2.2.3

独立个体移除算子考虑到无上限车辆问题中，较容易出现一条路线上涉及节点较少的问题，将独立个体纳入移除，可以设计节点节约值与路线总节约值在某程度上相近则移除。2.2.4

邻域问题移除算子针对每个节点进行邻域搜索，邻域内出现节点个数超过设置值则触发移除算子。2.2.5

需求值过大移除算子将任一路线中节点的需求量与总路线需求量进行比较，当设置范围相近时，则考虑该节点是需求过大节点，将其执行移除。2.3

优化插入算子插入算子除了涉及遗传算法的相关求解问题，还关系到多种本研究中单独引入的插入算子因素，具体如下。2.3.1

贪婪法插入算子使用贪婪法得到节点的最优插入位置，其对应插入后增加路程最小的插入点，即将对应的待插入节点乱序排列后使用贪婪法依次插入。该运算符重复地将请求插入整体最佳位置，并被称为最小成本位置。2.3.2

二分法插入算子对于所有的插入节点进行随机排序获得数组，利用二分查找法查找出插入位置，并将有序数组中插入位置后的数据后移一位，空出插入位置依次插入数组中的数据。2.4

基于LNS的GA优化（GA-LNS）求解动态VRP考虑到遗传算法对该问题解决效率的正向影响，以黄新林等[11]相关改进遗传算法研究的理解以及吕东许等[12]相关大领域搜索算法在任务规划方面的研究作为基础，将遗传算法纳入到研究中进行详细讨论。基于以上两种优化方向的研究思路，从最后一个角度，即插入时涉及到的数学问题求最优解出发，引入较容易跳出局部最优且适合处理大数据集问题的遗传算法。出于本研究的特殊性对其作优化改进获得如图3所示算法流程图，依据该流程运行遗传算法得出最优，将该最优值插入上述操作优化后的LNS算式中。3

实验分析为了验证该算法比现有的传统算法或优化前算法更有效，对其得到的性能数据进行比较与分析。从实验结果来看，该算法能在在大迭代次数内形成最优配送方案，同时满足已有的时间窗及多种约束。将本算法与已知信息不考虑动态问题的离线算法作比较，可发现路径最优性存在波动，但在该水平上近似有效，具体如图4所示。针对算法的惩罚问题进行初步的计算研究，以评估惩罚成本成分对问题解决方案的影响。特别是对小尺寸实例上的惩罚效果有较好展示。通过测试了Cs不同数值对结果的影响，对10个客户、三个普通车辆和三个临时车辆的实例进行深入演算研究。最终得出违反时间窗口约束如何通过改变Cs和Ch的值来影响目标函数。不考虑Cr上限的影响，将其值设置为1000，以便为所有客户提供服务。对于q的每个值，给予相对应的不同Cs和Ch值，最终得出解决方案成本以及常规车辆和临时车辆路线的数量。研究结果显示，时间窗违规不会影响解决方案的配置，因为对于不同的Cs和Ch值，常规车辆和临时车辆的数量几乎保持不变。相反，临时车辆的补偿对解决方案有更大的影响，临时车辆路径的数量随着q的减小而增加。我们通过以下统计数据来评估各种实验中的解决方案。总成本为匹配司机的补偿和后备行程的成本之和。任务匹配为由临时车辆提供服务的任务比例；完成度代表由后备服务提供的任务比例。司机匹配为分配给任务的临时车辆数量；一些提供服务的临时车辆将不会被使用。后备车辆为所有任务提供服务所需的后备车辆的数量。4

结

论本文研究了临时配送的动态路径优化问题，在该问题中，一家公司利用众包运输来分发其部分客户订单。对于面临“最后一公里”交付带来的复杂问题而言，众包运输被认为是一