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

J4 ›› 2013, Vol. 35 ›› Issue (1): 124-129.

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

王君

（天津财经大学商学院，天津 300222）

收稿日期:2011-11-22 修回日期:2012-02-25 出版日期:2013-01-25 发布日期:2013-01-25
作者简介:王君(1983),男，天津人，博士，研究方向为物流工程和智能优化。
基金资助:
国家社科基金资助项目(11CGL102)；天津财经大学科研发展基金资助项目(Y1110，Q1208)

Multi-objective memetic algorithm for vehicle routing problem with time windows

WANG Jun

(School of Business,Tianjin University of Finance and Economics,Tianjin 300222,China)

Received:2011-11-22 Revised:2012-02-25 Online:2013-01-25 Published:2013-01-25

摘要/Abstract

摘要：

针对物流配送中带时间窗的车辆路径问题，以最小化车辆使用数和行驶距离为目标，建立了多目标数学模型，提出了一种求解该问题的多目标文化基因算法。种群搜索采用遗传算法的进化模式和Pareto排序的选择方式，局部搜索采用禁忌搜索机制和存储池的结构，协调两者得到的Pareto非占优解的关系。与不带局部搜索的多目标遗传算法和单目标文化基因算法的对比实验表明，本文算法的求解质量较高。

关键词: 带时间窗的车辆路径问题, 文化基因算法, 多目标优化, 禁忌搜索

Abstract:

The Vehicle Routing Problem with Time Windows (VRPTW) is addressed in the paper. A multiobjective mathematic model is designed with goals of minimizing the vehicle number and the travel distance. A memetic algorithm is proposed, targeting this problem. The pattern of population search is genetic algorithm and Pareto ranking selection, while the local search uses tabu and solution pool to coordinate Pareto nondominated solutions obtained by the two searches. Compared with the multiobjective genetic algorithm without the local search and the singleobjective memetic algorithm, experimental results show the effectiveness of the proposed algorithm.

Key words: vehicle routing problem with time windows;memetic algorithm;multiobjective optimization;tabu search

王君. 带时间窗车辆路径问题的多目标文化基因算法[J]. J4, 2013, 35(1): 124-129.

WANG Jun. Multi-objective memetic algorithm for vehicle routing problem with time windows[J]. J4, 2013, 35(1): 124-129.

[1]	安园园, 马晓宁. 改进遗传算法与多目标优化模型的航班路径规划[J]. 计算机工程与科学, 2024, 46(09): 1660-1666.
[2]	罗莉, 石伟, 何鸿君, 潘国腾, 王蕾, 龚锐. 一种面向IO Die的敏捷验证方法[J]. 计算机工程与科学, 2023, 45(04): 571-576.
[3]	申晓宁, 游璇, 陈庆洲, 潘红丽, 黄遥. 采用双档案协同进化离散多目标烟花算法的低碳疫苗冷链优化配送[J]. 计算机工程与科学, 2022, 44(12): 2255-2265.
[4]	李艺辉, 刘作军, 李洁. 基于模糊逻辑NSGA-Ⅲ的开关磁阻发电机多目标优化算法[J]. 计算机工程与科学, 2021, 43(03): 542-550.
[5]	张明珠, 曹杰, 王斌. 基于精英集的多目标差分进化聚类算法[J]. 计算机工程与科学, 2021, 43(01): 170-179.
[6]	马永杰, 陈满丽, 陈敏. 基于Pareto解集分段预测策略的动态多目标进化算法[J]. 计算机工程与科学, 2020, 42(08): 1454-1462.
[7]	衡红军, 戚馨桐. 考虑任务均衡的加油车动态调度问题[J]. 计算机工程与科学, 2020, 42(05): 923-930.
[8]	朱登京，段倩倩. 无参分组大规模变量的多目标算法研究[J]. 计算机工程与科学, 2020, 42(04): 603-609.
[9]	赵凤1,2，孔令润1,2，马改妮1,2. 多目标粒子群和人工蜂群混合优化的阈值图像分割算法[J]. 计算机工程与科学, 2020, 42(02): 281-290.
[10]	黄洪涛1，武继刚1，郑露露1，缪裕青2. 面向无线内容分发网络的树形拓扑生成算法[J]. 计算机工程与科学, 2018, 40(12): 2133-2140.
[11]	张凤斌，范学林，席亮. 免疫入侵检测多目标优化克隆选择算法研究[J]. 计算机工程与科学, 2018, 40(02): 261-267.
[12]	陈诗军1，王慧强2，陈大伟1，刘秀兵2,胡海婧2. 基于改进禁忌搜索的基站布局优化算法[J]. 计算机工程与科学, 2018, 40(02): 341-347.
[13]	李克武,张功萱,朱昭萌. 云环境中基于分解的多目标工作流调度算法[J]. 计算机工程与科学, 2016, 38(08): 1588-1594.
[14]	薛蒙蒙，马永涛，刘敬浩. 基于模拟退火粒子群算法的认知引擎研究[J]. 计算机工程与科学, 2016, 38(08): 1640-1646.
[15]	董跃华,刘力. 基于AHTPSO的连续属性离散化算法[J]. J4, 2016, 38(05): 1014-1023.