程序员经验分享-hwhale

带时间窗的车辆路径问题的多目标模因算法

2023-05-16

求解带时间窗车辆路径问题的多目标模因算法

  • 1.问题描述和数学建模建立
  • 多目标模因算法
    • 解的构造
    • 自适应局部搜索链
      • （1）多方向局部搜索策略
      • （2）强化的局部搜索链技术
      • （3）自适应局部搜索链过程
      • （4）存档更新策略
  • 参考文献
  • 源码下载

1.问题描述和数学建模建立

  带时间窗的车辆路径问题(vehicle routing problem with time window，VRPTW)是一个经典的组合优化问题。它涉及到一组客户的服务呼叫及车辆的调度分配，表现出多目标的性质。在车辆路径问题的众多变种问题中，带时间窗的车辆路径问题是在车辆路径问题中为服务的客户添加交付时间约束。其被定义为：创建一个从车场到地理位置分散的客户的可用路径集，使分配策略有最低的成本。对于每个客户，服务在它的时间窗上进行。也就是，每个客户的服务应该在给定的时间窗内开始。如果车辆在客户点的最早开始服务时间之前到达，车辆必须等待，且等待期间不能为客户提供服务。相反，如果车辆的到达时间违反了它的时间窗约束，会产生延迟时间。由于带时间窗的车辆路径问题是车辆路径问题的一个特例，因此它也是一个NP难问题。
在这里插入图片描述  综上所述，多目标带时间窗的车辆路径问题数学模型可以表述为：
在这里插入图片描述
公式(1)是一个有五个目标的多目标带时间窗的车辆路径问题。第一个目标函数为公式(2)，表示尽量减少车辆的数量。第二个目标函数为公式(3)，表示最小化总行程距离。第三个目标函数为公式(4)表示最小化最长路线的行驶时间。第四个目标函数为公式(5)，表示尽量减少因提早到达而造成的总等候时间。第五个目标函数为公式(6)，表示尽量减少因迟到而造成的总延误时间。第一个约束为公式(7)，表示确保每条路线的总需求不超过车辆的最大容量。第二个约束条件公式(8)，表示每个客户点的延迟时间不能超过允许的最大延迟时间。第三个约束条件公式(9)，表示每辆车应在关闭时间前返回车场（注意：车场也有一个时间窗口 

    (
   
   
    0
   
   
    ,
   
   
    
     e
    
    
     0
    
   
   
    )
   
  
  
   (0,{e_0})
  
 
</span><span class="katex-html"><span class="base"><span class="strut" style="height: 1em; vertical-align: -0.25em;"></span><span class="mopen">(</span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right: 0.166667em;"></span><span class="mord"><span class="mord"><span class="mord mathdefault">e</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height: 0.301108em;"><span class="" style="top: -2.55em; margin-left: 0em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">0</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height: 0.15em;"><span class=""></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span></span>。</p>

多目标模因算法

  本文提出了一种求解带时间窗车辆路径问题的多目标模因算法，以便能够有效地、充分地利用在局部搜索过程中获得的有潜力的解，从而引导搜索向最优的帕累托前沿方向前进。多目标模因算法的总体框架如算法1所示，它是在面向多目标带时间窗的车辆路径问题的基于局部搜索的多目标优化算法（LSMOVRPTW）[1]启发下设计的，克服了基于局部搜索的多目标优化算法在局部搜索过程中对生成的有潜力的解不能充分搜索的缺点。
在这里插入图片描述  如算法1所示，多目标模因算法由解的构造、自适应局部搜索链和存档更新策略三个主要组件组成。具体来说，在多目标模因算法开始时，首先，构建一个初始种群，并将其存储在一个外部存档中；然后，从外部存档中选择一个解，去执行由面向目标的局部搜索算子组成的自适应局部搜索链，并在局部搜索期间，用生成的解更新外部存档。
  在下面的小节中，将给出这三个组件的详细信息。

解的构造

  解的构造方法如算法2所示。在构建解决方案时，首先，从未被服务的客户中随机选择一个客户来创建一条路径。然后，使用FIRST策略[2]将其他没有服务的客户插入到所创建的路径中。具体来说，在FIRST策略中，每个客户被插入到第一个可插入的合法位置。如果没有合法的插入位置，则用这个客户创建新路径。利用该方法，可以在较短的时间内构造出满足约束条件的多样化解。在本研究中，当新解被构造后，使用存档更新策略将其存储到外部存档中。解决方案的构建过程直到档案的大小等于目标的数量为止。
在这里插入图片描述

自适应局部搜索链

  在自适应局部搜索链（ALSC）中，有两个关键的组成部分：多方向局部搜索策略（MD-LS）和强化的局部搜索链技术（eLS-Chain）。多方向局部搜索策略引入不同的面向目标的局部搜索算子，面向问题的知识进行多方向搜索，而强化的局部搜索链技术则选择多方向局部搜索策略过程中产生的有潜力的解，以基于链的方式继续搜索。

（1）多方向局部搜索策略

  正如基于局部搜索的多目标优化算法[1]中所讨论的，不同的目标具有不同的特性，如：物理意义、规模和优化难度。因此，设计不同的面向目标的局部搜索算子对于优化多目标带时间窗的车辆路径问题是必不可少的。由于基于局部搜索的多目标优化算法中使用的面向目标的局部搜索算子表现出了良好的性能，本算法也使用了其中的局部搜索算子，来进行链式的搜索。算法3简要描述了不同目标的多方向局部搜索策略。在算法3中， 

     f
    
    
     1
    
   
  
  
   f_1
  
 
</span><span class="katex-html"><span class="base"><span class="strut" style="height: 0.88888em; vertical-align: -0.19444em;"></span><span class="mord"><span style="margin-right: 0.10764em;" class="mord mathdefault">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height: 0.301108em;"><span class="" style="top: -2.55em; margin-left: -0.10764em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height: 0.15em;"><span class=""></span></span></span></span></span></span></span></span></span></span>的局部搜索过程不同于<span class="katex--inline"><span class="katex"><span class="katex-mathml">

 
  
   
    
     f
    
    
     2
    
   
  
  
   f_2
  
 
</span><span class="katex-html"><span class="base"><span class="strut" style="height: 0.88888em; vertical-align: -0.19444em;"></span><span class="mord"><span style="margin-right: 0.10764em;" class="mord mathdefault">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height: 0.301108em;"><span class="" style="top: -2.55em; margin-left: -0.10764em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height: 0.15em;"><span class=""></span></span></span></span></span></span></span></span></span></span>-<span class="katex--inline"><span class="katex"><span class="katex-mathml">

 
  
   
    
     f
    
    
     5
    
   
  
  
   f_5
  
 
</span><span class="katex-html"><span class="base"><span class="strut" style="height: 0.88888em; vertical-align: -0.19444em;"></span><span class="mord"><span style="margin-right: 0.10764em;" class="mord mathdefault">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height: 0.301108em;"><span class="" style="top: -2.55em; margin-left: -0.10764em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">5</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height: 0.15em;"><span class=""></span></span></span></span></span></span></span></span></span></span>。为了优化f1 ，首先使用轮盘赌的选择方法从X<sub>cur </sub>中选择一条路径，其中路径的选择概率与路径上的客户点数量成反比。然后，将选择路径中的每个客户插入到其它路径中第一个遍历到的合法位置。如果选择路线上的所有客户都成功插入到其它路径，解中使用的车辆数量将减1。<br> <img src="https://img-blog.csdnimg.cn/20200505111317267.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5na2tpdA==,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"><img src="https://img-blog.csdnimg.cn/20200505111456989.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5na2tpdA==,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></p>

（2）强化的局部搜索链技术

  为了进一步利用MD-LS生成的有潜力的解来指导搜索，将局部搜索链[3]的概念引入到MMA中。正如Molina等人[3]所描述的，局部搜索链的目标是“将连续局部搜索算法集中作用于有希望得到改进的地方”。为了使用局部搜索链，强化的局部搜索链技术被提出，并与多方向局部搜索策略相结合。
  在强化的局部搜索链技术中，需要解决两个关键问题：怎样使用面向目标的局部搜索来构造局部搜索链，和怎样选择强化的局部搜索链技术中的解，以便用不同的局部搜索算子优化。
  为了解决第一个问题，eLS-Chain根据目标的顺序依次执行局部搜索算子。也就是说，局部搜索链是通过执行如下面向目标的局部搜索来构建的：
在这里插入图片描述
如公式（10）所示，首先对选择的解执行 的局部搜索，生成一个新的解，然后对目标 

     f
    
    
     2
    
   
  
  
   f_2
  
 
</span><span class="katex-html"><span class="base"><span class="strut" style="height: 0.88888em; vertical-align: -0.19444em;"></span><span class="mord"><span style="margin-right: 0.10764em;" class="mord mathdefault">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height: 0.301108em;"><span class="" style="top: -2.55em; margin-left: -0.10764em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height: 0.15em;"><span class=""></span></span></span></span></span></span></span></span></span></span>、<span class="katex--inline"><span class="katex"><span class="katex-mathml">

 
  
   
    
     f
    
    
     3
    
   
  
  
   f_3
  
 
</span><span class="katex-html"><span class="base"><span class="strut" style="height: 0.88888em; vertical-align: -0.19444em;"></span><span class="mord"><span style="margin-right: 0.10764em;" class="mord mathdefault">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height: 0.301108em;"><span class="" style="top: -2.55em; margin-left: -0.10764em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">3</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height: 0.15em;"><span class=""></span></span></span></span></span></span></span></span></span></span> 、<span class="katex--inline"><span class="katex"><span class="katex-mathml">

 
  
   
    
     f
    
    
     4
    
   
  
  
   f_4
  
 
</span><span class="katex-html"><span class="base"><span class="strut" style="height: 0.88888em; vertical-align: -0.19444em;"></span><span class="mord"><span style="margin-right: 0.10764em;" class="mord mathdefault">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height: 0.301108em;"><span class="" style="top: -2.55em; margin-left: -0.10764em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height: 0.15em;"><span class=""></span></span></span></span></span></span></span></span></span></span>和<span class="katex--inline"><span class="katex"><span class="katex-mathml">

 
  
   
    
     f
    
    
     5
    
   
  
  
   f_5
  
 
</span><span class="katex-html"><span class="base"><span class="strut" style="height: 0.88888em; vertical-align: -0.19444em;"></span><span class="mord"><span style="margin-right: 0.10764em;" class="mord mathdefault">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height: 0.301108em;"><span class="" style="top: -2.55em; margin-left: -0.10764em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">5</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height: 0.15em;"><span class=""></span></span></span></span></span></span></span></span></span></span> 进行局部搜索。注意，局部搜索链也可以用这五个局部搜索算子以不同顺序来构造。根据我们的初步测试，在多目标模因算法中，采用以目标的顺序构造或以随机顺序构造的局部搜索链之间没有显著差异。因此，为了简单起见，本算法使用以目标次序构造而成的局部搜索链。在未来的工作中，我们将全面评估不同顺序的局部搜索链的有效性。<br> <img src="https://img-blog.csdnimg.cn/20200505131503397.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5na2tpdA==,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"><img src="https://img-blog.csdnimg.cn/20200505184549981.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5na2tpdA==,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"><br> <img src="https://img-blog.csdnimg.cn/20200505131809120.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5na2tpdA==,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"><img src="https://img-blog.csdnimg.cn/20200505131834499.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5na2tpdA==,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></p>

（3）自适应局部搜索链过程

  自适应局部搜索链结合了多方向局部搜索策略和强化的局部搜索链技术两种机制，如算法4所示。其中， |LSChains|表示局部搜索链执行的次数， |A| 是当前存档的规模。从算法4中，多方向局部搜索策略和强化的局部搜索链技术以一种交替的方式从步骤1执行到步骤5，然后更新每个局部搜索算法的成功率(步骤6-10)。
在这里插入图片描述

（4）存档更新策略

在这里插入图片描述

参考文献

[1] Zhou Y, Wang J. A local search-based multiobjective optimization algorithm for multiobjective vehicle routing problem with time windows[J]. IEEE Systems Journal, 2014, 9(3): 1100~1113.
[2] Tarantilis C D, Anagnostopoulou A K, Repoussis P P. Adaptive path relinking for vehicle routing and scheduling problems with product returns[J]. Transportation Science, 2013, 47(3): 356~379.
[3] Molina D, Lozano M, García-Martínez C, et al. Memetic algorithms for continuous optimisation based on local search chains[J]. Evolutionary computation, 2010, 18(1): 27~63.

源码下载

https://github.com/zkk123456/Multiobjective-memetic-algorithm-based-on-adaptive-local-search-chains-for-vehicle-routing-problem-w.git

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

带时间窗的车辆路径问题的多目标模因算法 的相关文章

随机推荐

  • 网络基础2

    网络基础2 应用层 amp 传输层典型协议 应用层 自定制协议 私有协议 xff0c HTTP协议 传输层 UDP amp TCP协议 应用层 负责应用程序之间的数据沟通 应用层协议其实是面向程序员的协议 xff0c 因为应用程序是程序员写

  • ubuntu服务器通过iso进行系统升级

    ubuntu服务器通过iso进行系统升级 1 添加iso文件源 xff1a sudo mount t iso9660 o loop ubuntu 18 04 6 live server amd64 iso media cdrom 挂在镜像文

  • ROS学习（1）：gazebo保存加载世界

    roslaunch文件分析 xff08 古月居大神提供 xff0c 来源于ROS机器人开发实践视频 xff09 96 view mbot gazebo play ground launch lt launch gt lt 设置launch文

  • connect to host port 22: Connection refused

    Windows 使用SSH连接树莓派 xff1a 提示 xff1a 这里简述项目相关背景 xff1a 今天练习发现使用MobaXterm可以正常连接到树莓派 xff0c 但是使用windows终端就不可以连接 xff0c 显示connect

  • 8本游戏开发书籍推荐

    很多刚刚接触游戏开发的朋友经常问我 xff1a 如何开始学习游戏开发 xff1f 我从事游戏开发行业很多年了 xff0c 坦率地讲 xff0c 开发游戏充满挑战性 xff0c 需要开发人员具备大量的技能与积极的创新精神 希望这篇小文能帮助朋

  • windows通过SSH控制树莓派

    windows通过SSH控制树莓派 xff1a 因学习需要在windows系统下对树莓派进行SSH连接 xff0c 包括SSH密钥生成 密钥传输及公钥保存等 Windows下密钥的产生 在Windows下使用 ssh keygen生成公钥和

  • raspistill command not found

    raspistill command not found xff1a 提示 xff1a 这里简述项目相关背景 xff1a 今天使用树莓派来调用摄像头 xff0c 摄像头为树莓派官方摄像头 xff0c 在升级系统和配置后发现使用raspist

  • 树莓派I2C基本用法

    文章目录 一 I2C二 I2C配置1 I2C02 I2C13 I2C34 I2C45 I2C56 I2C6 三 I2C工具总结 一 I2C 树莓派默认打开I2C功能 xff0c 如果I2C没有打开 xff0c 可以使用命令sudo rasp

  • 树莓派RTC

    文章目录 一 RTC准备二 RTC芯片三 为什么使用hwclock显示找不到硬件总结 一 RTC准备 在使能树莓派RTC之前 xff0c 需要先为树莓派RTC模块安装电池 xff08 一般为纽扣电池 xff09 二 RTC芯片 树莓派4B使

  • 树莓派debian11更换国内源

    更换国内源 修改文件 etc apt sources list deb https mirrors tuna tsinghua edu cn debian bullseye main contrib non free span class

  • cpptools占用率过高

    问题描述 使用vscode发现在系统中cpptools CPU占用率达到百分百 电脑发生严重卡顿 解决方案 xff1a 此问题的出现是因为使用了C C 43 43 这个插件 xff0c 如果直接禁用此插件就可以解决这个问题 如果希望使用这个

  • ROS话题的定义和使用

    ROS话题的定义和使用 自定义话题消息 自定义话题消息主要包括以下步骤 xff1a 定义msg文件在package xml中添加功能中依赖在CMakeList txt中添加编译规则编译生成语言相关文件 编写 msg文件 进入要定义 msg文

  • 如何在VScode中利用git来下载GitHub上的源码

    一 Git安装与下载 官网下载地址 xff1a Git Downloads https git scm com downloads xff08 注意安装时选择的默认编辑器选择vscode xff0c 然后修改安装路径其他默认下一步就ok了

  • PhpStorm 2018 安装及破解方法

    https blog csdn net u012278016 article details 81772566

  • mitmproxy笔记

    mitmproxy证书在http mitm it下载 或者在 mitmproxy ubuntu安装mitmproxy xff0e 可以到官网下载二进制文件 xff0e pip安装出了问题 xff0e Firfox和Chrome有各自独立的证

  • [Extensive Reading]目标检测(object detection)系列（十六）YOLOv4：平衡速度与精度

    简介 YOLOv4是YOLO之父Joseph Redmon宣布退出计算机视觉的研究之后推出的YOLO系列算法 xff0c 其作者Alexey Bochkovskiy也参与了YOLO之前系列算法 xff0c YOLOV4 Optimal Sp

  • 【Python】Python函数名后的-＞(横线和大于号)代表什么？

    目录 参考例子优点 参考 本文主要参考以下链接 xff1a 在def定义函数的时候 64 和 gt 代表什么 python中 gt 是什么意思python 定义函数 def 后面的 xff1e xff0c xff1a 表示的含义 例子 如下

  • Keil软件中使用“Go To Definition Of ”时提示“source browser:‘xxxx‘undefined definition/reference”

    在编写DMA的初始化函数时 xff0c 为了节约时间 xff0c 直接用了之前的模板 xff0c 但是在用DMA DeInit 函数时 xff0c 当右键点击此语句使用 Go To Definition Of 时 xff0c 该功能失效 x

  • 期末单片机复习题及答案（答案不保证全部正确95分）

    作者主页 xff1a 凉开水白菜 作者简介 xff1a 共同学习 xff0c 互相监督 xff0c 热于分享 xff0c 多加讨论 xff0c 一起进步 点赞 x1f44d 收藏 再看 xff0c 养成习惯 订阅的粉丝可通过PC端文末加我微

  • 带时间窗的车辆路径问题的多目标模因算法

    求解带时间窗车辆路径问题的多目标模因算法 1 问题描述和数学建模建立多目标模因算法 解的构造自适应局部搜索链 xff08 1 xff09 多方向局部搜索策略 xff08 2 xff09 强化的局部搜索链技术 xff08 3 xff09 自适

热门标签