基于改进全局人工鱼群算法的VRPSPDTW研究

计算机工程与应用 ›› 2016, Vol. 52 ›› Issue (21): 21-29.

基于改进全局人工鱼群算法的VRPSPDTW研究

黄务兰1，2，张涛1，3

1.上海财经大学信息管理与工程学院，上海 200433
2.常州大学商学院，江苏常州 213164
3.上海财经大学上海市金融信息技术研究重点实验室，上海 200433

出版日期:2016-11-01 发布日期:2016-11-17

Vehicle routing problem with simultaneous pick-up and delivery and time-windows based on improved global artificial fish swarm algorithm

HUANG Wulan1，2, ZHANG Tao1，3

1.School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China
2.Business School of Changzhou University, Changzhou, Jiangsu 213164, China
3.Shanghai Key Laboratory of Financial Information Technology, Shanghai University of Finance and Economics, Shanghai 200433, China

Online:2016-11-01 Published:2016-11-17

摘要/Abstract

摘要： 研究带时间窗的同时送取货车辆路径规划问题（VRPSPDTW），并建立0-1混合整数规划模型。为进一步提高人工鱼群算法的寻优能力和收敛速度，提出一种改进的全局人工鱼群算法，并通过实验确定算法参数。算法将模型中的时间窗和车载量两个强约束纳入适应度函数进行处理，降低算法计算复杂度。以最小化发车数（NV）和路由距离（TD）为优化目标，通过王与陈提供的VRPSPDTW算例与基本人工鱼群算法（AFSA）和并行模拟退火算法（P-SA）进行比较，验证了改进全局人工鱼群算法的有效性。实验结果显示：IGAFSA获得的NV和TD目标值均优于AFSA，TD目标值优于P-SA。

关键词: 全局人工鱼群算法, 组合优化, 带时间窗同时送取货车辆路径问题（VRPSPDTW）, 逆向物流

Abstract: This paper concerns a Vehicle Routing Problem with Simultaneous Pick-up and Delivery and Time-Windows（VRPSPDTW）. A binary mixed binary integer programming model is developed for the problem. To further improve the convergence speed and optimization capability of the artificial fish swarm algorithm, an Improved Global Artificial Fish Swarm Algorithm（IGAFSA） is proposed, and the parameters of the algorithm are also determined by experiments. In order to reduce computational complexity, during the course of the algorithm, the time windows constraint and the vehicle capacity constraint are allowed to violate. Computational results are reported from Wang and Chen’s benchmark and compared with the results from Artificial Fish Swarm Algorithm（AFSA） and Parallel Simulated Annealing（P-SA） that minimizes the Number of Vehicles（NV） and the total Travel Distance（TD）, which demonstrate the effectiveness of the IGAFSA algorithm. The results show that the IGAFSA which obtains the NV and TD solutions is better than AFSA, and its TD solutions are better than P-SA too.

Key words: global artificial fish swarm algorithm, combinational optimization, Vehicle Routing Problem with Simultaneous Pick-up and Delivery and Time-Windows（VRPSPDTW）, reverse logistic

黄务兰1，2，张涛1，3. 基于改进全局人工鱼群算法的VRPSPDTW研究[J]. 计算机工程与应用, 2016, 52(21): 21-29.

HUANG Wulan1，2, ZHANG Tao1，3. Vehicle routing problem with simultaneous pick-up and delivery and time-windows based on improved global artificial fish swarm algorithm[J]. Computer Engineering and Applications, 2016, 52(21): 21-29.

[1]	陈展，公建宁，刘媛媛，徐京邦. 基于禁忌搜索的多AGV系统路径优化算法[J]. 计算机工程与应用, 2021, 57(10): 273-278.
[2]	孙晶，李硕，赵会群. 基本路径测试用例自动生成的方法研究[J]. 计算机工程与应用, 2018, 54(20): 48-53.
[3]	杨小东，康雁，柳青，孙金文. 求解作业车间调度问题的禁忌分布估计算法[J]. 计算机工程与应用, 2017, 53(7): 147-153.
[4]	孙强，沈玉志，李士金. 回收不确定下WEEE逆向物流网络鲁棒优化设计[J]. 计算机工程与应用, 2017, 53(4): 263-270.
[5]	乔佩利，王娜. 考虑逆向物流第三方配送的选址路径问题研究[J]. 计算机工程与应用, 2017, 53(10): 55-60.
[6]	林若男，李强. 云计算环境下基于模板的任务调度策略与算法[J]. 计算机工程与应用, 2016, 52(19): 48-52.
[7]	戎容，吴萍. 基于遗传算法的股票市场选择模型[J]. 计算机工程与应用, 2016, 52(18): 167-172.
[8]	李果1，洪旭东2，许建1，黄翰2. 求解护士分配问题的矩阵编码进化算法[J]. 计算机工程与应用, 2015, 51(4): 244-248.
[9]	李迎1，张璟1，2，虎群1，李军怀1，2. 人工鱼群算法在虚拟机分配中的应用[J]. 计算机工程与应用, 2015, 51(4): 22-28.
[10]	孙强1，沈玉志2，李士金1. 逆向物流多产品两阶段再生产网络鲁棒优化[J]. 计算机工程与应用, 2015, 51(3): 18-23.
[11]	林耿. 最小赋权支配集的迭代禁忌搜索算法[J]. 计算机工程与应用, 2015, 51(23): 78-81.
[12]	蒋国清1，潘勇2，胡飞跃1. 两阶段式的物流配送路径优化方法[J]. 计算机工程与应用, 2015, 51(2): 255-258.
[13]	王亚荣，徐秋平. 基于窄带图割的交互式快速目标提取[J]. 计算机工程与应用, 2013, 49(3): 226-229.
[14]	刘宇1，2，3，4，赵怀慈1，3，4，花海洋1，3，4. 飞行试验航路规划方法研究与实现[J]. 计算机工程与应用, 2013, 49(21): 262-265.
[15]	郜庆市，孙树栋，韩青，钟尧. 蚁群算法参数组合的博弈优化[J]. 计算机工程与应用, 2013, 49(21): 51-55.