物流系统优化理论

1、定位-配送路线最优化问题研究摘要：LRP问题一直是物流领域的研究热点， 本文就多个工厂，多个配送中心的LRP问题进 行了讨论，并结合库存进行了研究，建立了相应的模型。由于问题本身是NP-hard，所以我们用启发式算法对该问题进行求解，首先用类似“插入”法求得初始解，然后用类似“路线 改善”并结合禁忌搜索法对所求得的解进行改进，最后进行了算例分析。 关键词：定位配给车辆路线安排禁忌搜索库存1.引言随着当今物流向不规则性和全球化的趋势发展,企业竞争日趋激烈,企业管理者希望能协调物流系统各个环节，以最低的价格、最好的服务满足顾客的需要，因此在LAP VRP禾口其他物流决策模型的基础上，产生了集成物流

2、管理的概念，这种概念认为：在设施（工厂、库存点或分销中心）相对于客户的位置、货物的配给、运输货物的车辆路线安排之间存在相互依赖的关系，根据这种关系来相应地进行综合优化与管理。根据这种集成物流管理系统的概念，就产生了对设施定位-车辆运输路线安排为题（Location-Routing Problems，LRP）的研究。通过建立 LRP模型，对于多客户与多设施的情形，可同时解决确定设施最优数量、容量与寻求最优运输计划、 路线安排之间的总体问题， 从而降低物流成本， 提高产品分销的效率。般而言,LRP是指给定一系列潜在的设施点（这些设施的容量、位置为已知）和客户（客户的需求量、位置为已知），确定设施的

3、位置和数量以及确定最佳运输行驶路线，使总的费用最低。在LRP中有很多约束条件，女口：每个客户只能从一个设施得到货物，且每个客户只能由一辆车服务； 每辆车从一个设施出发， 最后回到这个设施点， 且每一条线路上的客户需求之和不能超过车的容量等等。目前LRP的算法大致可以分为两类，一类是精确算法，一类是启发式算法。精确算法有:分枝定界；动态规划；整数规划等。启发式算法有：先解决定位-配给，然后解决运输路线安排；先解决运输路线安排，再解决定位 -配给；节约成本/插入等，另外还有一些人工智能的启发式算法，如遗传算法、蚁群算法神经网络算法等1】。虽然目前解决LRP的算法很多,但其中大部分精确算法是为特定的

4、LRP研究设计的，因而希望建立具有普遍意义的解决LRP而目前大多数启发的精确算法，为判定启发式算法解决问题的效率提供一个有意义的基准。LRP问题的启发式算法。式算法是将LRP分解成几个子问题先后解决，因而在同一个决策层次内，这样的算法对定位 和行程路线因素权衡分析很不充分，因而希望能建立同时解决整个2. LRP模型及Tabu search 算法2.1 LRP的数学模型本文讨论的是多工厂，多物流中心的定位一一车辆路线安排问题，同时考虑了简单的库存控制，期模型可叙述如下:基本假设2.1.1(1)2.1.2参数设定本文考虑的是多工厂多物流中心的定位一一车辆安排问题;每个客户只能由一辆车服务；每条路线

5、上的客户需求之和不能超过车的装载能力;没一条线路从一个中心出发并回到同一中心；所有的车辆是相同的，即装载能力相同; 货物大小、价值相同。工厂的数目;客户的数目;配送中心的数目;节点的数目；工厂的下标；客户的下标；配送中心的下标(j=1,.,n);I 节点的下标(1=1,.,N );M最大路线数；j工厂p到配送中心j的单位运输费用;xPj配送中心j到工厂P的进货数;配送中心j的建造费用;从节点k到I的行驶费用;di客户i的需求;bp工厂P的生产能力;Sj配送中心j的容量;车的装载能力;Rj配送中心j的需求量;货物的单位成本;固定订购成本;hj配送中心j的单位时间，单位库存价值的存储成本;Qj配送

6、中心j的订购批量(Qj = 2Rj )；hjCZj_J1客户i被分配到配送中心j 二o其他_1配送中心建立=jo其他卩边(k,l)在线路r上Wklr冷其他Vkr =1节点k在线路r上0其他2.1.3数学模型s.t.n+送 fjyjj壬+ Z 0巳+(?用+( j I QjQi,号)hjCQj2M N N+ Z Z SdlWklr(0)rT k经I吕n无xpjj吕p(p=1,P)(1)diZj 兰 Sjyj(j=1,.,n)n无 Vn+,rdii壬V(r=1M)V N无送Wklrr 3 k=i=1(l=n+1，N)N艺 WklrlN=Swlkrl i(k=1,N;r=1 ,.,M)N无 Wklr

7、l zt= Vkr(k=1,N;r=1 ,.,M)n送 Zj = 1(i=1,m)(i=1,m;j=1 ,.,n)(8)1）PmZ Xpj =2 diZijP 4i4(j=1，n)(9)Vir yj 兰 0(j=1,n ;r=1 ,.,M)(10)Vjr + Vi 也r -Zij 1(i=1,m;j=1 ,.,n ;r=1 ,.,M)(11)其中（0）式中第一项为工厂到配送中心的运输费用，第二项为配送中心的建造费用，第三 项为货物成本与订购成本以及库存成本，第四项为配送中心到客户的运输成本。约束（ 表示工厂生产能力的约束；（2）表示配送中心容量的约束；（3）表示每一条线路的客户需求和不能超过车

8、的容量；（4）表示一个客户只能由一辆车服务；（5）表示路线连续性约束，即表示在一条路线上对每个节点来说，如果一辆车从该节点进那么该辆车应该从这个节点出来；（6）表示如果节点k被分配到路线r上，那么有且只有一条边流出该节点；（7）表示一个客户能分配到且只能分配到一个配送中心；（8）表示只有当配送中心开放时才能给其分配客户；（9）表示配送中心的进货与出货相等；（10）表示只有当配送中心开放时，一条线路 才能始于该中心；（11）表示一个客户只能分配到一个配送中心和一条线路上。2.2算法的实现2.2.1初始解的求法首先任意开放一个配送中心， 按节约法插入客户以生成线路，直到该线路不能容纳更多的客户，按

9、此法依次生成其他的线路， 直到该配送中心不能容纳更多的客户。然后开放第二最后按运输问题安排工厂给这个配送中心，如此一次开放配送中心直到所有的客户被服务。些物流中心供货，运输问题是解一个线性规划问题。2.2.2 解的改进解的改进包括配送中心的改进和路线的改进。（1 ）配送中心的改进对于配送中心的改进，用类似relocate exchange的方法进行改进。这种交换包括：被选中的配送中心之间的交换以及被选中的配送中心与未被选中的配送中心之间的交换，我们 记这种交换为 relocate excha nge 。（2）路线的改进采用2-0pt exchange和Or-opt exchange ，再结合禁

10、忌搜索法对路线进行改进。2-opt exchange E就是在可行的基础上两条边与另外两条边交换，如图:Ofto一Oo I fcQO图中表示客户，表示配送中心，表示配送路线Or-opt exchange 2就是把线路中相邻的 丨个点插入到其他位置，一般而言丨3 ,如图:o oOto oioA0*0oto*o2-opt exchange可用于同一配送中心不同线路上的两边交换, 同一线路上的点的交换，也可用于不同线路点的交换。Or-opt exchange 可用于Tabu search是一种启发式算法，为了防止算法陷入局部最优，当领域中的最优解比当前解要差时，仍把它当作新的当前解，因而它具有记忆功

11、能和深度探索功能。本文采用两层禁忌搜索法。首先应用于配送中心的改进，它的邻域结构为下面定义的relocate exchange2-opt与Or-0pt的邻域来定义的，其的邻域，再应用于线路的改进，它的邻域结构是根据禁忌表长度为5.定义1:3U relocateexchange = U 師有的能与j交换的中心为relocate exchange的邻域，其大小为o(n2 ),jn为配送中心的数目；U 2_o pt:U , j +1）|（j, j +1）-n 使（i,i +1）与（j, j +1）能被（i, j+1）与（j,i+1）交换 （i，i十）勺为2-opt的邻域（i,i+1 ）与（j,j+1

12、 ）属于同一个中心上的不同路线上）。很容易知道它的 大小为o（m2 ）, m为客户的数目，n 为所有线性集合。Ug pt = U j|（j, j+1）n，该I个点可以插入在j与j+1之间为Or-opt的邻 口中l个连续的点域（丨3 ）。显然它的大小也为 o（m2 1两层Tabu search 算法:Ste p1 :初始解的构造。首先任意开放一个配送中心，按节约法插入客户以生成线路，直到该线路不能容纳更多的客户，按此法一次生成其他线路， 直到该配送中心不能容纳更多客户。然后开放第二个配送中心，如此依次开放配送中心直到所有客户被服务。最后按运输问题安排工厂给这些配送中心供货，构成初始解。Step2

13、 :不断循环Step2.1直到不能再改善所求到的最优解。Step2.1 :对于每一个开放的中心 j，与其相关的relocate exchange邻域中的每一个中心交换，在每一次交换中将执行Step2.2，知道在此邻域求得最优解。把此最优解当作当前解，其反向交换被禁，更新禁忌表。Step2.2 :不断循环Step2.2.1直到不能再改善所求到的最优解。Ste p2.2.1:对于每一个客户i，在2-0pt的邻域中求与（i,i+1 ）有关的最优解,把它当作当前最优解，其反向交换被禁，更新禁忌表。不断循环Ste p2.2.2Ste P2.2.2直到不能再改善所求到的最优解。:对于每一个客户i （有时包

14、含i+1,i+2）在其Or-opt邻域中求得最优解,把它当作最优解，其反向插入被禁，更新禁忌表。Ste p2.2.3:利用SteP2.2.2所求的最优解从新安排工厂给这些中心供货以及从新 安排库存。把Step2求得的最优解作为我们要求的解。3.算例构造及结果分析3.1算例实验的构造本文的数据主要采取文献 4的数据，其工厂、客户与待选的配送中心平均分布在U （0,100）上，客户的需求是450,600的随机数，不同配送中心单位库存费用是0.3,0.8随机数，配送中心的容量为5000,10000的随机数，工厂的生产能力为20000,30000的随参数数值工厂数3, 4，5待选的配送中心数10， 1

15、5， 20客户数100， 150， 200车的装载能力3000， 4000配送中心的建造费用1200单位货物进货费2单位距离运费2固定订购费20机数，工厂到中心的单位运费为0.2,0.7的随机数，其他参数如表:3.23.2.1算例实验结果及分析不同参数下的配送路线(1)工厂数为3，待选配送中心数为10,客户为100,车的装载能力为3000中心路线114-49-37-45-24, 76-47-22-88-64265-29-55-25-38, 48-94-69-46-63 , 59-43-40-31399-26-35-32-15, 33-58-39-66-17-28482-9-11-72-93,

16、3-27-78-54-89585-67-92-73-56-70, 36-57-53-98-19, 42-12-50-16-61684-41-97-96-34-7, 87-77-23-80-30-91,1-6-100-4-8-62751-90-74-21-79, 18-44-10-95-20871-2-52-5-13-75, 68-81-60-86-83工厂数为4，待选配送中心为15,客户为150,车的装载能力为3000中心路线1135-46-120-142-24,81-67-86-9-1222125-131-110-29-26,56-60-11 , 91-52-80-132-78,76-83-

17、134-148-130-653129-149-39-18-70,111-87 , 99-40-113-103-15, 66-38-89-4432-19-54-116-140,59-23-127-6-147-495150-97-62-69-136,22-118-95 , 108-124-31-8-43, 41-16-82-58-100636-55-10-44-119,126-115-84-72-73-45725-138-107-75-34,27-143-63-57-146-50868-48-33-20-117,61-123-98-64-79, 145-133-53-77-109-939112-5

18、1-47-30 , 137-21-71-13-102-101, 92-105-85-128-7410121-139-5-3-17,114-90-106-28-1, 96-144-7-371142-104-141-88-35,12-14-94-2工厂数为5，待选配送中心为20,客户为200,车的装载能力为4000中心路线162-112-72-74-71-159-27-109,32-83-81-105-161-77-70, 78-9-1192125-185-163-85-104-162-173-503171-135-98-158-147-153-3-21,69-165-56-63-181-130,

19、110-68-41-175-864128-198-10-169-35-24-193，4-177-146-48-126-89-385192-58-189-92-187-167-80，103-195-150-55-117-46-8766-8-190-54-39，151-152-120-179-67-88728-91-101-200-132-144-134，19-183-43-188-197-31-1788148-199-61-157-14，53-122-154-79-127-18-124-1399123-59-142-194-129-40-114-136，12-37-2-52-94-76-6410

20、149-99-186-138-1-90-47，182-11-166-196-711113-115-17-141-13-116-26，174-172-143-118-25-102-331242-66-15-131 ，29-93-34-107-97-108-231360-133-16-145-111-20-5，184-170-45-1061430-191-49-65-96-95，140-51-168-160-44-156-7315121-57-137-180-82-36，176-75-164-155-100-22-84322 不同参数下的数值结果与分析比较F表为不同参数下（工厂数、待选配送中心数、

21、客户数、车的装载能力）的各种费用与总费用:工厂数待选配 送中心 数客户数车的装载能力使用的配送中心数工厂到 中心的 运输成 本中心到 客户的 运输成 本货物及 订购和 中心建 造成本库存成本总成本3101003000814103385711588121431359853101004000815049345511585921211364863151003000810426347711604121771321233151004000810426328011603921751319213201003000710449406011466117691309413201004000710449308011

22、462117291298804101003000811525464811571920411339344101004000812705365611571120331341074151003000810409362711575020521318394151004000810409322611578820901315154201003000712728496711502618341345564201004000712777403611502618341336745101003000812145415311574720091340555101004000812271321911568819501331

23、295151003000711318435411470018341322075151004000710446313111473518691301845201003000710477423911480916391311655201004000710477322211494617761304224151503000112098563821731362916203420415150400011209875024173139291920207142015030001220272589917391829182030084201504000121969348011739742974201443515150

24、300011176266243172778287219952151515040001117613477317272928231979405201503000121991368901737572811203372520150400012192994238173803285720019852020030001525404832923014637122675925202004000152516662732300993665265205从上表中我们可以看出：一般而言，在其他条件相同的情况下，当工厂数增加时，工厂到配送中心的运输费用会减少，总费用也会减少；当待选配送中心数目增加时，总的费用除少数外是减少

25、的；当车的装载能力增加时， 配送中心到客户的运输成本减少，总成本也相应 减少。出现上述原因主要是当工厂数增加时，进货地点选择增加，因而工厂到配送中心的运输可选择库存费用降低，到客户费用减少，从而使总的费用减少；待选配送中心数目增加时, 运输成本低，进货运输成本低的中心，因而使成本相应的减少；当车的装载能力增加时，使也减少了总成本。使用的车辆数目减少，路线变少，从而节约了配送中心到客户的运输成本,4.总结与展望本文围绕LRP的研究,建立了带库存控制的多工厂、多物流中心的定位-路线安排问题的数学模型，并设计了基于relocate exchange、 2-opt exchange 禾R Or-opt exchange 的令邻域结构的两层Tabu search算法，构造了基于本问题的算例实验，给出了结果分析，从分析中我们可以看出，计算结果是合理的，从而验证了算法的有效性。到目前为止，LRP的研究取得了很大的进展，但还有很多地方值得进一步研究。就本文而言，有很多不完善的地方，有以下几个方面值得深入研究:(1) LRP模型的改进本文的模型是在很多假设的情况下建立起来的,实际中LRP的模型是十分复杂的、 大规LRP模型，多种车型、多货模的。例如：客户的需求是随机的、不断变化的且带时间窗的的 物种类的模型以及对库存模型