文档介绍：第卷第期厦门大学学报自然科学版. .
年月.

,
曼,●●●, 、●●●●●●【

∑∑
单回路运输问题的表上作业求解∑
∑
: 喊●
刘旺盛,黄敏霁,李茂青“
厦门大学信息科学与技术学院,福建厦门
摘要:基于单回路运输问题的数学模型的特征与多点间运输问题有相似之处,提出了单回路运输问题的表上作业求解
法;并探讨了该方法的求解适用原则,除了适用大部分多点问运输问题可行解的确定原则法外,还可以和其启发式算
法——,优化方法有待继续探索.
关键词:单回路运输问题;旅行商问题;多点问运输问题;表上作业法;闭回路法
中图分类号:. 文献标识码: 文章编号:———

单回路运输问题及其模型排列,随着顶点数的增加,计算量会产生组合爆炸,属
于“完全问题”,
单回路运输问题主要见于单一车辆的路径安排,
指在运输线路优化中,设存在节点集合,选择一条闭输问题而提出的,后来逐步应用到飞机航线的安排、快
合路径遍历所有的节点,使该车辆遍历所有用户的同递服务、
时,,就是最为典型
是单一性只有一个回路和遍历性不可遗漏性. 的一个单回路运输问题,国内外学者对其进行了大量
该问题的数学描述为:设有个节点。,。,⋯, 、动态规划算
.已知从节点到节点的距离为其阶矩法及分支定界法等精确算法,但由于精确算法所能
阵为: .若从某节点出发,遍历其它一个节求解的问题规模非常有限,实际中使用的往往是多项
点各一次,最后返回出发点,
:经典的插入算法按插入规则的不同分为若干
, 若从节点到节点类、最近邻点法和树算法等;需要借助计算机实现的
, 若不从节点到节点禁忌搜索法、模拟退火算法、遗传算法及其他智能算法
则其数学模型为: 和各种智能算法的混合算法等。.

实际上,从模型中可以看出: : 一,
一
这与产销平衡的多点间运输问题的约束特征相同,因
此可以尝试用表上作业法求解.
,,⋯,
表上作业法求解
,,⋯,
该问题在图论的意义上就是所谓的最小由于寻找的回路是包含所有城市节点的一个循
圄问题¨,模型还有其它一些等价的书写形式,此环,故可以把任意一个城市节点作为起点,也是终点.
表上作业法在求解多点间运输问题时可以运用闭回路
优化得到最优解,
收稿日期:
基金项目:国家“工程”三期项目,福建省自然科学基金项目输问题时运用闭回路法优化易出现子回路,因此本文
:
现工作单位:集美大学现代物流研究中心将单回路运输问题转化为产销平衡的多点间
通讯作者:.. 运输问题,建立求解表格:视需遍历的城市,。,⋯,
第期刘旺盛等:单回路运输问题的表上作业求解
既为产地起始地又为销