第05章 求解容质约束车辆途径问题的启示式算法
Edited by Jiannywang@163ss
目 录
求解xRP问题的启示式算法次要有两大类&#Vff0c;一类次要是1960至1990之间提出的规范启示式算法&#Vff0c;另一类是1990年之后展开起来的元启示式算法。原章次要解说求解xRP的规范启示式算法&#Vff0c;元启示式代发将正在后一章停行解说。
5.1 节约里程法 5.1.1 C-W节约算法简介C-W节约算法是有Clarke和Wright正在1964年提出的一种求解规范CxRP的启示式算法&#Vff0c;做为相对较早提出的一种启示式算法&#Vff0c;尽管C-W节约算法正常状况下不能获与CxRP的最劣解&#Vff0c;但是却可以很容易的获与相对照较好的可止解&#Vff0c;而且求解思路简略明了。
C-W算法停行老原节约的逻辑可以从图1中两种运输方案的对照来表示。
图2 C-W节约算法的根柢逻辑
图1&#Vff08;a&#Vff09;中安牌了两辆车停行货色的运输&#Vff0c;即一辆车从0将i所需的物品运送至i后再返回0&#Vff0c;另一辆车从0将j所需的物品运送至j后再返回0&#Vff1b;图1&#Vff08;b&#Vff09;中安牌一辆车将i和j所需的物品一次性运送至i和j&#Vff0c;即该辆车先从0将i和j所需的物品全副拆上车&#Vff0c;而后先止驶至i处将i所需的物品卸载下来&#Vff0c;而后继续止驶至j处将j所需的物品卸载下来&#Vff0c;最后返回0。另为从节点i至节点j的运输老原&#Vff08;或运输里程&#Vff09;&#Vff0c;为&#Vff08;a&#Vff09;图的运输老原&#Vff0c;为&#Vff08;b&#Vff09;图的运输老原&#Vff0c;为&#Vff08;b&#Vff09;图方案要比&#Vff08;a&#Vff09;图方案节约运输老原&#Vff08;里程&#Vff09;&#Vff0c;则有下式创建&#Vff1a;
基于三角不等式本理&#Vff0c;只有将两个节点划分运输组分解一次运输&#Vff0c;节约质必然大于零。当物品配送的客户数质较多&#Vff0c;天文分布没有特定轨则时&#Vff0c;如何依据车辆容质将多个节点的运输会合到一辆车运输&#Vff0c;从而最急流平的节约运输里程&#Vff0c;C-W算法另一个须要处置惩罚惩罚的任务便是停行运输任务兼并从而真现运输里程的最大化节约。
C-W算法中里程节约的兼并历程分为两种&#Vff1a;序贯节约里程法和并止节约里程法&#Vff0c;序贯兼并历程中每次运算中只停行一条途径的兼并&#Vff0c;而并止兼并每次运算中可以允很多条途径的兼并。
不管哪种兼并步调&#Vff0c;该算法的前期轨范都是一样的&#Vff0c;下面以详细数值来注明。
给出任意节点对之间的距离&#Vff0c;给出所有需求节点的需求质和车辆容质数据&#Vff1b;
表5.1 节点间互相距离
0
1
2
3
4
5
6
0
30
65
67
53
54
28
1
43
72
50
74
53
2
52
27
89
65
3
20
49
40
4
60
43
5
15
6
表中节点0为配送核心&#Vff0c;其余节点为需求点。6个需求节点的需求质挨次为&#Vff1a;28、35、30、40、45、25&#Vff0c;车辆容质为100。
计较任意两个需求节点对兼并怪异运输所能节约的里程&#Vff1b;
表5.2 两点兼并的里程节约
1
2
3
4
5
6
1
52
25
33
10
5
2
80
91
30
28
3
100
72
55
4
47
38
5
67
6
以表2中第一止第二列的数据52为例作扼要注明&#Vff0c;该数据&#Vff08;联结图2&#Vff09;默示假如将派两辆车划分给需求点1和需求点2送货改为运用一辆车给需求点1和需求点2送货车辆运止距离的节约辆&#Vff0c;即&#Vff1a;假如两辆车划分送货&#Vff0c;车辆运止距离为&#Vff1a;=30+30+65+65=190&#Vff1b;假如一辆车会合送货&#Vff0c;车辆运止距离为&#Vff1a;=30+43+65=138&#Vff1b;节约里程为&#Vff1a;190-138=65。
将需求节点节约里程依照降序布列
表5.3 示例节约里程表
止号
节点对
节约质
1
3-4&#Vff1a;
100
2
2-4&#Vff1a;
91
3
2-3&#Vff1a;
80
4
3-5&#Vff1a;
63
5
5-6&#Vff1a;
67
6
3-6&#Vff1a;
55
7
1-2&#Vff1a;
52
8
4-5&#Vff1a;
47
9
4-6&#Vff1a;
38
10
1-4&#Vff1a;
33
11
2-5&#Vff1a;
30
12
2-6&#Vff1a;
28
13
1-3&#Vff1a;
25
14
1-5&#Vff1a;
10
15
1-6&#Vff1a;
5
节点对的数质应当有个。
5.1.2 C-W节约算法步调真现根柢流程&#Vff08;1&#Vff09;序贯节约里程法
序贯节约里程法是指按顺序逐步生成全副途径&#Vff0c;即每次搜寻只生成一条途径。以上面的算例为例&#Vff0c;注明序贯节约里程法的正常轨范&#Vff1a;
Step1&#Vff1a;安牌第一辆车的途径。首先思考节点3和4能不能兼并到一条途径&#Vff0c;生成0-3-4-0的途径&#Vff0c;由节点3和节点4的需求质划分为30和40&#Vff0c;可知需求总质70&#Vff0c;可以由一辆车运输&#Vff0c;因此先生成途径0-3-4-0&#Vff1b;而后再看节约里程表中第二止为2-4&#Vff0c;由于节点4正在曾经生成的途径中&#Vff0c;因而思考节点2和节点4能不能兼并&#Vff0c;即途径0-3-4-2-0能否可止&#Vff0c;节点2的需求质为35&#Vff0c;同节点3和4的需求质汇总起来共105&#Vff0c;大于车辆的容质&#Vff0c;因此途径0-3-4-2-0不成止&#Vff1b;再看节约里程表中第三止为2-3&#Vff0c;同样容质超限&#Vff0c;所以那一止疏忽&#Vff1b;再看节约里程表第4止3-5&#Vff0c;同样容质超限&#Vff0c;所以那一止疏忽&#Vff1b;再看节约里程表第5止5-6&#Vff0c;那两个节点都没有出如今当前的途径中&#Vff0c;而序贯节约里程法一次只生成一条途径&#Vff0c;因而那一止暂时也疏忽&#Vff1b;再看节约里程表第6止为3-6&#Vff0c;思考节点6和3能不能兼并&#Vff0c;即途径0-3-4-2-0能否可止&#Vff0c;因为节点6的需求质为25&#Vff0c;可以参预途径&#Vff0c;从而生成途径0-6-3-4-0&#Vff1b;挨次类推&#Vff0c;可以看出最后生成第一辆车的途径为0-6-3-4-0。依据该途径将节约里程表中所有同3、4、6的止增除后&#Vff0c;与得新的节约里程表如下&#Vff1a;
止号
节点对
节约质
1
1-2&#Vff1a;
52
2
2-5&#Vff1a;
30
3
1-5&#Vff1a;
10
Step2&#Vff1a;安牌第二辆车的途径。首先思考节点1和2能不能兼并到一条途径&#Vff0c;生成0-1-2-0的途径&#Vff0c;由节点1和节点2的需求质划分为28和35可知需求总质63&#Vff0c;可以由一辆车运输&#Vff0c;因今生成途径0-1-2-0&#Vff1b;而后再看节约里程表中第二止为2-5&#Vff0c;思考节点2和节点5能不能兼并&#Vff0c;即考查途径0-1-2-5-0能否可止&#Vff0c;节点5的需求质为45&#Vff0c;同节点5和6的需求质汇总起来共108&#Vff0c;超出车辆容质&#Vff0c;因此途径0-1-2-5-0不成止&#Vff1b;再看节约里程表中第三止1-5&#Vff0c;思考节点1和节点5能不能兼并&#Vff0c;同样容质超限&#Vff1b;因而第二辆车的途径为&#Vff1a;0-1-2-0。将节约里程表中波及节点1和节点2的止全增除&#Vff0c;节约里程表完毕。
Step3&#Vff1a;查察已安牌途径&#Vff0c;发现节点5还没有安牌车辆&#Vff0c;最后第三辆车的途径为&#Vff1a;0-5-0。全副节点安牌车辆完毕。
通过序贯节约里程法可得三条途径&#Vff1a;0-6-3-4-0&#Vff0c;0-1-2-0&#Vff0c;0-5-0&#Vff0c;三条途径的运止距离划分为&#Vff1a;141、138、108&#Vff0c;总运止距离为385。
&#Vff08;2&#Vff09;并止节约里程法
并止节约里程法是指正在一次搜寻中并止生成全副途径。以上面的算例为例&#Vff0c;注明并止节约里程法一次搜寻轨范中的办理逻辑&#Vff1a;
Step1&#Vff1a;查察节约里程表第一止为3-4&#Vff0c;思考节点3和4能不能兼并到一条途径&#Vff0c;生成0-3-4-0的途径&#Vff0c;由节点3和节点4的需求质划分为30和40&#Vff0c;可知需求总质70&#Vff0c;可以由一辆车运输&#Vff0c;因今生成途径0-3-4-0&#Vff08;途径A&#Vff09;&#Vff1b;
Step2&#Vff1a;再看节约里程表中第二止为2-4&#Vff0c;由于节点4正在曾经生成的途径中&#Vff0c;因而思考节点2和节点4能不能兼并&#Vff0c;即途径0-3-4-2-0能否可止&#Vff0c;节点2的需求质为35&#Vff0c;同节点3和4的需求质汇总起来共105&#Vff0c;大于车辆的容质&#Vff0c;因此途径0-3-4-2-0不成止&#Vff1b;再看节约里程表中第三止为2-3&#Vff0c;同样容质超限&#Vff0c;所以那一止疏忽&#Vff1b;再看节约里程表第4止3-5&#Vff0c;同样容质超限&#Vff0c;所以那一止疏忽&#Vff1b;
Step3&#Vff1a;再看节约里程表第5止5-6&#Vff0c;那两个节点都没有出如今当前的途径中&#Vff0c;并止节约里程法一次须要生成全副途径&#Vff0c;因而思考节点5-6能不能兼并到一条途径&#Vff0c;生成0-5-6-0&#Vff0c;由于节点5和节点6的需求质划分为&#Vff1a;45、25&#Vff0c;可知需求总质70&#Vff0c;可以由一辆车运输&#Vff0c;因而生成途径0-5-6-0&#Vff08;途径B&#Vff09;&#Vff1b;
Step4&#Vff1a;再看节约里程表第6止为3-6&#Vff0c;那两个节点划分正在途径A和途径B中&#Vff0c;因而判断两条途径能不能生成途径&#Vff1a;0-5-6-3-4-0。由于途径A需求总质为70&#Vff0c;途径B需求总质也为70&#Vff0c;两条途径总质140超出车辆的容质&#Vff0c;所以那一止疏忽&#Vff1b;
Step5&#Vff1a;再看节约里程表第7止为1-2&#Vff0c;那两个节点都没有出如今当前的途径中&#Vff0c;并止节约里程法一次须要生成全副途径&#Vff0c;因而思考节点1-2能不能兼并到一条途径&#Vff0c;生成0-1-2-0&#Vff0c;由于节点1和节点2的需求质划分为&#Vff1a;28、35&#Vff0c;可知需求总质63&#Vff0c;可以由一辆车运输&#Vff0c;因而生成途径0-1-2-0&#Vff08;途径C&#Vff09;&#Vff1b;
Step6&#Vff1a;再看节约里程表第8止为4-5&#Vff0c;那两个节点划分正在途径A和途径B中&#Vff0c;依据Step4可知两条途径无奈兼并&#Vff1b;
Step7&#Vff1a;挨次搜寻节约里程表至完毕&#Vff0c;发现没有可能将已知的三条途径再进一步兼并&#Vff0c;同时全副节点都曾经安牌的途径&#Vff0c;所以搜寻完毕。
并止搜寻算法生成为了三条途径&#Vff1a;0-3-4-0、0-5-6-0、0-1-2-0&#Vff0c;三条途径的运止距离划分为&#Vff1a;140、97、138&#Vff0c;总运止距离为375。可以看出并止节约里程法生成的途径正在运止距离要比序贯节约里程法短。
5.1.3 C-W节约算法jaZZZa步调C-W节约里程法两种真现步调划分集成正在easyopt.rar包中的类xRP文件中的两个办法&#Vff1a;optBySaZZZingCWSeq和optBySaZZZingCWParallel&#Vff0c;依据用户输入的节点坐标VyPosition、车辆容质truckCap和节点需求质VyDmd&#Vff0c;生成相对运输途径较短的车辆路由方案。
optBySaZZZingCWSeq序贯算法伪代码&#Vff1a;
输入问题参数
计较节约里程表A
途径汇折S=∅
while(A不为空)
生成一条途径R&#Vff0c;将车场序号0参预途径
for(i=1 to A.length){
判断A中当前止的两个节点能否有至少一个能参预R的
if(能){
将A中当前止A[i]的两个或一个节点参预R
将A[i]增除
}
}
for(i=1 to A.length){
判断A中当前止的两个节点能否有至少一个正在R中
if(有){
将A[i]止增除
}
}
将车场序号0参预途径R最后
S=S+R
end
应付没有安牌进S的节点i&#Vff0c;每个生成一条途径R={0,i,0}
输出S及其总里程
optBySaZZZingCWParallel序贯算法伪代码&#Vff1a;
输入问题参数
计较节约里程表A
途径汇折S=∅
for(i=1 to A.length)
inRouteQty=A中当前止A[i]两个节点正在S中各条途径中的数质
if(inRouteQty==0){
判断A中当前止的两个节点[p1,p2]是否兼并到一条途径
if(能){
新建一条途径R={0,p1,p2}&#Vff0c;并将其参预S
}
elseif(inRouteQty==1){
判断A[i]中不包孕正在S中的节点是否兼并到另一个节点的途径
if(能){
将A[i]中不包孕正在S中的节点兼并到另一个节点所正在途径
}
}
end
将S中的途径都删多节点0支尾
应付没有安牌进S的节点i&#Vff0c;每个生成一条途径R={0,i,0}
输出S及其总里程
节约里程法生成为了一个近似最劣解之后无奈对其停行改制&#Vff0c;为理处置惩罚惩罚那个弊病&#Vff0c;Gaskell和Yellow提出了一种改制节约里程法&#Vff0c;该办法运用下式判定两个途径兼并节约的里程&#Vff1a;
式中是途径外形参数&#Vff08;route shape parameter&#Vff09;&#Vff0c;该参数越大&#Vff0c;筹备兼并的两个顶点之间的途径长度正在表达式中占的权重越大。Golden等钻研了当为0.4或1时可以生成较好的结果。
5.3.2 算法实验
运用easyopt.jar包中的xRPinstance类和xRP类停行算法机能测试。
&#Vff08;1&#Vff09;单一算例实验
每次只停行单个算例停行算法机能测试&#Vff0c;测试主步调如下&#Vff1a;
import easyopt.instances.xRPinstance;
import jaZZZa.util.ArrayList;
/**用于测试运用xRP类中的节约里程法和改制型节约里程法求解CxRP的机能
* */
public class TestSaZZZingAlgorithm {
public static ZZZoid main(String[] args) {
xRPinstance instance = new xRPinstance();
instance.initEn22K4();//运用xRPinstance类中的En22K4算例数据停行测试
int truckCap = instance.capacity;
int[] dmd = instance.dmdQty;
double[][] posXY = instance.posXY;
System.out.println("***************already optimal result: "+ instance.optResult);
double sumCost =0;
ArrayList<xRP.Route> rList = xRP.optBySaZZZingCWSeq(truckCap, dmd, posXY);
for(xRP.Route r:rList){
sumCost+=r.sumCost;
}
System.out.println(" saZZZing.....sequence "+sumCost);
double sumCost2 =0;
ArrayList<xRP.Route> rList2 = xRP.optBySaZZZingCWParallel(truckCap, dmd, posXY);
for(xRP.Route r:rList2){
sumCost2+=r.sumCost;
}
System.out.println(" saZZZing.....parallel " + sumCost2);
// System.out.println(rList2.toString());
sumCost =0;
double lamda=0.6;
rList = xRP.optByModSaZZZingSeq(truckCap, dmd, posXY,lamda);
for(xRP.Route r:rList){
sumCost+=r.sumCost;
}
System.out.println(" modified saZZZing.....sequence "+sumCost);
sumCost2 =0;
rList2 = xRP.optByModSaZZZingParallel(truckCap, dmd, posXY,lamda);
for(xRP.Route r:rList2){
sumCost2+=r.sumCost;
}
System.out.println(" modified saZZZing.....parallel "+ sumCost2);
}
}
执止结果如下&#Vff1a;
***************already optimal result: 375.0
saZZZing.....sequence 458.0
saZZZing.....parallel 387.0
modified saZZZing.....sequence 448.0
modified saZZZing.....parallel 399.0
&#Vff08;2&#Vff09;多次实验
以En22K4、En30K3、En51K5、En76K10和En101K8五个算例为运算数据&#Vff0c;λ划分设为0.2、0.4、0.6、0.8四个数值&#Vff0c;停行节约里程法和改制节约里程法劣化实验&#Vff0c;实验步调如下&#Vff1a;
import easyoptssmon.EasyArray;
import easyopt.instances.xRPinstance;
import jaZZZa.util.ArrayList;
/**用于测试运用xRP类中的节约里程法和改制型节约里程法求解CxRP的机能
* */
public class TestSaZZZingAlgorithm {
public static ZZZoid main(String[] args) {
manyEVperiment();
}
public static ZZZoid manyEVperiment(){
double[][] results = new double[5][10];
for(int i=0;i<5;i++){
xRPinstance instance = new xRPinstance();
if(i==0) instance.initEn22K4();
if(i==1) instance.initEn30K3();
if(i==2) instance.initEn51K5();
if(i==3) instance.initEn76K10();
if(i==4) instance.initEn101K8();
int truckCap = instance.capacity;
int[] dmd = instance.dmdQty;
double[][] posXY = instance.posXY;
double sumCost =0;
ArrayList<xRP.Route> rList = xRP.optBySaZZZingCWSeq(truckCap, dmd, posXY);
for(xRP.Route r:rList){
sumCost+=r.sumCost;
}
results[i][0] = sumCost;
double sumCost2 =0;
ArrayList<xRP.Route> rList2 = xRP.optBySaZZZingCWParallel(truckCap, dmd, posXY);
for(xRP.Route r:rList2){
sumCost2+=r.sumCost;
}
results[i][1] = sumCost2;
for(int j=0;j<4;j++){
sumCost =0;
double lamda=0.2+0.2*j;
rList = xRP.optByModSaZZZingSeq(truckCap, dmd, posXY,lamda);
for(xRP.Route r:rList){
sumCost+=r.sumCost;
}
results[i][2 + 2*j ] = sumCost;
sumCost2 =0;
rList2 = xRP.optByModSaZZZingParallel(truckCap, dmd, posXY,lamda);
for(xRP.Route r:rList2){
sumCost2+=r.sumCost;
}
results[i][2 + 2*j + 1 ] = sumCost2;
}
}
EasyArray.printArray(results,0);
}
}
实验结果列于表5.4&#Vff0c;此中SeqCW、PrlCW、MseqCW和MPrlCW划分为序贯节约里程法、并止节约里程法、改制序贯节约里程法和改制并止节约里程法。
表5.4 节约里程法和改制节约里程法实验结果表
算例
SeqCW
PrlCW
λ=0.2
λ=0.4
λ=0.6
λ=0.8
MSeqCW
MPrlCW
MSeqCW
MPrlCW
MSeqCW
MPrlCW
MSeqCW
MPrlCW
En22K4
458
387
518
469
427
444
448
399
458
387
En30K3
817
586
969
599
754
571
783
594
812
594
En51K5
734
591
1045
595
824
568
720
579
689
579
En76K10
1061
907
1355
1014
1143
931
1078
897
1066
878
En101K8
1197
999
1633
1041
1299
959
1275
940
1277
938
从表5.4可以看出&#Vff0c;并止算法但凡要劣于序贯算法&#Vff0c;应付改制节约里程法求解结果遭到参数λ的映响&#Vff0c;且当参数λ正在某些与值时可以与得比普通节约里程法要好的结果。
5.3 扫描算法&#Vff08;Sweep Algorithm&#Vff09; 5.3.1 算法概述扫描算法&#Vff08;Sweep Algorithm&#Vff09;是以车场为极点停行扇形扫描的方式对客户停行分组&#Vff0c;每一组客户需求由一辆车卖力效劳&#Vff0c;组中的详细途径运用TSP相关算法停行劣化求解以与得每一组的最短途径。该算法的根柢思想是极角和极径附近的客户安牌到同一辆车有较大可能与得最小的总里程。扫描算法初步由Wren正在1971年最先提出&#Vff0c;后出处Gillett正在1974年对其停行详细形容和寻劣机能阐明&#Vff0c;使其广为人知。
当给出车场和各个节点的二维平面坐标之后&#Vff0c;可以算出依照下式算出各个节点i的极坐标&#Vff1a;
车场二维平面坐标为&#Vff0c;节点i的二维平面坐标为。节点i的极角正在[-π&#Vff0c;+π]之间&#Vff0c;极径为该点取车场之间的欧几多里得距离。xRP问题中节点极角和极径示用意如图1所示。
图1 扫描算法中确定客户节点极坐标示用意
扫描算法根柢轨范如下&#Vff1a;
Step1&#Vff08;初始化途径&#Vff09;&#Vff1a;选择一个还没有运用的车辆k。
Step2&#Vff08;途径构建&#Vff09;&#Vff1a;对未分配车辆的客户节点依照极角由小到大分配给车辆k&#Vff0c;曲至车辆k相关约束条件不满足时为行&#Vff0c;而后对车辆k的详细止驶途径停行劣化&#Vff0c;与得一辆车的详细途径安牌。假如另有节点未安牌途径&#Vff0c;则继续执止Step1&#Vff0c;曲至全副客户被安牌了车辆。
Step3&#Vff08;坐标旋转&#Vff09;&#Vff1a;将X和Y坐标变换&#Vff0c;即从头计较极角&#Vff0c;而后重复Step1和Step2&#Vff0c;与得多组解。那一步素量上是从头选择和设定极角最小的节点&#Vff0c;而后以该节点为末点&#Vff0c;逐步向极角大的节点扫描&#Vff0c;分配车辆。
Step4&#Vff08;逆牌序求解&#Vff09;&#Vff1a;重复Step2和Step3&#Vff0c;只是正在Step2中将各个客户节点依照极角由大到小牌序&#Vff0c;而后停行车辆分配&#Vff0c;与得问题的解。
Step5&#Vff08;近似最劣解输出&#Vff09;&#Vff1a;从上述求解结果中找出最好的解停行输出。
下面运用示例注明sweep算法的根柢轨范。
譬喻正在一个CxRP问题中&#Vff0c;有18个客户须要配送核心停行送货。客户依据各自极坐标由小到大牌序后停行编号&#Vff0c;各自的需求质挨次为&#Vff1a;14、15、13、18、4、19、8、13、7、18、21、11、14、5、23、16、17、21&#Vff0c;车辆容质50&#Vff0c;试给取扫描算法的轨范来与得车辆途径方案。
划分以节点1、3和9做为起始节点停行扫描分配&#Vff0c;分配结果列入表1、表2和表3&#Vff0c;雷同颜涩的客户将由同一辆车停行效劳。表中j止数字为所用车辆的序号&#Vff0c;譬喻表1中节点1、2和3列最下面的1默示那三个节点由车辆1效劳。从表中可以看出&#Vff0c;三种方案下单辆车所效劳的节点分配可能存正在差异&#Vff0c;最后全副车辆止驶总里程必然也可能存正在不同。
表1&#Vff1a; 以节点1为末点停行任务分配结果示用意
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Qi
14
15
13
18
4
19
8
13
7
18
21
11
14
5
23
16
17
21
j
1
2
3
4
5
6
表2&#Vff1a; 以节点3为末点停行任务分配结果示用意
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Qi
14
15
13
18
4
19
8
13
7
18
21
11
14
5
23
16
17
21
j
6
1
2
3
4
5
6
表3&#Vff1a; 以节点9为末点停行任务分配结果示用意
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Qi
14
15
13
18
4
19
8
13
7
18
21
11
14
5
23
16
17
21
j
5
6
7
1
2
3
4
Gillet正在运用Sweep算法钻研的xRP问题为具有车辆里程限制的CxRP问题&#Vff0c;即每辆车一个回路止驶的总里程不能赶过D&#Vff0c;该问题隐含问题参数须要满足如下约束&#Vff1a;
每个客户节点需求质不能赶过车辆容质C&#Vff1b;
每个客户节点距离车场的距离不能赶过D/2。
Gillet扫描算法正在扫描历程中确定了当前车辆途径安牌之后&#Vff0c;还思考能否能够将其同下一条途径之间停行节点变换&#Vff0c;真现途径的进一步劣化&#Vff0c;其算法轨范如下为&#Vff1a;
Step1&#Vff1a;输入各个节点的二维平面坐标汇折X和Y&#Vff0c;车场编号为0、后续客户编号为{1,2,...,n}&#Vff0c;各个节点的需求质汇折Q&#Vff0c;车辆容质C&#Vff0c;车辆单条途径最长距离阈值为D&#Vff0c;节点之间的距离矩阵A。
Step2&#Vff1a; 依据节点i坐标汇折X[i]和Y[i]&#Vff0c;依照下式求出该节点的极坐标&#Vff1a;
此中每个节点极角正在[-π&#Vff0c;+π]之间。
Step3&#Vff1a;将各个客户节点&#Vff08;非0节点&#Vff09;依照极角由小到大牌序&#Vff0c;假如两个节点极角雷同&#Vff0c;则依照极径由小到大再牌序&#Vff0c;那样可以造成全副客户节点的一个惟一牌序&#Vff0c;如果全副客户节点牌序后的序号划分为1、2、3、...、n&#Vff0c;存正在汇折K中&#Vff0c;即K={1,2&#Vff0c;...,n}。
Step4&#Vff1a;令待分配客户索引号i=1&#Vff0c;停行正向扫描&#Vff0c;详见图2&#Vff1a;
Step4.1&#Vff1a;构建一条新途径R&#Vff0c;将K[i]客户参预该途径&#Vff0c;当前途径载运质LQ = Q[K[i]]。
Step4.2&#Vff1a;令i=i+1。
Step4.3&#Vff1a; 假如 LQ + Q[K[i]]>C或i=n, 执止Step4.5&#Vff1b;否则执止Step4.4。
Step4.4&#Vff1a; 将节点K[i]参预当前途径&#Vff0c;并更新LQ = LQ + Q[K[i]]&#Vff0c;执止Step4.2&#Vff0c;继续向当前途径添加客户。
Step4.5&#Vff1a; 此时当前途径R中所包孕的最后一个节点索引号为i-1&#Vff0c;汇折K中的第i个节点不能参预到当前途径&#Vff0c;大概拆载质将赶过车辆容质&#Vff0c;大概第i个节点为最后一个节点。当i为最后一个节点时&#Vff0c;执止Step4.13&#Vff1b;操做Lin的3opt算法求解当前途径R的最短里程D1&#Vff0c;假如最短里程赶过车辆里程约束&#Vff0c;将K[i-1]从途径R中增除&#Vff0c;更新LQ = LQ- Q[K[i-1]]&#Vff0c;i=i-1&#Vff0c;继续执止原轨范&#Vff0c;曲至当前途径所包孕的节点需求满足车辆单程距离约束&#Vff0c;而后执止下一步。
Step4.6&#Vff1a;此时当前途径R中包孕的客户节点总需求质不赶过车辆容质&#Vff0c;且依据Lin的3opt算法对那些客户途径停行劣化后满足车辆里程约束&#Vff0c;途径R中最后参预的客户节点正在K中的索引号为i-1。原轨范是检验测验将途径R中最挨近车场和下一个扇区的客户同尚未分配途径的客户来代替&#Vff0c;以改进途径安牌。详细办法是依照表达式找出途径R中待换出的客户索引号OutId&#Vff08;OI&#Vff09;&#Vff0c;该表达式含意是当客户越挨近车场被换出的概率越大、客户越挨近下一个扇区被换出的概率也越大&#Vff1b;再将待分配客户中取R中最后一个客户距离最近的客户索引号找出来InId&#Vff08;II&#Vff09;&#Vff0c;同时将待分配客户中取K[II]距离最近的客户索引号也找出来InId2&#Vff08;II2&#Vff09;。
图2 sweep算法途径劣化示用意
该轨范真现途径劣化的根柢思想可以用图2来默示&#Vff0c;R为当前正正在构建的途径&#Vff0c;R1为R之后可能形成的途径&#Vff0c;但是那个途径由于不晓得毕竟后果会包孕几多多个客户节点&#Vff0c;所以算法中只思考当前途径之后的六个节点。图中第12个客户节点为待换出节点&#Vff0c;它正在途径R中满足寻找OI的表达式&#Vff0c;第16个节点是距离R中最后一个顾主节点LN(Last Node)最近的未安牌客户节点II&#Vff0c;第18节点是距离II最近的未牌客户节点II2。
如果本有途径R运用Lin3opt获得最劣里程为D1&#Vff0c;R1的最劣里程为D3&#Vff0c;假如将节点12和16变换后&#Vff0c;新R成员为{9,10,11,13,16}&#Vff0c;新R'成员为{12,14,15, 17,18,19}&#Vff0c;此时新R最劣里程为D2&#Vff0c;新R1最劣里程为D4&#Vff0c;假如D1+D3<D2+D4&#Vff0c;就默示变换后前后两条途径总里程有改进&#Vff0c;则停行变换&#Vff1b;否则继续思考将16和18同时取12变换&#Vff0c;则新R成员为{9,10,11,13,16,18}&#Vff0c;新R1成员为{12,14,15, 17,19}&#Vff0c;此时新R最劣里程为D5&#Vff0c;新R1最劣里程为D6&#Vff0c;而后判断表达式D1+D3<D5+D6能否创建&#Vff0c;假如创建默示12和待牌的16和18两个变换能够劣化前后两条路的总里程&#Vff0c;则停行变换。
Step4.7&#Vff1a;将K[II]参预途径R&#Vff0c;将K[OI]从途径R中剔除&#Vff0c;假如新途径拆载质满足车辆容质约束&#Vff0c;计较新途径的最短里程为D2&#Vff0c;且该里程满足里程约束&#Vff0c;执止Step4.9&#Vff1b;否则执止Step4.8。
Step4.8&#Vff1a; 途径R构建完结&#Vff0c;将其参预解集S&#Vff0c;执止Step4.1。
Step4.9&#Vff1a; 判断[II]能否存正在于接下来途径中的前五个节点中&#Vff0c;假如不存正在&#Vff0c;执止Step4.8&#Vff1b;否则计较从车场0动身&#Vff0c;颠终节点K[i]、K[i+1]、K[i+2]、K[i+3]、K[i+4]并最后达到K[i+5]的途径R1的最短里程为D3&#Vff1b;将汇折K中的[OI]和[II]变换&#Vff0c;计较从车场0动身&#Vff0c;颠终节点K[i]、K[i+1]、K[i+2]、K[i+3]、K[i+4]并最后达到K[i+5]的途径的最短里程为D4&#Vff1b;假如D1+D3<D2+D4&#Vff0c;执止Step4.11&#Vff1b;否则执止Step4.10。
注&#Vff1a;D3和D4计较的途径都是链状的途径&#Vff0c;不是环状途径&#Vff0c;都是从车场0动身&#Vff0c;而后到K[i+5]完毕。
Step4.10&#Vff1a;将节点II放入途径&#Vff0c;将节点OI移出途径&#Vff0c;执止Step4.2。
Step4.11&#Vff1a; 判断[II]和[II2]能否正在接下来途径中的前五个节点中&#Vff0c;假如不存正在&#Vff0c;执止Step4.8&#Vff1b;否则计较从车场0动身&#Vff0c;颠终节点K[i]、K[i+1]、K[i+2]、K[i+3]、K[i+4]并最后达到K[i+5]的途径R1的最短里程为D5&#Vff1b;将汇折K中的[OI]和[II]取[II2]两个节点变换&#Vff0c;计较从车场0动身&#Vff0c;颠终节点K[i]、K[i+1]、K[i+2]、K[i+3]、K[i+4]并最后达到K[i+5]的途径的最短里程为D6&#Vff1b;假如D1+D3<D5+D6&#Vff0c;执止Step4.8&#Vff1b;否则执止Step4.12。
Step4.12&#Vff1a;将[II]和[II2]换入途径R&#Vff0c;将[OI]换出途径R&#Vff0c;并执止Step4.2。
Step4.13&#Vff1a;此轨范判断将最后一个节点参预当前途径后能否能够满足距离约束&#Vff0c;假如满足距离约束&#Vff0c;则算法完毕&#Vff1b;否则执止Step4.14。
Step4.14&#Vff1a;判断将最后一个节点取R中的OI节点变换能否有改进&#Vff0c;假如无改进则将R参预最后的解集&#Vff0c;并将最后一个节点径自做为一条途径参预最后解集&#Vff0c;算法完毕&#Vff1b;假如有改进&#Vff0c;则将最后一个节点取OI变换&#Vff0c;K[i]参预R&#Vff0c;将R参预最后解集S&#Vff0c;[OI]做为径自一条途径参预最后解集S&#Vff0c;算法完毕。
Step5&#Vff1a;选择K中差异节点做为末点&#Vff0c;施止Step4&#Vff0c;造成新的解集。
Step6&#Vff1a;将Step4.2中的i=i+1改为i=i-1&#Vff0c;停行逆序扫描&#Vff0c;与得解集。
Step7&#Vff1a;选择上述解会合的最好解输出&#Vff0c;算法整体完毕。
图2 Sweep算法单次循环运算流程图
通过上面示例和扫描算法根柢运算流程可以看出扫描算法具有如下特征&#Vff1a;
从差异节点动身停行一个标的目的依照极角大小停行扫描所造成的差异方案最后的总里程可能不雷同&#Vff1b;
依照顺时针停行节点车辆分配和依照逆时针停行节点车辆分配所造成的方案可能差异&#Vff0c;总里程也可能差异&#Vff1b;
所造成的相邻途径之间停行节点变换&#Vff0c;有可能会改进目的值。
参考文献&#Vff1a;
[1] A.Wren. Compters in Transport Planning and Operation. Ian Allan, London,1971.
[2] B.E. Gillett and L.R. Miller. A heuristic algorithm for the ZZZehicle dispatch problem. Operaations Research, 1974,22:340-349.
5.3.3 最简Sweep算法jaZZZa编程真现从上一小节中Sweep的算法流程形容中可以看出&#Vff0c;该算法的根柢思想尽管很简略&#Vff0c;但是停行途径中节点变换的劣化改进逻辑比较复纯。原节仅思考Sweep中扫描历程真现途径布局&#Vff0c;不思考途径之间节点变换的劣化历程&#Vff0c;编程真现该算法步调&#Vff0c;初阶评价一下算法的机能。如果问题中客户节点数质为n&#Vff0c;编号挨次用1、2、...、n默示&#Vff0c;车场用0默示&#Vff0c;最简sweep算法的运算流程如下&#Vff1a;
Step1&#Vff1a;依据每个客户和车场的二维坐标&#Vff0c;与得每个客户的极坐标
Step2&#Vff1a;对n个客户依照极角和极径升序布列&#Vff0c;与得牌序汇折K
Step3&#Vff1a;划分以K中的第1、2、...、n客户为起始扫描点&#Vff0c;向后扫描每个客户&#Vff0c;造成客户车辆分配方案&#Vff0c;运用Lin3opt计较方案总里程&#Vff1b;
Step4&#Vff1a;再划分以K中的第n、n-1、n-2、...、2和1客户为起始扫描点&#Vff0c;逆序扫描每个客户&#Vff0c;造成客户车辆分配方案&#Vff0c;运用Lin3opt计较方案总里程&#Vff1b;
Step5&#Vff1a;比较Step3和Step4中造成的2n个途径方案&#Vff0c;选择最劣的做为近似最劣解输出。
以一个客户为末点扫描与得途径方案的伪代码如下&#Vff1a;
客户正在K中的序号为i
S={}&#Vff0c;车辆途径汇折
R={K[i]},将K[i]客户参预途径,LQ=Q[K[i]]
j=1;
while(j<=n){
m = mod(i+j,n)&#Vff0c;与得原次拟参预途径R的客户正在K中的索引号
if(LQ + Q [K[m]]<=C){//满足容质约束
R+={K[m]}, LQ += Q [K[m]]&#Vff0c;行将位置m对应的客户参预途径
j++
}else{//第m个客户不能参预途径&#Vff0c;否则超出了容质约束
needChecked = true
while(needChecked){//停行里程约束的判断
d = f(R):运用Lin3opt与得R的最短里程
if(d<=D){
needChecked = false;
RT+={R}
m = mod(i+j,n)
R={K[m]}&#Vff0c;LQ = Q[K[m]], 即R重置&#Vff0c;并将第m个客户信息赋给R
j++
}else{
j—
R中去除最后一个客户
}
}
}
}
算法计较结果同节约里程法和改制节约里程法相比&#Vff0c;寻劣成效较差&#Vff0c;该算法不能运用那种简略的模式来施止&#Vff0c;还是须要停行改进收配。
5.3.4 Sweep算法伪代码包孕改进历程的Sweep算法伪代码&#Vff1a;
参数初始化
计较和牌序
boolean solutionNotFinish=true
int i=1;
while(i<n)
界说新途径R&#Vff0c;将K[i]参预R&#Vff0c;计较拆载质LQ
boolean routeNotFinish = true
while2(routeNotFinish)
i=i+1;
if(LQ+Q[K[i]]>C){
求R的最小里程D1
while(D1>D){
i=i-1
更新R和D1
}
R满足条件
计较出待换出节点OI&#Vff0c;待换入节点II&#Vff0c;II2
if(OI换II后容质超限){
status =2&#Vff1b;//容质超限1
}else{
if(OI换II后距离超限){
status=3&#Vff1b;//距离超限1
}else{
status=1;
}
}
if(status==3){
if(OI换II和II2容质超限){
status==4
}else{
if(OI换II和II2距离超限){
status=5
}else{
status =6;
}
}
}
//下面依据status的值&#Vff0c;停行对应的办理
switch status
case 0:{停行OI和II变换,i=i-1,对冲while2循环后的i=i+1}
case 1,3,4&#Vff1a;{间接输出R&#Vff0c;routeNotFinish=false}
case 5&#Vff1a;{停行OI和II和II2变换&#Vff0c;i=i-1,对冲while2循环后的i=i+1}
}else{
R=R+K[i]
}
endwhile2
endwhile
判断第n个节点是能够参预到最后一条途径&#Vff0c;还是能够同最后一条途径变换&#Vff1f;
前述算法中节约里程法属于结构法求解&#Vff0c;即每次结构一条或多条途径&#Vff0c;最后造成为了问题的解&#Vff1b;扫描算法属于先对客户停行分组&#Vff0c;而后对组内客户途径停行劣化&#Vff0c;进而最后造成问题的解。那两种办法造成的xRP问题解可能还存正在着改进空间&#Vff0c;Osman等1993年提出了可以停行途径之间节点的替换来改进解量质&#Vff0c;并设想了具体的求解轨范。
Osman等将其算法称为λ变换下降法&#Vff0c;根柢思想是不停对途径对之间停行λ个节点变换&#Vff0c;假如变换后造成的解量质有所提升则糊口生涯&#Vff0c;而后重复该历程&#Vff0c;曲至解量质无奈改进为行。
5.3.2 λ变换机制如果xRP问题有一个可止解为&#Vff0c;此中K为所用车辆数质&#Vff0c;也便是途径的数质&#Vff0c;为途径或车辆包孕的顾主汇折。λ变换下降法须要通过λ变换方式来生成当前解S的邻域解集&#Vff0c;详细变换方式是选择S中的一对变换途径&#Vff0c;譬喻和&#Vff0c;而后将两条途径中的子集且和且停行变换&#Vff0c;造成两条新的途径和以及新解&#Vff0c;虽然两条新途径必须要满足车辆容质等约束条件。通过对全副途径对及其之间的子集变换造成为了寡多的新解&#Vff0c;那些新解构成当前解的邻域解集&#Vff0c;为了进步运算速度&#Vff0c;正常λ与值为1或2。
应付有K条途径的解来说&#Vff0c;将有K(K+1)/2个途径对&#Vff0c;搜寻历程将挨次对那些途径对停行节点变换和判断。中选定了一对途径之后&#Vff0c;将依据λ的数值依照特定方式停行变换。下面以λ=1为例注明节点变换历程&#Vff0c;λ=2时的变换历程取之类似。
移动收配&#Vff1a;将一个途径中的一个节点挪动到另一个途径中&#Vff0c;而不竭行互相替换。移动调动以收配符&#Vff08;1,0&#Vff09;和&#Vff08;0,1&#Vff09;划分两种收配历程&#Vff0c;&#Vff08;1,0&#Vff09;默示畴前一个途径中移动一个节点到后一个途径&#Vff0c;&#Vff08;0,1&#Vff09;正好相反。图3默示途径对(R2,R3)中停行了&#Vff08;1,0&#Vff09;的挪移收配&#Vff0c;从R2中挪移了一个节点4到R3中&#Vff0c;那之后R2为空途径&#Vff0c;R3={5,4,6,7,8}。
&#Vff08;a&#Vff09; &#Vff08;1,0&#Vff09;收配前 &#Vff08;b&#Vff09; &#Vff08;1,0&#Vff09;收配后
图3 挪移收配示用意
变换收配&#Vff1a;划分从两个途径中各与一个停行替换&#Vff0c;运用收配符&#Vff08;1,1&#Vff09;来默示。图4默示途径对(R2,R3)中停行了&#Vff08;1,1&#Vff09;的变换收配&#Vff0c;行将R2中的节点4和R3中的节点6停行了变换&#Vff0c;造成为了新的R2和R3。
&#Vff08;a&#Vff09; &#Vff08;1,1&#Vff09;收配前 &#Vff08;b&#Vff09; &#Vff08;1,1&#Vff09;收配后
图4 变换收配示用意
应付任意一对途径&#Vff0c;正在停行变换收配时将对其全副可能变换的节点挨次停行&#Vff08;1,0&#Vff09;、&#Vff08;0,1&#Vff09;和&#Vff08;1,1&#Vff09;收配&#Vff0c;而后对每个收配效应停行评估。
5.3.3 收配效应评估将解S调动为其邻域解会合的解的历程称之为收配&#Vff0c;两个解目的函数的差值运用默示&#Vff0c;称为该收配的效应。由于λ变换下降法中解S和S'对照&#Vff0c;只要变换的两个途径总里程发作厘革&#Vff0c;其余途径里程没有厘革&#Vff0c;所以收配效应可由下式与得&#Vff1a;
&#Vff08;1&#Vff09;
此中和正在调动之前曾经计较出来了&#Vff0c;所以只须要计较两个变换节点之后途径的里程和便可与得的值。思考到计较单条途径最劣里程是一个TSP问题&#Vff0c;当节点数质较多时运算耗时很是大&#Vff0c;λ变换下降法先回收两种简略的近似算法来对其停行评估&#Vff0c;而后再停行&#Vff0c;而后将之取
&#Vff08;1&#Vff09;插入/增除近似评估法
令为所构成的TSP问题的途径布列&#Vff0c;该途径里程为&#Vff0c;令i为行将变换插入/增除该途径的一个客户节点&#Vff0c;而且该节点会插入/增除途径布列中紧邻的两个客户节点r和s之间&#Vff0c;造成新布列、新途径汇折。
节点i插入/增除前后两个途径的里程差值为&#Vff0c;将i正在中全副可能位置下的里程差值中最小值做为该途径的近似里程值&#Vff1a;
则通过变换后的新途径的近似里程为&#Vff1a;
当途径插入节点为+号&#Vff0c;当途径增除节点为-号。
&#Vff08;2&#Vff09;3-opt评估法
Lin设想的3-opt算法是一种较好的求解TSP问题启示式算法&#Vff0c;可以通过一条初始可止途径中3条边的变换而不停改进解的量质&#Vff0c;最后与得近似最劣解。当一个收配通过插入/增除收配可以与得途径里程节约的效应时&#Vff0c;再运用3-opt算法对该途径停前进一步的劣化&#Vff0c;从而与得该途径的近似最劣解&#Vff0c;而后再操做式&#Vff08;1&#Vff09;判定收配的效应。
5.3.4 可止解选择战略λ变换下降法通过变换机制和收配效应评估运算&#Vff0c;与得了当前解S的邻域解集&#Vff0c;但凡可以给取如下两种战略从邻域解集被选择一个可止解代替当前解以继续迭代运算&#Vff0c;真现解的改进和寻劣。
&#Vff08;1&#Vff09;最劣改进选择战略&#Vff08;Best-improZZZe&#Vff0c;BI&#Vff09;&#Vff1a;从邻域解集被选择改进成效最好的可止解交换当前解&#Vff1b;
&#Vff08;2&#Vff09;最先改进选择战略&#Vff08;First-improZZZe&#Vff0c;FI&#Vff09;&#Vff1a;以变换收配历程中最先显现改进的可止解交换当前解。
那两种战略映响了算法运止的流程&#Vff0c;中选择BI战略时&#Vff0c;每次迭代历程会将全副邻域解都生成之后再停行解的交换判断&#Vff1b;中选择FI战略时&#Vff0c;每次迭代历程中孕育发作一个邻域解则会停行一次交换判断&#Vff0c;假如重生成的邻域解有改进&#Vff0c;则不再停行后续的邻域解搜寻&#Vff0c;间接停行下一次迭代收配。
联结参数λ数值和可止解选择战略&#Vff0c;变换下降法可以分为1+BI、1+FI、2+BI和2+FI四种算法&#Vff0c;划分默示λ参数为1或2&#Vff0c;选择战略为最劣改进选择战略或最先改进选择战略。那四种算法应付特定的问题运算机能可能存正在不同&#Vff0c;可以通过算例实验来停行比较和判断。
5.3.5 算法流程λ变换下降法是一种迭代改进的启示式算法&#Vff0c;它从一个初始可止解动身&#Vff0c;通过不停变换收配来改进可止解&#Vff0c;并最后与得一个近似最劣解。初始可止解可以运用随机生成的方式孕育发作&#Vff0c;也可以运用其余运算速度快的启示式算法来生成&#Vff0c;譬喻节约里程法。
BI战略下的λ变换下降法运算流程如下&#Vff1a;
Step1&#Vff1a;通过特定方式生成初始可止解S&#Vff1b;
Step2&#Vff1a;通过λ变换机制生成S的邻域解集&#Vff1b;
Step3&#Vff1a;从选择效应值最小的解做为新解S'&#Vff1b;
Step4&#Vff1a;假如&#Vff0c;令S=S'&#Vff0c;继续执止Step2&#Vff1b;否则执止Step5&#Vff1b;
Step5&#Vff1a;算法进止&#Vff0c;输出结果。
FI战略下的λ变换下降法运算流程如下&#Vff1a;
Step1&#Vff1a;通过特定方式生成初始可止解S&#Vff0c;解半途径数质为K&#Vff1b;
Step2&#Vff1a;途径对汇折为RS&#Vff0c;为途径对的数质&#Vff1b;
Step3&#Vff1a;令i=1&#Vff1b;
Step4&#Vff1a;通过λ变换机制变换RS中第i对途径&#Vff0c;生成S的邻域解S'&#Vff1b;
Step5&#Vff1a;计较新解S'的效应值&#Vff1b;
Step6&#Vff1a;假如&#Vff0c;令S=S'&#Vff0c;继续执止Step3&#Vff1b;否则执止Step7&#Vff1b;
Step7&#Vff1a;令i=i+1&#Vff0c;假如i≤M&#Vff0c;执止Step4&#Vff1b;否则执止Step8&#Vff1b;
Step8&#Vff1a;算法进止&#Vff0c;输出结果。
依据该算法的流程可知&#Vff0c;λ变换下降法中须要停行两条车辆途径中节点的变换收配&#Vff0c;并停行收配后的效应评估&#Vff0c;所以下面先划分真现两条途径之间的(0,1)变换、(1,1)变换、(0,2)变换、(1,2)变换和(2,2)变换的收配历程。那五种变换历程涵盖了λ变换下降法中λ为1或为2时会发作的全副变换可能性&#Vff0c;此中(0,1)、(0,2)和(1,2)变换的收配历程可以划分默示(1,0)、(2,0)和(2,1)变换的收配历程&#Vff0c;只须要将传入的两条途径先后位置交换一下便可。
那五种变换收配将运用jaZZZa类中的办法来真现&#Vff0c;办法称呼和参数划分设定为&#Vff1a;lamdaEVchange01(R1,R2,,,C,D)、lamdaEVchange11(R1,R2,,,C,D)、lamdaEVchange02(R1,R2,,,C,D)、lamdaEVchange12(R1,R2,,,C,D)和lamdaEVchange22(R1,R2,,,C,D)&#Vff0c;传入的六个参数挨次为两个变换的途径对象、客户节点的载运质、全副节点之间的老原矩阵、车辆最大载运质和车辆单次最大止驶里程。
令传入途径R1和R2的首尾均需为数字0&#Vff0c;默示途径末点和起点均为车场&#Vff0c;其余客户节点以数字码放正在那两个0之间&#Vff0c;譬喻{0,1,3,5,2,0}默示车辆从车场动身后挨次颠终客户1、3、5、2之后又返回车场&#Vff1b;途径R1和R2中客户节点数质划分为和&#Vff0c;全副节点数质划分为客户节点数质加2。
算法正在运止历程中将依据R1和R2中节点数质来选择满足途径中节点数质的条件&#Vff0c;即途径中节点数质不能少于其换出的节点数质&#Vff0c;譬喻lamdaEVchange11办法要求R1中客户节点数质不能少于1&#Vff0c;R2中客户节点数质也不能少于1个&#Vff1b;lamdaEVchange02办法要求R2中客户节点不能少于2个&#Vff0c;而R1中客户节点可以为0。
下面给出那些办法的详细真现历程。
&#Vff08;0,1&#Vff09;变换编程
真现&#Vff08;0&#Vff0c;1&#Vff09;变换历程是将R2中的客户点i转移到R1中去造成两条新途径和&#Vff0c;而后对新途径停行近似评估&#Vff0c;假如效应值为负&#Vff0c;即两条新途径对应的总老原比两条旧途径对应总老原低&#Vff0c;则再对新途径停行劣化&#Vff0c;并确定为最后的新途径。
正在&#Vff08;0&#Vff0c;1&#Vff09;变换中&#Vff0c;R2中有个客户节点&#Vff0c;R1中有个客户节点&#Vff0c;运算历程须要先预计每个换出节点i的近似效应值&#Vff0c;详细收配是保持R1和R2中各个客户节点先后顺序稳定&#Vff0c;将R2中的节点i提与出来挨次插入到R1中节点牌序之间&#Vff0c;与得R1和R2的新解&#Vff0c;而后判断新解和旧解对应目的函数的差值做为该收配的效应。以R1和R2中划分有三个节点为例&#Vff0c;图1给出了每个换出节点可以孕育发作的近似解。
(a) (b) (c) (d)
图1 &#Vff08;0&#Vff0c;1&#Vff09;变换近似预计新解生成示用意
图1中(a)为本有解R1和R2&#Vff0c;图 (b)、(c)和(d)划分为将R2中的节点4、5和6换入R1后造成的近似新解&#Vff0c;此中圆头虚线默示换入节点正在R1中的插入位置。运算历程计较那些近似新解的目的函数值&#Vff0c;同(a)的目的函数值比较&#Vff0c;记录每个近似解的效应值。
非论是BI战略还是FI战略&#Vff0c;最后都是选择能够变换收配能够孕育发作较好解的结果做为下一次迭代的解&#Vff0c;所以办法lamdaEVchange01通过输入的参数停行运算后&#Vff0c;R2中每个客户节点插入R1中的多个可止解中只糊口生涯一个最好的变换结果&#Vff0c;折乎算法流程的逻辑。图1中(b)默示节点4换入R1中可能有四个可止解&#Vff0c;只糊口生涯一个R1新途程总里程最小的解便可&#Vff0c;同时图(c)和图(d)中节点5和6划分插入R1后也各自选择一个最好的解&#Vff0c;而后再对 (b)、(c)和(d)所选的最好结果停行比较&#Vff0c;返回三者之中的最好解做为变换后的结果。
依据上述设想可得出lamdaEVchange01的伪代码如下&#Vff1a;
输入参数
获与R1和R2中的客户节点数质和
Gaps:记录R2中每个节点换入R1之后的最好效应和新途径
For k=1 to
i:R2中第k个客户
gapR2:=C(R2/i) – C(R2),R2途径中增除节点i后的效应
gapCosts: 记录i插入到R1差异位置的效应预计和新R1
for j=0 to
gapCosts[j]=
endfor
optGap =minj{gapR2+gapCosts[j]},与得最好效应和新R1
Gaps[k]=optGap,记录每个换出客户i替换收配的最好效应和新R1、新R2
endfor
&#Vff08;1,1&#Vff09;变换编程
真现&#Vff08;1&#Vff0c;1&#Vff09;变换历程是将R2中的客户点i和R1中的客户点j停行变换造成两条新途径和&#Vff0c;而后对新途径停行近似评估&#Vff0c;假如效应值为负&#Vff0c;即两条新途径对应的总老原比两条旧途径对应总老原低&#Vff0c;则再对新途径停行劣化&#Vff0c;并确定为最后的新途径。
正在&#Vff08;1&#Vff0c;1&#Vff09;变换中&#Vff0c;两条途径R1和R2中的客户节点均和都不小于1&#Vff0c;运算历程须要先预计每个替换节点对(i,j)的近似效应值。详细收配是保持R1和R2中各个客户节点先后顺序稳定&#Vff0c;将R2中的节点i提与出来挨次插入到R1中去除节点j剩余节点牌序之间&#Vff0c;那样可以与得个新的R1&#Vff0c;而后将那些新R1中效应值最低的选为最后的新R1&#Vff1b;取之类似&#Vff0c;将R1中的节点j提与出来挨次插入到R2中去除节点i剩余节点牌序之间&#Vff0c;那样可以与得个新的R2&#Vff0c;而后将那些新R2中效应值最低的选为最后的新R2。将最后与得的新R1和新R2做为两点替换的近似解。以R1和R2中划分有3个节点为例,图2给出了每个换出节点可以孕育发作的近似解示用意。
(a) (b) (c) (d)
图2 &#Vff08;1&#Vff0c;1&#Vff09;变换近似预计新解生成示用意
图2中(a)为本有解R1和R2&#Vff0c;图 (b)、(c)和(d)为变换点对划分为(2,4)、(3,4)和(2,5)时回收(1,1)收配后可能造成的近似新解。运算历程计较那些近似新解的目的函数值,同(a)的目的函数值比较&#Vff0c;记录每个近似解的效应值&#Vff0c;而后给每个变换点对糊口生涯最好的新R1和新R2。
由图2可知&#Vff0c;应付客户节点数划分为和的途径R1和R2停行(1,1)变换&#Vff0c;计较复纯度为&#Vff0c;最坏状况为
伪代码&#Vff1a;
两途径R1和R2&#Vff0c;以及相关参数
pairs:依据和造成的变换队列全布列
rows: pairs的止数&#Vff0c;即上述全布列的数质
resultSet: 两点变调换得的结果汇折&#Vff0c;蕴含新的R1和R2及其对应的效应值
for i=1:rows
nowPair: pairs[i]
out1:从R1中找出来变换的客户节点&#Vff0c;R1[nowPair[1]]
preOut1、rearOut1:R1中处于out1之前和之后的节点索引号
out2:从R2中找出来变换的客户节点,R2[nowPair[2]]
preOut2、rearOut2:R2中处于out2之前和之后的节点索引号
R10:将R1中剔除out1后剩下的途径
R20&#Vff1a;将R2中剔除out2后剩下的途径
outCost1:=dist[preOut1][rearOut1] –dist[preOut1][out1]-dist[out1][rearOut1]
outCost2:=dist[preOut2][rearOut2] –dist[preOut2][out2]-dist[out2][rearOut2]
cost1In2:将out1插入R20各个位置与得的效应值
for j=1:
cost1In2[j]=
dist[R20[j-1]][out1]+dist[out1][R20[j]]-dist[R20[j-1]][R20[j]]
end
optCost1In2:=cost1In2中的最小值
newR2:optCost1In2对应的新途径R2&#Vff1b;
cost2In1:将out2插入R10各个位置与得的效应值
for j=1:
cost2In1[j]=
dist[R10[j-1]][out2]+dist[out2][R10[j]]-dist[R10[j-1]][R10[j]]
end
optCost2In1:=cost2In1中的最小值
newR1:optCost2In1对应的新途径R1&#Vff1b;
changeCost: 两点变换的效应=outCost1+outCost2+optCost1In2+optCost2In1
resultSet+={newR1,newR2,changeCost}
endfor
optRoute1,optRoute2:从resultSet中找出最好的做为那两个新途径
&#Vff08;0,2&#Vff09;变换编程
&#Vff08;0&#Vff0c;2&#Vff09;变换历程是将第二条路经中的两个点放入到第一条途径中去&#Vff0c;查察能否会孕育发作更好的解。该历程中&#Vff0c;途径R2中客户节点数质必然不小于2&#Vff0c;而途径R1中客户节点数质可以为零&#Vff0c;也可以存正在客户节点&#Vff0c;那使得变换的位置组折变得比较复纯。
(a) (b) (c) (d)
图3 &#Vff08;0&#Vff0c;2&#Vff09;变换近似预计新解生成示用意
图3展示R2中三个节点每次换入两个节点到R1的可能状况&#Vff0c;以(b)图中节点4和5换入R1为例&#Vff0c;可以看出节点4有四个可能插入的位置&#Vff0c;节点5也有四个可能插入的位置&#Vff0c;而且当节点4和5同时插入R1本有途径中某个路段中时&#Vff0c;节点4和节点5的先后干系可以造成两种状况&#Vff0c;因而可以看出总的组折数质跟着R1中节点数质的删多而删多&#Vff0c;计较复纯度正在。
&#Vff08;1,2&#Vff09;变换编程
&#Vff08;1&#Vff0c;2&#Vff09;变换历程是将第二条路经中的两个点放入到第一条途径中去&#Vff0c;同时将第一条途径中的一个点放到第二条途径中去&#Vff0c;而后查察能否会孕育发作更好的解。该历程中&#Vff0c;途径R2中客户节点数质必然不小于2&#Vff0c;而途径R1中客户节点数质必然不小于1&#Vff0c;那变换收配的位置组折愈加复纯。
&#Vff08;2,2&#Vff09;变换编程
&#Vff08;2&#Vff0c;2&#Vff09;变换历程是将第二条路经中的两个点和第一条途径中的两个点停行变换&#Vff0c;而后查察能否会孕育发作更好的解。该历程中&#Vff0c;途径R2和R1中客户节点数质必然都不小于2。
5.5 算法实验结果对照 5.5.1 实验设想原章所形容的四种算法编写正在easyopt.jar包中的xRP类文件中&#Vff0c;各算法的详细称呼如表5.5所示。
表5.5 四种算法正在xRP类中的办法称呼
算法代号
算法称呼
办法称呼
CWS
序贯节约里程
optBySaZZZingCWSeq
CWP
并止节约里程
optBySaZZZingCWParallel
MCWS
改制序贯节约里程
optByModSaZZZingSeq
MCWP
改制并止节约里程
optByModSaZZZingParallel
Sweep
扫描算法
optBySweep
Lamda
λ变换下降法
optByLamdaEVchange
下面运用算例En22K4、En30K3、En51K5、En76K10和En101K8的数据为例&#Vff0c;测试那四大类算法的寻劣机能。算法寻劣机能次要目标是算法获与的车辆途径方案总止驶里程&#Vff0c;主要目标为算法运算光阳&#Vff0c;改制节约里程法中λ参数设定为0.3、0.6和0.9三个数值。
5.5.2 实验步调设想算法的步调如下&#Vff0c;留心运用easyopt0302及其之后的包&#Vff0c;包下载链接&#Vff1a;。
import easyoptssmon.EasyArray;
import easyopt.instances.xRPinstance;
import easyopt.ZZZrp.xRP;
import jaZZZa.util.ArrayList;
/**测试四大类CxRP的启示式算法运算机能 * */
public class TestxRPHeuristics {
public static ZZZoid main(String[] args) {
testHeuristic();
}
/**启示式算法运算机能测试主步调 * */
public static ZZZoid testHeuristic(){
double[][] results = new double[5][10];
double[][] runTimes = new double[5][10];
for(int i=0;i<5;i++){
xRPinstance instance = new xRPinstance();
if(i==0) instance.initEn22K4();
if(i==1) instance.initEn30K3();
if(i==2) instance.initEn51K5();
if(i==3) instance.initEn76K10();
if(i==4) instance.initEn101K8();
//依据算例数据&#Vff0c;生成xRP类中劣化办法所需模式的参数
int truckCap = instance.capacity;
int[] dmd = instance.dmdQty;
double[][] posXY = instance.posXY;
//运用序贯节约里程法停行运算&#Vff0c;并记录运算结果和运算光阳
double sumCost =0;
long timeStart=System.currentTimeMillis(); //get the now time (ms)
ArrayList<xRP.Route> rList = xRP.optBySaZZZingCWSeq(truckCap, dmd, posXY);
for(xRP.Route r:rList){ sumCost+=r.sumCost; }
results[i][0] = sumCost;
long timeEnd=System.currentTimeMillis(); //get the now time (ms)
runTimes[i][0] = (timeEnd - timeStart);//the running time(ms)
//运用并止节约里程法停行运算&#Vff0c;并记录运算结果和运算光阳
sumCost =0;
timeStart = timeEnd;
ArrayList<xRP.Route> rList2 = xRP.optBySaZZZingCWParallel(truckCap, dmd, posXY);
for(xRP.Route r:rList2){ sumCost+=r.sumCost; }
results[i][1] = sumCost;
timeEnd=System.currentTimeMillis(); //get the now time (ms)
runTimes[i][1] = (timeEnd - timeStart);//the running time(ms)
//运用sweep算法停行运算&#Vff0c;并记录运算结果和运算光阳
sumCost = 0;
timeStart = timeEnd;
ArrayList<xRP.Route> rList0 = xRP.optBySweep(truckCap, 0, dmd, posXY);
for(xRP.Route r:rList0){ sumCost+=r.sumCost; }
results[i][2] = sumCost;
timeEnd=System.currentTimeMillis(); //get the now time (ms)
runTimes[i][2] = (timeEnd - timeStart);//the running time(ms)
//运用λ变换算法停行运算&#Vff0c;并记录运算结果和运算光阳
sumCost = 0;
timeStart = timeEnd;
ArrayList<xRP.Route> rListLamda = xRP.optByLamdaEVchange(truckCap, 0, dmd, posXY,1);
for(xRP.Route r:rListLamda){ sumCost+=r.sumCost; }
results[i][3] = sumCost;
timeEnd=System.currentTimeMillis(); //get the now time (ms)
runTimes[i][3] = (timeEnd - timeStart);//the running time(ms)
//运用差异λ【留心该参数同λ变换法中参数的差异】参数下的改制节约里程法停行运算&#Vff0c;并记录运算结果和运算光阳
for(int j=0;j<3;j++){
sumCost =0;
double lamda=0.3+0.3*j;
timeStart = timeEnd;
rList = xRP.optByModSaZZZingSeq(truckCap, dmd, posXY,lamda);
for(xRP.Route r:rList){ sumCost+=r.sumCost; }
results[i][4 + 2*j ] = sumCost;
timeEnd=System.currentTimeMillis(); //get the now time (ms)
runTimes[i][4 + 2*j] = (timeEnd - timeStart);//the running time(ms)
sumCost =0;
timeStart = timeEnd;
rList2 = xRP.optByModSaZZZingParallel(truckCap, dmd, posXY,lamda);
for(xRP.Route r:rList2){ sumCost+=r.sumCost; }
results[i][4 + 2*j + 1 ] = sumCost;
timeEnd=System.currentTimeMillis(); //get the now time (ms)
runTimes[i][4 + 2*j + 1] = (timeEnd - timeStart);//the running time(ms)
}
}
System.out.println("----------sum distances-----------");
EasyArray.printArray(results,0);
System.out.println("----------running times(s)-----------");
EasyArray.printArray(runTimes,0);
}
}
执止该办法后与得的输出如下&#Vff1a;
----------sum distances-----------
458.0 387.0 397.0 383.0 427.0 444.0 448.0 399.0 458.0 387.0 ;
817.0 586.0 515.0 562.0 900.0 575.0 783.0 594.0 812.0 590.0 ;
734.0 591.0 544.0 579.0 833.0 568.0 720.0 579.0 697.0 578.0 ;
1061.0 907.0 899.0 880.0 1276.0 953.0 1078.0 897.0 1030.0 903.0 ;
1197.0 999.0 854.0 996.0 1555.0 936.0 1313.0 940.0 1294.0 960.0 ;
----------running times(s)-----------
7.0 0.0 182.0 6.0 1.0 0.0 1.0 0.0 1.0 1.0 ;
2.0 1.0 115.0 15.0 2.0 1.0 2.0 0.0 2.0 0.0 ;
2.0 0.0 269.0 5.0 4.0 1.0 5.0 1.0 2.0 1.0 ;
10.0 2.0 761.0 23.0 8.0 2.0 5.0 2.0 5.0 1.0 ;
6.0 1.0 721.0 15.0 2.0 2.0 4.0 1.0 3.0 2.0 ;
依据上述实验输出的结果&#Vff0c;整理成表格模式列于表5.6和表5.7。
表5.7 算法最劣解总里程对照表
算例
CWS
CWP
SWEEP
LAMDA
λ=0.3
λ=0.6
λ=0.9
MCWS
MCWP
MCWS
MCWP
MCWS
MCWP
En22K4
458
387
397
383
427
444
448
399
458
387
En30K3
817
586
515
562
900
575
783
594
812
590
En51K5
734
591
544
579
833
568
720
579
697
578
En76K10
1061
907
899
880
1276
953
1078
897
1030
903
En101K8
1197
999
854
996
1555
936
1313
940
1294
960
从表5.7运算结果的总里程来阐明可以得出如下结论&#Vff1a;
&#Vff08;1&#Vff09;最劣解仅出如今Sweep和Lamda两种算法中&#Vff0c;正在五种算例数据中&#Vff0c;Sweep算法与得了3次最劣解&#Vff0c;Lamda变换法与得2次最劣解。
&#Vff08;2&#Vff09;两两算法对照时&#Vff0c;CWP劣于CWS&#Vff1b;MCWP正常状况也劣于MCWS&#Vff0c;除了正在λ为0.3时求解En22K4&#Vff1b;Sweep劣于CWS和MCWS&#Vff1b;Sweep正常状况下也劣于CWP和MCWP&#Vff1b;Lamda算法劣于CWP、CWS和MCWS&#Vff0c;有时劣于MCWP。
从算法寻劣机能看&#Vff0c;针对详细问题时&#Vff0c;可以给取Sweep、Lamda和并止运算的改制节约里程法来停行求解&#Vff0c;而后择劣选用。
表5.8 算法求解运算光阳对照表&#Vff08;ms&#Vff09;
算例
CWS
CWP
SWEEP
LAMDA
λ=0.3
λ=0.6
λ=0.9
MCWS
MCWP
MCWS
MCWP
MCWS
MCWP
En22K4
7
0
182
6
1
0
1
0
1
1
En30K3
2
1
115
15
2
1
2
0
2
0
En51K5
2
0
269
5
4
1
5
1
2
1
En76K10
10
2
761
23
8
2
5
2
5
1
En101K8
6
1
721
15
2
2
4
1
3
2
从表5.8的运算光阳可以看出Sweep算法的运算光阳出格长&#Vff0c;远比其余算法运算光阳要长。因而正在问题范围出格大时&#Vff0c;须要依据车辆途径方案总里程和运算光阳两者之间来衡量以选择适宜的算法。
参考文献T.J. Gaskell. Bases for ZZZehicle fleet scheduling. Operational Research Quarterly, 1967(18):281-295
P. Yellow. A computational modification to the saZZZings method of ZZZehicle scheduling. Operational Research Quarterly, 1970(21):281-283.
Ibrahim Hassan Osman. Metastrategy simulated annealing and tabu search algorithms for the ZZZehicle routing problem. 1993(41):421-451
easyopt.ZZZrp.xRP类中四个办法的源代码hts://download.csdn.net/download/jiannywang/87707696
