物流设计大赛算法介绍

地区坐标的调取

利用python调取高德API实现配送点的名称与该点经纬度坐标的匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import requests
import json
import xlrd
import xlwt

work_book = xlrd.open_workbook('/Users/xjh/Desktop/物流设计大赛/中国外运杯案例附件/附件8:两日订单.xlsx')
# 获取第一个工作表
table = work_book.sheet_by_index(0)
# 获取行数
nrows = table.nrows
# 获取列数
ncols = table.ncols
# 定义excel_list
excel_list = []
for row in range(0, nrows):
# 获取单元格数据
cell_value1 = table.cell(row, 4).value
# 把数据追加到excel_list中
excel_list.append(cell_value1)

#调用高德api转化经纬度
def coords(city):
# 输入API问号前固定不变的部分
url = 'https://restapi.amap.com/v3/geocode/geo'
# 将两个参数放入字典
params = { 'key': '65ff66fb8970e85b077efe406f11be48',
'address': city }
res = requests.get(url, params)
jd = json.loads(res.text)
return jd['geocodes'][0]['location']

outlist = []
coordinate_lis = []
for i in range(1,len(excel_list)):
loca = coords(excel_list[i])
outlist.append(loca)
tmp_lis = []
tmp_lis.append(float(loca.split(',')[0]))
tmp_lis.append(float(loca.split(',')[1]))
tmp_dir = {}
tmp_dir["coordinate"] = tmp_lis
coordinate_lis.append(tmp_dir)
print(outlist)
print(coordinate_lis)
bJson = json.dumps(coordinate_lis, ensure_ascii=False)
f = open('/Users/xjh/Desktop/物流设计大赛/new_json.json', 'w')
f.write(bJson)

data_w=xlwt.Workbook(encoding = 'utf-8')
table_w=data_w.add_sheet('data')
savalist = []
ite = 0
print(outlist)
for item in range(len(outlist)):
table_w.write(ite, 0, excel_list[item+1])
table_w.write(ite,1,outlist[item])
ite += 1
data_w.save('/Users/xjh/Desktop/物流设计大赛/coordinates.xlsx')

环线分区

​ 为了摆脱摆脱车辆配载时的车型选择与环线限制之间的冲突,利用其强大的数学计算库,空间数据计算的函数库AMap.GeometryUtil找到配送点与环线的分布关系——配送点是否在环线多边形范围内,实现配送点环线分区的目标。环线分区

​ 对本案例所提供的数据集合——北京区域内的配送点数据集进行名称坐标匹配后对其进行环线分区操作,其中不同环线分区范围内采用不同的 marker 进行标记,标记点 0 是提货地,即(北京市通州区通州区招商局物流集团)。分区结果可视化

遗传算法

编码

在使用GA求解TSP问题时,我们可以简单地采用整数编码的形式对染色体进行编码,比如配送点的个数为5,那么一个可行的染色体表达为12345。比如说需要服务的顾客数目为5,而最多允许使用3辆车来服务这些顾客,那么一种可行的染色体表达为1263475,那么这个1263475究竟代表什么意思呢? 1263475中的6和7代表配送中心,6和7将顾客12345划分为3段,划分为3条路径。(0代表配送中心)

第1条路径为0-1-2-0
第2条路径为0-3-4-0
第3条路径为0-5-0

适应度函数

当然采用上述编码方式不能保证解码的各条配送路径都满足载重量约束和时间窗约束,所以为了能够简单解决违反约束这一问题,我们使用惩罚函数的办法来进行求解。
具体计算公式如下:

$$f(x)=c(s)+aq(s)+\beta w(s)$$

$c(s)$表示车辆总行驶距离,$q(s)$表示各条路径违反的容量约束之和,$w(s)$表示所有配送点违反的时间窗约束之和。

$$w(s)=\sum_{i}^n{(a_i+li),0}$$

$a_i$表示车辆到达配送点i的时间,$l_i$表示顾客i的右时间窗因为目标函数越小越好,而在选择操作时需要将适应度值大的个体选择出来,这里我们将适应度函数设为惩罚函数的倒数,即为1/f(s)。

构造初始解

构造的初始解并不一定能够满足载重量约束和时间窗约束,但是我们所构造的初始解能在一定程度上降低GA的搜索难度,假设配送点数目为n。
STEP1: 从所有配送点中随机选择一个配送点j∈……n.
STEP2: 初始化车辆使用数目k←1
STEP3: 生成一个遍历顾客的序列Seq←[j,j+1…..n,1,….j-1]
STEP4: 遍历序号为i,一直遍历到n即生成初始解。按遍历照序Seq遍历配送点Seg(i),将配送点Seq(i)添加到第k条路径中,然后分2种情况:

  • 如果第k条路径满足载重量约束,那么这里又分为3种情况:
  1. 如果当前路径为空,直接将配送点Seq(i)添加到路径中;.
  2. 如果当前路径只有一个配送点,再添加新配送点Seg(i)时,需要根据左时间窗大小进行添加;
  3. 如果当前路径访问的配送点数目Ir大于1,则需要遍历这lr-1 对连续的配送点的中间插入位置,然后确认顾客Seg(i)的左时间窗能否在中间插入位置前后的配送点的左时间窗之间。如果存在这样的中间插入位置,则将配送点Seq(i)插入到该位置。如果不存在这样的中间插入位置,则将配送点seq(i)插到当前路径末尾。
  • 如果第k条路径不满足载重量约束,则先储存第k辆车在访问顾客Seg(i)之前所访问的配送点,然后更新k←k+1。

构造完初始解之后,这就是一个完整的配送方案,例如分组结果为:135,84,267,初始染色体:


其中0表示中国外运公司,01350表示某车辆中心出发,经过1、3、5站点卸货后返回中心,另一辆车同样从中心出发,经过8,4站点卸货后返回中心,其它的依次类推,这样就构造成功了初始解。

染色体交叉

单点交叉:

随机产生$(1,SL)$区间的两个正整数$n1$和$n2$,要求$n1$和$n2$位置上的基因(站点)不能同时为“虚拟站点”或“中国外运公司”,对于同一分组(路径),直接交换$n1$和$n2$所对应位置的基因;对于不同分组$n1$和$n2$,产生之$(0,1)$间的随机数$p$,如果$p(n)$大于$p$,交换$n1$和$n2$位置的基因,否则不交换,如下所示。

块交叉:

类似于点交叉,产生随机数,确定同一(或不同路径)的两个区间,同一路径内区间块直接交叉;不同路径内的区间块,产生$(0,1)$之间的随机数$p$,如果两个区间块内各基因交叉概率均大于$p$,两个区间块实施交叉。

变异操作

变异操作比较简洁,就是先随机生成两个位置,然后将这两个位置上的基因进行交换。比如说,有如下个体:
父代: 12345678.
这时随机选择两个变异位置a和b,比如说a=3,b=6,那么交换后的个体为:
子代: 264537810

染色体在经过基因交叉处理后,得到若干组染色体,染色体中的“0”代表中国外运公司,连续两个“0”之间的基因排列代表一子路径,即某车辆行程安排,检测是指考虑车辆的速度和载重是否满足行程安排的时间窗和车辆配载约束,如果某染色体所有子路满足约束条件,那么该染色体为“可行解”,否则为“不可行解”,丢弃;通过计算各可行解的满意度对其进行评价。

matlab实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
% Summary:
% 1. Each salesman starts at the first point, and ends at the last
% point, but travels to a unique set of cities in between (none of
% them close their loops by returning to their starting points)
% 2. Except for the first and last, each city is visited by exactly one salesman
%
% Note: The Fixed Start is taken to be the first XY point and the Fixed End
% is taken to be the last XY point
% Input:
% XY %送货点坐标 N by 2 矩阵(用于画图)
% DMAT %距离矩阵 N by N
% NSALESMEN 有多少个nSalesmen
% MINTOUR 每一个nSalesmen必须 travel 大于等 MINTOUR 个送货点
% POPSIZE 每一次迭代的种群个数,必须为8的倍数,因为新生代的产生是由 8 个
% 老家伙产生 8 个新家伙
% NUMITER 迭代次数,这个代码是将这些次数都迭代完的。
% SHOWPROG 画图,如果等于1,就将每一次迭代路径画出来
% SHOWRESULT 画图,如果等于1,将最后的结果,城市坐标,路径和历史总长度
%
% Output:
% OPTROUTE (integer array) 输出最佳路径
% OPTBREAK (integer array) 输出中断点
% MINDIST (scalar float) 总距离
%
%


function varargout = MTSP_GA_Balance(xy,dmat,nSalesmen,minTour,popSize,numIter,showProg,showResult)
if nargin < 8
disp("缺失参数");
end

% Verify Inputs 验证输入是否可行,验证原理为送货点个数 N 是否和 距离矩阵的 size相等
[N,dims] = size(xy);
[nr,nc] = size(dmat);
if N ~= nr || N ~= nc
error('Invalid XY or DMAT inputs!')
end
n = N-1; %除去了起始点

% Sanity Checks 验证输入:可以不看
nSalesmen = max(1,min(n,round(real(nSalesmen(1)))));
%验证输入的送货车辆数是不是大于1,并且是整数,否则帮你四舍五入改了
minTour = max(1,min(floor(n/nSalesmen),round(real(minTour(1)))));
%验证输入的minTour是不是大于1,并且是整数,否则帮你四舍五入改了
popSize = max(8,8*ceil(popSize(1)/8));
%验证输入的个体数是否为8的整数(因为后面的分组8个为一组),否则帮你用ceil函数改了
numIter = max(1,round(real(numIter(1))));
%验证输入的迭代次数是否大于1,否则帮改了
showProg = logical(showProg(1));
%验证是否为1或0,下同
showResult = logical(showResult(1));


% Initializations for Route Break Point Selection
nBreaks = nSalesmen-1; %设置中断点个数。
dof = n - minTour*nSalesmen; % degrees of freedom
addto = ones(1,dof+1);
for k = 2:nBreaks
addto = cumsum(addto);
end
cumProb = cumsum(addto)/sum(addto);


% Initialize the Populations
popRoute = zeros(popSize,n); % population of routes,popRoute 为所有个体的路径基因型
popBreak = zeros(popSize,nBreaks); % population of breaks
for k = 1:popSize
popRoute(k,:) = randperm(n)+1; %随机产生所有个体的路径基因型,下同。
popBreak(k,:) = rand_breaks(); %rand_breaks()为产生中断点的代码,在下面呢。
end


%画图时,将每一个货运车走的路用不用颜色标出来。
pclr = ~get(0,'DefaultAxesColor');
clr = [1 0 0; 0 0 1;1 0.5 0; 0.67 0 1; 0 1 0];
if nSalesmen > 5
clr = hsv(nSalesmen);
end
%% GA with Balance
globalMin = Inf; %全局标准。设为无穷大。
globalBalance = Inf; %全局均衡度
globalDist = Inf; %全局最优路长
bestLength = zeros(1,nSalesmen);%全局分段路长
totalDist = zeros(1,popSize); %初始化总距离,是一个行向量,每一个个体对一应一个总距离
balance = zeros(1,popSize); %初始化均衡值,是一个行向量,每一个个体对一应一个均衡值
distBalance = zeros(1,popSize); %评价标准

History = zeros(popSize,nSalesmen); %储存一个popsize里面的分段路径长度
distHistory = zeros(1,numIter); %历史距离,用于比较最好的距离,每一次迭代,都产生一最好距离作为历史距离存起来。
dbHistory = zeros(1,numIter); %评价指标最好历史

tmpPopRoute = zeros(8,n);
%暂时变量,用完就丢。用于产生新个体的,(路径的基因型)
tmpPopBreak = zeros(8,nBreaks);
%同上,用于产生新的中断点的基因型
newPopRoute = zeros(popSize,n);
%新生代的路径基因型
newPopBreak = zeros(popSize,nBreaks);
%新生代的断点基因型

if showProg
pfig = figure('Name','MTSPOF_GA | Current Best Solution','Numbertitle','off');
end
%画图:初始点

for iter = 1:numIter
% Evaluate Members of the Population
dhistory = zeros(1,nSalesmen);
for p = 1:popSize
d = 0;
pRoute = popRoute(p,:);
%将相应的个体的路径基因型取出
pBreak = popBreak(p,:);
%将相应的个体的中断点基因型取出
rng = [[1 pBreak+1];[pBreak n]]';
%计算每个货运车的距离之用
%下面的迭代用于计算每个个体的对应的所有货运车的总距离

max_d = -1;
for s = 1:nSalesmen
rightnow_d = 0;
rightnow_d = rightnow_d + dmat(1,pRoute(rng(s,1))); % 加上从出发点到下一个城市的距离
for k = rng(s,1):rng(s,2)-1 %加上路径中的距离
rightnow_d = rightnow_d + dmat(pRoute(k),pRoute(k+1));
end
rightnow_d = rightnow_d + dmat(pRoute(rng(s,2)),1); % 加上从城市回到起点的距离

dhistory(s) = rightnow_d;
d = d + rightnow_d;
if rightnow_d > max_d
max_d = rightnow_d;
end
end

minus_d = 0;
for i = 1:nSalesmen-1
for j = 1:nSalesmen
tmp = abs(dhistory(i)-dhistory(j));
if tmp > minus_d
minus_d = tmp;
end
end
end
totalDist(p) = d;
balance(p) = minus_d/max_d;
distBalance(p)= 0.5*d + 0.5*nSalesmen*(max_d);
History(p,:) = dhistory;
end

% Find the Best Route in the Population
[min_judge,index] = min(distBalance);
min_dist = totalDist(index);
min_bala = balance(index);
tmpdist = History(index,:);

distHistory(iter) = min_dist;
dbHistory(iter) = min_judge;
if min_judge < globalMin
%若本次迭代时的最佳标准小于历史全局最小值。
%就把他画在图上,并记录一共画了几次。
globalMin = min_judge;
globalBalance = min_bala;
globalDist = min_dist;
bestLength = tmpdist;
opt_rte = popRoute(index,:);
opt_brk = popBreak(index,:);
rng = [[1 opt_brk+1];[opt_brk n]]';
if showProg
% Plot the Best Route
figure(pfig);
for s = 1:nSalesmen
rte = [1 opt_rte(rng(s,1):rng(s,2)) 1];
%下面用于三维画图,如果输入的坐标时三维的,那么就启动如下代码用以三维绘图
if dims == 3, plot3(xy(rte,1),xy(rte,2),xy(rte,3),'.-','Color',clr(s,:));
else plot(xy(rte,1),xy(rte,2),'.-','Color',clr(s,:)); end
title(sprintf('Total Distance = %1.4f, Iteration = %d',globalDist,iter));
hold on
end
if dims == 3
plot3(xy(1,1),xy(1,2),xy(1,3),'ko');
else
plot(xy(1,1),xy(1,2),'ko');
end
hold off
end
end

%% 子代个体的产生过程
% 产生一个随机序列,用于挑选随机的8个父代产生子代
% 8个家伙来交配产生子代,(其实也不算交配啦!)
randomOrder = randperm(popSize);
for p = 8:8:popSize
rtes = popRoute(randomOrder(p-7:p),:);
brks = popBreak(randomOrder(p-7:p),:);
%随机挑选的8个父代
dists = totalDist(randomOrder(p-7:p));
[ignore,idx] = min(dists);
%从这8个父代中挑选出最佳父代,用于产生8个子代。
bestOf8Route = rtes(idx,:);
bestOf8Break = brks(idx,:);
routeInsertionPoints = sort(ceil(n*rand(1,2)));
%从中挑选出基因序列的2个位置
%这两个位置用来从父代中产生新的基因新的
I = routeInsertionPoints(1);
J = routeInsertionPoints(2);
for k = 1:8 % Generate New Solutions
tmpPopRoute(k,:) = bestOf8Route;
tmpPopBreak(k,:) = bestOf8Break;
switch k
case 2 % Flip
%将最佳父代的基因型从上面两个位置中间的片段反转,产生一个子代。
tmpPopRoute(k,I:J) = tmpPopRoute(k,J:-1:I);
case 3 % Swap
%交换这两个片段的基因,产生新子代。
tmpPopRoute(k,[I J]) = tmpPopRoute(k,[J I]);
case 4 % Slide
% 自己看吧,描述不出
tmpPopRoute(k,I:J) = tmpPopRoute(k,[I+1:J I]);
%上面都是调整路径基因型的
%下面用于调整中断点基因型,过程差不多,大家可以自己看的
case 5 % Modify Breaks
%随机产生,跟最佳父代没关系的一代。
tmpPopBreak(k,:) = rand_breaks();
case 6 % Flip, Modify Breaks
tmpPopRoute(k,I:J) = tmpPopRoute(k,J:-1:I);
tmpPopBreak(k,:) = rand_breaks();
case 7 % Swap, Modify Breaks
tmpPopRoute(k,[I J]) = tmpPopRoute(k,[J I]);
tmpPopBreak(k,:) = rand_breaks();
case 8 % Slide, Modify Breaks
tmpPopRoute(k,I:J) = tmpPopRoute(k,[I+1:J I]);
tmpPopBreak(k,:) = rand_breaks();
otherwise % Do Nothing
end
end
newPopRoute(p-7:p,:) = tmpPopRoute;
newPopBreak(p-7:p,:) = tmpPopBreak;
end
popRoute = newPopRoute;
popBreak = newPopBreak;
end

%% 用于画出统计结果图
if showResult
% Plots
figure('Name','MTSP_GA_BALANCE | Results','Numbertitle','off');
plot(dbHistory,'b','LineWidth',1.8,'color',[0.255 0.878 0.816]);
title('Best Solution History');
set(gca,'XLim',[0 numIter+1],'YLim',[0 1.1*max([1 dbHistory])]);
end

%% 返回结果
if nargout
varargout{1} = opt_rte; %参数1 最佳个体的路径基因型
varargout{2} = opt_brk; %参数2 最佳个体的中断点基因型
varargout{3} = globalDist; %参数3 最佳个体的总距离
varargout{4} = bestLength; %参数4 每段路径的长度
end

%% 产生终端点代码(随机生成每一个送货车至少走个3个城市。
function breaks = rand_breaks()
if minTour == 1 % No Constraints on Breaks
tmpBreaks = randperm(n-1);
breaks = sort(tmpBreaks(1:nBreaks));
else % Force Breaks to be at Least the Minimum Tour Length
num_adjust = find(rand < cumProb,1)-1;
spaces = ceil(nBreaks*rand(1,num_adjust));
adjust = zeros(1,nBreaks);
for kk = 1:nBreaks
adjust(kk) = sum(spaces == kk);
end
breaks = minTour*(1:nBreaks) + cumsum(adjust);
end
end
%% 部分数据输出
disp("综合标准:"+globalMin);
disp("均衡度:"+globalBalance);
end %结束总function

规划结果


规划路径展示:

遗传算法实现配载与路径的规划后,调用高德 API 的 AMap.TruckDriving 函数,设置货车的车型大小,高度,宽度,载重,车牌省份等限制元素来对该配送货车的路径进行可视化展示。并设置显示实时路况信息,显示绿色代表畅通,黄色代表轻微拥堵,红色代表比较拥堵,灰色表示无路况信息。路径可视化

改进算法,发展方向

碳测算模型的加入

在低碳经济下的绿色路径优化模型,还有一定的欠缺之处。但是只考虑了路径长度这一因素进行分析,在未来我们会提出基于碳排放量的关键因素模型,会多方面考虑,其中不乏包括已有的,还会包括燃油类型,燃油因子,提出$CO_2$排放量测算模型,并将其作为影响因子加入到我们已经设计的遗传算法的适应度函数当中。进一步优化低碳经济视角下的绿色路径优化模型。

宏观方面的测算可以采用基于燃料消耗的统计数据计算$CO_2$排放,计算公式可以采用下面的形式:

$$E=\sum_{i}^{}{F_i\times V_i}$$

式中:
E——道路交通$CO_2$排放量;
$F_i$——不同燃料类型的排放因子;
$V_i$——不同燃料类型消耗量;
$i$——燃料类型(汽油、柴油、天然气、电力等) ;

路径优化与装载相互制约

装箱配载和车辆路径问题都属于NP难题,为了实现两者的综合最优,会采用两种启发式算法组成的混合算法进行求解,以避免单一算法的局限性,相互制约,提高解的质量和求解速度。求解路径问题采用元启发式算法:在进行货物装箱配载时,通常使用启发式算法进行求解,同时调用装箱检验算法验证是否可以成功配载。常见的装箱检验算法有:最深位置填充算法、最大接触面积填充算法、最大齐平装载算法、基于“块”的装箱算法等。

本文标题:物流设计大赛算法介绍

文章作者:北徯。

发布时间:2020年11月21日 - 00:00:00

最后更新:2020年11月21日 - 22:13:25

原始链接:https://www.xiangjunhong.com/posts/da7fb8ae.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------------本文结束 感谢您的阅读-------------------