李想等：两级选址-路径问题的大规模邻域搜索模拟退火算法 ·955· 1.2模型假设 ∑mu≥0a,HseN, (20) (1)候选配送中心、中转站和需求点的数量、地理 位置、固定成本已知，各级配送车辆固定成本已知，需 ma≤oa,Hs∈Ns,Hd∈Nn, (21) 求点的配送需求量已知 An≥，ce, (22) (2)各级物流设施容量已知，分配给各级物流设 n。≤a,VcENc,VsENs. (23) 施的总需求量不能超过设施的容量限制. 式(1)为目标函数.为了降低物流配送网络总体 (3)各级配送车辆容量已知，各配送路径上车辆 成本，目标函数为二级物流配送网络总成本最小化，物 载重不能超过容量限制. 流总成本包括：选择的配送中心固定成本、选择的中转 (4)各节点间距离按照欧氏距离计算，各级配送 站固定成本、一级配送车辆固定成本、二级配送车辆固 车辆单位长度配送成本已知. 定成本、一级配送路径运输成本、二级配送路径运输 (5)每个需求点只能被一辆车服务一次，各级配 成本. 送车辆从物流设施节点出发并返回相同物流设施 式(2)~(23)为约束条件.式(2)保证每个被选 节点 择的中转站只能被一辆一级配送车辆服务一次，未被 1.3数学模型 选择的中转站不能被服务：式(3)保证每个需求点只 Mn2=ACm+￡6s+ 能被一辆二级配送车辆服务一次：式(4)保证一级配 EN. 送网络中每个节点的进出车辆相同：式(5)保证二级 且A三c+Cuya+ E 配送网络中每个节点的进出车辆相同：式(6)保证一 AA名+AAA Cymc (1) 级配送网络中各节点之间不存在回路：式(7)保证二 级配送网络中各节点之间不存在回路；式(8)限制了 s.t. 盆名听e (2) 一级配送网络中各个配送中心之间不允许存在路径； A点g=l.ieN (3) 式(9)限制了二级配送网络中各个中转站之间不允许 存在路径：式(10)表示每个中转站只能被一个配送中 三y三=0，VeN.Ve (4) 心完成服务；式(11)保证每个需求点只能被一个中转 三-三=0，ie水keK. (5) 站完成服务；式(12)保证任意一级配送车辆只能完成 一条服务路径，并且出发点必须是配送中心；式(13) xi=0,VieN,Vvev, (6) 保证任意二级配送车辆只能完成一条服务路径，并且 ym=0,Hi∈N2,HkeK, (7) 出发点必须是中转站：式(14)保证每条一级配送路径 -0.Veev. (8) 上的所有中转站被该条路径上的配送中心服务：式 点Aa=0,eK, (9) (15)保证每条二级配送路径上的所有需求点被该条 路径上的中转站服务；式(16)保证一级配送路径中车 三=l.e, (10) 辆容量不会超过一级配送车辆容量限制：式(17)保证 是=1，ee 二级配送路径中车辆容量不会超过二级配送车辆容量 (11) 限制：式(18)保证配送中心所服务的中转站配送总量 .1.Veev. (12) 不会超过该配送中心容量限制：式(19)保证中转站所 名An≤l,VeK, 服务的需求点配送总量不会超过该中转站容量限制： (13) 式(20)和(21)保证中转站只能够通过被选择的配送 三，+三1+m, 中心完成服务：式(22)和(23)保证需求点只能够通过 VsENs,Hd∈Np,HueV, 被选择的中转站完成服务. (14) 是+点a≤1+： 2求解算法 VcENc,VsENs,VkeK, (15) 本文提出了大规模邻域搜索模拟退火算法(simu- AAg4≤0keK, (16) lated annealing-large neighborhood search,SA-LNS) nd≤0，VueK 较大规模的二级选址-路径问题进行求解.模拟退火 (17) 算法是通过对固体物质高温退火的物理过程进行模 名n≤0.eN. (18) 拟，物理中将某一固体物质加热到以足够高的温度后， dn.m.QVdeN. 再令其逐步降温，在升温过程时，固体物质内能较大， (19) 内部粒子变为无序状，随着温度的下降，内能减少，内李 想等: 两级选址鄄鄄路径问题的大规模邻域搜索模拟退火算法 1郾 2 模型假设 (1) 候选配送中心、中转站和需求点的数量、地理 位置、固定成本已知,各级配送车辆固定成本已知,需 求点的配送需求量已知. (2) 各级物流设施容量已知,分配给各级物流设 施的总需求量不能超过设施的容量限制. (3) 各级配送车辆容量已知,各配送路径上车辆 载重不能超过容量限制. (4) 各节点间距离按照欧氏距离计算,各级配送 车辆单位长度配送成本已知. (5) 每个需求点只能被一辆车服务一次,各级配 送车辆从物流设施节点出发并返回相同物流设施 节点. 1郾 3 数学模型 MinZ = 移d沂ND CDdwd + 移s沂NS CSs zs + 移i沂ND 移 j沂NS 移v沂V CVv xijv + 移i沂NS 移 j沂NC 移k沂K CKk yijk + 移i沂ND 移 j沂NS 移v沂V cv xijv cfij + 移i沂NS 移 j沂NC 移k沂K ck yijk csij . (1) s. t. 移i沂N1 移v沂V xijv = zj,坌j沂NS , (2) 移i沂N2 移k沂K yijk = 1,坌j沂NC , (3) 移i沂N1 xijv - 移i沂N1 xjiv = 0,坌j沂N1 ,坌v沂V, (4) 移i沂N2 yijk - 移i沂N2 yjik = 0,坌j沂N2 ,坌k沂K, (5) xiiv = 0,坌i沂N1 ,坌v沂V, (6) yiik = 0,坌i沂N2 ,坌k沂K, (7) 移i沂ND 移 j沂ND xijv = 0,坌v沂V, (8) 移i沂NS 移 j沂NS yijk = 0,坌k沂K, (9) 移d沂ND msd = 1,坌s沂NS , (10) 移s沂NS ncs = 1,坌c沂NC , (11) 移i沂ND 移 j沂NS xijv臆1,坌v沂V, (12) 移i沂NS 移 j沂NC yijk臆1,坌k沂K, (13) 移g沂N1 xsgv + 移h沂N1 xdhv臆1 + msd , 坌s沂NS ,坌d沂ND ,坌v沂V, (14) 移g沂N2 ycgk + 移h沂N2 yshk臆1 + ncs, 坌c沂NC ,坌s沂NS ,坌k沂K, (15) 移i沂NC 移 j沂N2 yijkdi臆QK ,坌k沂K, (16) 移i沂ND 移 j沂N1 移c沂NC xijvncjdc臆QV ,坌v沂V, (17) 移c沂NC dcncs臆QS ,坌s沂NS , (18) 移s沂NS 移c沂NC dcncsmsd臆QD ,坌d沂ND , (19) 移d沂ND msd逸wd ,坌s沂NS , (20) msd臆wd ,坌s沂NS ,坌d沂ND , (21) 移s沂NS ncs逸zs,坌c沂NC , (22) ncs臆zs,坌c沂NC ,坌s沂NS . (23) 式(1)为目标函数. 为了降低物流配送网络总体 成本,目标函数为二级物流配送网络总成本最小化,物 流总成本包括:选择的配送中心固定成本、选择的中转 站固定成本、一级配送车辆固定成本、二级配送车辆固 定成本、一级配送路径运输成本、二级配送路径运输 成本. 式(2) ~ (23)为约束条件. 式(2)保证每个被选 择的中转站只能被一辆一级配送车辆服务一次,未被 选择的中转站不能被服务;式(3) 保证每个需求点只 能被一辆二级配送车辆服务一次;式(4) 保证一级配 送网络中每个节点的进出车辆相同;式(5) 保证二级 配送网络中每个节点的进出车辆相同;式(6) 保证一 级配送网络中各节点之间不存在回路;式(7) 保证二 级配送网络中各节点之间不存在回路;式(8) 限制了 一级配送网络中各个配送中心之间不允许存在路径; 式(9)限制了二级配送网络中各个中转站之间不允许 存在路径;式(10)表示每个中转站只能被一个配送中 心完成服务;式(11)保证每个需求点只能被一个中转 站完成服务;式(12)保证任意一级配送车辆只能完成 一条服务路径,并且出发点必须是配送中心;式(13) 保证任意二级配送车辆只能完成一条服务路径,并且 出发点必须是中转站;式(14)保证每条一级配送路径 上的所有中转站被该条路径上的配送中心服务;式 (15)保证每条二级配送路径上的所有需求点被该条 路径上的中转站服务;式(16)保证一级配送路径中车 辆容量不会超过一级配送车辆容量限制;式(17)保证 二级配送路径中车辆容量不会超过二级配送车辆容量 限制;式(18)保证配送中心所服务的中转站配送总量 不会超过该配送中心容量限制;式(19)保证中转站所 服务的需求点配送总量不会超过该中转站容量限制; 式(20)和(21)保证中转站只能够通过被选择的配送 中心完成服务;式(22)和(23)保证需求点只能够通过 被选择的中转站完成服务. 2 求解算法 本文提出了大规模邻域搜索模拟退火算法( simu鄄 lated annealing鄄large neighborhood search, SA鄄鄄 LNS) 对 较大规模的二级选址鄄鄄 路径问题进行求解. 模拟退火 算法是通过对固体物质高温退火的物理过程进行模 拟,物理中将某一固体物质加热到以足够高的温度后, 再令其逐步降温,在升温过程时,固体物质内能较大, 内部粒子变为无序状,随着温度的下降,内能减少,内 ·955·