牛奶配送问题的两阶段平衡TSP优化算法研究

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (16): 5-9.

牛奶配送问题的两阶段平衡TSP优化算法研究

丁雪枫1，尤建新1，2

1.同济大学经济与管理学院，上海 200092
2.上海大学管理学院，上海 200444

出版日期:2012-06-01 发布日期:2012-06-01

Study on optimal algorithm of 2-period balanced TSP for milk delivery problem

DING Xuefeng1, YOU Jianxin1，2

1.School of Economics and Management, Tongji University, Shanghai 200092, China
2.School of Management, Shanghai University, Shanghai 200444, China

Online:2012-06-01 Published:2012-06-01

摘要/Abstract

摘要： 牛奶配送问题中包含访问次数不同的节点，该问题可以当做两阶段旅行商问题进行求解。为有效地求解节点个数处于平衡条件下的牛奶配送问题的两阶段旅行商问题，提出了一种启发式优化求解方法，有助提高目标问题的求解效率和性能。针对节点数量平衡性和节点访问次数不同的特点，提出一种基于节点划分的动态规划优化。通过对实例进行计算和比较，结果验证了所提方法的有效性和优越性。

关键词: 牛奶配送问题, 节点平衡, 两阶段, 旅行商问题

Abstract: Milk delivery problem is a problem which contains different visiting time node, it can be regarded as a 2-period TSP. In order to solve 2-period traveling salesman problem for milk delivery problem under balancing condition effectively, a heuristic optimal algorithm is proposed, which can improve efficiency and performance on solving target objection. Considering the node characteristics both number balance and different visiting time, a dynamic programming optimal method based on node division is proposed. By calculating and comparing on examples, the result shows the effectiveness and superiority of this proposed algorithm.

Key words: milk delivery problem, node balancing, 2-period, traveling salesman problem

丁雪枫1，尤建新1，2. 牛奶配送问题的两阶段平衡TSP优化算法研究[J]. 计算机工程与应用, 2012, 48(16): 5-9.

DING Xuefeng1, YOU Jianxin1，2. Study on optimal algorithm of 2-period balanced TSP for milk delivery problem[J]. Computer Engineering and Applications, 2012, 48(16): 5-9.

[1]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[2]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[3]	陈思远，林丕源，黄沛杰. 指针网络改进遗传算法求解旅行商问题[J]. 计算机工程与应用, 2020, 56(19): 231-236.
[4]	周克良，龚达欣，张宇龙. 区域破坏重建的蚁群优化算法[J]. 计算机工程与应用, 2020, 56(14): 62-67.
[5]	刘明霞1，游晓明1，刘升2. 基于聚度的自适应动态混沌蚁群算法[J]. 计算机工程与应用, 2019, 55(3): 15-22.
[6]	顾清华，孟倩倩. 优化复杂函数的粒子群-鸽群混合优化算法[J]. 计算机工程与应用, 2019, 55(22): 46-52.
[7]	胡士娟，鲁海燕，黄洋，许凯波. 求解工作量平衡多旅行商问题的改进遗传算法[J]. 计算机工程与应用, 2019, 55(17): 150-155.
[8]	陈佳，游晓明，刘升，李娟. 结合信息熵的多种群博弈蚁群算法[J]. 计算机工程与应用, 2019, 55(16): 170-178.
[9]	李娟，游晓明，刘升，陈佳. 自适应模糊蚁群系统[J]. 计算机工程与应用, 2019, 55(15): 75-81.
[10]	赵亚文，熊瑞平，乔治，梁齐齐，罗勇. 应用捕食搜索策略的改进多态蚁群算法[J]. 计算机工程与应用, 2019, 55(14): 115-121.
[11]	姚书婷，胡志华，魏晨. 多禁止时间窗约束的路径恢复问题研究[J]. 计算机工程与应用, 2019, 55(12): 265-270.
[12]	范建平，卫媛，吴美琴. 考虑中间变量产出时滞性的两阶段评价[J]. 计算机工程与应用, 2018, 54(8): 36-43.
[13]	陈雷，张红梅，张向利. 自适应动态邻域布谷鸟混合算法求解TSP问题[J]. 计算机工程与应用, 2018, 54(23): 42-50.
[14]	白景波，李宏伟，陈亮，冯玉芳，刘建永. 双链量子蚁群系统及应用[J]. 计算机工程与应用, 2018, 54(21): 1-6.
[15]	徐小平，张东洁. 基于猴群算法求解旅行商问题[J]. 计算机工程与应用, 2018, 54(2): 144-148.