禁忌搜索算法求解带时间窗的车辆路径问题原理讲解

举报
格图洛书 发表于 2021/11/18 23:43:09 2021/11/18
【摘要】 前言 今天为大家带来用禁忌搜索算法(下文简称TS)求解带时间窗的VRP问题(下文简称VRPTW)。 下面带大家体会TS的思想。以VRPTW为例,VRPTW的解的形式为每辆车所经过的顾客,比如说有15个顾客,并且仅需3辆车完成全部配送任务。,则解如下所示(序号代表顾客编号): 车辆1:4 2 9 10&...

前言

今天为大家带来用禁忌搜索算法(下文简称TS)求解带时间窗的VRP问题(下文简称VRPTW)。

下面带大家体会TS的思想。以VRPTW为例,VRPTW的解的形式为每辆车所经过的顾客,比如说有15个顾客,并且仅需3辆车完成全部配送任务。,则解如下所示(序号代表顾客编号):

车辆1:4 2 9 10 14

车辆2:11 1 3 7 13

车辆3:15 8 6 5 12

假设当前解所有车辆行驶的总距离是100.

要用TS求这个问题,第一步是要确定禁忌表,包括禁忌表的形式以及禁忌表的长度。还是举例说明,先定义(i,k),其表示顾客i由车辆k服务,则当前解S的邻域N(S)为从当前解的任一路径中移除当前路径的任一顾客,并将该顾客插入到其他路径,当然这一系列操作必须满足时间窗约束和容量约束(PS,邻域结构有很多种形式,这里只给出一种最简单的邻域结构)

下面先给出禁忌表的形式,初始禁忌表的禁忌长度都设为0。

表中(i,k)表示路径k中的顾客i一旦从路径k中移除,则连续L代不能插

文章来源: wenyusuran.blog.csdn.net,作者:文宇肃然,版权归原作者所有,如需转载,请联系作者。

原文链接:wenyusuran.blog.csdn.net/article/details/108404044

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。