当前位置:首页 >> 天文/地理 >>

中国邮递员问题的整数规划模型

第 19 卷 第 6 期 2010 年 12 月













Jo ur nal of Sy stems & M anag ement

V ol. 19 N o. 6 D ec. 2010

文章编号: 1005 2542( 2010) 06 0684 05

中国邮递员问题的整数规划模型
冯俊文
( 南京理工大学 经济管理学院, 南京 210094)

摘要 基于无向图的传统中国邮递员问题, 给出了相应的显式整数规划模型, 应用整数规划软件包求 解可以方便地确定相应问题的最优投递路线, 进一步地, 讨论了一类基于有向图的广义中国邮递员问题, 给 出了相应的显式整数规划模型; 并研究了随机中国邮递员问题, 建立了相应的确定型等价模型。举例说明了 各种模型的有效性。最后, 讨论了中国邮递员问题的可能推广及其建模问题。 关键词: 中国邮递员问题; 整数规划; 最优化模型; 赋权图 中图分类号: F 224. 3 文献标识码: A

Integer Programming Modeling for Chinese Postman Problems
FEN G J un w en
( Scho ol of Econom ics and M anagement, Nanjing U niv ersity of Science and T echno logy , N anjing 210094, China) Abstract As far as t he t radit ional Chinese Postm an P roblem ( CP P ) is concerned, based o n t he discus sions in t he undirect ed and direct ed graphs respectively , t he co rresponding int eger pro gramm ing m odels ar e proposed, some numerical ex am ples are g iv en t o demo nstr at e the ut ility o f t he models. Furt her more, t he mo dels are ex t ended to t he case w ith st ochast ic w eight s ( the corresponding problem is called Sto chast ic Chinese P ost m an P roblem) . F inally, some possible generalizat ions o f the Chinese Postm an Problem ar e discussed briefly . Key words: chinese po st man problem ; int eg er prog ramming; optim al model; w eight ed g raph 关于邮递员 最优投递路线问题最早 是由管梅 谷[ 1] 首先提出并进行研究的, 国际上现在统称之为 中国邮递员问题。管梅谷给出了这一问题的奇偶点 图上作业法。Edmonds 等
[ 2]

主要是从图论角度展开的, 给出的多数都是各种启 发式算法或递推算法 [ 4 12] 。本文从数学规划的角度 进行研究。数学 规划建模具有 借助软件包求解 方 便、 易于修改和推广等多方面的优点, 即使对于大型 问题也易于建模分析和解决的优点。

给出了中国 邮递员问
[ 3]

题的改进算法, 较前者的计算更为有效。管梅谷 对有关中国邮递员问题的研究情况进行了综述。

早期关于中国邮递员问题的讨论总是基于无向 图展开的, 事实上, 由于单行线或上下行路线的坡度 等原因, 这一问题有时必须借助于有向图来进行研 究和解决。到目前为止, 对中国邮递员问题的研究
收稿日期: 2009 08 07 修订日期: 2010 01 25

1

传统中国邮递员问题的建模

传统的中国邮递员问题可以概述如下: 一个邮 递员每次送信要从其所在的邮局出发, 走遍所负责 投递范围内的每条街道, 完成送信任务后回到原来 的邮局, 应该选择怎样的路线行走, 才能使得所走的 总路程数最小。把该问题抽象成图论问题就是给定 一个连通图 G( V , E ) , 其中: V = { V 1 , V 2 , !, V n } 是 顶点的集合, 表示街道交汇的地方; E 是顶点间边的

基金项目: 国家自然科学基金资助项目( 79870030) 作者简介: 冯俊文( 1960 ) , 男, 教授, 博士生 导师。研究 方向 为 管理决策分析。E mail: f eng junw en8@ h ot m ail. com

第6期

冯俊文: 中国邮递员问题的整数规划模型

685

集合, 表示街道, 即 E = { eij = ( V i , V j ) ; 顶点 V i 与 V j 间有边 e ij } , 每个边 eij ? E 上有非负权重 w ( e ij ) = w ( V i , V j ) , 表示边即街道的长度。问题是要确定 G 的一个子图( 是一个圈) , 它过每条边至少 1 次, 而 且使得该圈的总权( 即图上各边的和) 最小。 从图论知识[ 13 14] 知, 若 G 不含有奇点( 即相邻 边的个数为奇数) , 则 G 有圈, 它过每边 1 次且仅仅 1 次, 所以这个圈就是所要求的圈。若 G 含有奇点 ( 即相邻边的个数为奇数) , 则 G 的任一过每边至少 1 次的圈, 必在某些边上通过多于 1 次。若在边 e 上通过了 k 次, 设 e ij = ( V i , V j ) , 就在 V i 与 V j 之间 添加 k - 1 条新边, 并令这些条新边的权 都等于边 eij 的权, 称这些新边为 eij 的添加边。显然, 若边 e 上 的添加边多余 1 条, 那么去掉其中偶数条后, 得到的 图中任一过每边至少 1 次的圈的总权不会增大。因 此可以假定每边上添加边的个数至多 1 条。这样, 寻找邮递员最优投递路线的问题就可以归结为如下 图论问题: 给定连通图 G( V , E ) , 每条边 e= ( V i , V j ) ? E 对应的顶点 V i 和 V j 之间添加 1 条边 e#= ( V j , V i ) , 得到边数双倍于 G 的另一个连通图 G#( V , E#) , 求 E1
e ? E1

?
j

x j, i -

s. t .

( j , i) ? E #

j ( j , i) ? E#

?

x i, j = 0,

i = 1, 2, !, n !( i , j ) ? E !( i , j ) ? E#

x i, j + x j , i % 1, x i, j = 0 或 1,

这一模型不仅可以用于求解中国邮递员问题, 而且可以确定相应的最 优投递路线: 如 x i, j = 1, 即 表示邮递员应该从 V i 沿着边( 即街道) e ij 到 V j 。

2

广义中国邮递员问题及其建模
上节所述的邮递员问题, 假定了邮递员投递范

围内的每条街道的上行和下行是无差别的, 而在实 际信件的投递过程中可能不是这样的, 如遇到单行 线街道、 街道有一定的坡度、 街道两边不能单行中同 时投递等。这样的邮递员问题称之为广义的中国邮 递员问题。这一广义的中国邮递员问题可以抽象为 一个有向图问题。 类似于前面所述的邮递员问题( 称为传统的中 国邮递员问题) , 广义的邮递员问题可以叙述为: 给 定一个连通有向图 G ( V , E ) , 每个弧 e 上有非负权 w ( e) , 需要寻找 G 的一个回路, 它过每个弧至少 1 次, 且使得总权为最小。 对于广义的中国邮递员问题, 添加弧的个数至 多 1 条有时已经不再可行, 即需要多条添加弧, 才能 使对应的连通有向图 G 的任一顶点的进向弧 数与 出向弧数 相同, 从 而使 G#( V , E#) 存在 回路 ( E 回 路) 。在此, 如 e= ( V i , V j ) ? E, 则称弧 e 是顶点 V j 的进向弧, 同时也是顶点 V i 的出向弧。可以证明, 如 G( V , E) 的顶点数为 n, 则每条弧上至多增加( n1) 条添加弧, 即可实现各顶点的进向弧数与出向弧 数相等。 根据以上分析, 对于 G ( V , E ) 的每条弧 ei, j ? E 定义一正整数变量 x i, j , 表示弧 eij 上增加 了( x i, j 1) 条添加弧, 由此形成另一个有向图 G#( V , E#) 。类 似于上节的分析, 可以有如下广义中国邮递员问题 的显式整数规划模型( GCPP) : min
( i, j ) ? E

E#, E 1

E 使图 G 1 ( V , E 1 ) 不 含奇 点且 总权

?

w ( e) 为最小。 为叙述方便, 若 e= ( V i , V j ) ? E, 则记为 ei, j ? E

或( i, j ) , 而相应的添加边为 ej , i , 与边 ei, j ? E#相对 应, 设定一 0- 1 整数变量 x i, j 。若 e i, j ? E#, 即称边 是从 V i 到 V j 的, 或称为弧。这样, 就可以把无向图 理解为有向图。每个 E 1 惟一对应一组 x i, j 的值, 反 之亦然。可以借助变量 x i, j ( i= 1, 2, !, n; j = 1, 2, !, n) 来定义最优投递员问题的约束如下: ( 1) 过每边至少 1 次且添加边至多 1 条, E 1 对 应的所有的 x i, j 的值( 称为 E 1 的值系) 满足: 对 !ei, j ? E, x i, j + x j , i %1 ( 2) 图 G 1 ( V , E 1 ) 不含奇点, 即对于任意一个顶 点 V i , 有进向弧, 必有与之等量的出向弧:

?x
j &i

j, i

-

?x
j &i

i, j

= 0

?

w i, j x i, j x j, i j ( j , i) ? E

这一问题的 目标是使 得 G 1 ( V , E 1 ) 的总 权最 小, 即 min
( i, j ) ? E#

s. t .

j ( j , i) ? E

?

?

x i, j = 0,

i = 1, 2, !, n !( i , j ) ? E

?

w i, j x i, j

x i, j = 1, 2, !, 或 n, 员问题的最优投递路线。

其中, w i, j 为边 e i, j 上的权, w j , i = w i, j 。 这样, 就得到中国邮递员问题的显式整数规划 模型( CP P) 如下: min
( i, j ) ? E#

通过这一模型的求解, 可以得到广义中国邮递

?

3

数值例示求解
例 1 考虑图 1 所示的中国邮递员问题:

w i, j x i, j

686













第 19 卷

( a) 无向图

( b) 有向图

图1

传统中国邮递员问题

根据前面的模型讨论, 这一数值例示邮递员问 题对应的整数规划模型如下: min 2( x 1, 8 + x 8, 1 ) + 4( x 8, 7 + x 7, 8 ) + 5( x 1, 2 + x 2, 1 ) + 3( x 8, 9 + x 9, 8 ) + 3( x 6, 7 + x 7, 6 ) + 6( x 2, 9 + x 9, 2 ) + 4( x 9, 6 + x 6, 9 ) + 5( x 3, 2 + x 2, 3 ) + 4( x 9, 4 + x 4, 9 ) + 4( x 5, 6 + x 6, 5 ) + 9( x 3, 4 + x 4, 3 ) + 4( x 4, 5 + x 5, 4 ) x 2, 1 + x 8, 1 - x 1, 2 - x 1, 8 = 0 x 1, 2 + x 9, 2 + x 3, 2 - x 2, 1 - x 2, 9 - x 2, 3 = 0 x 2, 3 + x 4, 3 - x 3, 2 - x 3, 4 = 0 x 3, 4 + x 9, 4 + x 5, 4 - x 4, 3 - x 4, 9 - x 4, 5 = 0 x 6, 5 + x 4, 5 - x 5, 6 - x 5, 4 = 0 x 7, 6 + x 9, 6 + x 5, 6 - x 6, 7 - x 6, 9 - x 6, 5 = 0 x 6, 7 + x 8, 7 - x 7, 6 - x 7, 8 = 0 s. t . x 1, 8 + x 7, 8 + x 9, 8 - x 8, 1 - x 8, 7 - x 8, 9 = 0 x 2, 9 + x 4, 9 + x 6, 9 + x 8, 9 - x 9, 2 x 9, 4 - x 9, 6 - x 9, 8 = 0 x 1, 8 + x 8, 1 %1, x 1, 2 + x 2, 1 %1, x 6, 7 + x 7, 6 %1, x 9, 6 + x 6, 9 %1, x 9, 4 + x 4, 9 %1, x 3, 4 + x 4, 3 %1, x 8, 7 + x 7, 8 %1 x 8, 9 + x 9, 8 %1 x 2, 9 + x 9, 2 %1 x 2, 3 + x 3, 2 %1 x 5, 6 + x 6, 5 %1 x 4, 5 + x 5, 4 %1,
[ 14]

图2

广义中国邮递员问题

相应的广义中国邮递员问题的整数规划模型如 下: min 2x 1, 2 + 8x 1, 4 + x 3, 1 + 6x 2, 4 + 7x 4, 3 + x 2, 5 + 5x 5, 4 + x 6, 4 + 2x 7, 2 + 9x 3, 7 + 4x 6, 7 + 3x 6, 5 + 2x 8, 5 + x 5, 9 + 6x 9, 6 + 3x 7, 9 + x 7, 10 + x 10, 9 + 7x 9, 8 + 9x 8, 11 + 2x 11, 9 + 4x 10, 11 x 3, 1 - x 1, 2 - x 1, 4 = 0 x 1, 2 - x 2, 4 - x 2, 5 = 0 x 4, 3 - x 3, 1 - x 3, 7 = 0 x 1, 4 + x 2, 4 + x 5, 4 + x 6, 4 + x 7, 4 - x 4, 3 = 0 x 2, 5 + x 8, 5 + x 6, 5 - x 5, 4 - x 5, 9 = 0 s. t . x 9, 6 - x 6, 5 - x 6, 4 - x 6, 7 = 0 x 6, 7 + x 3, 7 - x 7, 4 - x 7, 9 - x 7, 10 = 0 x 9, 8 - x 8, 5 - x 8, 11 = 0 x 5, 9 + x 10, 9 + x 11, 9 + x 7, 9 - x 9, 6 - x 9, 8 = 0

x i, j = 0 或 1

x 7, 10 - x 10 , 9 - x 10, 11 = 0 x 10, 11 + x 8 , 11 - x 11, 9 = 0 x i, j = 1, 2, !, 或 10 应用相同的整数规划求解软件, 求解这一模型 得到下列最优解: x 1, 2 = 2, x 1, 4 = 1, x 3, 1 = 3, x 2, 4 = 1, x 4, 3 = 5 x 2, 5 = 1, x 5, 4 = 1, x 6, 4 = 1, x 7, 4 = 1, x 3, 7 = 2 x 6, 7 = 2, x 6, 5 = 1, x 8, 5 = 1, x 5, 9 = 2, x 9, 6 = 4 x 7, 9 = 1, x 7, 10 = 2, x 10, 9 = 1, x 9, 8 = 2, x 8, 11 = 1 x 11, 9 = 2, x 10, 11 = 1 最小权重为 159。假定邮局在顶点 V 1 , 则有如 下投递路线:

应用整数规划求解工具 QSB

, 求解得到这一

问题的最优解, 如: x 1, 2 = x 2, 1 = x 1, 8 = x 8, 1 = x 8, 7 = x 9, 8 = x 7, 6 = x 2, 9 = x 3, 2 = x 6, 9 = x 4, 3 = x 9, 4 = x 5, 6 = x 6, 5 = x 5, 4 = x 4, 5 = 1, 其他 x i, j = 0, 最小权重为 68。 假定邮局在顶点 V 1 , 则有如下最优投递线路: e1, 2 ? e2, 9 ? e9, 8 ? e8, 7 ? e7, 6 ? e6, 5 ? e5, 6 ? e6, 9 ? e9, 4 ? e4, 5 ? e5, 4 ? e4, 3 ? e3, 2 ? e2, 1 ? e1, 8 ? e8, 1 注意, 这一问题的最优投递路线不惟一。同理 可以求得邮局从 任何一顶点出发时的最 优投递路 线。 例2 考虑图 2 所示的广义中国邮递员问题。

第6期

冯俊文: 中国邮递员问题的整数规划模型

687

e1, 2 ? e2, 4 ? e4, 3 ? e3, 1 ? e1, 4 ? e4, 3 ? e 3, 1 ? e1, 2 ? e2, 5 ? e5, 4 ? e4, 3 ? e3, 7 ? e7, 10 ? e 10, 11 ? e11, 9 ? e9, 8 ? e8, 11 ? e11, 9 ? e9, 6 ? e6, 5 ? e5, 9 ?e9, 8 ? e8, 5 ?e5, 9 ? e9, 6 ?e 6, 7 ? e7, 9 ? e9, 6 ? e6, 4 ? e4, 3 ? e3, 7 ? e7, 10 ? e10, 9 ? e9, 6 ? e6, 7 ? e7, 4 ? e4, 3 ? e3, 1 这是一个回路。类似可以确定邮局在任一顶点 时的最佳投递路线。这一最优投递路线是根据模型 的最优解, 采用类似接龙游戏的方法找出的。这里 需要注意的是, 如某 x i, j 的值大于 1, 意味着该弧要 重复走。所 有 x i, j 的和应 等于所 走的 所有街 道数 ( 包括重复走的) 。

平。如果 诸权 重均服 从正 态分 布而 且相互 独立, w i, j 服从 N ( 1 NCPP ( ) min s. t . w w( i, j ) ? E# i, j

,

2 i, j

) , 则 1 CPP ( ) 和 2 CP P( w ) 分

别等价于下列 2 个数学规划:

?

i, j

x i, j - F- 1 ( )

( i, j ) ? E#

?

2 i, j

x2j %0 i,

CPP 的约束条件 2 NCPP ( w ) max s. t . w( i, j ) ? E#

?

i, j

x i, j - F- 1 ( )

( i, j ) ? E#

?

2 i, j

x2j %0 i,

4

随机中国邮递员问题及其建模
上述讨论的传统的和广义的中国邮递员问题都

CPP 的约束条件 其中: F( X ) 为标准正态累积分布函数; F - 1 ( y ) 为其 逆函数。进一步地, 可分别等价于如下 2 个数学规 划问题: 1 NCPP ( )# min
( i, j ) ? E#

假定与边或弧相联系的权重是确定型的常数。实际 中经常遇到权重非固定的情况, 如考虑的权重是该 街道上所花费的投递时间, 这一参数往往不是常数, 每次投递所花费 的时间会由于邮件量的 多少而变 动, 但一般会遵循某种变化形式, 即权重是具有某种 分布的随机变量, 这时可以称对应的问题为随机中 国邮递员问题。处理传统中国邮递员问题的奇偶点 图上作业法
[ 1]

?

i, j

x i, j + F- 1 ( )

( i, j ) ? E #

?

2 i, j

x 2i, j = w

s. t . CPP 的约束条件 w2 NCPP ( w )# max
( i, j ) ? E #

?

i, j 2 i, j

x i, j
2 i, j

及其改进算法

[ 2]

对这一随机问题都无

能为力, 但借助于本文建立的整数规划模型, 应用 随机规划理论 [ 16 18] , 可以很方便地进行处理。 随机问题的处理方法有多种, 如期望值法、 机会 约束法、 最优值分布法、 相关机会约束法、 多阶段( 如 两阶段) 法。本文在此处仅讨论机会约束法, 其核心 是概率约束条件的确定型等价处理。其他方法可以 按照随机规划理论类似处理, 在此略去。 注意到, CPP 或 GCP P 的约束中都不含有权重 参数, 因此, 处理权重随机的问题只需要将目标函数 做相应的确定型等价处理即可。权重随机时, 目标 函数 也是 随机 变 量, 根 据随 机 规划 理 论, 随机 的 CPP 问题可以转化为如下 2 个确定型等价模型 1 CP P( ) min s. t . 2 CP P( w ) max P s. t.
( i, j ) ? E# [ 17]

( i, j ) ? E#

?

= F ( )

-1

x

s. t. CPP 的约束条件 其中, 注意到 F
- 1

( )是

的单调递增函数。

对于其他类型的随机问题也可以类似地进行分 析。注意上述规划是非线性的, 因此需要借助非线 性整数规划的求解工具和软件或两阶段法 [ 18] 进行 求解, 大型问题也可以借助于现代智能优化算法进 行求解[ 19] 。 对于广义中国邮递员问题也可以类似讨论相应 的随机问题, 在此从略。

5

结 语
本文基于传统的中国邮递员问题, 建立了这一

:

w P
( i, j ) ? E#

?

问题的显式整数规划模型, 并将之推广到基于赋权 w i, j x i, j ( w % 有向图的广义邮递员问题和权重不确定的随机邮递 员问题。另外的 推广是考虑权 重是模糊型或灰 色 型、 粗糙型、 信度型的中国邮递员问题, 根据相应的 不确定性内涵, 对于目标函数进行相应的确定型转 化。 本文讨论的是单目标问题, 如果考虑多目标中 国邮递员问题, 数学规划灵活、 机动、 易于修正和变 形的特点, 可以用来非常方便地处理这一可能的拓 展问题。

CPP 的约束条件

?

w i, j x i, j ( w %

CP P 的约束条件 其中, 1 CPP( ) 指对固定的 处, 称 求解 x i, j 以及权重 w 。 而 2 CPP( w ) 指对固定的权重 w 求解 x i, j 和 。此 为权重 w 的可行度, w 为总权重的希望水

688








[ 10]





第 19 卷

参考文献:
[ 1] [ 2] 管梅 谷. 奇偶 点图 上作 业法 [ J] . 数 学学 报, 1960, 3 ( 10) : 263 266. Edmo nds J, Jonhso n E L . M atching, euler to ur s and chinese postman [ J ] . M athematical P ro gr amming, 1973, 35( 5) : 88 124. [ 3] [ 4] [ 5] [ 6] 管梅谷. 中国 投递员问题综述[ J] . 数学研究与评论, 1984, 4( 1) : 113 119. 舒兴明. 利用 F1oy ed H ung ary 法求解中 国邮路问 题 [ J] . 华南热带农业大学学报, 2003, 9( 2) : 32 35. 吴振奎, 王全 文, 刘振航. 中国邮路问题的一个解 法 [ J] . 运筹与管理, 2004, 12( 3) : 44 47. 覃太贵, 杨 磊. 混合中国邮递员问题的扰动 恢复讨 论及其一种启发 式算 法[ J] . 湖北 师范 学院 学报 ( 自 然科学版) , 2005, 25( 02) : 29 33. [ 7] [ 8] 李 玮, 王 雷. 中国 邮递 员问题 的 DN A 计算 [ J] .

韩爱丽, 朱大铭. 基于一种新的边权编码方案的中国 邮递. 员问题的 DN A 计算模型[ J] . 计算机研 究与发 展, 2007, 14( 6) : 1053 1062.

[ 11] [ 12] [ 13] [ 14] [ 15]

金 费 田

毅. 对) 中国 邮递员 问题? 的数 理分析 [ J] . 科技 蓉, 崔杜武. 中国邮 递员问题 的动态规划 算法研 丰, 马仲蕃. 图与网络 流理论[ M ] . 北京: 科学出

经济市场, 2009, 15( 03) : 3 5. 究[ J] . 计算机研究与发展, 2005, 12( 02) : 17 20. 版社, 1987. 胡运权. 运筹学教 程[ M ] . 2 版. 北京: 清 华大 学出 版社, 2003. Chang Y ih L ong, Robert S Sulliven. Q uantitat ive sy stems for business plus, v ersion 2. 0 [ M ] . N ew Yo rk: P rentice Ha ll, Inc. , 1991. [ 16] [ 17] G reetha S, N air K P K. O n stochast ic spanning tree pr oblem[ J] . N etw orks, 1993, 23( 8) : 675 679. L iu Boding. T heo ry and pr act ice o f uncertain pro g ramming ( seco nd editio n) [ M ] . Beijing : U T L AB, 2007. [ 18] [ 19] L iu Boding. U ncertain theo ry ( third editio n) [ M ] . Beijing: U T L A B, 2007. 王 凌. 智能优化算法 及其应 用[ M ] . 北京: 清 华大 学出版社, 2004.

计算机应用, 2009, 19( 07) : 1880 1883. 李念祖. 关于中 国邮 递员问 题的 最优 完全子 图算 法 [ J] . 上海师范大学学报( 自然科学版) , 2006, 25( 4) : 26 29. [ 9] 吴 杰. 求解中国邮递 员问题 的一种思 路[ J] . 科 技 资讯, 2007, 16( 14) : 211 212.

下期发表论文摘要预报

考虑战略顾客行为时的两阶段报童模型
黄 松, 杨 超, 张 曦
( 华中科技大学 管理学院, 武汉 430074)
摘 要: 在季节 性产品销售环境下, 考虑由一个零售商和可以无限细 分的顾客群体组成的 两级供应 链系统, 研究了

考虑战略顾客行为时两阶段报童模型的库存与定价 决策问 题。传统的 两阶段 报童模 型没有 考虑战 略顾客行 为对 于零售商的库存和定价决策的影响, 实际上顾客在购买时 将会考 虑产品 在销售 期内完 整的价格 路径, 以最大 化期 望效用为目标确定最优购买时机, 而零售商则以最大化期望收益为目标确定最优 订货数量和 设定价格 路径。引入 理性预期均衡分析, 研究了零售商和战略顾客双方同时行 动静态 博弈时 的理性 预期均 衡解, 并进一 步分析了 零售 商承诺销售价格不变时的理性预期均衡解, 最后, 通过两组 数值算例对模型进行了说明。


更多相关标签: