基于聚类的LNS算法求解异构VRP问题.pdf

该文研究了异构车辆路径问题(heterogeneous fleet vehicle routing problem,HVRP),在经典 HVRP 模型的基础上,设计了结合均值漂移聚类算法及大邻域搜索算法的混合求解算法(mean shift-large neighborhood search,MS-LNS)。该算法通过均值漂移聚类算法对客户集进行分类,达到减少计算量、加快算法收敛速度的效果。算法使用单链设计,结合 swap 邻域变换及 insert 邻域变换产生新式邻域变换方法,使邻域变换方法可以随机处理路径间与路径内变换。新增 redistribution邻域变换,在变换后对新解检测是否存在不满足车辆载重利用率的子路径,并将其删除,达到提高车辆利用率的目的。3组仿真实验使用 9 组算例:实验一比较了异构与同构车辆的配送效果,验证结果表明异构车辆配送方案成本较低;实验二验证了聚类算法在不同规模客户数据中的有效性;实验三使用 MD-LNS 算法计算了 4 组算例,并与 4 种算法的结果进行比较,验证了在得出相近最优解的前提下,该算法能够减少算法的总体运行时间。仿真实验结果验证了模型的合理性及算法的有效性。关键词:异构车辆路径问题;均值漂移聚类算法;大邻域搜索算法;单链设计;redistribution 邻域变换中图分类号:TP301.6摇 摇 摇 摇摇摇 文献标识码:A摇 摇 摇 摇 摇 摇 文章编号:1673-629X(2023)09-0098-07doi:10.3969/j.issn.1673-629X.2023.09.015LNS Algorithm Based on Clustering for Solving HVRPZHAO Xiong,LI Lin(School of Science,Shenyang Aerospace University,Shenyang 110136,China)Abstract:We mainly study the heterogeneous fleet vehicle routing problem(HVRP).Based on the classical HVRP model,a mean shiftlarge neighborhood search(MS-LNS)algorithm,which combined with the mean shift clustering algorithm and large neighborhoodsearch algorithm,was proposed.The customer data was divided by classifying the customer set,so as to reduce the amount of calculationand accelerate the convergence speed of the algorithm.The use of single chain design,combined with the swap and insert neighborhoodsearch,the new neighborhood search was produced,which can randomly handle the neighborhood search between paths and one path.Inaddition,a new neighborhood search named redistribution was used to detect whether there is a sub path that does not meet the vehicleload utilization rate for the new solution after the neighborhood search,and delete it to improve the vehicle utilization rate.Ninenumerical examples were used to set up three groups of experiments.Experiment one compares the distribution effects of heterogeneousand homogeneous vehicles,and the verification results show that the cost of heterogeneous vehicle distribution scheme is low.Experimenttwo verifies the effectiveness of clustering algorithm in different scales of customer data.Experiment three uses MD-LNS to calculatefour examples and compare with the four algorithms.It is verified that the algorithm proposed can reduce the overall running time on thepremise of obtaining similar optimal solutions.Simulation results verify the rationality of the model and the effectiveness of the algo鄄rithm.Key words:HVRP;mean-shift clustering algorithm;large neighborhood search algorithm;single chain design;redistributionneighborhood search0摇 引摇 言车辆 路 径 规 划 问 题(vehicle routing problem,VRP)是规定一组车辆在一组客户集合间运输货物,并使车辆路径满足相应目标函数要求的研究,是物流运输行业中十分重要的一个研究命题,是优化物资分配,调度运输的方法之一。VRP 自 1959 年被提出后便得到了学者们的关注,形成以 VRP 为基础的各项分支研究。HVRP 便是其中之一,主要研究不同车辆在运输第 33 卷摇 第 9 期2023 年 9 月摇 摇 摇 摇 摇 摇 摇 摇 摇 摇计 算 机 技 术 与 发 展COMPUTER TECHNOLOGY AND DEVELOPMENT摇 摇 摇 摇 摇 摇 摇 摇 摇 摇Vol.33摇 No.9Sep.摇 2023调度中的物资分配问题,其中车辆以车辆归属、车辆属性等进行区分。在 HVRP 下存在不同的研究方向,比如带时间 窗的 HVRP 问题1-3(heterogeneous fixedfleetvehicleroutingproblemwithtimewindows,HVRPTW)、带取送货的 HVRP 问题4-5(heterogeneousfixed fleet vehicle routing problem simultaneous pickupand delivery,HVRPSPD)等。VRP 已知是 NP 难问题,可知 HVRP 也是 NP 难问题。精确方法求解问题具有一定难度,为能快速求解问题,部分学者通过模拟自然演变,采用元启发式方法进行求解,并取得了不错的成果。Wu6在求解车辆数量限制下的 VRP 时,使用自适应大邻域搜索算法,并将算法的消除与添加两个变换步骤加以改进,将客户运用聚类方法分类,并在消除变换过程按照聚类结果消除,避免单客户消除方法中客户返回原位置这种算力上的浪费。Molina7在求解 HVRPTW 时设计了一种具有局部搜索的混合蚁群算法(ant colony system,ACS),称为 memetic-ACS 算法,并在其实验中得到了新的最优解。鲁建厦8研究了不同初始解对算法的影响,并证明使用聚类算法生成的初始解能使算法收敛速度有较大改进。Meliani9和 Wei10在其研究中就用 C-W 节约算法来求解模型的初始解。Jin11使用多启动策略来增加每次迭代的初始解的多样性,以此加大产生当前最优解的可能性。闫军12通过将客户集合分成不同的子群,简化数据复杂度然后再进行求解。为提高初始解效率,该文通过均值漂移聚类算法将客户分成多个子类,在初始化时优化每条路径对客户个体的选择,从而优化算法初始解。而后通过单链设计优化邻域变换方法,加快 LNS 算法的收敛速度,并通过三组实验验证了 MS-LNS 算法的合理性及有效性。1摇 问题描述与数学模型HVRP 包括车辆数量限制下(heterogeneous fleetvehicle routing problem)的 HFVRP 和无车辆数量限制(fleet size and mix vehicle routing problem)的 FSMVRP两类13。HFVRP 主要求解在现有资源下如何优化分配,而 FSMVRP 则更侧重于市场需求的最优调度方案。该文研究了 FSMVRP。1.1摇 问题描述该模型以最小化总成本为目标函数值。共有 N个客户需要服务,每个客户的需求量为 qi。车场标记为 0 点。运输车辆数量为 K,共有 M 种车辆。异构车辆按照最大载荷量区分,第 k 种车辆的载荷为 Qk,启动成本为 Ck,单位行驶成本为 Cu。车辆从车场出发服务客户,服务完后回到车场。dij表示客户 i 到 j 的距离。1.2摇 数学模型min:F=移Ni=0移Nj=0移Kk=1Cuxijkdij+移Nj=1移Kk=1Ckx0jk(1)s.t.移j沂Nx0jk=移j沂Nxj0k=1摇(2)移i沂N移k沂Kxijk=移i沂N移k沂Kxjik=1,坌j 沂 N(3)移i沂N移j沂Nqjxijk臆 Qk,坌k 沂 K(4)其中,式(1)F 为目标函数,最小化车辆总成本;式(2)保证每辆车必经过0 点,即车辆必从0 点出发且回到0点;式(3)保证每个客户只有一辆车服务,且只服务一次(此条件可以消除子路径的可能性);式(4)保证车辆不会超载。xijk为 0-1 变量,当车辆 k 经过弧 ij 时为1,否则为 0。2摇 基于均值漂移聚类的 LNS 算法在求解 HVRP 问题时常使用随机算法或贪心算法生成初始解。相较于随机算法,贪心算法获取的初始解距最优解更近,能加快算法前期收敛进度,但由于贪婪算法的最近邻选择机制减弱了初始解群的多样性,使算法容易出现早熟现象。为找到更合适的初始解,加快算法收敛,该文提出使用均值漂移聚类算法区分客户子集,依照客户子集初始化客户列表。2.1摇 编摇 码总路径 赘 采用单链编码方式。客户从 1 开始编号 V=1,2,N。车辆依照类型从客户集后一位开始编号 M=N+1,N+2,N+L,其中任意一个元素表示一类车辆。每辆车的子路径 赘k表示为(N+1,3,5,9,12,4,7),其中起始点为车辆类别,其后所有点为子路径中的客户点。总路径表示为 赘=赘1,赘2,赘K。2.2摇 均值漂移聚类算法初始化均值漂移聚类的主要方法是在客户区域内设置 M个移动点粒子 Xm,在每次迭代过程中移动点粒子搜索扫描半径内的所有客户点,依照公式(5)(其中 Sm为 fm限制条件)生成移动向量来更新移动点坐标(6),当某些移动点十分接近的时候将这些移动点合并,直到所有移动点不再变化时停止迭代。此时剩余移动点的个数就代表客户点聚类的个数,而每个移动点扫描过的客户就属于此类别的客户子集。fm=1Sm(xi-Xm),坌m 沂 MSm=xi|椰xi-Xm椰2 maxQk,坌k 沂 K 则转到步骤 4;若 Qk Qd hQk,埚k 沂 K 则转到步骤 5;若 Qd minhQk,坌k 沂 K 则转到步骤 6;Step4:选择载荷量最大的车辆 k沂K,按照总路径初始化的方式生成需求量 qd刚好大于 hQk的子路径,其子路径包含的客户集为 vl,则剩余客户集合 Vl=Vl-vl,剩余客户需求量 Qd=Qd-qd。返回到步骤3继续判断;Step5:选择对应车辆 k,按照总路径初始化方式生成子路径;Step6:配置车辆 s=argminQk,坌k 沂 K 先将 Vl按回路总成本最小排成路径 赘s,再从已服务客户集合Vl=V-Vl 中,按照最小目标函数值增量方式提取路径 赘l中客户点 i 到路径 赘s,并保证客户 i 提取后 赘l满足车辆 l 的载重下限要求,直到 赘s满足步骤3 为止。2.4摇 变换后解的接受准则该文采用模拟退火算法的接受准则判断每次变换后的路径能否替换当前解。当前解的目标函数值高于当前个体最优解时,通过计算公式(7)得到接受概率,再通过轮盘赌形式决定是否接受当前解。其优点在于前期温度值 T 较高时使粒子具有较大的容错能力,可以让粒子在邻域内快速移动;而后期 T 值减小使粒子容错能力减弱,增强了粒子邻域搜索能力,加快收敛进程。每当接受准则成功执行时需要更新温度值 T=籽T。其中 籽 为温度变化率。P=e(F(Papb)-F(赘)/T摇(7)算法流程见图 3。FPapbPagbPagbredistribution图 3摇 MS-LNS 算法流程先使用聚类算法将客户分为多个子群,而后对每个子群使用贪婪算法,这样既能兼顾贪婪算法对初始解群的优化,也能保证初始种群的多样性。该文通过单链编码方式改进变换方法使得每次变换的空间更大,搜索速度更快。对于使用率较差的车辆使用redistribution 变换重排。以此三种方式对 LNS 算法进行改进,加快 LNS 求解速度。3摇 仿真实验3.1摇 实验数据使用 Golden14及 Penna15提供的 13-17、20 号算001摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 计算机技术与发展摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 第 33 卷例和对应车辆数据(表 1 中共有六种不同的运输车辆Ver.A-Ver.F),以及 Solomon16中 c201、r201、rc201算例进行实验。Solomon 算例使用 20 号算例中车辆数据进行实验。表 1 中 Q 为车辆载荷,C 为车辆固定成本。表 1摇 车辆数据No摇 摇 摇 Ver.A摇 摇 摇摇 摇 摇 Ver.B摇 摇 摇摇 摇 摇 Ver.C摇 摇 摇摇 摇 摇 Ver.D摇 摇 摇摇 摇 摇 Ver.E摇 摇 摇摇 摇 摇 Ver.F摇 摇 摇QCCuQCCuQCCuQCCuQCCuQCCu132020130351.140501.2701201.71202252.52004003.2141201 00011601 500 1.13003 500 1.4155010011002501.6160450216401001802001.61404002.11750251120801.22001501.53503201.8206010011403001.720050023.2 摇 参数设计为保证算法的收敛速度与跳出局部最优的能力,需要优化现有的算法参数。文中算法涉及两个参数,即聚类算法扫描半径 r 和模拟退火温度变化量 籽。分别通过以下两种方式计算适合文中算法的参数值:3.2.1摇 聚类算法扫描半径 r为保证使用均值漂移聚类时不会出现过多孤立点,保证客户集合分类符合实际,采用箱型图检测客户点距离并尝试 1/4 位数,中位数,3/4 位数做扫描半径的效果。15、16 号算例为 50 个客户点(图 4(a),17号算例为 75 个客户点(图 4(b),20 号算例为 100 个客户点(图 4(c)。图 4摇 四组数据在 1/4 位数时的客户分类四组客户数据在取中位数作为扫描半径时都无法对客户集合进行分类,取 1/4 位数时每组的分类情况如图 4 所示。在 1/4 位数周围取值进行验证时发现,相较于 rc201,15 号及 17 号客户数据的分类对扫描半径的取值十分敏感,令 15 号数据的扫描半径 r=20.7时,分类个数缩减到 3 个。令 r=19 时分类的数据较r=20.2 时有比较明显的变化,而 r=17 时 15 号客户数据则被分为六类。为保证分类质量,在 3.2 节计算当中使用 1/4 位数进行计算求解。3.2.2摇 模拟退火温度变化率 籽采用多组不同的变化率对算例进行检测,以检查不同变化率之间的差别,找到尽可能好的参数值。如图 5 所示,共设置 4 组参数值 0.95、0.9、0.8、0.7。依照算法生成50 个粒子迭代变换1 000 次,总计10 次实验的平均结果。模拟退火的接受条件(7)中粒子每接受一次变换,温度变量 T 便会依照变化率 籽 进行变化,当 籽 过大时会导致温度 T 变化缓慢,粒子变换的容错能力过强,不利于粒子的局部搜索;而当 籽 过小时 T 变化过快,会导致算法过快收敛,无法跳出局部最优解。可以看出不论在图 5(a)还是在图 5(b),当变化率 籽=0.9 时,算法收敛能力最好。当 籽=0.8 或 0.7 时,算法收敛能力相差不大,但都弱于 籽=0.9 的时候,说明 籽=0.9 时可以保持良好的收敛性能,具有较快的下降速度。图 5摇 模拟退火温度变化率 籽 变化曲线3.3摇 实验结果进行了三组仿真实验。实验一通过比较同种车辆下与异种车辆下的总成本、总路径长度及实际平均载货率,验证异构车辆在 VRP 中是否存在优势。实验二通过比较 20 号数据、c201、r201、rc201 在 MS-LNS 算法及 LNS 算法下的实验结果,检验均值漂移算法是否对算法收敛有增益效果。实验三使用文中算法计算13-16 号算例并与 Penna15中结果进行比较。该文使用 java 编程,在 Intel(R)Core(TM)i5-4200H CPU101摇 第 9 期摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 赵摇 雄等:基于聚类的 LNS 算法求解异构 VRP 问题 2.80 GHz 计算机上运行。图 6摇 17 号算例实验结果摇 摇 实验一:对 17 号算例进行 10 次计算,每次计算共得出四组数据:总成本、固定成本、移动成本及载重比,再将所得数据按照总成本大小顺序排列。为减少数据区间不同所造成的影响,使用相对数进行比较,其计算公式为:qR=qA/q,其中 qR代表相对结果,qA代表数据绝对值,q 代表各组数据的平均值。计算结果如图 6所示。其中,车辆类型 B 的使用量与总成本成反比,而载重比在总成本不断升高情况下有着逐渐下行的表现,说明在车辆低载重比的情况下难以达到最优解。分别比较异构车辆与其中四种单一车辆的计算结果,观察总成本、总路径长度及实际平均载货率之间的差别。由表 2 可知,B 类车辆的计算结果与异构车辆的计算结果十分相近,且比 A、C、D 类结果要好,该结果正好和图 6 中显示的各类车辆数量与总成本之间的关系相对应,且异构车辆问题中车辆的平均载重比在五类数据中最大,表示异构车辆问题中所有种类车辆都得到了充分的利用。由此可以证明,异构车辆的 VRP模型相较于单一车辆的 VRP 模型具有一定优势。表 2摇 异构车辆与单一车辆配送结果比较车辆类型摇 摇 摇 总成本摇 摇 摇 摇摇 摇 摇 总路径长度摇 摇 摇 摇摇 摇 摇 移动成本摇 摇 摇 摇minavgminavgminavg平均载重比异构2 084.851 22 098.012 6806.119 2902.289 21 166.445 81 174.197 30.981 3A2 415.8122 426.686 61 690.8121 701.686 51 690.8121 701.686 50.940 7B2 093.061 62 150.697 3937.376948.343 81 124.851 21 138.012 60.947 2C2 137.565 32 158.953 5725.043 5739.302 31 087.565 31 108.953 50.974 3D2 419.819 02 432.212 5640.118640.1181 139.8191 152.212 50.974 3摇 摇 实验二:运用 MS-LNS 算法和 LNS 算法分别计算20 号算例、c201、r201 及 rc201 算例10 次,其中实验结果的平均值如图 7 所示。图 7摇 MS-LNS 算法与 LNS 算法比较可以看出,图 7(a)和 7(c)中两种初始化方案尚未产生较大差异,比较(a)(c)两图的迭代曲线可知:两种算法的收敛速度相当。在图 7(b)和图 7(d)中均值漂移算法使得初始值相较于使用贪心算法有较大改进,图 7(b)中虽然 MS-LNS 在起始点位置的目标函数值与 LNS 相比稍差,但后续迭代过程中 MS-LNS的收敛速度却比 LNS 的收敛速度要快,使得 1 000 次迭代后 MS-LNS 算法的结果要比 LNS 算法的更好。实验三:将文中算法与四种算法进行比较,数据如表 3 表 5 所示。其中 FSMFD 模型的目标函数为固定成本与移动成本总和最小,FSMF 模型为固定成本最小,FSMD 模型指移动成本最小。BKs 指目前对应算例中的最优解值,CG 算法及计算结果由文献17给出,SMA-U1 由文献18给出,VNS1 由文献19给出。时间(t)单位为秒。%为 MS-LNS 算法与 ILS-RVND 算法的增量百分比。从表 3 可以看出,文中算法在最优值(m)上与 Penna15的改进算法还有一定差201摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 计算机技术与发展摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 第 33 卷距。文中算法最优解与 ILS-RVND 算法的平均差距为 2.67%。在求得文中算法最优解情况下所耗时间(t)要少,算例 13 所耗时间比 ILS-RVND 少 20.39 s,算例14 的时间少6.25 s,算例15 少6.15 s,算例16 少10.97 s。表 3摇 FSMFD 模型结果NoBKsCGSMA-U1VNS1ILS-RVNDMS-LNS%13m2 964.652 964.652 964.652 964.652 964.653 141.215.97t-3.950.32-27.677.28-73.6914m9 126.909 126.909 126.909 126.909 126.909 187.540.67t-51.78.9-11.275.02-55.4615m2 634.962 634.962 635.212 634.962 634.962 780.155.54t-4.361.04-13.477.32-45.6616m3 168.923 168.923 169.123 168.923 168.923 265.323.06t-5.9813.05-17.556.58-62.51表 4摇 FSMF 模型结果NoBKsCGSMA-U1VNS1ILS-RVNDMS-LNS%13m2 4062 406.362 406.362 406.362 408.412 501.843.88t-1017.12-30.377.06-76.7514m9 1199 119.039 119.039 119.039 119.039 187.790.75t-5119.66-11.455.07-55.7215m2 586.372 586.372 586.372 586.372 586.372 682.373.71t-1025.1-19.296.21-67.8116m2 720.432 720.432 729.082 720.432 720.432 838.084.32t-1116.37-19.986.79-66.02表 5摇 FSMD 模型结果NoBKsCGSMA-U1VNS1ILS-RVNDMS-LNS%13m1 491.861 491.861 491.861 491.861 491.861 560.784.62t-4.113.45-30.686.69-78.1914m603.21603.21603.21603.21603.21618.882.60t-20.410.86-13.924.37-68.6115m999.82999.82999.82999.82999.821 080.658.08t-4.619.14-14.76.3-57.1416m1 1311 1311 1311 1311 1311 220.387.90t-3.3613-17.256.79-60.64摇 摇在 FSMFD 模型中 MS-LNS 算法的平均耗时较ILS-RVND 算法减少了 59.33%;在 FSMF 模型中平均耗 时 减 少 了 66.58%;在 FSMD 模 型 中 减 少 了66.15%。由此验证了文中算法的高效性和可行性。4摇 结束语在基本 HVRP 模型的基础上,根据客户点分布的空间特性,提出了结合均值漂移聚类的大邻域搜索算法,设计了三组仿真实验。三组仿真实验结果分别验证了异构车辆配送方案在求解 VRP 问题中的效果更好,表明均值漂移聚类算法在随机分布和聚类分布这两类客户数据下对 LNS 算法的收敛速度提高更有效果。未来的研究方向可以对车辆的不同属性,如车辆载荷、车辆移动成本等因素进行敏感性分析,研究不同属性变化情况对目标函数的影响。参考文献:1摇 PENNA P,AFSAR H M,PRINS C,et al.A hybrid iterative301摇 第 9 期摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 赵摇 雄等:基于聚类的 LNS 算法求解异构 VRP 问题local search algorithm for the electric fleet size and mix vehi鄄cle routing problem with time windows and recharging sta鄄tionsJ.IFAC-PapersOnLine,2016,49(12):955-960.2摇 BARADARAN V,SHAFAEI A,HOSSEINIAN A H.Sto鄄chastic vehicle routing problem with heterogeneous vehiclesand multiple prioritized time windows:mathematical model鄄ing and solution approachJ.Computers&Industrial Engi鄄neering,2019,131(3):187-199.3摇JIANG P,MEN J K,XU H,et al.A variable neighborhoodsearch-based hybrid multiobjective evolutionary algorithmfor hazmat heterogeneous vehicle routing problem with timewindowsJ.IEEE Systems Journal,2020,14(3):1-12.4摇 ALTPARMAK F,KARA M,KEECI B.A mathematical for鄄mulation and heuristic approach for the heterogeneous fixedfleet vehicle routing problem with simultaneous pickup anddelivery J.Journal of Industrial,Management Optimiza鄄tion,2021,17(3):1069-1100.5摇NEPOMUCENO N,SABOIA R B,PINHEIRO P R.A fastrandomized algorithm for the heterogeneous vehicle routingproblem with simultaneous pickup and deliveryJ.Algo鄄rithms,2019,12(8):158.6摇 YAN W,WANG Y,HE G,et al.An improved adaptive largeneighborhood search algorithm for the heterogeneous fixedfleet vehicle routing problem C/Proceedings of 2017IEEE 8th international conference on software engineeringand service science.Beijing:IEEE,2017:657-663.7摇 MOLINA J C,SALMERON J L,EGUIA I.An ACS-basedmemetic algorithm for the heterogeneous vehicle routingproblem with time windowsJ.Expert Systems with Appli鄄cations,2020,157:113379.8摇 鲁建厦,翟文倩,李嘉丰,等.基于改进混合蛙跳算法的多约束车辆路径优化J.浙江大学学报:工学版,2021,55(2):259-270.9摇 MELIANI Y,HANI Y,ELHAQ S L,et al.A developed tabusearch algorithm for heterogeneous fleet vehicle routing prob鄄lemJ.IFAC-PapersOnLine,2019,52(13):1051-1056.10 WEI L,ZHANG Z,LIM A.An adaptive variable neighbor鄄hood search for a heterogeneous fleet vehicle routing problemwith three-dimensional loading constraintsJ.IEEE Com鄄putational Intelligence Magazine,2014,9(4):18-30.11 JIN L,WANG D,ZHANG J.Heterogeneous fixed fleet vehi鄄cle routing problem based on fuel and carbon emissionsJ.Journal of Cleaner Production,2018,201:896-908.12 闫摇 军,常摇 乐,王璐璐,等.带时间窗的同时取送货车辆路径问题求解算法J.工业工程,2021,24(5):72-76.13 KUSUMA S,ANAN M,JANSSENS G K,et al.Heterogene鄄ous VRP review and conceptual frameworkC/Proceed鄄ings of the international multiconference of engineers andcomputer scientists.Hong Kong:IMECS,2014:1052-1059.14 GOLDEN B,ASSAD A,LEVY L,et al.The fleet size andmix vehicle routing problemJ.Computers&OperationsResearch,1984,11(1):49-66.15 PENNA P H V,SUBRAMANIAN A,OCHI L S.An iteratedlocal search heuristic for the heterogeneous fleet vehicle rou鄄ting problemJ.Journal of Heuristics,2013,19(2):201-232.16 SOLOMON M M.Algorithms for the vehicle routing andscheduling problems with time window constraintsJ.Oper鄄ations Research,1987,35(2):254-265.17 CHOI E,TCHA D W.A column generation approach to theheterogeneous fleet vehicle routing problemJ.Computersand Operations Research,2005,34(7):2080-2095.18 PRINS C.Two memetic algorithms for heterogeneous fleetvehicle routing problems J.Engineering Applications ofArtificial Intelligence,2008,22(6):916-928.19 IMRAN A,SALHI S,WASSAN N A.A variable neighbor鄄hood-based heuristic for the heterogeneous fleet vehicle rou鄄ting problem.J.European Journal of Operational Re鄄search,2009,197(2):509-518.401摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 计算机技术与发展摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 第 33 卷