开放式带时间窗车辆路径问题及变邻域搜索算法

陈久梅,李英娟,胡 婷,但 斌,李 俊

(1.重庆工商大学 长江上游经济研究中心,重庆 400067；2.重庆工商大学 管理科学与工程学院，重庆 400067；3.重庆工商大学 工商管理学院，重庆 400067；4.重庆大学 经济与工商管理学院，重庆 400044)

0 引言

近年来，随着O2O平台的快速发展，物流配送需求大幅度增长，人们的消费模式从线下向线上转变。相比线下而言，线上平台面临更多挑战，如配送时效性与准确性、配送成本等。以美团外卖为例，在消费者下单、商家接单和骑手配送的几大环节中，骑手配送是关键，面临最大的挑战便是车辆调度问题。与传统车辆路径问题(Vehicle Routing Problem, VRP)不同，骑手配送环节往往由第三方平台负责，配送结束后车辆不必返回商家，这属于开放式车辆路径问题。此外，顾客往往对接受配送有最早和最晚时间的要求。该车辆路径具有受时间窗约束的特征，这类问题属于学术界研究的开放式带时间窗车辆路径问题(Open Vehicle Routing Problem with Time Windows, OVRPTW)。

OVRPTW在现实中应用广泛，如报纸配送、牛奶配送、快递服务、校园班车、大型生产制造业原材料的运输等。以校园班车为例，校车下午从学校出发，沿着预定路线，依次按照预定时间到达学生下车点，直到最后一位学生下车，早上接学生的情况正好相反。又如，当某些公司不拥有车队，或其车队不合适或不足以满足顾客需求时，这家公司需要将全部或部分货物交付第三方或借助外部载体进行运输，这种情况下车辆不必返回仓库，费用主要取决于行驶距离，即开放路线的长度。类似地，对于危险品、易耗品、易腐食品、建筑材料、原材料的运输等，以及铁路部门或者航空公司在运送货物时，车辆在完成一批货物运输后，为节省物流成本无需返回原出发点。上述物流配送过程中，货物的到达时间是影响消费者服务满意度的关键因素之一，因此车辆路径通常是执行具有时间窗约束的开放路线。

虽然OVRPTW的应用广泛，但目前的研究还相对较少。REPOUSSIS等[1]针对OVRPTW设计了一种贪婪的前瞻性路径构造启发式求解算法，该算法通过组合顾客选择和路径插入来利用时间窗相关信息;FAIZ等[2]针对OVRPTW分别建立了两个整数线性规划模型：基于弧的混合整数线性规划模型并采用通用求解器求解和基于路径公式设计一个列生成框架，最后经过数值实验比较了两种模型的性能;RUSSELL[3]提出一种利用建模语言和CP优化器约束编程的方法，解决多产品报纸生产和投递的协调问题;CHEN等[4]基于紧急程度采用插入启发式算法构造初始解，运用带强化学习的变邻域搜索算法求解具有时间窗和开放路径的周期车辆路径问题;REPOUSSIS等[5]结合新达尔文主义进化模型的基本原理和短时记忆的禁忌搜索算法，提出一种进化算法求解OVRPTW;BRANDO[6]针对OVRPTW设计了迭代局部搜索算法，并采用Solomon、Homberger和Gehring等算例进行求解;李三彬等[7]提出一种多开始禁忌搜索算法求解OVRPTW，同样使用Solomon算例进行验证;RUSSELL等[8]在构建初始路径的基础上，使用禁忌搜索对路径改进;孙国华[9]设计了改进的自适应遗传算法求解开放车辆路径。

变邻域搜索(Variable Neighbourhood Search, VNS)算法作为一种新元启发式算法，最早由MLADENOVI等[10]提出，该算法通过改变邻域结构使搜索方向多元化，从而增强搜索能力，优化计算性能[11]。鉴于VNS算法的优越性，其已经被广泛应用于解决VRP的各种扩展问题。XU等[11]使用VNS算法求解连续性车辆路径问题;SEVKLI等[12]提出一种求解OVRP的变邻域搜索算法，并在各种标准算例和大规模实际问题上进行了测试;REZGUI等[13]将VNS算法应用于解决具有异车型和时间窗等约束条件的问题;姚冠新等[14]将改进VNS算法用于研究多隔室车辆路径优化问题。

本文针对OVRPTW，在建立数学模型的基础上，借鉴文献[1]的贪婪插入法生成初始解，设计VNS算法对其进行求解。算法框架中融入GLOVER[15]的路径重连和KINDERVATER等[16]的邻域搜索算子，并将邻域搜索嵌套在VNS算法的抖动过程中。通过求解两组算例，并将求解结果与已有文献进行比较，验证了VNS算法的有效性。

1 问题描述与模型构建

OVRPTW是经典VRPTW的一个扩展问题，可考虑为配送中心安排车辆将物品配送给一系列顾客，每辆车完成自己所负责配送的最后一位顾客后，服务结束，无需返回配送中心。其中，车辆有容量限制，在配送过程中不得超载；顾客在地理位置上是分散的，且各自有不同的需求量及接受配送服务的时间窗。OVRPTW的目标是构建一组满足所有顾客点需求的总行驶成本最小的配送路径。

OVRPTW可用有向图D=(V,A)来表示，其中V表示点集，A表示边集。点集V=Vc∪{0}，其中Vc表示顾客点集，0表示配送中心。边集A=Ac∪E(0)，其中Ac={(i,j)|i,j∈Vc,i≠j}表示顾客点i到顾客点j的边集，E(0)表示离开配送中心的边。给定点子集G⊆Vc，δ(G)表示到达G的边，E(G)表示离开G的边。d(G)表示G中所有顾客的需求量之和，Q表示车辆容量。车辆集合为K={1,2,…,k}。

借鉴KALLEHAUGE[17]的方法，OVRPTW的解记为R={r1,r2,…,rk}，其中rk=(0,vk1,vk2,…)，vkj∈Vc。路径rk上所有顾客的需求量之和记为d(rk)，车辆行驶成本记为c(rk)，路径rk上顾客vkj的实际开始服务时间记为ssvkj，服务时间记为svkj，车辆从点i到点j的行驶时间记为tij，节点i的开始服务时间时间窗为[ai,bi]，其中a0=0。若路径rk上任意顾客vkj都满足avkj≤ssvkj≤bvkj且d(rk)≤Q，则路径rk为可行路径。若任意rk∈R均为可行路径，则R为OVRPTW的一个可行解，X(•)表示“•”中边的数量。由此，可构建OVRPTW的模型。

目标函数：

(1)

s.t.

X(δ(i))=1,∀i∈Vc;

(2)

X(E(i))=1,∀i∈V,i≠vk(|rk|-1),∀k∈K;

(3)

X(E(i))=0,∀i=vk(|rk|-1),∀k∈K;

(4)

X(E(G))≤|G|-1,G⊆Vc,|G|≥2;

(5)

ssvkj=max{ssvk(j-1)+svk(j-1)+tvk(j-1)vkj,avkj},

∀j∈Vc,∀k∈K;

(6)

avkj≤ssvkj≤bvkj,∀j∈Vc,∀k∈K;

(7)

d(rk)≤Q,∀k∈K。

(8)

目标函数(1)表示车辆总行驶成本最小。约束(2)表示有且仅有一辆车到达顾客点为其提供服务;约束(3)表示车辆到达任意路径rk上除最后一个顾客点外，必须离开;约束(2)和约束(3)保证了路径的连续性;约束(4)表示任意路径rk上车辆服务完最后一个顾客即结束;约束(5)用于消除子回路径。约束(6)和约束(7)表示任意路径上任意顾客vkj的实际开始服务时间必须在其时间窗内;约束(8)表示车辆容量约束，即任意路径rk上顾客需求量之和不得超过车辆容量。

OVRPTW中，车辆不需要像VRPTW那样返回配送中心。从图论角度看，求解VRPTW是要找到一组哈密顿回路(如图1)，而求解OVRPTW是要找到一组哈密顿路径(如图2)。SYSLO等[18]认为哈密顿路径问题是NP-hard问题，因为它可以转换成等价的哈密顿回路问题。因此，OVRPTW也是NP-hard问题。考虑到变邻域搜索算法的优越性以及该算法在车辆路径问题方面的成功应用[18-19]，在此运用变邻域搜索算法对OVRPTW进行求解。

2 算法设计

VNS算法的基本思想是通过系统改变邻域，从一个解跳到另一个解，不断改善现有解，以得到更好的解。与禁忌搜索、模拟退火等传统的元启发式算法相比，VNS算法不但结构简单，容易实现，而且与求解问题无关，适用于各种优化问题[20]。为提高求解效果，本文在基本VNS算法的框架下，在其抖动阶段，采用当前解向个体历史最优解和种群历史最优解靠近的路径重连来实现；在其邻域搜索阶段，采用路径内和路径间的交换、插入、2-opt算子来实现，并将邻域搜索嵌套在抖动过程中。

定义1抖动算子记为SNk，k=1,2，其中SN1指当前解向个体最优解靠近的路径重连，SN2指当前解向种群最优解靠近的路径重连；邻域搜索记为LNl，l=1,2,3，其中LN1指交换算子，LN2指插入算子，LN3指2-opt算子。求解OVRPTW的VNS算法伪代码如下：

Generate the initial solution x

Definition:a set of neighborhood structures SNkfor k=1,2 for shaking

a set of neighborhood structures LNlfor l=1,2,3 for local search

while(stopping criterion is not met)do

k=1

l=1

while k≤2 do //shaking

x′←SNk(x)

while l≤3 do // neighborhood search

x″←LNl(x′)

If Z(x″)

x′←x″

else

l=l+1

End if

End while

If Z(x′)

x←x′

Else

k=k+1

End if

End while

End while

Output x

2.1 解的表示

OVRPTW的路径集合R={r1,r2,…,rk}，其中路径rk表示车辆k服务的顾客点及其服务顺序，rk=(0,vk1,vk2,…)。为保证每辆车从配送中心出发，服务完最后一个顾客后不再返回，每条路径第一个元素均为0，其余元素为非0。每个非0数字对应一个顾客，数字不重复。所有路径的集合构成一个解，如路径r1=(0,1,3)，r2=(0,2,5,6)，r3=(0,4)表示由3辆车服务6个顾客点的一个解，如图3所示。

图3中，车辆1从配送中心出发，依次服务顾客1和3；车辆2从配送中心出发，依次服务顾客2、5和6;车辆3从配送中心出发，服务顾客4。这个解可表示为{0,1,3,0,2,5,6,0,4}。该种表示具有如下优点：①每条路径可以表示车辆提供服务的顾客点及其服务的先后顺序；②每个顾客点的服务时间可以根据式(6)计算得到，然后根据式(7)判断是否满足时间窗约束；③可以很方便地计算整条路径上所有顾客的需求总量，从而根据约束条件(8)判断是否超过车辆容量。

2.2 初始解的生成

初始解的生成采用贪婪插入法，将顾客点依次插入最优插入位置，形成一条条行驶路径，直到完成所有顾客点的插入，即生成初始解。

定义2最优插入位置。给定路径rk=(0,vk1,vk2,…)，在vk1之前和vkj之后共有|rk|个插入候选位置。如果插入后新路径增加的车辆行驶成本最小，则该位置称为最优插入位置。

生成初始解的步骤如下：

步骤1随机选择一个不在任意一条路径上的顾客点，将其与配送中心相连接。

步骤2以该顾客点和配送中心的连线为轴，围绕配送中心顺时针进行扫描，以时间窗和车辆容量为约束条件，将满足条件的顾客点按照贪婪插入的方法，插入到最优插入位置，循环该步骤，直到不满足约束为止，便形成一条车辆行驶路径。

步骤3若系统中存在不在任意一条路径上的顾客点，则转步骤1。

步骤4若系统中所有顾客均在某条路径上，则形成一系列行驶路径，得到初始解。

步骤5算法结束。

2.3 抖动

抖动是变邻域搜索的关键阶段，它能够改变解的搜索方向，实现搜索空间多样化，避免陷入局部最优。本文算法中的抖动阶段采用路径重连实现当前解到另一个解的转换。

定义3可行的路径重连。路径重连(path relinking)是GLOVER[15]在1997年引入的元启发式算法，该方法通过在当前解与导向解之间建立联系来生成新解，若生成的新解可行，则该操作称为可行的路径重连。本文分别以个体历史最优解和种群历史最优解作为导向解进行路径重连。

抖动的步骤如下：

步骤1选择导向解中某条路径rk。

步骤2将路径rk包含的顾客点从当前解中删除。

步骤3当前解中，将有顾客点被删除的路径中剩下的顾客点，在满足式(7)和式(8)有关时间窗和车辆容量约束条件下，添加到没有删除顾客点的其他路径上。

步骤4将路径rk直接加入到当前解中，便得到了一个新解。

步骤5算法结束。

假定随机选择导向解中的一条路径为(0,2,4)。当前解中含有顾客点2和顾客点4的路径分别为r1和r2。首先分别从r1和r2中删除顾客点2和顾客点4;r1和r2中剩余顾客点，在满足时间窗和车辆容量约束条件下，依次添加到没有删除顾客点的其他路径上；不满足上述约束的顾客点，则保留在原路径上。将导向解中路径(0,2,4)加入到当前解中，由此生成新解。

2.4 邻域搜索

邻域搜索采用交换、插入和2-opt三种算子[16]。三种算子同时考虑选择的顾客点或边在同一路径和不同路径2种情况。

定义4可行交换。基于可行解中同一条路径，交换2个顾客点产生新路径。若交换后，新路径上交换位之后的顾客点满足式(7)顾客时间窗约束，则该交换为可行交换。基于可行解中不同路径，交换2个顾客点产生两条新路径。若形成的新路径均满足式(7)顾客时间窗约束和式(8)车辆容量约束，则该交换为可行交换。

交换步骤如下：

步骤1在路径集中随机选择2个顾客点。

步骤4算法结束。

定义5可行插入。在路径中随机选择一个顾客，若将该顾客点从当前位置删除，然后插入到同一路径或不同路径中，形成新的路径依然是可行路径，则这个插入操作被称为可行插入。

插入步骤如下：

步骤1从路径rk=(0,vk1,…,vkl,…,vkn,…)中随机选择一个顾客(记为vkl)并将其从rk中删除。

步骤4算法结束。

定义6可行2-opt。在同一路径rk或不同路径rk和rk′中，将两条不相邻的边断开重新连接，若形成路径是可行路径，则称该2-opt操作为可行2-opt。

2-opt步骤如下：

步骤1在路径集中随机选择两条不相邻的边，将其断开。

步骤3若断开的两条边位于不同路径上，分别记为rk和rk′。

步骤5算法结束。

由图4可知，当断开同一条路径上不相连的两条边(1,3)和(4,2)后，将被断开的路径段(3,4)反转，得到新的路径(0,1,4,3,2,5)。

由图5可知，当断开两条路径上两条边(3,5)和(4,7)后，将被断开的两个路径段进行交叉连接，得到新的路径(0,1,3,7,8)和(0,2,4,5,6)。

需要注意的是，邻域搜索时，由于顾客点位置发生变化，需要判断路径是否可行。由于在同一路径上执行3种操作算子时，该路径包含的顾客点没有发生变化，必定满足车辆容量的约束，只需考虑是否满足时间窗。而在不同路径上执行3种操作算子时，每条路径上包含的顾客点发生变化，此时除了考虑是否满足时间窗的约束以外，还要考虑是否满足车辆容量的约束。

2.5 算法复杂度分析

VNS算法时间复杂度分析如下：对于最大迭代次数为Tmax、问题规模为I的OVRPTW，生成初始解解的时间复杂度为O(1)；每个解的操作中，顾客移动、顾客交换、2-opt和路径重连的时间复杂度均为O(I2)；是否接受新解的时间复杂度为O(1)；每一代的时间复杂度为a×O(I2)+b×O(1)，其中a,b为正整数；Tmax代的时间复杂度为Tmax×(a×O(I2)+b×O(1))。因此，整个算法的时间复杂度为O(1)+Tmax×(a×O(I2)+b×O(1))。可见，所提算法的时间复杂度与算法迭代次数和问题规模有关。

2.6 算法证明

引理1最优解存在性。OVRPTW存在最优解x*。

证明OVRPTW为线性规划问题，属于凸优化问题[21]，因此存在最优解x*[22]，证毕。

定理1邻域存在性。模型存在最优解，因此在可行解集F内，给定一个解x(x≠x*)，则至少存在一个邻域结构N，满足N=|x→x*|，并称解x*在解x的邻域结构N内，即解x与最优解x*之间至少存在一个广义距离，广义距离可以是欧式距离、汉明距离或者k-opt算子等[23]。

证明反证法。若模型对于任意给定可行解x(x∈F)，不存在一个邻域结构N=|x→x*|，即解x*不在可行解集F中，则解x*不是模型的最优解，与已知矛盾。证毕。

定理2局部最优解可穷性。模型为组合优化问题且存在最优解x*，任意给定一个可行解x，则在解x的邻域结构N(x)范围内可以找到所有局部最优解。

证明因为模型为组合优化问题，则N(x)邻域内解空间有限，所以可以通过枚举算法获得所有局部最优解，即局部最优解是可穷的。证毕。

引理2路径可行性。使用VNS算法得到的开放式带时间窗的车辆路径是可行的。

证明可行解集F中所有解x均满足定义的等式约束(2)～约束(8)，变邻域也是在可行解集F内寻找不同的邻域结构Ng，从而寻找局部最优解xg，即xg∈F，因此局部最优解xg满足定义的等式约束(2)～约束(8)，局部最优解中的路径也满足模型条件约束。证毕。

基于以上定理和引理，证明使用VNS算法求解OVRPTW具有可行性。

3 实验结果与分析

下面采用两组算例测试本文VNS算法求解OVRPTW的性能。算例1来自文献[24]；算例2采用100个顾客点的Solomon标准测试算例(http://web.cba.neu.edu/～msolomon/problems.htm)。

算法采用Microsoft Visual Studio 2017编程，在Intel(R)Core(TM)i7-8750H CPU@2.20 GHz 2.21 GHz环境下运行。本文参数设置如下：种群规模为N=50，最大迭代次数Tmax=1 000，随机运行10次。

3.1 算例1结果对比分析

算例1中顾客坐标是在[1,150]×[1,150]的区域内随机生成，其编号为1,2,…,19,20，配送中心坐标为(70,70)，其中顾客具体信息(坐标、货物需求量及时间窗)参见文献[24]。本文将VNS算法与文献[24]中的简单遗传算法、基于or-opt的模拟退火算法、混合遗传算法，文献[25]中的基本蚁群算法、单点单亲遗传混合蚁群算法、多点单亲遗传混合蚁群算法，文献[26]中的基本蝙蝠、精英遗传混合蝙蝠、多点重组精英混合蝙蝠、单点重组精英混合蝙蝠共11种算法的求解结果进行比较，具体结果如表1所示。

表1 11种算法结果比较

由表1可知，使用同一组算例求解VRPTW问题时，本文VNS算法的平均路径长度以及最优路径长度均最短，而使用的车辆数比简单遗传算法、基本蚁群算法、单点单亲遗传混合蚁群算法、多点单亲遗传混合蚁群算法、基本蝙蝠以及精英遗传混合蝙蝠都要少。这表明，在求解VRPTW时，本文VNS算法求解质量相比其他算法更优。

尽管表1所呈现的结果能初步验证本文的VNS算法在求解质量上具有优越性，但还需进一步通过统计学上的显著性检验，比较排序以上11种算法在同一个数据集上的性能优劣。Friedman检验[27]作为非参数检验的方法，能对多种算法在每个数据集上的计算结果进行比较排序，并检验算法在置信区间内是否存在显著性差异。详细比较结果和统计结果分别如表2和表3所示。

表2 11种算法Friedman检验排序及秩平均值

表3 Friedman统计结果

Friedman检验秩平均值越低，算法性能越优。因此，由表2的结果可知，11种算法性能排序为：VNS算法(1.67)>单点(多点)重组精英混合蝙蝠(3.00)>混合遗传算法(3.67)>精英遗传混合蝙蝠(5.50)>单点单亲遗传混合蚁群算法(6.17)>基于or-opt的模拟退火算法(6.33)>多点单亲遗传混合蚁群算法(7.17)>基本蚁群算法(9.50)>简单遗传算法(9.83)>基本蝙蝠(10.17)。

表3显示了在自由度为10、置信区间为99%的卡方分布下，Friedman统计量为25.262，p值为0.005<0.01，由此可得出11种算法之间存在1%水平下显著差异的结论。综上所述，根据表1的求解结果，如表2和表3的统计结果可知，本文VNS算法在各方面均较优，11种算法之间存在显著性差异。因此，初步验证了本文VNS算法在求解VRPTW时具有可行性和有效性。

3.2 算例2结果对比分析

算例2采用经典的Solomon Benchmark算例集，共包括R1,C1,RC1,R2,C2,RC2六类。每类算例均是在100×100的单位区域内生成了1个配送中心和100个顾客点，其中R类、C类和RC类客户的地理位置分别由随机分布、聚类分布以及混合随机聚类分布生成；R1、C1、RC1类算例的时间窗紧，而R2、C2、RC2类算例的时间窗宽，因此在每条路径上能服务更多的客户。Solomon Benchmark的算例，原本是VRPTW的算例。在此，借鉴文献[5-6]的作法，即采用该算例的基本数据，车辆服务完最后一个顾客即结束，不用返回配送中心。本文将VNS算法与文献[5]的改进的禁忌搜索启发式算法(Improved Tabu Search Heuristic，TS)、贪婪的前瞻性路线构造启发式算法(Greedy Look-Ahead Route Construction heuristic Algorithm，GLARCA)、进化算法(Evolutionary Algorithm, EA)和贪婪的随机多启动轨迹局部搜索算法(Greedy Randomized Multi-Start Trajectory local Search algorithm, GRMSTS)以及文献[6]的统一的变邻域搜索算法(Unified Variable Neighborhood Search，UVNS)、统一的混合遗传搜索算法(Unified Hybrid Genetic Search，UHGS)、弹射链迭代局部搜索算法(Iterated Local Search Algorithm，ILSA)和求解OVRPTW的当前已知最好解(Best Known Solutions，BKS)的求解结果进行比较。

(1)解比较

通过与已有文献最好解，以及其他算法得到的解进行比较，分析本文VNS算法的求解性能，如表4和表5所示。表中：TD表示总行驶成本;GAP表示VNS算法的解比当前已知最好解之间的差距，GAP=(已有文献最好解-已知最好解)/已知最好解×100%。

表4 Solomon中R1、C1和RC1数据集的详细结果

表5 Solomon中R2、C2和RC2数据集的详细结果

由表4可知，本文VNS算法在求解R1、C1和RC1类算例中，有16个算例的VNS解比当前已知最好解更优，5个算例的VNS解与当前已知最好解相同，其行驶成本平均节约了0.60%。由表5可知，在求解R2、C2、RC2类算例中，有19个算例的VNS解比当前已知最好解更优，3个算例的VNS解与当前已知最好解相同，其行程成本平均节约了7.80%。因此，由表4和表5的详细结果及比较可知，VNS算法能表现出良好的求解质量和性能，由此进一步验证了本文VNS在求解OVRPTW上的可行性和有效性。

(2)收敛性分析

为分析VNS算法的收敛性，本文以算例2中R101～R104、RC101～RC104、R201～R204、和RC201～RC204为例，根据VNS算法求解OVRPTW随机运行10次，迭代1 000次的过程数据，绘制两组VNS算法收敛图，如图6和图7所示。

由图6可知，算法在300代之前收敛速度快，300～900代中收敛速度较慢，在900代左右向各自的最好解收敛。由图7可知，算法在200代之前收敛速度较快，在200～900代中收敛速度缓慢，在900代后收敛于各自的最好解。因此，根据两组收敛图可知，VNS算法不管是在求解时间窗宽的算例还是时间窗窄的算例，最终都能收敛于各自的最好解。由此可知，本文VNS算法具有较好的收敛性。

(3)稳定性分析

为了分析本文VNS算法的稳定性，采用箱形图来观测VNS算法求解R101～R104、RC101～RC104、R201～R204、和RC201～RC204每组算例10次后得到解的分布情况，如图8和图9所示。其中，黑色粗线表示中位数，该箱形图分别由上四分位数和下四分位数组成，竖线表示该组结果的平均偏差，竖线两端的横线分别为上限(最大值)和下限(最小值)，空心的圆圈表示异常值。

由图8可知，R101～R104和RC101～RC104的箱盒长度短，上四分位数和下四分位数间距较小，且部分算例其上下四分位数接近于0。相比图8来说，图9中R201～R204和RC201～RC204的箱盒长度虽较长，但异常值较少，其中R201～R204的解不存在异常值。从两组箱形图整体来看，平均偏差均较小。由此可知，本文利用VNS算法求解OVRPTW 10次后解的离散程度较小，从而表明本文VNS算法具有稳定性。

4 结束语

在外卖配送过程中，通常需要骑手满足配送时效性、准确性以及开放性等要求。本文基于此背景，对开放式带时间窗车辆路径问题进行探讨，考虑配送车辆无需返回配送中心和时间窗等影响，构建配送行驶总成本最小化为目标函数的OVRPTW模型，并设计了一种变邻域搜索的启发式算法进行问题求解。本文通过使用两组算例，利用VNS算法分别对VRPTW和OVRPTW进行求解，并与已有文献和现有已知最好解进行对比分析。实验结果表明：①本文设计的VNS算法在求解VRPTW时，能获得更短的运输里程，且与众多种算法相比，该算法优势明显；②在求解OVRPTW时，大多数算例的VNS算法最好解都优于已有文献最好解，通过该算法求解，明显降低了车辆行驶成本，由此表现出VNS算法良好的求解质量；③通过收敛图和箱形图可知，本文VNS算法在求解OVRPTW时，具有较好的收敛性和稳定性，最终验证了该算法良好的求解性能。

未来，将进一步考虑天气、交通、实时路况和突发事件等对路径优化的影响，建立相应的数学模型并设计算法求解。