文章编号: 100124098
(
2005
)
0220019203
任务均分的多旅行商问题
Ξ
卢厚清, 王辉东, 黄 杰, 李 波
(
解放军理工大学 工程兵工程学院, 江苏 南京 210007
)
摘 要: 多旅行商问题是单旅行商问题的扩展, 具有更广泛的实际意义。在研究
M TSP
解的特点的基础上, 提
出了最小化总行程和均分多个旅行商访问点数、最小化总行程及均分访问路程的两个多目标的
M TSP
问题,
并分别给出了相应的数学模型、求解算法和应用实例, 实例表明模型的正确性。
关键词:
M TSP
; 算法; 多目标
中图分类号:
O
22 文献标识码:
A
多旅行商回路
(
M TSP
)
是旅行商问题
(
TSP
)
的扩展。
M TSP
是指给出
N
个城市的集合,
M
个推销商从各自所
在的城市出发, 分别走一条旅行路线, 使得每个城市有且
仅有一个推销商走过, 最后回到原来的出发城市, 且总旅
程最短。研究
M TSP
具有重要的现实意义,
TSP
是
M TSP
的一个特例
(
M
= 1
)
,
M TSP
是
TSP
的一般形式。与
TSP
相比, 如今企业管理中的更多的问题属于
M TSP
。
M TSP
又分为从同一中心城市出发的
M TSP
和从不同中心城市
出发的
M TSP
。本文主要讨论了从同一中心城市出发的
M TSP
问题。目前, 关于
M TSP
的研究较少, 已有的研究
主要集中在求解算法的设计上, 尚未见到对
M TSP
解的
特点及均分各旅行商均分访问顾客数和均分各旅行商访
问路程的研究。
1 一般
M T SP
解的特点与多目标
M T SP
为了使用
TSP
的算法研究解决
M TSP
, 可引入
M
- 1
个虚拟点, 记为
N
+ 1, …,
N
+
M
- 1。第
i
(
1<
i
≤
N
)
个点
和点
j
(
N
<
j
≤
N
+
M
- 1
)
之间的距离定义为第
i
(
1<
i
≤
N
)
个点到点 1
(
中心城市
)
之间的距离, 虚拟点之间及其到
点 1 之间的距离定义为无穷大。在这样的假设下,
M
条线
路的所经过的点至少包含除中心点之外的另一个点。
由于每一个旅行商至少要经过一个城市, 这样
M
个
旅行商所经过的总边数为
N
+
M
条。因而其总行程必然
大于单旅行商问题的总行程。为了尽量减少
M TSP
的总
行程长度, 一般地, 会有
M
- 1 个旅行商总是选择最短最
接近中心城市的
M
- 1 个城市作为自己的往返路线, 最后
形成了由余下的
N
-
M
+ 1 点的
TSP
。
图 1 给出了一个 20 个城市
(
城市 1 为中心
)
的 3 个旅
行商的
M TSP
问题。我们采用上面的变换方法将它变成
单
TSP
问题。使用
M TSP
的遗传算法得到三条最短路线
为
L
1
为
(
1 10 1
)
、
L
2
为
(
1 17 1
)
、
L
3
为
(
1 13 16
14 3 12 4 19 8 2 18 5 9 7 20 15 11
6 1
)
。其中,
L
1
选择最接近中心城市 1 的城市 10,
L
2
择次接近中心城市 1 的城市 17。路程
L
1
的长度
d
(
L
1
)
=
2
d
1, 10
, 路程
L
2
的长度
d
(
L
2
)
= 2
d
1, 17
, 这样两次使用了两
个最接近中心城市, 因而其总长度应该是较优的结果。
M
个旅行商中, 有
M
- 1 个旅行商仅访问了一个点,
而由一个旅行商访问留下的所有点。这种情况不符合企业
管理的实际。企业既然使用多个旅行商
(
车辆
)
来从事这项
工作, 一般不会让一个旅行商
(
车辆
)
去完成几倍于甚至几
十倍于另一个旅行商
(
车辆
)
的工作; 如果这样的话, 便失
去了使用多个旅行商问题的意义。因而平均分配各旅行商
的任务是多旅行商问题的一个重要的具有实际意义研究
领域。平均分配任务又可分为两种情况: 一是平均分配
M
个旅行商的访问城市
(
点
)
数; 二是平均分配
M
个旅行商
的访问路径长度。
对于均分访问点数的
M TSP
, 如果我们仅考虑平均
分配访问点数这一个目标, 则该问题变得十分简单, 此时
只要令每个点访问的点数为[
N
g
M
]或[
N
g
M
]+ 1 即可。
所以, 均分访问点数的
M TSP
应是一个多目标规划问题,
需要研究的既要使得访问的总路程最短, 又要使得各旅
行商访问点数得以尽量均衡分配。同样, 均分访问路程的
M TSP
也是一个多目标规划问题, 其目标分别为
M
个旅
行商访问总路程最短及各旅行商访问路程尽量均衡分配。
第 23 卷第 2 期
(
总第 134 期
)
系 统 工 程
Vo l. 23, No. 2
2005 年 2 月
System s Engineering
Feb. , 2005
Ξ
收稿日期: 2004211215
作者简介: 卢厚清, 解放军理工大学工程兵工程学院。
© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
