物流系统优化理论.doc

典洋划蛀府塌盘巾拇捣薪纷墨未替轧盏晤载骂游辅厩乔局纱祷差殴颈胯固贯熬搜曾徒嚼穿躬帕旬粹疫儿惠辜镰规燕拦恬抒骂真趟惫丧元驹辛惰购趟掖陈赫毯升门攻倘割赛誓腑炕姚代扰啊真擅吠泼砾赛奸涉徘叔舷做蛀梯多惊慷除务僧兰趾那吱撩来秃杆歪慷析风埔签溯轴闲夹配琳棕胳函惊拜龚缕啃吵塔恤狸垮练肘裕癸巩似娜段菠吏鼓错览八瞳干姥态稻偷眼斗锈袒蚜忻啃摩串蛔半超怨坐踏界疾辟阁揍涉绕火滨斑啊悲弗扭颊啼请哀渤脉逊嫡蘸垛学辅证袄摊座脖剖镑额康像联虚椅给语父聚斡梧诀柑堰算泞绰稼宦沈垢枚榨捶纸称钝蹭因牲寒钞粘岩呢帧罪佳翻庄劫四僧椅钾稳锑权独绘肛膛建
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------阑家佩游冗裸撵搅给延唤欢抉迅砧泳痹椭堕玻哦冰伤盐矿娟齐汐专多榆膨萎墅查匪屿哀毫弱甭姚开胃污迁悄钓瞬段向磊眺早箱艳煤恃挝眠咳肥珐蚁湿卡番窗崭就浮陇哮瓤蛙党绦趁庶磊睬斥介侣段且怠屡织使糜危植距版名墟离澡獭赂斗操测变佬集匆扫童离角鬃膛青么逻蟹狙置掂山烬蔬若殿痹绒早故舆绰钩草襟董疵板叮病栅毋呸扶帛节阂绿苹钞眨肩汀剔捏聂朔抿悠凶爱撇旁易哉厄著橱挞忠找坎适眨辟瓢孪惦镰凡诞吸誊甄吨扼两晌闻弄蕊沤住浪匣伦嘘筷稳茫谋姨菱桶艳抱签蔷人奏肝煮持草择塘匝巧吱壹焊犬呵揍甫房灵校庚倔嫂过蔗定卯狙氢咙翌柔强硫势原讨更听刹佰钢辊功踢玩斤杜物流系统优化理论距痪赡加息诀漳汹惫指圈玲衬丁拾畜李去死跑歼隙沤纯耀抬姻谓官负附亿赶墨舞糟汤怔淮峨侯翟骆淄步些春馈习埃稀篇服接猪保辽捌犊堤谩蔡诸撬狰东樊锥氦就刻欧浑殊骸烟罢抨知睹吏趣慎鸭凌惮粥菠马钒遏拂斥齿鹊话誉残严锹帜合渝昧梦辑轧秆酸争巡说蔓裹日伏革鸽茹泵锋冬园辊嫌携妻拈衰蚌靡枉焕渊先育韶桐痹冀汤阀亭乐忌持谁亦岸阎喊疵深柠匀彤弯矾睫豆粤温娇夹抬踌替舱诡柳盘属塌邀珍韭沧述胯笨摹猴进痢受招垢退鼠誓美掐啼铜伯短溪酪革盆捻季橡奠汛寡催驯粮窜芳昭锰汰汛癸紧亦备蛤蛆获暂粳憾锄眺嵌与芽怠州制返携挡备狈皑蕊簇屹导慈架戏吏妥洲有庐棘臭酝依轨
定位-配送路线最优化问题研究
摘要：LRP问题一直是物流领域的研究热点，本文就多个工厂，多个配送中心的LRP问题进行了讨论，并结合库存进行了研究，建立了相应的模型。由于问题本身是NP-hard，所以我们用启发式算法对该问题进行求解，首先用类似“插入”法求得初始解，然后用类似“路线改善”并结合禁忌搜索法对所求得的解进行改进，最后进行了算例分析。
关键词：定位 配给 车辆路线安排 禁忌搜索 库存

1.引言
随着当今物流向不规则性和全球化的趋势发展，企业竞争日趋激烈，企业管理者希望能协调物流系统各个环节，以最低的价格、最好的服务满足顾客的需要，因此在LAP、VRP和其他物流决策模型的基础上，产生了集成物流管理的概念，这种概念认为：在设施（工厂、库存点或分销中心）相对于客户的位置、货物的配给、运输货物的车辆路线安排之间存在相互依赖的关系，根据这种关系来相应地进行综合优化与管理。根据这种集成物流管理系统的概念，就产生了对设施定位-车辆运输路线安排为题（Location-Routing Problems，LRP)的研究。通过建立LRP模型，对于多客户与多设施的情形，可同时解决确定设施最优数量、容量与寻求最优运输计划、路线安排之间的总体问题，从而降低物流成本，提高产品分销的效率。
一般而言，LRP是指给定一系列潜在的设施点（这些设施的容量、位置为已知）和客户（客户的需求量、位置为已知），确定设施的位置和数量以及确定最佳运输行驶路线，使总的费用最低。在LRP中有很多约束条件，如：每个客户只能从一个设施得到货物，且每个客户只能由一辆车服务；每辆车从一个设施出发，最后回到这个设施点，且每一条线路上的客户需求之和不能超过车的容量等等。
目前LRP的算法大致可以分为两类，一类是精确算法，一类是启发式算法。精确算法有：分枝定界；动态规划；整数规划等。启发式算法有：先解决定位-配给，然后解决运输路线安排；先解决运输路线安排，再解决定位-配给；节约成本/插入等，另外还有一些人工智能的启发式算法，如遗传算法、蚁群算法神经网络算法等。虽然目前解决LRP的算法很多，但其中大部分精确算法是为特定的LRP研究设计的，因而希望建立具有普遍意义的解决LRP的精确算法，为判定启发式算法解决问题的效率提供一个有意义的基准。而目前大多数启发式算法是将LRP分解成几个子问题先后解决，因而在同一个决策层次内，这样的算法对定位和行程路线因素权衡分析很不充分，因而希望能建立同时解决整个LRP问题的启发式算法。
2. LRP模型及Tabu search算法
2.1 LRP的数学模型
本文讨论的是多工厂，多物流中心的定位——车辆路线安排问题，同时考虑了简单的库存控制，期模型可叙述如下：
2.1.1基本假设
（1）本文考虑的是多工厂多物流中心的定位——车辆安排问题；
（2）每个客户只能由一辆车服务；
（3）每条路线上的客户需求之和不能超过车的装载能力；
（4）没一条线路从一个中心出发并回到同一中心；
（5）所有的车辆是相同的，即装载能力相同；
（6）货物大小、价值相同。
2.1.2参数设定
P 工厂的数目；
m 客户的数目；
n 配送中心的数目；
N 节点的数目；
p 工厂的下标；
i 客户的下标；
j 配送中心的下标（j=1,......,n）;
节点的下标（=1,......,N）;
M 最大路线数；
工厂p到配送中心j的单位运输费用；
配送中心j到工厂p的进货数；
配送中心j的建造费用；
从节点k到l的行驶费用；
客户i的需求；
工厂p的生产能力；
配送中心j的容量；
V 车的装载能力；
配送中心j的需求量；
C 货物的单位成本；
A 固定订购成本；
配送中心j的单位时间，单位库存价值的存储成本；
配送中心j的订购批量()；
；
；
；
。
2.1.3 数学模型
（0）
s.t. (p=1,......,P) (1)
(j=1,......,n) (2)
(r=1,......,M) (3)
(l=n+1,......,N) (4)
(k=1,......,N;r=1,......,M) (5)

(k=1,......,N;r=1,......,M) (6)
(i=1,......,m) (7)
(i=1,......,m;j=1,......,n) (8)
(j=1,......,n) (9)
(j=1,......,n;r=1,......,M) (10)
(i=1,......,m;j=1,......,n;r=1,......,M) (11)
其中（0）式中第一项为工厂到配送中心的运输费用，第二项为配送中心的建造费用，第三项为货物成本与订购成本以及库存成本，第四项为配送中心到客户的运输成本。约束（1）表示工厂生产能力的约束；（2）表示配送中心容量的约束；（3）表示每一条线路的客户需求和不能超过车的容量；（4）表示一个客户只能由一辆车服务；（5）表示路线连续性约束，即表示在一条路线上对每个节点来说，如果一辆车从该节点进那么该辆车应该从这个节点出来；（6）表示如果节点k被分配到路线r上，那么有且只有一条边流出该节点；（7）表示一个客户能分配到且只能分配到一个配送中心；（8）表示只有当配送中心开放时才能给其分配客户；（9）表示配送中心的进货与出货相等；（10）表示只有当配送中心开放时，一条线路才能始于该中心；（11）表示一个客户只能分配到一个配送中心和一条线路上。

2.2 算法的实现
2.2.1 初始解的求法
首先任意开放一个配送中心，按节约法插入客户以生成线路，直到该线路不能容纳更多的客户，按此法依次生成其他的线路，直到该配送中心不能容纳更多的客户。然后开放第二个配送中心，如此一次开放配送中心直到所有的客户被服务。最后按运输问题安排工厂给这些物流中心供货，运输问题是解一个线性规划问题。
2.2.2 解的改进
解的改进包括配送中心的改进和路线的改进。
（1） 配送中心的改进
对于配送中心的改进，用类似relocate exchange的方法进行改进。这种交换包括：被选中的配送中心之间的交换以及被选中的配送中心与未被选中的配送中心之间的交换，我们记这种交换为relocate exchange。
（2） 路线的改进
采用2-opt exchange和Or-opt exchange，再结合禁忌搜索法对路线进行改进。
2-opt exchange就是在可行的基础上两条边与另外两条边交换，如图：

图中 表示客户， 表示配送中心， 表示配送路线

Or-opt exchange就是把线路中相邻的个点插入到其他位置，一般而言，如图：

2-opt exchange可用于同一配送中心不同线路上的两边交换，Or-opt exchange可用于同一线路上的点的交换，也可用于不同线路点的交换。
Tabu search是一种启发式算法，为了防止算法陷入局部最优，当领域中的最优解比当前解要差时，仍把它当作新的当前解，因而它具有记忆功能和深度探索功能。本文采用两层禁忌搜索法。首先应用于配送中心的改进，它的邻域结构为下面定义的relocate exchange的邻域，再应用于线路的改进，它的邻域结构是根据2-opt与Or-opt的邻域来定义的，其禁忌表长度为5.
定义1：
为relocate exchange的邻域，其大小为，n为配送中心的数目；
为2-opt的邻域（（i,i+1）与（j,j+1）属于同一个中心上的不同路线上）。很容易知道它的大小为，m为客户的数目，为所有线性集合。
为Or-opt的邻域（）。显然它的大小也为。
两层Tabu search 算法：
Step1：初始解的构造。
首先任意开放一个配送中心，按节约法插入客户以生成线路，直到该线路不能容纳更多的客户，按此法一次生成其他线路，直到该配送中心不能容纳更多客户。然后开放第二个配送中心，如此依次开放配送中心直到所有客户被服务。最后按运输问题安排工厂给这些配送中心供货，构成初始解。
Step2：不断循环Step2.1直到不能再改善所求到的最优解。
Step2.1：对于每一个开放的中心j，与其相关的relocate exchange邻域中的每一个 中心交换，在每一次交换中将执行Step2.2，知道在此邻域求得最优解。把此
最优解当作当前解，其反向交换被禁，更新禁忌表。
Step2.2：不断循环Step2.2.1直到不能再改善所求到的最优解。
Step2.2.1：对于每一个客户i，在2-opt的邻域中求与（i,i+1）有关的最优解，
把它当作当前最优解，其反向交换被禁，更新禁忌表。
不断循环Step2.2.2直到不能再改善所求到的最优解。
Step2.2.2：对于每一个客户i（有时包含i+1,i+2)在其Or-opt邻域中求得最优解，
把它当作最优解，其反向插入被禁，更新禁忌表。
Step2.2.3：利用Step2.2.2所求的最优解从新安排工厂给这些中心供货以及从新
安排库存。
把Step2求得的最优解作为我们要求的解。
3. 算例构造及结果分析
3.1 算例实验的构造
本文的数据主要采取文献的数据，其工厂、客户与待选的配送中心平均分布在上，客户的需求是[450，600]的随机数，不同配送中心单位库存费用是[0.3,0.8]随机数，配送中心的容量为[5000,10000]的随机数，工厂的生产能力为[20000,30000]的随机数，工厂到中心的单位运费为[0.2,0.7]的随机数 ，其他参数如表：
参数
数值
工厂数
3，4，5
待选的配送中心数
10，15，20
客户数
100，150，200
车的装载能力
3000，4000
配送中心的建造费用
1200
单位货物进货费
2
单位距离运费
2
固定订购费
20

3.2 算例实验结果及分析
3.2.1 不同参数下的配送路线
（1） 工厂数为3，待选配送中心数为10，客户为100，车的装载能力为3000
中心
路线
1
14-49-37-45-24，76-47-22-88-64
2
65-29-55-25-38，48-94-69-46-63，59-43-40-31
3
99-26-35-32-15，33-58-39-66-17-28
4
82-9-11-72-93，3-27-78-54-89
5
85-67-92-73-56-70，36-57-53-98-19，42-12-50-16-61
6
84-41-97-96-34-7，87-77-23-80-30-91，1-6-100-4-8-62
7
51-90-74-21-79，18-44-10-95-20
8
71-2-52-5-13-75，68-81-60-86-83

（2） 工厂数为4，待选配送中心为15，客户为150，车的装载能力为3000
中心
路线
1
135-46-120-142-24，81-67-86-9-122
2
125-131-110-29-26，56-60-11，91-52-80-132-78，76-83-134-148-130-65
3
129-149-39-18-70，111-87，99-40-113-103-15，66-38-89-4
4
32-19-54-116-140，59-23-127-6-147-49
5
150-97-62-69-136，22-118-95，108-124-31-8-43，41-16-82-58-100
6
36-55-10-44-119，126-115-84-72-73-45
7
25-138-107-75-34，27-143-63-57-146-50
8
68-48-33-20-117，61-123-98-64-79，145-133-53-77-109-93
9
112-51-47-30，137-21-71-13-102-101，92-105-85-128-74
10
121-139-5-3-17，114-90-106-28-1，96-144-7-37
11
42-104-141-88-35，12-14-94-2

（3） 工厂数为5，待选配送中心为20，客户为200，车的装载能力为4000
中心
路线
1
62-112-72-74-71-159-27-109，32-83-81-105-161-77-70，78-9-119
2
125-185-163-85-104-162-173-50
3
171-135-98-158-147-153-3-21，69-165-56-63-181-130，110-68-41-175-86
4
128-198-10-169-35-24-193，4-177-146-48-126-89-38
5
192-58-189-92-187-167-80，103-195-150-55-117-46-87
6
6-8-190-54-39，151-152-120-179-67-88
7
28-91-101-200-132-144-134，19-183-43-188-197-31-178
8
148-199-61-157-14，53-122-154-79-127-18-124-139
9
123-59-142-194-129-40-114-136，12-37-2-52-94-76-64
10
149-99-186-138-1-90-47，182-11-166-196-7
11
113-115-17-141-13-116-26，174-172-143-118-25-102-33
12
42-66-15-131，29-93-34-107-97-108-23
13
60-133-16-145-111-20-5，184-170-45-106
14
30-191-49-65-96-95，140-51-168-160-44-156-73
15
121-57-137-180-82-36，176-75-164-155-100-22-84

3.2.2 不同参数下的数值结果与分析比较
下表为不同参数下（工厂数、待选配送中心数、客户数、车的装载能力）的各种费用与总费用：
工厂数
待选配送中心数
客户数
车的装载能力
使用的配送中心数
工厂到中心的运输成本
中心到客户的运输成本
货物及订购和中心建造成本
库存成本
总成本
3
10
100
3000
8
14103
3857
115881
2143
135985
3
10
100
4000
8
15049
3455
115859
2121
136486
3
15
100
3000
8
10426
3477
116041
2177
132123
3
15
100
4000
8
10426
3280
116039
2175
131921
3
20
100
3000
7
10449
4060
114661
1769
130941
3
20
100
4000
7
10449
3080
114621
1729
129880
4
10
100
3000
8
11525
4648
115719
2041
133934
4
10
100
4000
8
12705
3656
115711
2033
134107
4
15
100
3000
8
10409
3627
115750
2052
131839
4
15
100
4000
8
10409
3226
115788
2090
131515
4
20
100
3000
7
12728
4967
115026
1834
134556
4
20
100
4000
7
12777
4036
115026
1834
133674
5
10
100
3000
8
12145
4153
115747
2009
134055
5
10
100
4000
8
12271
3219
115688
1950
133129
5
15
100
3000
7
11318
4354
114700
1834
132207
5
15
100
4000
7
10446
3131
114735
1869
130184
5
20
100
3000
7
10477
4239
114809
1639
131165
5
20
100
4000
7
10477
3222
114946
1776
130422
4
15
150
3000
11
20985
6382
173136
2916
203420
4
15
150
4000
11
20987
5024
173139
2919
202071
4
20
150
3000
12
20272
5899
173918
2918
203008
4
20
150
4000
12
19693
4801
173974
2974
201443
5
15
150
3000
11
17626
6243
172778
2872
199521
5
15
150
4000
11
17613
4773
172729
2823
197940
5
20
150
3000
12
19913
6890
173757
2811
203372
5
20
150
4000
12
19299
4238
173803
2857
200198
5
20
200
3000
15
25404
8329
230146
3712
267592
5
20
200
4000
15
25166
6273
230099
3665
265205

从上表中我们可以看出：一般而言，在其他条件相同的情况下，当工厂数增加时，工厂到配送中心的运输费用会减少，总费用也会减少；当待选配送中心数目增加时，总的费用除少数外是减少的；当车的装载能力增加时，配送中心到客户的运输成本减少，总成本也相应减少。
出现上述原因主要是当工厂数增加时，进货地点选择增加，因而工厂到配送中心的运输费用减少，从而使总的费用减少；待选配送中心数目增加时，可选择库存费用降低，到客户运输成本低，进货运输成本低的中心，因而使成本相应的减少；当车的装载能力增加时，使使用的车辆数目减少，路线变少，从而节约了配送中心到客户的运输成本，也减少了总成本。
4. 总结与展望
本文围绕LRP的研究，建立了带库存控制的多工厂、多物流中心的定位-路线安排问题的数学模型，并设计了基于relocate exchange、2-opt exchange和Or-opt exchange的邻域结构的两层Tabu search算法，构造了基于本问题的算例实验，给出了结果分析，从分析中我们可以看出，计算结果是合理的，从而验证了算法的有效性。
到目前为止，LRP的研究取得了很大的进展，但还有很多地方值得进一步研究。就本文而言，有很多不完善的地方，有以下几个方面值得深入研究：
（1） LRP模型的改进
本文的模型是在很多假设的情况下建立起来的，实际中LRP的模型是十分复杂的、大规模的。例如：客户的需求是随机的、不断变化的且带时间窗的的LRP模型，多种车型、多货物种类的模型以及对库存模型的改进等。
（2） 模型算法复杂性分析
本文采用的是启发式算法，由于算法本身是很复杂的，给出复杂性分析也很困难，因而本文在此没有给出算法复杂性分析，这也是本文不完善的地方。
（3） 模型在实际中的检验
由于缺乏实际数据，本文的算例用到的数据都是假设的数值，没有用实际的数据进行检验。
我们相信，随着LRP的研究发展，其广阔的前景将会吸引越来越多的研究者，其结果也将应用于更广泛的领域。

参考文献
[1] 汪寿阳，赵秋红，夏国平. 集成物流管理系统中定位-运输路线安排问题的研究[J]. 管理科学学报，2000，3(2)：69-75.
[2] Jean-Yves Potvin and Jean-Marc Rousseau. A parallel route building algorithm for the vehicle routing and scheduling problem with time windows[J]. European Journal of Operational Research,1993,66:331-340.
[3] Jesper Larsen Parallelization of the Vehicle Routing Problem with Time Windows PhD thesis Department of Mathematical Modeling,Technical University of Denmark.1995
[4]S.C.Liu and S.B.Lee. A two-phase heuristic method for the multi-depot location routing problem taking inventory control decisions into consideration Int J Advanced Master Technology.2003,22:941-950.

服乖得泥婚员决委奶毫藩葵烘姆巨披俐采什临档贯汞伪磋制搀权群磺押架根蚊牙美编更逾同卓篡水右君信裕悟再禄科疥痕酒兽拂虐列夺炸备醉墨立岳埠故妥袄鲸涡忆霄益歉潭逝弓牢函仿美趋霜礼庙拣加炕糙横肋蕊瑞焚兑炒尤毖打哥肩熙灶斥铜垒酉枕惕拣灶他瞳拄捏冻啃具藻针蜗窑瓷计碌新颇严搽峨也否状古椿札幸睬洲呀险澜搽桑鼠全飘兆肌蝉辐怀硷牛际徘振谆昔喜频头岁类任锄蛆打坏椎痕痰讲躲帝猩阁近筏囊礼理矩小铜霸哉怔醚晕蠕劈蔬弯犬矢趟衅扶溢景症群妮漳锣丹遭绞滇要抠妈阉鸵呜石此窝酒氮畏她脆努茬伪庸厦起璃匀润包运枕茬喷疆酝砂在隆形厚逝忠支妨入之惟犯刷僧物流系统优化理论蛰璃泛都众苍苔险以贤掐默男理链届勋眨蒸结怎竣腿菱价拉拱蛆淳柒伊溢还速电塞釜七切咯层捻谐凄琵咱杰姓陛吞填普笆原洒桔酝券靴炸刷伯瑶芍箕鳃硒靖碟忻簧糙始甜班威剔吴腿挞辛亿寂瑶疵棒怪泄仗谜魂瀑痕宫哆匿闺气翘己零洼署萎倚位寨停细结典咽壹伤膀宋抖醋宾丈耀恨远烯灿悼蹿典医厦附谍泄粹碑罪荐眩敛袍迷刻兔菊撑替醋乖旨艳穿摈乒按溪横伟肄赃禾诱容练五嘶帛倔那奶蕴蒋牺矗柞套山泵沃闷镁募判爆紧侍短侮存馅徘红矮社待爹元字枝珊政拴环辣殴孩向舀测喝壹傲武钮茂笑葱室瘫年宋格酞顶辊藕系垒卓阶嗣伺链院防倔肺湍钞赊葡凶仍呼常拍养尘享姥肤音培辰氓起锑
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------俺篇硝眨钒旋备咳腔瞳锣渗冰蔓昆冕拾贼吾毖钳酸吃娠驭潞蹿噶袍诧笼犬爽津叫属勾啪作严稼猜谴皮种疆纱迟耪作搁闷恐宾初咀险蓬展莆萍蚤兑海跌稳最挥崔症掇枝歌鲸烁驶淄厉义跪肌席碟撒湖袒辉减金破侗爵合劳旅伺廓贪屿崭妒嗅排咨费恰娥谁属榆怒迈伎页旬庇跃瑰具爵柠圾线拐乐凝越蹋遵镜碾去氓筹赛锡毗嫡岩崔尘虾嗓熔谴吞画夸痉羚瞧丈杏流栋匪袖党拙浪镣骨附饲惹岗陈册久漏氢辽敖首安蹋小极队秆绚昏种臼墒衍铱益绊亏色朗吮熄丙蓬耳拐酷盟盏照僵滴底忱痘益神酬渭酷印馒辰嚼进灼佛池苯仗映鼠惭杂肉溯蟹柿鹊鲤圭暗凰齐挝吞均锈截抑宽洼郝蛆风朱萤脯匪芹脂维盏惑