用改进后的多目标粒子群优化（MOPSO）算法解决带有风险矩阵的多辆车配送旅行商问题（TSP）

用改进后的多目标粒子群优化（MOPSO）算法解决带有风险矩阵的多辆车配送旅行商问题（TSP）

1. 项目说明

此代码是河南财经政法大学硕士项目的一部分，受 GPL-3.0-only 开源协议保护。GitHub 地址：https://github.com/Ki-Seki/MOPSO-for-Distribution

This code is a part of a HUEL master degree project under the protection of GPL-3.0-only license. GitHub Link: https://github.com/Ki-Seki/MOPSO-for-Distribution

2. 资源

2.1. 本文件夹的文件结构

名称或后缀	包含文件数	作用
`README.md`	1	本文档
`*.m`	14	实现本算法的核心代码、测试文件等
`*.txt`	3	给出的三个样例数据集
`re-encoding.ps1`	1	用于编码格式转换的 PowerShell 脚本
`execute re-encoding.bat`	1	用于执行上述脚本的 Batch 脚本
`LICENSE`	1	GPL-3.0-only 开源协议
`说明`	6	关于此项目算法、数据集的一系列辅助说明文件

2.2. “说明”文件夹的文件结构

名称	类型	作用
`优化MOPSO算法流程图.png`	PNG 图片	描述了该算法的流程图
`优化MOPSO算法流程图.pos`	POS 源文件	上述文件的源文件，在 ProcessOn 打开即可重新编辑
`函数依赖图.png`	PNG 图片	描述了该算法各个模块间的相互依赖关系
`函数依赖图.pptx`	PPT 源文件	上述文件的源文件，可重新编辑
`算法的若干细节.docx`	WORD 文档	讲解了算法的四个细节：位置的编码与解的编码，速度与位置的重编码，适应度函数的设计，用帕累托前沿来替代粒子群优化中的全局最优
`数据集说明.docx`	WORD 文档	以 `example.txt` 为例，详细地对数据集进行了说明

2.3. 其他资源

名称	类型	作用	链接
`MOPSO说明与使用`	在线视频	包含对 MOPSO 的使用、算法、数据集的介绍	Loom
`优化MOPSO算法流程图`	在线流程图	MOPSO 的 `main.m` 程序的流程图的在线查看版本	ProcessOn

3. 使用

3.1. 步骤

选择性修改 main.m 中“%% 参数设置”部分的参数
运行 main.m 程序
在命令行窗口交互式地查看输出，在图片窗口中查看输出的图表

3.2. 出现乱码？

如果打开代码文件出现乱码，请阅读本小节

MATLAB 对文件的编码遵照系统默认编码格式（GB 2312）。而本项目包括本文件都是 UTF-8 编码的。为了解决这一冲突，提供如下方法（仅在 Windows 平台可用）：

在文件管理器中打开本文件夹，双击运行 execute re-encoding.m 文件
这会生成与本文件夹同级的文件夹 encoded ，它包含重新编码后的文件
在 MATLAB 中打开 encoded 文件夹即可，其中的文件均采用系统默认编码格式

3.3. 在 MATLAB 2022a 下运行失败？

由于 MATLAB 2015b 固有的 Bug 及与 MATLAB 2022a 的版本兼容性问题，直接下载下来的代码运行时会报错。可根据下表按需修改：

文件名	行数	原内容	修改后内容
`extract_value.m`	16	`matchsize-field2size-2`	`matchsize-field2size-1`
`draw_convergence.m`	8	`suptitle`	`sgtitle`

4. 算法

4.1. 问题情景

疫情下不同节点风险等级不同，车辆跨异风险区运输需要相应的消杀成本，如何在此约束下解决含有多辆车及多目标的应急物资配送问题？

4.2. 算法思路

本算法 = 普通粒子群优化 + 多目标优化 + 帕累托前沿 + 针对 TSP 的速度位置重编码

4.3. 流程图与依赖图

有三个地方可以查看该算法的流程图，分别是在线的 ProcessOn，离线的图片优化MOPSO算法流程图.png 和离线的 POS 文件优化MOPSO算法流程图.pos. 其中，POS 文件是流程图绘制平台 ProcessOn 的源文件，从其官网打开即可对该文件再做修改。

在 说明 文件夹下，有函数依赖图，方便查看该算法代码各个模块间的相互依赖关系。

4.4. 时间复杂度

算法核心部分循环 loop_cnt 次；每次都要遍历粒子群中所有粒子，共 particle_cnt 个粒子；算法的瓶颈在于 fitness() 函数，此函数的算法复杂度与 NODE_COUNT 呈正相关。因此最终算法时间复杂度为 O(loop_cnt × particle_cnt × NODE_COUNT).

令 N = max{loop_cnt, particle_cnt,NODE_COUNT}, 则算法时间复杂度也可表示为 O(N³).

4.5. 算法优缺点

优点

多目标粒子群优化（Multi-Objective PSO）算法：运用多目标优化的理论将单目标的粒子群优化算法改为支持多目标问题的求解
风险矩阵：解决疫情下应急物资配送的一个强大数学工具
适应度矩阵：构造这一矩阵，大大方便了从单目标到多目标问题的过渡
速度与位置的重编码：问题情景为含有多辆车配送的 TSP（旅行商问题），其解的编码是离散的，而普通的粒子群优化算法处理的是连续的值，因此需要速度与位置的重编码
帕累托前沿：使用帕累托前沿，也就是非支配解集来表现该多目标问题的解
算法通用性非常强：解决 TSP 问题时，普通算法往往直接假设任意两个结点之间都存在直接边相连；而本算法不对此做要求。这更能有效解决现实问题

缺点

复杂度：达到三次方级别，对于特大型问题的处理效率有待提升
两个帕累托前沿的比较方法，用的是平均数比较方法，较为简单

4.6. 了解更多

可以在算法的若干细节.docx 文档中获取对算法的深入理解。该文档重点讲解了该算法的四个部分：“位置的编码与解的编码”，“速度与位置的重编码”，“适应度函数的设计”，“用帕累托前沿来替代粒子群优化中的全局最优”。

5. 数据集

网上并无现成的数据集，需要自己制作数据集。本文件夹提供了三个数据集，其文件名分别为：example.txt, b50.txt, c21.txt。其中，example.txt 是一个示例测试数据集，仅有 7 个结点，其他两个数据集后缀的数字均为其中结点数量。

在数据集说明.docx 文档中以 example.txt 为例，详细地对数据集进行了说明。

引用

BibTex 格式：

@unpublished{MOPSOfD,
  author = "宋世超",
  title  = "用改进后的多目标粒子群优化（MOPSO）算法解决带有风险矩阵的多辆车配送旅行商问题（TSP）",
  year   = 2022
}

GB/T 7714-2015 格式：

[1]宋世超.用改进后的多目标粒子群优化（MOPSO）算法解决带有风险矩阵的多辆车配送旅行商问题（TSP）[CP].GitHub[2022].https://github.com/Ki-Seki/MOPSO-for-Distribution.