[摘要]省电力物资周转库是仓储网络架构的关键节点，文中研究带库存容量限制的周转库选址与考虑时间窗和装载量约束的车辆配送路径优化的组合决策问题，构建以配送总成本是小为目标的选址-路径问题模型，设计两阶段启发式算法进行求解。第一阶段设计聚类-重心-搜索算法，求解带库存容量限制的省周转库选址问题;第二阶段采用自适应大邻域搜索算法，解决考虑时间窗和装载量约束车辆配送路径优化问题。基于S首2022年历史物流数据和已有仓储资源规模，采用两阶段启发式算法确定省电力物资周转库选址和配送路径。结果表明该算法能够有效降低仓储网络的总配送成本。

　　[关键词]电力物资:选址-路径问题;K-mein,聚类:重心法;自适应大邻城搜索算法

　　近年来，国家电网公司提出全网“一盘棋”发展战略，将“仓储资源一盘棋、物流配送一张网、实物资源一体化”作为仓储配送网络布局目标。省公司层面组织开展“省周转库—市县终端库”规划，各省周转库负责辐射区域内入库目录物资的集中抽检、集中存储，向辐射范围内的市县终端库进行物资转储、主动配送；市县终端库负责本单位检储配目录外物资的到货验收、抽样送检、暂存与中转供应，负责接收周转库配送物资及暂存中转供应，向需求单位提供工程领料或物资主动配送服务。省级仓储体系设置多个省级周转库，打破仓储管理的行政区域壁垒，实现资源由按业务属性、行政区域配置转向全域、全资源按需统筹配置。省周转库的合理选址布局、省周转库与市县终端库间的配送路径优化，是开展仓储网络优化工作的关键。

　　选址一路径问题(Location-Routing Problem,LRP)是选址定位问题和车辆路径问题的组合问题，两者都属于NP-hard问题。该问题最早由Gandy和Dohrn提出，用于解决在规划设施点的同时考虑访问客户顺序的问题"。Naeys Salhi将LRP求解算法归为4种类型:连续的启发式算法、基于聚类的算法、迭代的启发式算法和分阶层的启发式算法2。Fazayeli等提出了一种二阶段遗传算法求解带时间窗和模糊需求的LRP问题肉。王道平等通过引入客户重要度以及聚集度构造两阶启发式算法对物流配送选址-路径问题进行了求解.姫杨蓓蓓等利用两阶段启发式算法求解快递企业末端配送网络规划问题，第一阶段利用K-means聚类解决选址问题，第二阶段利用蚁群算法解决车辆配送路径问题。路世昌等利用两阶段启发式算法求解低碳物流选址-多车型路径问题6。

　　目前，国内外学者对于选址-路径问题的研究主要集中于快递和消费品领域，电力物资配送具有供应需求计划性强应急配送时效要求高、物资包装标准化程度低的特点,关于电力物资仓储网络选址一路径问题的研究相对较少、周鹏程针对电力公司物资配送中心选址优化决策问题，构建基于FCE的配送中心选址优化模型，采用NSGA-I算法进行多目标函数求解”。刘栋首先根据电网公司物资存储及管理的实际情况，采用免疫算法对配送重心选址模型进行求解，在选址方案确定后，利用启发式算法求解得到是优配送路线中。王程远针对电网企业的电力输配物流系统存在的问题，建立考虑要盖的配送节点选址-路径优化模型，采用结合模拟退火算法与局部搜索算法的混合启发式算法求解[0)。以上研究均为新建配送中心选址-路径问题，且未考虑时间窗约束。本文针对基于企业现有仓库资源的省周转库选址和路径规划问题进行研究，以总配送成本最小为目标建立数学模型，采用聚类-重心算法在备选市县终端库中选定首周转库，然后设计边界搜索算法对配送区域进行调整，以满足各辐射范围内的库存容量要求，最后针对选定的首周转库配送区域方案，设计自适应大邻域搜索算法求解固定时间窗的车辆配送路径问题。以S省国网公司周转库选址-路径问题为例，证明两阶段启发式算法的有效性。

　　1问题模型

　　1.1问题描述

　　已知市县终端库位置坐标、现有存储能力以及历史配送量、服务时间限制等信息。将满足检储配目录物资存储要求的市县终端库作为备选省周转库集合，从中选取n个作为省周转库，确定辐射范围，在满足车辆承载能力以及时间窗约束的前提下，规划从各个省周转库到市县终端库的车辆行驶路线,实现构建的“首周转库-市县终端库”两级仓储网络总配送成本最小。

　　1.2模型假设

　　①市县终端库需求量不可拆分且每个市县终端库仅能被一个省周转库和一辆车服务；

　　②车辆行驶过程无停留，到达市县终端库即可卸货；

　　③各市县终端库物资需求不能超过车辆最大装载量。

　　1.3符号说明

　　①集合。

　　表示市县终端库集台，{i|i=1,2 3….9;M表示备选省周转库集合，(m|m=1，2 3.….M.ME C:K表示省周转库m的车辆集合(k_|k_=1.2.3,'"，K_}。

　　②参数。

　　m表示某一备选省周转库;i表示某一市县终端库;k表示某一车辆;F_表示备选首周转库m的存储容量;a表示市县终端库m被选为首周转库后增加的固定费用;b;表示市县终端库i的固定费用;p表示车辆单位运输价格;d表示备选省周转库m到市县终端库i之间的行驶距离;q:表示市县终端库的运输需求;d表示市县终端库1到市县终端库之间的行驶距离;Q表示车辆最大载货量;h:表示市县终端库i允许最早开始配送时间;r表示市县终端库i允许晕晚配送时间;;表示市县终端库1的配送任务开始时刻;e:表示市县终端库的配送任务结束时刻;t表示车辆k的工作时间;t表示车辆的最长工作时间tm,1表示同一配送线路上车辆从市县终端库i-1到达市县终端库i的时间;u;表示同一配送线路上车辆在市县终端库i所停留的时间。

　　③决策变量。

　　w表示备选省周转库m是否被选为首周转库。选中为1.反之为0;x表示市县终端库i是否由首周转库m提供服务，如果提供服务为1.反之为0.y表示省周转库m的车辆k是否配送市县终端库i,如果配送为1.反之为0;z.表示省周转库m的车辆k由市县终端库i行驶到市县终端库j.其值为1.反之为0。

　　1.4模型建立

　　式（１）表示总配送成本最小化。式（２）表示省周转库被选中才能服务市县终端库。式（３）表示市县终端库只能被一个省周转库服务。式（４）表示选定省周转库与市县终端库的配送关系。式（５）表示选定省周转库的最大数量。式（６）表示市县终端库的需求总量不能超过省周转库的存储容量。式(7)表示车辆的限重，即货物的总运输量不能超过车辆的

　　最大装载量。式(8)表示省周转库所有车辆访问市县终端库的次数和，每个市县终端库只访问一次，式(9)表示所有车辆均从省周转库出发。式(10)表示车辆从该市县终端库进入必将从该市县终端库离开，确保了市县终端库的访问顺序。式(11)表示每辆车的工作时间不得超过最大工作时间、式(12)(13)表示车辆配送市县终端库所需的时间。式(14)表示市县终端库配送任务的时间窗约束。

　　2算法设计

　　对于省电力物资周转库选址-路径优化问题，设计两阶段启发式算法进行求解。第一阶段设计聚类-重心-搜索算法选定省周转库并确定配送区域;第二阶段针对选定的省周转库辐射区域，采用自适应大邻域搜索算法求解固定时间窗的车辆配送路径问题。

　　2.1聚类-重心-搜索算法

　　首先根据市县终端库位置坐标，采用K-means算法确定分类区域。然后根据市县终端库历史物流量采用重心位置法确定簇内重心，以聚类重心与备选省周转库之间实际行驶距离和最短为目标，确定省周转库选址方案。簇内重心数学表达式为式(15)(16).

　　其中.xpyp分别是类别P的市县终端库i的经度坐标和纬度坐标。α。为类别P的市县终端库i的历史物流量,X和Yp是簇内重心位置。

　　根据各市县终端库地理坐标，建立各市县终端库与省周转库距离矩阵，基于就近服务原则构建省周转库初始配送区域，应用边界搜索方式对区域划分进行调整，满足各自辐射区域内存储容量限制、具体搜索步骤如下:

　　步骤1在省周转库配送区域边界以单位距离划定范围,构建市县终端库构建搜索集台;

　　步骤2若集合不为空，将集台内市县终端库根据需求量大小进行排序，否则在现有边界范围基础上，增加单位距离划定范围，转至步骤1.重新构建市县终端库构建搜索集合;

　　步骤3在集台中依次判断市县终端库交换首周转库后,若省周转库减少资源缺口条件，将满足条件的市县终端库分配至相邻区域省周转库，否则不执行交换;

　　步骤4若省周转库不存在资源缺口或到达最大搜索范围，则输出区域调整结果。

　　2.2自适应大邻域搜索算法

　　针对固定时间窗的车辆配送路径问题，采用自适应大邻域搜索算法(ALNS)进行求解。算法采用整数编码，编号0表示省周转库，编号1.2….n表示市县终端库。车辆从省周转库出发，分别为各市县终端库提供服务。

　　采用节约里程法构造问题的初始解，节约里程法的思想为，由三角形各边关系性质计算各站点间的节约里程值。根据节约里程值在满足约束条件下将运输过程中的线路进行合并，每次合并后使得总运输里程减小的程度最大。

　　算法共计采用4种邻城搜索算子，分别为RandorDestroyWorstDestroy RandonRepair和GreedyRepai reRandonDestros和WorstDestroy为破坏算子，其中，RandomDestroy算子会随机选择路径中1-3个市县终端库节点进行移除操作,WorstDestroy算子则会选择路径中1-3个使目标函数增量量大的点进行移除操作;RandamRepair和GreedyRepalr为修复算子，与破坏算子类似，RandonRepair算子会采用随机策略将移除的市县终端库节点重新插入路径中，GreedyRepair算子则会采用贪婪思想。在ALNS算法中，每次针对解的操作都会选用一对破坏和修复算子进行，每个算子均有得分和权重，算法会根据一定的策略和算子的权重对算子进行选择，本文采用轮盘赌选择法(Roulette Wheel Selection RVS进行破坏与修复算子的选择。

　　ALNS算法的每次迭代中，算子评分统计表都会根据被选中破坏及修复算子在运算时的表现进行更新。算法每迭代指定次数后进入权重调整阶段，依据式(17)调整破坏及修复算子权重，同时重置各算子评分。

　　其中，ω。为算子权重,s。为算子分数，u为算子使用次数6为权重更新系数。自适应大邻域搜索算法具体步骤如下:

　　步骤1采用节约里程法构造初始解;

　　步骤2采用轮盘赌选择一对破坏算子和修复箅子，生成改进解;

　　步骤3计算改进解的目标函数值，若改进解目标函数优于当前解，则接受改进解，否则拒接改进解，更新算子分数;

　　步骤4若改进解目标函数优于最优解，则接受改进解为最优解。更新算子分数;

　　步骤5若迭代次数达到权重更新轮数，则更新算子权重;

　　步骤6若迭代次数达到最大迭代次数，则输出最优解。

　　3案例分析

　　3.1省周转库选址

　　S省电网公司设114个市县终端物资仓库，综合考虑2022年物资需求特性、供给特性、物理特性和检测需求，选定配电箱、10kv变压器、交流三相隔离开关、电缆分支箱、架空绝缘线缆等物资列入周转库入库物资目录。根据以上物资存储需求以及各市县公司物资仓库库容能力、检测能力,选定5个市县公司物资仓库作为首周转库备选仓库，拟从中选定4个作为首周转库。各备选省周转库的地理位置如表1所示。

　　首先采用K-means算法对各市县终端库进行聚类分析，生成4个聚类簇，聚类结果如图1所示。

　　由聚类分析求得4个聚类簇后，按照重心法模型求解各个首周转库选址坐标、将各物资需求点坐标、2021年物流量代入式(16)(17)，得出聚类1区域重心坐标。在5个备选省周转库中以聚类重心与备选首周转库之间实际行驶距离和最短为目标。最终确定W1、W2、W3、W5作为省周转库。在省周转库选址方案确定后，基于就近服务原则，确定各省周转库配送区域初始方案，然后采用边界搜索方式调整配送区域，满足各省周转库库存容量约束省周转库选址及辐射市县终端库如图2所示。

　　3、2配送路径优化

　　假设省周转库每周为配送间隔向下属市县终端库配送物资，以2022年52个周配送数据为例进行算法分析。假设配送车辆选用9.6米货车，根据各类配送物资空间占有率和车辆最大承载能力确定车辆配载情况;车辆每天最大工作时间为7小时，每次装卸货物时间为30分钟;运价采用阶梯计价模式，运输距离低于50km部分，运价为1185元，运输距离超过50公里的部分按22.5元/公里的标准进行计价。

　　节约里程法与自适应大邻城搜索算法优化效果对比如表2所示。

　　通过分析$首电力公司2022年全年配送数据得出，相比于节约里程法，使用自适应大邻域搜索算法可使配送成本优化9.52%。

　　4结语

　　本文针对基于企业现有仓库资源的省周转库选址和路径规划问题进行研究，以总配送成本最小为目标建立数学模型，设计两阶段启发式算法进行求解。首先采用聚类-重心算法在备选市县终端库中选定首周转库，然后设计边界搜索算法对配送区域进行调整，以满足省周转库各辐射范围内的库存容量要求，最后针对选定的省周转库配送区域方案，设计自适应大邻域搜索算法求解固定时间窗的车辆配送路径问题。通过8省电网公司省周转库选址和路径优化算例，验证该算法的有效性。综合考虑选址、库存和路径优化是提升物流系统效益和鲁棒性的关键，因此首周转库选址-库存-路径集成优化是有待研究的问题。

　　[参考文献]

　　[1]CDT Watson-Gandy,PJ Dohrn.Depot location with van sa lesmen-A practical approach[J].Onega:The Interna-tona liurmel of Maregiment Seienca.10 78.10):321-321

　　[2]Nagy G,SalhiS Location mrouting:1 Saue!,mod els and methods[J].European Journal of Operational Research,2007，117(2):649-672.

　　[3]Fazayfli S,Endi A.，K anelabedi I.N.Location-routing problem in multimodal transportation networkwith time windows and fuzzy demands:Presenting a two-part genetio algor ithm[J].Computers&Industr ial Engineer ing.2018:233-246.

　　[4]王道平.徐展，杨岑基于两阶段启发式算法的物流配送选址-路径问题研究[」运筹与管理17.264)10-75+83

　　[5]姬杨蓓蓓,储昊成枫基于阶段算法的快递企业未端配送网络优化研究[|系统工程_2期37(01):100-105

　　[6]路世昌，邵旭伦，李丹基于两段启发式算法的低碳物流选址一多车型4径问题研究J制造业自动化2021，45/3)202-207

　　[7]周鹏程。电网物资配送中心选址优化决策研究[D北京:华北电力大学(北京),2019.

　　[8]刘栋，电网物资存储模式及配送优化研究[D]。北京:华北电力大学，2018.

　　[9]王程远.电网企业的配送节点选址-路径优化问题研究[D]。广州:华南理工大学2018.