遗传算法优化最大化效应的某些需求点可不配送的vrptw问题

本文主要是介绍遗传算法优化最大化效应的某些需求点可不配送的vrptw问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

标题:遗传算法优化最大化效应的某些需求点可不配送的vrptw问题

摘要:

在可不配送的车辆路径配送问题(VRPTW)中,我们面临着优化路径规划以最大化效用的挑战。本文提出了一种基于遗传算法的方法,旨在解决具有硬时间窗约束的可不配送VRPTW问题。该方法通过多个遗传算法操作符,如选择、交叉和变异,逐代优化车辆的路径规划,以实现效用的最大化。

引言

可不配送的VRPTW问题是一种经典的组合优化问题,它要求在考虑车辆容量限制和时间窗约束的情况下,将货物从中心仓库配送到多个客户地点。然而,在实际应用中,某些客户可能不愿意接受配送,因此我们需要优化路径规划以最大化效用,同时满足硬时间窗约束。

方法

本文提出的方法基于遗传算法,它是一种启发式算法,通过模拟生物进化过程来求解优化问题。遗传算法操作符包括选择、交叉和变异。

2.1 个体表示

每个个体都表示一个车辆路径规划方案,其中包括从中心仓库出发,经过一系列客户地点,最后返回仓库的路径。

2.2 适应度函数

适应度函数用于评估每个个体的优劣程度。在这里,我们将效用最大化作为目标函数。效用的计算可以根据具体问题进行定义,例如货物价值的总和或客户满意度的加权和。

2.3 选择操作

选择操作用于根据适应度函数的结果选择优秀的个体。在本方法中,我们采用轮盘赌选择策略,根据个体适应度与总适应度的比例进行选择。

2.4 交叉操作

交叉操作用于生成新的个体。在本方法中,我们采用部分映射交叉(PMX)算子,将两个个体的染色体部分交换,以产生具有新路径规划的个体。

2.5 变异操作

变异操作用于引入新的基因组合。在本方法中,我们采用交换变异算子,随机选择两个客户地点,并交换它们在路径中的位置。

实验与结果

我们使用一组模拟数据对提出的方法进行实验。实验结果表明,遗传算法能够有效地优化可不配送的VRPTW问题中的效用最大化。通过多轮迭代,算法逐渐收敛于较优解。

主程序如下:

数据如下:

需求地序号

x坐标(千米)

y坐标(千米)

需求量

时间窗开始

时间窗结束

利润

缺货成本

0

125

85

0

6

12

0

0

1

185

35

6

6

12

100

200

2

153

165

9

6

12

100

200

3

38

107

10

6

12

100

200

4

0

0

4

6

12

100

200

5

8

11

3

6

12

100

200

6

87

85

2

6

12

100

200

7

68

160

5

6

12

100

200

8

118

197

8

6

12

100

200

9

65

10

2

6

12

100

200

10

170

120

2

6

12

100

200

11

190

80

7

6

12

100

200

12

130

40

9

6

12

100

200

13

110

121

9

6

12

100

200

14

188

151

3

6

12

100

200

15

107

75

1

6

12

100

200

16

137

51

7

6

12

100

200

17

149

27

4

6

12

100

200

18

19

86

7

6

12

100

200

19

97

149

4

6

12

100

200

20

131

157

5

6

12

100

200

程序结果如下:

程序运行时间(s)

runtime201 =

                 63.243826

遗传算法优化得到的最优目标函数

ans =

          6655.92002859396

遗传算法优化得到的最优染色体

bestChrom =

  1 至 28 列

     0     1     1     0     1     1     1     1     1     1     1     1     1     1     1     1     1     1     1     1     7     8    20     5     2    14    10    11

  29 至 40 列

    17    12    15     4     1     9    16     3    18     6    13    19

显示各个路径(遗传算法)

第1辆车的路径

route1 =

     0     7     8    20     0

loadline =

     0     0    18

    18    18    13

    13    13     5

     5     5     0

     0     0     0

运行时间表

outcell01 =

    '路径点'    '到达时间'             '开始服务时间'          '结束时间'        

    [    0]    [               6]    [               6]    [               6]

    [    7]    [7.88403821617291]    [7.88403821617291]    [7.96737154950624]

    [    8]    [9.21139727271296]    [9.21139727271296]    [9.34473060604629]

    [   20]    [10.1859202398388]    [10.1859202398388]    [10.2692535731722]

    [    0]    [11.7142449226272]    [11.7142449226272]    [11.7142449226272]

第2辆车的路径

route1 =

     0     5     0

loadline =

     0     0     3

     3     3     0

     0     0     0

运行时间表

outcell01 =

    '路径点'    '到达时间'             '开始服务时间'          '结束时间'        

    [    0]    [               6]    [               6]    [               6]

    [    5]    [8.76875423250241]    [8.76875423250241]    [8.81875423250241]

    [    0]    [11.5875084650048]    [11.5875084650048]    [11.5875084650048]

第3辆车的路径

route1 =

     0     2    14    10     0

loadline =

     0     0    14

    14    14     5

     5     5     2

     2     2     0

     0     0     0

运行时间表

outcell01 =

    '路径点'    '到达时间'             '开始服务时间'          '结束时间'        

    [    0]    [               6]    [               6]    [               6]

    [    2]    [7.69516960803337]    [7.69516960803337]    [7.84516960803337]

    [   14]    [ 8.5990926810322]    [ 8.5990926810322]    [ 8.6490926810322]

    [   10]    [ 9.3660306141896]    [ 9.3660306141896]    [9.39936394752293]

    [    0]    [10.5395393726221]    [10.5395393726221]    [10.5395393726221]

第4辆车的路径

route1 =

     0    11    17    12     0

loadline =

     0     0    20

    20    20    13

    13    13     9

     9     9     0

     0     0     0

运行时间表

outcell01 =

    '路径点'    '到达时间'             '开始服务时间'          '结束时间'        

    [    0]    [               6]    [               6]    [               6]

    [   11]    [7.30384048104053]    [7.30384048104053]    [ 7.4205071477072]

    [   17]    [8.76065639312727]    [8.76065639312727]    [8.82732305979394]

    [   12]    [9.28775763712279]    [9.28775763712279]    [9.43775763712279]

    [    0]    [10.3432961509365]    [10.3432961509365]    [10.3432961509365]

第5辆车的路径

route1 =

     0    15     9    16     0

loadline =

     0     0    10

    10    10     9

     9     9     7

     7     7     0

     0     0     0

运行时间表

outcell01 =

    '路径点'    '到达时间'             '开始服务时间'          '结束时间'        

    [    0]    [               6]    [               6]    [               6]

    [   15]    [6.41182520563948]    [6.41182520563948]    [6.42849187230615]

    [    9]    [7.97626446542181]    [7.97626446542181]    [8.00959779875515]

    [   16]    [9.66670370967334]    [9.66670370967334]    [   9.78337037634]

    [    0]    [10.5044806314328]    [10.5044806314328]    [10.5044806314328]

第6辆车的路径

route1 =

     0     3    18     6     0

loadline =

     0     0    19

    19    19     9

     9     9     2

     2     2     0

     0     0     0

运行时间表

outcell01 =

    '路径点'    '到达时间'             '开始服务时间'          '结束时间'        

    [    0]    [               6]    [               6]    [               6]

    [    3]    [7.79477018027379]    [7.79477018027379]    [7.96143684694045]

    [   18]    [8.52782893728071]    [8.52782893728071]    [8.64449560394737]

    [    6]    [10.0046426548209]    [10.0046426548209]    [10.0379759881543]

    [    0]    [10.7979759881543]    [10.7979759881543]    [10.7979759881543]

第7辆车的路径

route1 =

     0    13    19     0

loadline =

     0     0    13

    13    13     4

     4     4     0

     0     0     0

运行时间表

outcell01 =

    '路径点'    '到达时间'             '开始服务时间'          '结束时间'        

    [    0]    [               6]    [               6]    [               6]

    [   13]    [            6.78]    [            6.78]    [            6.93]

    [   19]    [7.54741396161733]    [7.54741396161733]    [7.61408062828399]

    [    0]    [9.01122056400983]    [9.01122056400983]    [9.01122056400983]

punish_early =

     0

punish_late =

     0

outcell =

    '节点编号'    '达到时间'             '离开时间'        

    [      1]    [               0]    [               0]

    [      2]    [7.69516960803337]    [7.84516960803337]

    [      3]    [7.79477018027379]    [7.96143684694045]

    [      4]    [               0]    [               0]

    [      5]    [8.76875423250241]    [8.81875423250241]

    [      6]    [10.0046426548209]    [10.0379759881543]

    [      7]    [7.88403821617291]    [7.96737154950624]

    [      8]    [9.21139727271296]    [9.34473060604629]

    [      9]    [7.97626446542181]    [8.00959779875515]

    [     10]    [ 9.3660306141896]    [9.39936394752293]

    [     11]    [7.30384048104053]    [ 7.4205071477072]

    [     12]    [9.28775763712279]    [9.43775763712279]

    [     13]    [            6.78]    [            6.93]

    [     14]    [ 8.5990926810322]    [ 8.6490926810322]

    [     15]    [6.41182520563948]    [6.42849187230615]

    [     16]    [9.66670370967334]    [   9.78337037634]

    [     17]    [8.76065639312727]    [8.82732305979394]

    [     18]    [8.52782893728071]    [8.64449560394737]

    [     19]    [7.54741396161733]    [7.61408062828399]

    [     20]    [10.1859202398388]    [10.2692535731722]

>>

结论

本文提出了一种基于遗传算法的方法,用于解决具有硬时间窗约束的可不配送VRPTW问题。实验结果表明,该方法能够有效地优化路径规划,从而达到效用的最大化。未来的研究可以探索其他启发式算法或改进遗传算法的操作符,以进一步提高问题求解效果。

参考文献:

[1] Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.

[2] Braysy, O., & Gendreau, M. (2005). Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation Science, 39(1), 104-118.

程序运行时间(s)

runtime201 =

          36.6331173795092

遗传算法优化得到的最优目标函数

ans =

          4561.10885596154

遗传算法优化得到的最优染色体

bestChrom =

  1 至 25 列

     0     1     1     0     1     1     1     0     1     1     1     1     1     1     1     1     1     1     1     1    10    14     2    20     3

  26 至 40 列

    18     6     1    15     4     9     8    12    16    17    11     5     7    19    13

显示各个路径(遗传算法)

第1辆车的路径

route1 =

     0    10    14     2    20     0

loadline =

     0     0    19

    19    19    17

    17    17    14

    14    14     5

     5     5     0

     0     0     0

运行时间表

outcell01 =

    '路径点'    '到达时间'             '开始服务时间'          '结束时间'        

    [    0]    [               6]    [               6]    [               6]

    [   10]    [7.14017542509914]    [7.14017542509914]    [7.17350875843247]

    [   14]    [7.89044669158987]    [7.89044669158987]    [7.94044669158987]

    [    2]    [ 8.6943697645887]    [ 8.6943697645887]    [ 8.8443697645887]

    [   20]    [9.31255776101749]    [9.31255776101749]    [9.39589109435082]

    [    0]    [10.8408824438059]    [10.8408824438059]    [10.8408824438059]

第2辆车的路径

route1 =

     0     3    18     6    15     0

loadline =

     0     0    20

    20    20    10

    10    10     3

     3     3     1

     1     1     0

     0     0     0

运行时间表

outcell01 =

    '路径点'    '到达时间'             '开始服务时间'          '结束时间'        

    [    0]    [               6]    [               6]    [               6]

    [    3]    [7.79477018027379]    [7.79477018027379]    [7.96143684694045]

    [   18]    [8.52782893728071]    [8.52782893728071]    [8.64449560394737]

    [    6]    [10.0046426548209]    [10.0046426548209]    [10.0379759881543]

    [   15]    [10.4851895836542]    [10.4851895836542]    [10.5018562503209]

    [    0]    [10.9136814559604]    [10.9136814559604]    [10.9136814559604]

第3辆车的路径

route1 =

     0     9    12    16     0

loadline =

     0     0    18

    18    18    16

    16    16     7

     7     7     0

     0     0     0

运行时间表

outcell01 =

    '路径点'    '到达时间'             '开始服务时间'          '结束时间'        

    [    0]    [               6]    [               6]    [               6]

    [    9]    [7.92093727122985]    [7.92093727122985]    [7.95427060456319]

    [   12]    [9.38605271089082]    [9.38605271089082]    [9.53605271089082]

    [   16]    [9.79682080709893]    [9.79682080709893]    [ 9.9134874737656]

    [    0]    [10.6345977288584]    [10.6345977288584]    [10.6345977288584]

第4辆车的路径

route1 =

     0    17    11     0

loadline =

     0     0    11

    11    11     7

     7     7     0

     0     0     0

运行时间表

outcell01 =

    '路径点'    '到达时间'             '开始服务时间'          '结束时间'        

    [    0]    [               6]    [               6]    [               6]

    [   17]    [7.25538838611802]    [7.25538838611802]    [7.32205505278468]

    [   11]    [8.66220429820476]    [8.66220429820476]    [8.77887096487143]

    [    0]    [ 10.082711445912]    [ 10.082711445912]    [ 10.082711445912]

第5辆车的路径

route1 =

     0     5     0

loadline =

     0     0     3

     3     3     0

     0     0     0

运行时间表

outcell01 =

    '路径点'    '到达时间'             '开始服务时间'          '结束时间'        

    [    0]    [               6]    [               6]    [               6]

    [    5]    [8.76875423250241]    [8.76875423250241]    [8.81875423250241]

    [    0]    [11.5875084650048]    [11.5875084650048]    [11.5875084650048]

第6辆车的路径

route1 =

     0     7    19    13     0

loadline =

     0     0    18

    18    18    13

    13    13     9

     9     9     0

     0     0     0

运行时间表

outcell01 =

    '路径点'    '到达时间'             '开始服务时间'          '结束时间'        

    [    0]    [               6]    [               6]    [               6]

    [    7]    [7.88403821617291]    [7.88403821617291]    [7.96737154950624]

    [   19]    [8.58769404627708]    [8.58769404627708]    [8.65436071294374]

    [   13]    [9.27177467456107]    [9.27177467456107]    [9.42177467456107]

    [    0]    [10.2017746745611]    [10.2017746745611]    [10.2017746745611]

punish_early =

     0

punish_late =

     0

outcell =

    '节点编号'    '达到时间'             '离开时间'        

    [      1]    [               0]    [               0]

    [      2]    [ 8.6943697645887]    [ 8.8443697645887]

    [      3]    [7.79477018027379]    [7.96143684694045]

    [      4]    [               0]    [               0]

    [      5]    [8.76875423250241]    [8.81875423250241]

    [      6]    [10.0046426548209]    [10.0379759881543]

    [      7]    [7.88403821617291]    [7.96737154950624]

    [      8]    [               0]    [               0]

    [      9]    [7.92093727122985]    [7.95427060456319]

    [     10]    [7.14017542509914]    [7.17350875843247]

    [     11]    [8.66220429820476]    [8.77887096487143]

    [     12]    [9.38605271089082]    [9.53605271089082]

    [     13]    [9.27177467456107]    [9.42177467456107]

    [     14]    [7.89044669158987]    [7.94044669158987]

    [     15]    [10.4851895836542]    [10.5018562503209]

    [     16]    [9.79682080709893]    [ 9.9134874737656]

    [     17]    [7.25538838611802]    [7.32205505278468]

    [     18]    [8.52782893728071]    [8.64449560394737]

    [     19]    [8.58769404627708]    [8.65436071294374]

    [     20]    [9.31255776101749]    [9.39589109435082]

>>

这篇关于遗传算法优化最大化效应的某些需求点可不配送的vrptw问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/658583

相关文章

Vue3 的 shallowRef 和 shallowReactive:优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉,那么对 shallowRef 和 shallowReactive 是否了解呢? 在编程和数据结构中,“shallow”(浅层)通常指对数据结构的最外层进行操作,而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素,而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层(Shallow) 定义

HDFS—存储优化(纠删码)

纠删码原理 HDFS 默认情况下,一个文件有3个副本,这样提高了数据的可靠性,但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码,采用计算的方式,可以节省约50%左右的存储空间。 此种方式节约了空间,但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件,都会执行此策略。 默认只开启对 RS-6-3-1024k

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

MySQL高性能优化规范

前言:      笔者最近上班途中突然想丰富下自己的数据库优化技能。于是在查阅了多篇文章后,总结出了这篇! 数据库命令规范 所有数据库对象名称必须使用小写字母并用下划线分割 所有数据库对象名称禁止使用mysql保留关键字(如果表名中包含关键字查询时,需要将其用单引号括起来) 数据库对象的命名要能做到见名识意,并且最后不要超过32个字符 临时库表必须以tmp_为前缀并以日期为后缀,备份

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)