（计算机软件与理论专业论文）一维拓扑结构下的最优装卸路线问题.pdf

中山大学硕士学位论文 一维拓扑结构下的虽优装卸路线问题 一维拓扑结构下的最优装卸路线问题 计算机软件与理论 硕士生：李伟星 指导教师：郭嵩山 摘要 本论文研究的最优装卸路线问题是指如何安排若干有固定负载能力的车辆 来回装载点和卸载点完成装卸需求，并使得所有车辆中的最长运输时间最小。在 文中用数学模型定义了最优装卸路线问题。完整给出了一维拓扑结构下该问题在 不同情况下的复杂度证明。对“线形拓扑结构下单车辆没时间限制”的情况及“树 状拓扑结构下单车辆单负载能力没有时间限制”的情况，给出了多项式时间复杂 度的求最优方案算法。 关键字：线性结构、树状结构、装载和卸载、回路、n p h a r d 问题 中山大学硕士学位论文 一维拓扑结构下的最优装卸路线问题 t h es h o r t e s tr o u t ec u ta n df i l lp r o b l e mi no n ed i m e n s i o ns t r u c t u r e c o m p u t e rs c i e n c e n a m e ：w e i x i n gl i s u p e r v i s o r ：s o n g s h a ng u o a b s t r a c t i nt h i sp a p e r ，w es t u d yt h es h o r t e s tr o u t ec u ta n df i l lp r o b l e m ( s r c f p ) w h e r es o m e v e h i c l e sw i t hf i x e dc a p a c i t i e st r a v e lb e t w e e nc u ta n df i l lp o i n t st of i n i s ha l lc u ta n df i l l r e q u i r e m e n t ss ot h a tt h em a x i m u m o fv e h i c l e s t r a v e lt i m ei sm i n i m i z e d w es t a t ea n d c l a s s i f yt h es r c f pa n dp r e s e n tac o m p l e t ev i e wo fi t sc o m p u t a t i o n a lc o m p l e x i t i e s w i t hn p h a r d n e s sp r o o ff o ro n ed i m e n s i o nt o p o l o g i c a ls t r u c t u r e m o r e o v e r , s o m e s i m p l ec y c l e b a s e do p t i m i z a t i o n m e t h o d si s p r o p o s e dt o s o l v et h es r c f pi n p o l y n o m i a lt i m ec o m p l e x i t y ，f o rt h ec a s eo fs i n g l ev e h i c l ei nl i n e a rs t r u c t u r ew i t h o u t t i m ew i n d o wc o n s t r a i n ta n dt h ec a s eo fs i n g l ev e h i c l ew i t hu n i tc a p a c i t yi nt r e e s t r u c t u r ew i t h o u tt i m ew i n d o wc o n s t r a i n t k e y w o r d ：l i n e a rs t r u c t u r e 、t r e es t r u c t u r e 、c u ta n df i l l 、c y c l e 、n p - h a r d 中山大学硕士学位论文一维拓扑结构下的最优装卸路线问题 一、引言 当今的全球的商业世界面临两个主要的问题：( 1 ) 考虑原料、劳动力、管理 和风险等多方面因素，选择一个合适的地点建立供应站：( 2 ) 如何操作从供应商 到消费者的物流，使得运输费、进出口税等总耗费最小。 考虑如下的应用场景：一个庞大的建筑计划通常需要对地形作一定修正以满 足建筑需要，因此要从某个地点运大量泥土到另一个地点。而从一个地方挖土、 运输到倾卸点进行填补，无论从挖掘机的操作或维护来考虑，都是一笔不可忽视 的开销，它往往是建筑计划预算的一个重要组成部分。显然一个有多余泥土的高 地可以看作是一个装载点，一个需要泥土填补的洼地可看作是一个卸载点。当把 装载点处多余的泥土全部移到卸载点就完成了地形修整的目的了。为了节省建筑 计划的总体预算和加快计划进度，我们会尝试选择一种最优方案使得泥土运输路 线的时间耗费最小。 最短装卸路线问题可作为一种基本的模型应用至0 上述商业问题。假设有若干 装载点和卸载点，装载点为供应商，卸载点为消费者。我们也有一车队负责装载 点和卸载点之间的货物运输。车队的车辆有固定负载能力，从车站出发，完成任 务后回到车站。最短装卸路线问题的目标函数就是为每一辆车安排一路线，在所 有车合作下完成装卸需求，并使得所有车的路线中的最长距离最短。 s r c f p 是有负载限制的递送车辆调度问题 1 的变形，而当车辆数为1 ，每个 装卸点的装卸量为1 时，则是有负载限制的收取递送旅行售货员问题( c t s p p d ) 。 目前对于c t s p p d 有r e n a u d 2 使用启发式算法或a n j l y 3 多项式时间的近似算法 获得较好结果。而对于s r c f p 目前较好的研究结果，h e n d e r s o n 4 尝试了启发式 模拟退火算法处理单车辆单负载能力的情况，a n d r e wl i r a 5 尝试了禁忌搜索混 合模拟退火算法处理多车辆单负载能力的情况。在实际应用中，一些与s r c f p 模 型相关的辅助设计系统 6 7 的路线设计部分还需要人为设定的启发式规则或 专家系统。 本论文主要研究工作则是在s r c f p 在线形拓扑结构初步研究 8 的基础上，首 次对该问题在一维拓扑结构下的各种情况进行详细分类分析，利用n p 完全问题理 论 9 的一些基本原理，对n p 完全问题的情况给出证明，对不是n p i 司题的情况设 计出相应的多项式时间算法。 中山大学硕士学位论文 一维拓扑结构下的最优装卸路线问题 二、问题定义及主要研究结果 定义： v = v 1 ，v 2 ，v k ) 运输车辆集合，v i 也用于表示车辆的起始位置 l v = l v l ，l v 2 ，l v k 车辆的最大负载能力 c = 。1 ，c 2 ，) 装载点集合，c i 也用于表示装载点所在位置 l c = l c l ，l c 2 ，l c m ) 装载点的待装载总量( 1 c i 0 ，1 - i = m ) f 一 f 1 ，f 2 ，f n ) 卸载点集合，f i 也用于表示卸载点所在位置 l f = l f , ，l f 2 ，l f b 卸载点的待卸载总量( i f i o ，1 - i = m ) l c i + 善圻= o 装载量与卸载量的平衡限制 d ( p ，q ) 位置p 于位置q 之间的距离( 对称，位置包括装卸载 点位置和车辆起始位置) r i - - ( r i ，r ：，l - j 。) 车辆i 的装卸路线，l = i = k 满足： r r i 。，= v i r ie c uf ( 1 1 1 的装卸问题是p 问题。 显然d 1 = 2 磊。( n j r o w , i i l v l + d 7 ( f ) ) + 2 二( f ) 是该问题最优解的下界。 算法2 使用类似算法1 中的思路，求出每个s e g m e n t 的装卸回路，然后把 它们连接成最终装卸路线。 在车辆负载能力 1 的情况下求s e g m e n t 装卸回路的算法( 如图3 - 4 所示) ： 1 按l v 大小把s e g m e n t 的f l o w 分成若干连续的部分，最多分出不超过 ( m + n ) t m a x f l o w ；) l v 段，该步为复杂度为o ( ( m + n ) + m s x n o w ； l v ) 。 2 对于每一连续的部分，对应f l o w 大小可以用单圈回路实现装卸需求，找 一个单圈复杂度为o ( m + n ) 。 3 把2 中求得的所有单圈回路全部整合在一起，两个单圈的连接处可以任 选空载路线上重合的位置，每次连接的复杂度为o ( m + n ) 。 显然该算法2 求得的解和最优解下界一致，复杂度为 o ( ( n + m ) “m a x f l o w i l v ) 。 = 嬲 第二黟= = = = = = 了甄：夏：= = = 叠= 忑动 笫三步 一盥；一3 o 一! 塑! 一3 甄费 图3 - 4 中山大学硕士学位论文 一维拓扑结构下的最优装卸路线问题 定理3 ：车辆数为1 ，有时间条件限制的装卸问题是n p h a r d 问题。 引理：对于一辆车有时间限制的一般装卸问题，寻找可行解已是n p - h a r d 问题。 证明： 考虑如下特殊情况( 如图3 5 ) 有2 n + 1 个卸载点，五( 1 a i s2 n ) 分布在h 的右边任意位置。令 t 2 蓍d p - ，五) 。，2 一“和u 在同一位置。五1 s s 知的可访问时间为 o , 2 t ， ，2 。的可访问时间为 t t 。坑一1 ( 1 主f 主2 n + 1 ) 。 只有一个装载点c 。，i c l ；2 h + 1 ，可访问时间为 0 ，2 t 。 v e h i c l e 1 f i l l p o i n t 【t ，1 】 1c u tp o i n t 0 ，2 1 3 图3 - 5 如果要完成装卸需求，必须在t 时刻出现在h 位置。所以必须把正( 1 c i s 2 n ) 分 成两部分，一部分在 0 ，z 时段访问，另一部分在 t ，2 t 时段访问，如图3 - 6 。 因为t 2 善脚- ，五) ， 图3 - 6 群4 磊盹舻t _ 24 2 ) 。 此时问题变成如何将一组数分成两部分，使得它们的总和相等，即经典的分组问 中山大学硕士学位论文 一维拓扑结构下的最优装卸路线问题 题( p a r t i t i o np r o b l e m ) 。而分组问题是n p 完全问题，所以对于一辆车，有时 间限制的一般装卸问题，寻找可行解也是n p h a r d 问题。找最优解也是n p h a r d 问题。 推论i ：树状结构下，车辆数为l ，有时间限制的一般装卸问题是n p - h a r d 问题。 定理4 ：车辆数为2 的装卸问题是n p _ h a r d 问题。 考虑如下特殊情况( 如图3 - 7 ) 两车的位置为0 点，l v l = l v ：= 1 有n 个装载点，位置皆为0 ，l c i 一1 ( 1 s i s ”) 有n 个卸载点，位置为任意正数，坑一1 ( i s i s n ) v i & v 2 c 1 c n ( nc u tp o i n t s ) 问题归结为如何将f 分成两部分f i 和f 2 ( 互n e 一声，墨u e - f ) ，使得 腻im a x 协。叩a ，善，2 d ( v2 , f j ) 又因为磊，。d ( ) + ，；，2 d ：，小，荟，d ( ， ) ，所以由( 1 ) 嗍：m i n 慨即”，卜，善2 d ( v2 , f j ) l 即给出n 个数d p ，五) ，求如何把它们分成两部分，使得两部分数的总和的差的 推论2 ：树状结构下，车辆数为2 的装卸问题是n p h a r d 问题。 9 中山大学硕士学位论文 一维拓扑结构下的最优装卸路线问题 四、树状结构下的复杂度分析 定义： 任意两个位置之间有且仅有一条路径的装卸问题称之为线性结构的装卸问 题。( 该章如无特殊说明，皆指树状结构的情况下) 定理5 ：车辆数为1 ，负载能力为1 的装卸问题是p 问题。 引理5 1 ： 当树深为1 的情况，即除了根结 图4 2 1 0 中山大学硕士学位论文 一维拓扑结构下的最优装卸路线问题 第二步：计算所有非叶子结点之间的流量f l o w ，该步复杂度为0 ( m + n ) 。 舶w ( a ，b ) _ 剜。；溉+ 删溉 口到c i 的路不经过b口到f ；的碚不经过) 图4 3 第三步：找出所有以非叶子结点为根，深度为1 的树，该步复杂度为o ( m + n ) 。 图4 - 4 第四步：用引理i 中的方法，求出第三步中找到的所有树的的最优装卸回路( 如 图4 - 5 ) 。以结点i 为根，深度为l 的树的最优装卸回路简称i 的回路。该步复 杂度为o ( ( m + n ) + m a x c ；f ，j f ，i j ) 。 中山大学硕士学位论文 一维拓扑结构下的最优装卸路线问题 田 121 墨1 21 3 曰 2 垒2l2 4 2 12 42 8 曰 3l3 旦3 13 1 0 田4 亘4 兰4 鱼4 量4 王4 2 图4 - 5 第五步：把第四步中找到的所有回路连接成单一的装卸回路。 引理5 2 ：假如i 的回路和j 的回路有公共边，当且仅当结点i 和结点j 在原树中 相邻。而i 的回路出现j i j 的子序列次数等于j 的回路出现i j i 的子序列的次数， 皆为i t l o w o , j ) 1 次。 因此i 的回路与j 的回路可按如下规则进行连接合并( 如图4 - 6 ) ： 依次把j 的回路中按j i j 子序列分割的第k 段路径插入i 回路中的第k 个j 中就得 到合并后的回路。因为是回路，哪里是第1 段路径、第1 个j 并不重要。 其实也可以看作是依次把i 的回路中按班子序列分割的第k 段路径插入就回路 中的第k 个i 中，两个操作的效果是一样的。 c y c l e i ： 里兰! ! 兰二二二二兰 唧 n = l f l o w ( i , j ) l c y c l e j ： 塑兰塑兰二二二二! ! d c o m b i n e ( c y c l ei , c y c l e j ) 。固7 国。国d ! 二! ! 二! 二! ：二二二二二! 二竺 图4 - 6 假如有h 的回路与j 的回路存在公共边，而根据以上的连接规则，j 的回路和j 的回路合并后依然存在l f l o w 0 0 ) 阶h j h 的子序列，因为连接操作只破坏了i j i 和j i j 子序列。 中山大学硕士学位论文 一维拓扑结构下的最优装卸路线问题 引理5 3 ：无论连接顺序如何，第四步找到的所有回路能连接成单一的装卸回路。 对应前面的例子，一系列连接操作如下： c y c l e2 = 2 生212 生212 4 2 8 c y c l e4 = 堡542 垒6 生247 垒星 c o m b i n e ( 2 ，4 ) = 垒6 生量1 互生7 生呈l 互生5 生呈8 c o m b i n e ( 2 ，4 ) = 24 642 z4742l245 428 c y c l e1 = l21 31213 c o m b i n e ( ( 2 ，4 ) ，1 ) = 3u 4 74 址3 地454 28 24 6 c o m b i n e ( ( 2 ，4 ) ，1 ) = 2l31 24 7421312 4 54 282 4 6 c y c l e3 = 31393131 0 c o m b i n e ( ( ( 2 ，4 ) ，1 ) ，3 ) = 曩：麓2 4 74 2u 1 0 245 428 图4 7 回路有m + n 条，要合并m + n - 1 次，合并后的回路长度不超过2 三j c j j + 2 兰蚓，所以 该步复杂度为o ( ( m + n ) 。侄i c 。i + | f i ) ) 。 第六步：把第五步求得的单一回路中的长度为0 的边删去，得到最终回路，该步 复杂度为o ( i c i | + e l i , i ) 。 对应上面的例子，最终回路为242 。 最优性证明： 显然，树状结构下的装卸问题最优方案的下界也是： 观磊。( 1 月o w , i 例( f ) ) + 2 二( f ) 其中f l o w i d l ( i ) 分别为树中第i 条边的流量和长度。 而在算法的第一步中的扩展结点操作对总距离没有影响。在第二、三、四步中每 个深度为一的子树的最优回路经过第i 条边i n o w j l 次。在第五步中，合并过程把 每个子树重复的边进行连接，一直保证合并后的回路里经过第i 条边 t l o w j 次。 第六步也对总距离没有影响。所以该算法求得的可行解是问题的最优解之一。 中山大学硕士学位论文 一维拓扑结构下的最优装卸路线问题 定理6 ：树状结构下车辆数k = i 的装卸问题是n p - h a r d 问题。 考虑如下特殊情况( 如图4 - 8 ) ： n 个卸载点，有1 f is 1 v - 1 s l s n 。一个装载点，1 c - 一善1 f l 。 d f 2 d c 。 c l f j “ i c = i f fl 珏l 图4 - 8 v ) 卸髓 i7 i 。虬州丁中轧v r ： 率辆负载 a qn b 斗s i a + n ( ：i ： d i s t a n e e i = 4 搿 b 。 a 8 0 锄 我们可以对路径做如下修改： 装载蟹 b n 甜黻麟 9 v f 车辆负馥 一o 1 4 一 。 8 vf 一 v 一，。 q，c 一 一，。卧 m 0 最 一 一，挑 中山大学硕士学位论文 一维拓扑结构下的最优装卸路线问题 显然修改并没有违背问题的条件限制，而且也能完成装卸任务，即该路径也是一 个可行解。最重要的是后一路径与前一路径总长度差值为： d i s t a n c e 2 一d i s t a n c e l = 4 d c + 2 d f - 4 d f = 2 4 ( 2 d c - d f ) 2 d c d ( c ，c i ) = o d ( w i ，f i b ) = 01 = h = w i 显然该情况可以归结到图4 - 8 的情况，所以该问题是n p h a r d 问题。 中山大学硕士学位论文一维拓扑结构下的最优装卸路线问题 结语 本论文对一维拓扑结构下的几乎所有各种不同情况的最优装卸路线问题进 行了复杂度分析，并给出部分有效算法。尽管从数学、图论的角度来看，一维的 情况只是该问题的冰山一角，能给出有效算法的更是极简单的情况。但是考虑到 现实情况：大部分的道路分布是属性一维拓扑结构；出于管理成本和操作成 本，一般情况车队中所有车都是选择同一路线，可以把车队整体看作是单车辆； 通常现实车辆的运载能力远小于要运输的对象( 货物、泥土等) 的总量，所以 可以把车辆看作是单位负载能力。所以该论文的研究结果还是具有比较高的实用 价值。 中山大学硕士学位论文 一维拓扑结构下的最优装卸路线问题 参考文献 【1 g m o s h e i o v ，v e h i c l er o u t i n gw i t hp i c k - u p a n dd e l i v e r yt o u r p a r t i t i o n i n g h e u r i s t i c s ，c o m p u t e r sa n di n d u s t r i a le n g i n e e r i n g ，1 9 9 8 ，3 4 ：6 6 9 - 6 8 4 【2 】j r e n a u d ，f f b o e t o ra n dj o u e n n i c h e ，ah e u r i s t i cf o rt h ep i c k u pa n dd e l i v e r y t r a v e l i n gs a l e s m a np r o b l e m ，c o m p u t e r s o p e r a t i o n sr e s e a r c h ，2 0 0 0 , 2 7 ：9 0 5 - 9 1 6 【3 】s a n i l y ，j b r a m e l ，a p p r o x i m a t i o na l g o r i t h m sf o rt h ec a p a c i t a t e dt r a v e l i n g s a l e s m a np r o b l e mw j t hp i c k u p sa n dd e l i v e r i e s ，n a v a lr e s e a r c hl o g i s t i c s ，1 9 9 9 ，4 6 ： 6 5 4 一_ 6 7 0 州d h e n d e r s o n ，d e v a u g h a n ，s h j a c o b s o n ，r r w a k e f i e l da n de c s e w d l ， s o l v i n gt h es h o r t e s tr o u t ec u ta n df i np r o b l e mu s i n gs i m u l a t e da n n e a l i n g , e u r o p e a n j o u r n a lo fo p e r a t i o n a lr e s e a r c h ，2 0 0 3 ，1 4 5 ：7 2 - 8 4 5 】a l i m ，b r o d f i g u e s ，j z h a n g , t a b us e a r c he m b e d d e ds i m u l a t e da n n e a l i n gf o r t h es h o r t e s tr o u t ec u ta n df i l lp r o b l e m ，j o u r n a lo fo p e r a t i o n a lr e s e a r c hs o c i e t y ， 2 0 0 4 【6 】李影刚，徐天亮，多资源点物资发送计算机车辆调度系统模型，物流技术， 1 9 9 9 年第2 期：2 0 2 3 7 】w h a s k e w ，s h a l - j i b o u f i ，m j m a w d e s l e y ，d e p a t t e r s o n ，p l a n n i n gl i n e a r c o n s t r u c t i o np r o j e c t sa u t o m a t e dm e t h o df o rt h eg e n e r a t i o no fe a r t h w o r ka c t i v i t i e s ， a u t o m a t i o ni nc o n s t r u c t i o n 2 0 0 2 ，6 4 3 _ 6 5 3 【8 】8s g u o ，w _ l i ，a l i ma n dew a n g ，t h es h o r t e s tr o u t ec u ta n df i l lp r o b l e mi n l i n e a rt o p o l o g i c a ls t r u c t u r e ，t h