Beam-PSO优化算法在多行程车辆路径问题的应用

发布时间：2021-08-03 12:40

　　针对城市物流配送系统,研究了一类带时间窗和释放时间约束的多行程车辆路径问题。首先,对该运输调度问题进行了描述,构建了以总配送时长最小化为目标的数学模型。其次,为了快速获得问题的满意解,提出了Beam-PSO优化算法。在算法设计中,结合该问题的性质,构建了基于随机键的编解码方法,以克服标准粒子群算法无法直接适用于求解离散问题的不足。同时,设计了基于Beam search优化技术的局部搜索流程,用于强化算法的优化性能。最后,进行了仿真实验,实验结果表明了Beam-PSO优化算法的可行性和有效性。 

【文章来源】：计算机工程与科学. 2019,41(10)北大核心CSCD

【文章页数】：10 页

【部分图文】：

图２基于ＲＯＶ规则的随机键编码转换Ｆｉｇｕｒｅ２ＣｏｄｅｃｏｎｖｅｒｓｉｏｎｏｆＲＯＶ－ｂａｓｅｄｒａｎｄｏｍｋｅｙｓ

次类推，可将Ｄ维实数数组映射为１个１～Ｄ的排列数组。如图２所示，假设某一粒子的编码数值为（０．６３，０．２５，０．１７，０．４１），依据ＲＯＶ规则可将其转化为排列（４，２，１，３）。Ｆｉｇｕｒｅ２ＣｏｄｅｃｏｎｖｅｒｓｉｏｎｏｆＲＯＶ－ｂａｓｅｄｒａｎｄｏｍｋｅｙｓ图２基于ＲＯＶ规则的随机键编码转换Ｆｉｇｕｒｅ３Ｓｃｈｅｍａｔｉｃｄｉａｇｒａｍｏｆｔｒｉｐｓｐｌｉｔｔｉｎｇ图３行程划分示意图Ｆｉｇｕｒｅ４Ｓｃｈｅｍａｔｉｃｄｉａｇｒａｍｏｆｔｈｅｔｒｉｐｓｐｌｉｔｔｉｎｇｆｏｒｍｕｌｔｉｐｌｅｖｅｈｉｃｌｅｓ图４多车行程划分示意图在ＭＴＶＲＰ－ＴＷ－ＲＤ问题中，已知待服务的仓库点总数为Ｎ。首先考虑运输车总数为１的情形，由于每个行程至少服务１个仓库，因而整个运输过程至多分为Ｎ个行程。对于一个由所有仓库编号构成的排列（即１～Ｎ的随机排列），利用Ｎ－１个分割符即可实现所有行程的划分，图３给出了相应的编码与行程划分示意图，该算例中需要服务的仓库总数为９。在此基础上，考虑到配送车的总数为Ｍ的情形，为了实现各运输车辆的任务划分，只需要在图３编码的基础上增加Ｍ－１个分隔符。图４给出了多车配送行程划分的示意图，该算例中需要服务的仓库总数为９，运输车数目为３。图３中仓库总数为９，编码１～９表示仓库编号，１０～１７为分割符号，相邻２分隔符之间的仓库序列构成一个行程，行程出现的先后顺序即为所有行程在该辆车上的执行顺序。结合

的编码数值为（０．６３，０．２５，０．１７，０．４１），依据ＲＯＶ规则可将其转化为排列（４，２，１，３）。Ｆｉｇｕｒｅ２ＣｏｄｅｃｏｎｖｅｒｓｉｏｎｏｆＲＯＶ－ｂａｓｅｄｒａｎｄｏｍｋｅｙｓ图２基于ＲＯＶ规则的随机键编码转换Ｆｉｇｕｒｅ３Ｓｃｈｅｍａｔｉｃｄｉａｇｒａｍｏｆｔｒｉｐｓｐｌｉｔｔｉｎｇ图３行程划分示意图Ｆｉｇｕｒｅ４Ｓｃｈｅｍａｔｉｃｄｉａｇｒａｍｏｆｔｈｅｔｒｉｐｓｐｌｉｔｔｉｎｇｆｏｒｍｕｌｔｉｐｌｅｖｅｈｉｃｌｅｓ图４多车行程划分示意图在ＭＴＶＲＰ－ＴＷ－ＲＤ问题中，已知待服务的仓库点总数为Ｎ。首先考虑运输车总数为１的情形，由于每个行程至少服务１个仓库，因而整个运输过程至多分为Ｎ个行程。对于一个由所有仓库编号构成的排列（即１～Ｎ的随机排列），利用Ｎ－１个分割符即可实现所有行程的划分，图３给出了相应的编码与行程划分示意图，该算例中需要服务的仓库总数为９。在此基础上，考虑到配送车的总数为Ｍ的情形，为了实现各运输车辆的任务划分，只需要在图３编码的基础上增加Ｍ－１个分隔符。图４给出了多车配送行程划分的示意图，该算例中需要服务的仓库总数为９，运输车数目为３。图３中仓库总数为９，编码１～９表示仓库编号，１０～１７为分割符号，相邻２分隔符之间的仓库序列构成一个行程，行程出现的先后顺序即为所有行程在该辆车上的执行顺序。结合上述ＲＯＶ随机键编码方式和基于分割符的行程划分方法，对ＭＴＶＲＰ－ＴＷ－ＲＤ问题采用如下编

【参考文献】：
期刊论文
[1]求解车辆路径问题的人工蜂群算法[J]. 王志刚,夏慧明.  计算机工程与科学. 2014(06)
[2]基于混沌粒子群优化的新型VRP求解算法[J]. 于胜龙,薄煜明,陈志敏,吴盘龙,朱凯,尹明锋.  计算机工程与科学. 2012(12)



本文编号：3319636