（计算机软件与理论专业论文）车辆路径与三维装箱混合问题3lcvrp的研究.pdf

摘要 论文题目： 专 业： 硕士生： 指导教师： 车辆路径与三维装箱混合问题( 3 l c v r p ) 的研究 计算机软件与理论 王磊 郭嵩山教授 摘要 本文研究了现代物流算法中两个最重要的问题，车辆路径问题和装箱问题， 这两个问题已经被证明是n p h a r d ，单独针对两个问题，目前已经有大量的论文， 但是对这两个问题的综合( 3 l c v l 冲) 目前研究还比较少，该问题由2 0 0 6 年首 次被提出。 本文使用两阶段的禁忌搜索算法来安排车辆路径，并通过局部搜索求解带有 各种约束的装箱问题，最后通过分枝定界法进行后续优化。与现有文献中使用的 装箱方法不同，本文将两种经典的二维装箱方法b o t t o ml e f tw i t hf i l l 和t o u c h i n g p e r i m e t e r 进行了修改，并将其推广到三维情形，在综合考虑了3 l c v r p 中各种 装箱约束下，提出了非常高效的实现算法d e e p e s tb o t t o ml e f tw i t hf i l l 和 t o u c h i n ga r e a 。新的装箱算法的提出大大增加了车辆的空间利用率，大量的实验 结果表明，应用了b o t t o ml e f t 罚i t hf i l l 和t o u c h i n ga r e a 的两阶段禁忌搜索算法 无论在求解质量上还是求解时问上均好于目前己发表的论文，与f u e l l e r e r 等人 的a c o 算法相比，解的质量提高了大约2 9 ，而求解时间大约为其一半。 关键词：车辆路径、三维装箱、两阶段禁忌搜索、局部搜索、分枝定界法、d e e p e s t b o t t o ml e t tw i t hf i l l 、t o u c h i n ga r e a a b s t r a c t t i t l e ： m a j o r ： n a m e ： s u p e r v i s o r ： a ni n t e g r a t e dr e s e a r c hf o rt h ec a p a c i t a t e dv e h i c l er o u t i n gp r o b l e m w i t hc o n t a i n e rl o a d i n g c o m p u t e rs o f t w a r ea n dt h e o r y l e i w a n g p r o f e s s o rs o n g s h a ng u o a b s t r a c t t h i sp a p e ra d d r e s s e sa l li m p o r t a n tc o m b i n a t i o no fv e h i c l er o u t i n gp r o b l e ma n d c o n t a i n e rl o a d i n gp r o b l e m , w h i c ha r et w oi m p o r t a n tp r o b l e m si nm o d e r nl o g i s t i c s b o t hv e h i c l er o u t i n gp r o b l e ma n dc o n t a i n e rl o a d i n gp r o b l e ma r en p h a r d t oe i t h e ro f t h ep r o b l e m s , t h e r eh a v eb e e nal o to fp a p e r sp u b l i s h e d b u tt h ei n t e g r a t e dr e s e a r c hi s j u s tb e g i n n i n g t h i sp r o b l e mi sk n o w na s3 l c v r p , w h i c hw a sp r o p o s e db y m g e n d r e a ue ta 1 i n2 0 0 6 i ts o l v e st h ep r o b l e mb yat w o p h a s et a b us e a r c ha l g o r i t h mt h a ti n v o k e sa ni n n e r l o c a ls e a r c hp r o c e d u r ef o rt h el o a d i n gs u b p r o b l e m u s eb r a n c ha n db o u n dt o r e o p t i m i z ee a c hr o u t ef i n a l l y d i f f e r e n tt op r e v i o u sp a p e r s , 矗m o d i f i e st w oc l a s s i c h e u r i s t i c sf o rt w od i m e n s i o n a lb i np a c k i n ga n dg e n e r a l i z e st h e mt ot h r e ed i m e n s i o n a l b e s i d e st h a t ，i tp r o v i d e sv e r ye f f i c i e n ti m p l e m e n t a t i o n sc a l l e dd e e p e s tb o t t o ml e f t w i t hf i l la n dt o u c h i n ga r e ac o n s i d e r i n gv a r i e t i e so fl o a d i n gc o n s t r a i n t s t h e s et w o n e wl o a d m ga l g o r i t h m se n h a n c et h ec o n t a i n e rs p a c e u t i l i z a t i o n c o m p u t a t i o n a l e x p e r i m e n t ss h o wt h a tt h i sa l g o r i t h md o m i n a t e so t h e ra l g o r i t h m sp u b l i s h e db o t hi n s o l u t i o nq u a l i t ya n dr u n n i n gt i m e c o m p a r e dw i t ha c o a l g o r i t h mo ff u e l l e r e re ta 1 ， t h i sa l g o r i t h ma d v a n c e sb y2 9 0 0i ns o l u t i o nw h i l eo n l yt a k e sh a l fr u n n i n gt i m e k e yw o r d s ：v e h i c l er o u t i n gp r o b l e m ，c o m a i n e rl o a d i n g ，t w o - p h a s et a b us e a r c h , l o c a ls e a r c h ，b r a n c ha n db o u n d ，d e e p e s tb o t t o ml e f tw i t h f i l l ，t o u c h i n ga r e a 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体己经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 易私 日期：矽哆年f 月艿日 ， 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名： 2 知 日期：呷年厂月奠泊 翩签名：帮物 日期：纫夕年，月以7 日 第一章绪论 第一章绪论 1 1 本文研究的问题 带有三维装箱约束的车辆路径问题( t h r e e d i m e n s i o n a ll o a d i n gc a p a c i t a t e d v e h i c l er o u t i n gp r o b l e m , 3 l c v r p ) 结合了两个著名的n p h a r d 问题，车辆路径 问题( v e h i c l er o u t i n gp r o b l e m ) 和三维装箱问题( t h r e e d i m e n s i o n a lp a c k i n g p r o b l e m ) ，该问题由g e n d r e a u 等人【1 】首次提出，问题描述了在一个大型货物配 送中心( f r e i g h td i s t r i b u t i o n c e n t e r ) ，要将货物发给分布在各地的客户( c l i e n t ) ， 每个客户可能需要若干个货物，每个货物被抽象成一个长方体，属于同一个客户 的货物必须装在同一辆车里，以方便客户收货。货物中心有一定数目的车辆，每 辆车有一个长方体形状的货箱( c o n t a i n e r ) ，且有载重限制( c a p a c i t a t e d ) ，为了 简化问题，假设所有车辆具有相同的规格，即同样尺寸的货箱和同样的载重限制， 问如何为每辆车指派客户，且这些客户的货物能够在满足各种约束条件的情况下 装到车里，并为车辆安排一个合适的行驶路线，最终目标是在满足所有客户需求 以及车辆数目限制的情况下使得所有车辆行驶的总距离最小化。在实际应用中， 对装箱部分可能有诸多约束，文献【1 】提出了3 种约束，支撑面积( 要求至少有 7 5 的支撑面积，本文继续使用这个比例) ，非易碎品不能放在易碎品上面，货 物的后进先出( 卸货的时候只能拿暴露在外面的货物，被卸货物的上表面不能被 其它货物压着，后面不能被其它货物阻挡) 。 1 2 相关问题的研究现状 1 2 1 车辆路径问题的研究状况 针对车辆路径( v e h i c l er o u t i n gp r o b l e m ，v r p ) 问题，研究人员提出了大量 的启发式算法，最著名的是c l a r k e 和w r i g h t 2 在1 9 6 4 年提出的节约算法( s a v i n g s a l g o r i t h m ) ，该算法先用7 t 个客户初始化n 条路径，然后每次选择两条路径合并， 使得节约的费用最多，直到不存在可以合并的路径，合并两条路径节省的费用为 l 第一章绪论 = c i o + g o q j ，节约算法的朴素实现时间复杂度为d 2 l o g n ) 。节约算法如 图1 1 所示。 33 4 4 图1 一l 节约算法合并两条路径 r h m o l e 和s r j a m e s o n 在【3 】中对节约算法进行了一般化，并在此基础上提出 了顺序插入算法( s e q u e n t i a li n s e r t i o nh e u r i s t i c ) 。c h r i s t o f i d e s 、m i n g o z z i 和t o t h 4 】 提出了一种两阶段的顺序插入式算法( t w o p h a s es e q u e n t i a li n s e r t i o nh e u r i s t i c ) ， 该方法能够产生比节约算法更好的解，而运行时间大概是节约算法的两倍( 在 c h r i s t o f i d e s 、m i n g o z z i 和t o t h 的实现中) 。b i l l ye g i l l e t t 和l e l a n dr m i l l e r 5 针 对平面图提出了一种扫描算法( s w e e pa l g o r i t h m ) ，该算法分两个阶段进行，前 向扫描( f o r w a r ds w e e pa l g o r i t h m ) ，第一阶段将客户按照相对于车场的极角 ( p o l a r - c o o r d i n a t ea n g l e ) 进行排序，然后顺序的将客户插入路径，直到不能再插 入，每辆车服务极角序中连续的一段客户；第二阶段在相邻的两条路径k 和k + 1 之间进行调整，k 中的一个客户被k + 1 中的一个或若干个客户替换。 一些用来求解旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ) 的经典启发式发法 可以对已经生成的v r p 路径进行后续优化( p o s t o p t i m i z a t i o n ) ，其中最常用的是 s l i n 和b w k e r n i g h a n 6 提出的k o p t 启发式算法，该算法从现有的哈密尔顿 圈( h a m i l t o nc i r c l e ) 的n 条边中删除k 条边 1 ，x 2 ，x k ) ，再加入k 条边 ( y ，y 2 ，y k ) ，变成一个权值更小的哈密尔顿圈，不断的进行这个过程，直到 达到局部最优，最常用的有2 一o p t 和3 一o p t 。 近几十年，分枝定界法( b r a n c ha n db o u n d ) 被广泛的用于求解带有载重限 2 第一章绪论 制的车辆路径问题( c a p a c i t a t e dv r p , c v r p ) ，这类算法主要采用一些基本的组 合松弛方法( c o m b i n a t o r i a lr e l a x a t i o n s ) 来求取下界，比如任务分配( a s s i g n m e n t p r o b l e m , a p ) ，带有度数限制的最小生成树( d e g r e e c o n s t r a i n tm i n i m u ms p a n n i n g t r e e ，d m s t ) 。近年来，利用拉格郎日松弛( l a g r a n g i a nr e l a x a t i o n s ) 求下界的方 法被提出，从而大大增加了分枝定界法可以求解的问题规模。g l a p o r t e 和 n r o b e r t 在文献 刀中对各种分枝定界法进行了完整而详尽的分析。 近几年来，一些元启发式方法( m e t a h e u r i s t i c s ) 被大量应用来求解v r p 问 题，主要有六大类方法，模拟退火( s i m u l a t e da n n e a l i n g ，s a ) ，确定性退火 ( d e t e r m i n i s t i ca n n e a l i n g ，d a ) ，禁忌搜索( t a b us e a r c h , t s ) ，遗传算法( g e n e t i c a l g o r i t h m s , g a ) ，蚁群系统( a n ts y s t e m , a s ) ，和神经网络( n e u r a ln e t w o r k s , n n ) 【8 】。o s m a n 9 在1 9 9 3 年提出了用模拟退火和禁忌搜索的混合算法求解c v r p ( c a p a c i t a t e dv e h i c l er o u t i n gp r o b l e m ) ，同时结合了两种算法的优点，在邻域探 索的过程中，以一定概率接受劣解，他们采用( n + 1 ) 杪的二维禁忌表，表示一 个客户被移入某辆车或移出某辆车。m i c h a e lg e n d r e a u 等flo 】于19 9 4 年提出禁忌 搜索算法t a b u r o u t e ，他们在邻域变换的过程中允许非可行解( i n f e a s i b l e s o l u t i o n ) 的存在，即某辆车可能出现超重或者超过行驶距离限制，并引入两个 惩罚因子口和口对其进行惩罚，对一个解的评估由实际距离加上两部分惩罚构成， 在迭代过程中，动态的调整口和声，引导算法找到可行解。 1 2 2 装箱问题的研究状况 针对三维装箱( 3 d b i np a c k i n g ) 问题的启发式方法主要来自一些应用在二 维装箱问题( 2 d - b i np a c k i n g ) 上的方法，这里讨论的都是直角装箱( o r t h o g o r m l p a c k i n g ) ，即箱子的边要与容器的边平行。b r e n d as b a k e r 等人【1 l 】于1 9 8 0 年提 出了一种针对二维直角装箱的底边左边放置( b o t t o mu pl e f tj u s t i f i e d ，b l ) 算 法，他们的研究模型是把任意一组矩形装进一个固定宽度的，一端开口 ( o p e n e n d e d ) 的矩形箱子里，使得所用高度最小。该算法对于一个确定的装箱 序列，总是选择一个最靠底边，再尽量靠近左边的位置依次放入箱子，并证明了 如果按照宽度从大到小的顺序将矩形排序，使用b l 法求得的结果不会超过最优 3 第一章绪论 解的3 倍，即堕3 ，且这个界是不可改进的。b e r n a r dc h a z e l l e 1 2 于1 9 8 3 年 h o p 了 提出了一种对b l 的高效实现方法，时间复杂度为d ( 2 ) 。b l 可以很自然的扩展 到三维情形，就是最深最底最左放置法( d e e p e s t b o t t o m l e f t ，d b l ) 。1 9 9 9 年， l o d i 等人在【1 3 】中提出了触边( t o u c h i n gp e r i m e t e r ) 算法，每次在所有的正规位 置( n o r m a lp o s i t i o n ) 中选取一个接触边长最大的，算法复杂度为o ( n 3 ) ，该算 法能够较好的避免产生不可利用的小空间。2 0 0 4 年，e k b u r k e 等人【1 4 】提出了 一种新的启发式算法用于求解二维装箱问题，叫做最适合法( b e s t f i th e u r i s t i c ) 。 2 0 0 8 年，e p a r r e f i o 等人【1 5 】提出了极大空间( m a x i m a l s p a c e ) 算法，把可利用 的空间划分成若干个m a x i m a ls p a c e ，这些m a x i m a ls p a c e 覆盖了所有的剩余空 间，但并不要求它们是互斥的，即在空间中有可能相交，但不存在包含关系( 一 个空间完全在另一个空间内部) ，这一点也是极大( m a x i m a l ) 所指的意思；这 是一个构造性的算法，每次选择一个离集装箱项点最近的m a x i m a ls p a c e 来填充， 再选择一种货物，使用l a y e rb u i l d i n g 的方法将其装入这个m a x i m a ls p a c e ，算法 中使用了两种评价指标来选择货物及其摆放方式；该算法在基准测试数据上取得 了很好的实验效果，在强异构( s t r o n g l yh e t e r o g e n e o u s ) 尤其有效。 1 2 3 车辆路径与装箱混合问题的研究 m i c h a e lg e n d r e a u 等【1 6 】提出用禁忌搜索求解带有二维装箱约束的车辆路径 问题( v e h i c l er o u t i n gp r o b l e m sw i t ht w o d i m e n s i o n a ll o a d i n gc o n s t r a i n t s , 2 l c v r p ) 。m a n u e ll o f t 等【17 】于2 0 0 5 年提出2 l c v r p 的b r a n c ha n dc u t 算法用 于寻找精确解，他们通过使用下界、快速启发式算法和分枝定界法( b r a n c ha n d b o u n d ) 相结合的方法来判断装箱子问题是否有可行解，最大能够求解有3 5 个 客户，多于1 0 0 个货物的实例。 在3 l c v r p 方面，自文献【l 】后，g u e n t h e rf u e l l e r e r 等 1 8 1 提出蚁群算法( a n t c o l o n yo p t i m i z a t i o n ，a c o ) ，他们使用了一般化了的节约算法( g e n e r a l i z e d s a v i n g s a l g o r i t h m ) ，在节约算法中引入信息索以及反映装箱好坏的评价函数，再 通过局部搜索( l o c a ls e a r c h ) 进一步优化解，实验结果表明，a c o 产生的解比 t s 1 提高了4 4 。中山大学陈实【1 9 】在其毕业论文中提出了禁忌搜索和局部搜 4 第一章绪论 索两层算法求解3 l c v r p ，得出与a c o 算法相当的解，但求解时间大大减少。 1 3 本文主要工作及内容结构 以上3 篇文献在求解装箱子问题时均使用了相同的启发式算法，即b o t t o m l e f t 和t o u c h i n gp e r i m e t e r 在三维情形下的扩展，在放置箱子时，只考察了n o r m a l p o s i t i o n s 2 0 ，这样的n o r m a lp o s i t i o n 共有d ( n ) ，n 为箱子个数，他们的算法复 杂度均为o ( n 3 ) 。事实上这0 ( n ) 个n o r m a lp o s i t i o n 是远远不够的，本文中的装箱 算法考察y o ( n 3 ) 个位置，朴素的实现方法为o ( n s ) 的时间复杂度，本文提出了 快速判断相交、以及是否满足各种装箱约束的滑动方法，将算法优化为o ( n 4 ) ， 实验表明，新的装箱算法比原有装箱算法更有效( 容积利用率更高) ，虽然复杂 度高了一阶，但可以在较少的迭代次数内找到更优的解。与【l 】和【1 8 】相比，无论 在求解质量还是求解时间上都大大领先。另外，本文结合了【1 】和【1 9 】的优点，提 出了两阶段的禁忌搜索( t w o p h a s et a b us e a r c h ) ，第一阶段重在求解可行解， 第二阶段着重求最优解，两阶段禁忌搜索的优点是能够较快的找到可行解，在找 到可行解后，又能够充分的在可行域中探索，寻求较优解。 本文内容共分为七章：第一章即本章为绪论，介绍相关问题目前的研究状况 以及本文的研究方法和创新之处；第二章为问题描述，详细地定义了本文所要研 究的问题3 l c v r p ；第三章为v r p 问题的数学模型，主要概括了目前主流的两 种用于求解v l 冲问题的混合整数规划( m i x e dl m e g e rp r o g r a m m i n g ，m i p ) 模型； 第四章是针对3 l c v r p 的特殊约束建立的装箱问题的数学模型，该模型是由本 文首次提出的；第五章详细介绍求解3 l c v r p 的两阶段禁忌搜索加局部搜索算 法，是文章最重要的一部分；第六章是实验结果，与当前最优秀的算法在标准测 试数据上进行了对比，结果是相当有说服力的；第七章为结束语，对该问题未来 可能的研究方向提出了一些建议。 5 第二章问题描述 第二章问题描述 本文采用文献【1 】中的记号，设无向图g = ，e ) ，其中v = ( o ，1 ，2 ，扎) 是 n + 1 个顶点的集合，e 是连接任意两个顶点的边的集合，项点0 代表货物配送中 心( d e p o t ) ，所有货物都从这里被发往各个客户处，车辆在送完货物后必须返回 中心，顶点( 1 ，2 ，7 t ) 是7 1 个要服务的客户，每条边( f ，) 有一个权值q ，表示顶点 i n 项点，的距离。 货物中心总共有1 7 辆车，每辆车的装载空间均为s = w 胃l ，w 是宽度， h 是高度，j ，是长度，载重限制均为d 。以车厢底面左边靠里的顶点为原点，以宽 度方向为z 轴，以高度方向为y 轴，以长度方向为z 轴，建立如图2 1 所示的三维 直角坐标系，其中阴影部分所示的区域为车厢门，即装、卸货的作业区域。 圈2 一l 集装稻不恿图 客户f 需要的货物有m 个，总重量为d f ( f - - - 1 , 2 一，7 t ) ，属于客户f 的第k 个 货物被记为j 班，宽度为w 披，高度为h 长度为2 m ，客户i 所需货物的总体积为 v o l i = 是1w i k h i k l i k 。 货物只能在x z 平面内做9 0 。旋转。用 七( f = 1 一，n ，k = 1 m i ) 来标识货物，讹 是否为易碎品，等于1 表示是易碎品，等于o 表示不是易碎品。非易碎品不能压 6 第二章问题描述 在易碎品上面，称为f r a g i l i t y 约束。摆放货物的时候还要考虑其底面的支撑面积， 只有当支撑面积与底面积的比值超过一个给定的闽值d 时才允许摆放，称为 s u p p o r t 约束。当货车按照顺序服务客户的时候，必须能够顺利卸下其货物，卸 货时货物只能延z 轴方向移动，要卸的货物不能被其它货物压着，其前面不能被 其他货物挡住，称为l i f o 约束。 3 l c v r p 的求解目标是要寻找最多杪条路径( 每辆车一条路径) ，每条路径 均以车厂( d e p o t ) 为起点和终点，并满足以下约束： ( 1 )每个客户只被一辆车服务。 ( 2 )每辆车都不能超重。 ( 3 )对于每辆车，存在一种可行的三维直角装箱方案将属于这些客户的所有 货物装入车内，同时满足易碎品，底面支撑面积和货物的先进后出约束。 ( 4 )所有路径的长度之和最小化。 7 第三章v r p 问题的数学模型 第三章v r p 问题的数学模型 3 1 车辆流模型 车辆流模型( v e h i c l ef l o wm o d e l ) 【2 1 用o ( n 2 ) 个二元变量来表示车辆是否 会经过某条边，如果车辆经过边( l d e ，则取变量= 1 ，否贝t j x u = 0 。 目标： m f n e y 马v c u x u ， ( 3 - 1 ) 约束条件： f y x u = 1 ，w y ( 0 ) ， ( 3 2 ) y j y z u = 1 ，v i y ( o ) ， ( 3 - 3 ) 一 = 杪 (34x,ievxio ) = 杪， l 一， ，e v x o j = 杪， ( 3 5 ) f 仨s 马s x i i 7 ( s ) ，v s y ( o ) ，s 仍， ( 3 6 ) x i j o ，1 ) ，v i ，歹v ( 3 - 7 ) 式( 3 2 ) 保证每个客户的入度为l ，( 3 3 ) 保证每个客户的出度为1 ，( 3 4 ) 使车场的入度为v ，( 3 5 ) 使车厂的出度为，。( 3 6 ) 中r ( 回表示服务某个客户集 所需的最少车辆数，直观上来说，就是从s 外部进来的边数不能少于服务s 所需 的最小车辆数，因为一辆服务s 中客户的车至少会进入s 一次，该式同时保证了 图的连通性以及载重限制。在c v r p 问题中，用r 号竽- l 来代替r ( s ) 上述模型同 样有效【2 2 】。 l a p o r t e ，m e r c u r e 和n o b e r t 于1 9 8 6 年在【2 3 】中阐述了v r p 与它的一种松弛 形式( 忽略载晕限制) m - t s p 之问的关系。而l e n s t r a 和r o n n o o yk a n 则指出， m t s p 可以转化为1 - t s p 2 4 】，具体方法是：将d e p o t 复制秒一1 份，令 7 i7 = n + 1 7 1 ，v = ( 0 , 1 ，2 ，n 3 ，e = e u ( ( f ，j ) ：i , j v ：i j ，fo r j y 一矿) ， 第三章v r p 问题的数学模型 并定义如下扩展距离矩阵c = ( c u ) ，【2 5 】 f ， c 0 ( ，歹) v ， c 。= i 卜c i o ；淄粉猷潲： l 丫( f ，j v yu ( o ) ) ， y 取不同的值对应不同的问题，丫取正无穷时对应恰好有p 条路径的最小距离， 取0 表示最多妒条路径，取负无穷则表示在车辆数最少的情况下寻求距离的最小 化。 如果忽略约束( 3 6 ) ，并用c 0 代替c u ，则可以将v r p 问题松弛为t s p 问题， 可以使用一些求解t s p 问题下界的方法来求v r p 问题的下界。 一种经典的求t s p 问题下界的方法是1 - t r e e 算法，1 - t r e e 定义为：对于一个 给定的顶点f ，顶点集v f 】的最小生成树加上由f 连向v f 】的两条不同的边构成 一棵1 一t r e e ，一个1 一t r e e 恰好包含一个圈。 我们知道，在t s p 问题的一个可行解中，对于任意一个顶点f ，都有两条边 与它关联，假设我们去掉这个顶点和对应的两条边，则剩下的项点和边构成一条 路径，这个路径不包含回路，即是一棵树，如果对顶点集v a ) 求最小生成树， 则这个值一定是v ( f ) 中所有顶点构成的路径长度的一个下界，再从f 到v ( f ) 引 两条最小的边，这i v l 条边的权和可以作为t s p 问题的一个下界。 实际计算中，可以枚举顶点i ，每次找一个最小的1 - t r e e ，记为吼；最后以 r a i nh ：f 叼作为t s p 的下界。 引入1 7 1 个车厂并定义了新的距离矩阵后，流模型变为如下形式： 目标： m i n , i e y yc i j x i j ， ( 3 8 ) 约束条件： f yx o = 1w v ， ( 3 9 ) yx t ，= 1v i v ， f 盛s 马e s x o r ( s ) 蚣y 7 ( o ) ，s 谚， 9 ( 3 1 0 ) ( 3 h ) 第三章v r p 问题的数学模型 x i j ( 0 ，1 ) v i ，j v ( 3 1 2 ) 如果忽略约束( 3 1 1 ) ，则这是一个任务分派的问题( a s s i g n m e n tp r o b l e m , a p ) ， 可以在d ( i y 1 3 l 时间内解决。通过求解a p 问题也可以得到v r p 的一个下界。 3 2 集合划分模型 集合划分模型( s e tp a r t i t i o n i n g ) 最初由b a l i n s k i 和q u a n d t 2 6 于19 6 4 年提 出，令所有可行路径( 允a s i b l er o u t e s ) 的集合为尺= ( r x ，r z ，r 3 ，r q ，其中q = i r i ， 路径的费用为c = ( c 1 ，c 2 , c 3 ，c 口】，则v i 冲问题的任何一个可行解都可以看成 是r 中若干个元素的集合。用二元变量x f ( f = 1 , 2 ，q ) 表示路径r f 是否被选中， 用二元变量( = 1 , 2 一，q , j y ( o ) ) 表示路径吒中是否包含客户歹，则v r p 问题 可以用如下整数规划模型来描述， 目标： m i n e l lc i x i ， ( 3 1 3 ) 约束： 塾1 a u = 1 , j y ( o ) ， ( 3 一1 4 ) 冬1 z f q ， ( 3 - 1 5 ) z ( o ，1 ) ，f = 1 , 2 一，q 。 ( 3 1 6 ) 集合尺的大小通常都是指数级的，生成所有的可行路径通常是不可能的，因 此如何选择一部分可行路径成为问题的关键，关于路径选取( c o l u m ng e n e r a t i o n ) 目前已经有很多研究。 1 0 第四章三维装箱问题的数学模型 第四章三维装箱问题的数学模型 借鉴c s c h e n 等人 2 7 1 提出的数学模型，针对3 l c v r p 这个问题，本文提 出了一种针对单个车辆装箱问题的数学模型，该模型用来判断能否将己知的一组 货物全部装入单个车辆。 先定义三个二元变量用来表示任意两个货物的空间位置关系，既然货物不能 相交，那它们必定在某个方向上的坐标是不相交的，如果z 坐标不相交，称它们 为左右关系，y 坐标不相交称为上下关系，z 坐标不相交称为前后关系，用r i g h t i j 表 示货物i 在货物歹的右面，用幻砘，表示货物f 在货物的上面，用f r o n t f ，表示货物 f 被放在货物，的前面。对于任意两个货物，它们的空间位置关系有6 种。 用一个二元变量o r i e n t a t i o n i 表示货物i 底面的摆放方向，o r i e n t a t i o n l = 1 表示i 的宽度在x 轴方向上，o r i e n t a t i o n i = 0 表示i 的宽度在y 轴方向上。 用x i 表示i 最左边的位置，y i 表示i 最下边的位置，z i 表示i 最里边的位置，则 一个货物在空间中摆放的确切位置可以由托，y t ，z i 以及d r f p n t 口f 伽f 确定。三个 坐标可以是实数。 利用以上定义的一组变量，先来对无任何约束的单个车辆的装箱问题进行建 模。 0 x i w o r i e n t a t i o n w i 一( 1 一o r i e n t a t i o n i ) l i 0 溉h 一趣 0 盈一o r i e n t a t i o n i ，l i 一( 1 一o r i e n t a t i o n f ) m ( 夸1 ) ( 4 2 ) ( 4 3 ) f r o n t 0 + r i g h t 0 + t o p 0 + f r o n t i i + r i g h t j i + t o p j i = 1 ( 4 4 ) 旎+ ( 1 一r i g h t f ，) m + o r i e n t a t i o n j 哟+ ( 1 一o r i e n t a t i o n i ) ( 4 - 5 ) m + ( 1 一t o p o ) m 嚣+ 吩 ( 4 6 ) z f + ( 1 一f r o n t q ) m 弓+ o r i e n t a t i o n i 。b + ( 1 一o r i e n t a t i o n i ) 叶( 4 7 ) 式( 4 & ) 至( 4 9 ) 将每个货物约束在集装箱内部，( 4 1 0 ) 表示两个货物之 第四章三维装箱问题的数学模型 间有且仅有一种位置关系，事实上，货物i 有可能同时在货物j 的右面、上面、前 面，但我们只需要其中的一种关系，如果在歹的右面，则不用关心是否萄的上 面或前面，稍后的分析会指出这种约束大大缩小了问题的解空间。m 则表示一个 非常大的数，如果r f 9 h = 1 ，则式( 4 - 5 ) 变为x j + o r i e n t a t i o n l + ( 1 一o r i e n t a t i o n ) ，表示f 最左边的位置大于等于歹最右边的位置，如果 r i g h t f ，= 0 ，则式(4-5 ) 变为 x i + m 巧+ o r i e n t a t i o n j 叶+ ( 1 一o r i e n t a t i o n j ) r0 ，因为m 非常大，该式自 然成立，相当于忽略了这个约束。 这个模型是一个混合整数规划问题( m i x e di n t e g e rp r o g r a m m i n g ，m i p ) ，目 标就是求一个可行解( f e a s i b l es o l u t i o n ) ，我们来分析其复杂度，o r i e n t a t i o n i 的 取值为0 或1 ，m 个货物共有2 m 种组合，f r o n t i j 、r i g h t q 、c d p f ，的取值也为o 或1 ， 但由于式( 4 4 ) 的约束，。一得f r o n t 0 、r i g h t q 、t o p 0 、f r o n t j i 、r i g h t j 、t d 聊f 这6 个变 量有且只能有一个取1 ，即这6 个变量问的组合只有6 种情况，f 和j 的组合有瑶种 情况，根据排列组合的乘法原理，f r o n t u 、r i g h t o 、c o p f j 这些变量的取值有6 嚷种 组合，包括o r i e n t a t i o n 的取值情况，所有整数变元的取值共有2 m 6 种组合。 一旦整数变元的值确定了，剩下的问题就成了一个线性规划问题( l i n e a r p r o g r a m r n i n g ) ，一般的线性规划闻题是否具有多项式复杂度的算法尚未被证明 【2 8 ，而在这个特殊的模型中，多项式算法是存在的，稍后会给出分析。假定在 这个特殊模型中求解扎个变元的线性规划问题的复杂度为o ( l p n ) ，则无约束的三 维装箱问题的复杂度为0 ( 2 m 6 铙三岛m ) 。 这个剩余的线性规划问题有一个很特殊的地方，即每个不等式里最多有两个 变元，且每个变元的系数都是l 。因为x ，y ，中的任意两个不会同时出现在 一个不等式里，f l o x ，y j ，这三个变元是相互独立的，可以将其划分为3 组不 等式，分别求解3 个线性规划问题。仅用含有旎变元的问题为例说明如何求解， 该问题包含如下两种形式的不等式： l 第四章三维装箱问题的数学模型 o 规口f ( 4 1 1 ) z f 一号b i l ，其中6 u 0 ( 4 1 2 ) 第一种是针对单个变元的约束，第二种是针对两个变元的约束，这是一个差 分约束系统( s y s t e m o f d i f f e r e n c ec o n s t r a i n t s ) ，且所有的差( 饥，) 均为负数，可 以构造图论模型求解，而且比一般的差分约束问题更容易。把每个变元x f 关联到 一个顶点耽，对于每一个不等式工l x j b u ，由巧到耽连一条有向边，权值为。 再引入一个新的顶点，分别连一条有向边到秒”杪2 、，、，权值均为o 。如 果该图中存在圈，则无解，否则求出到其它各点的最长路d l 、d 2 、，、，再 令x l = d ”z 2 = d 2 、，、= d m ，将其代入( 4 8 ) 中看是否满足约束，如果 满足，就找到一个可行解，否则无解。可以用有向图的拓扑排序算法同时完成圈 的检测和最长路的计算，该算法的时间复杂度为o ( m 2 ) 。 综上所述，通过枚举整数变元，再求解差分约束问题的算法复杂度为 o ( 2 m 6 嚷m 2 ) 。 当加入易碎品约束( f r a g i l i t y ) 时，对于任意的f 、，且j 为非易碎品，歹为 易碎品，f 不能放在，的上面。如果c d p f ，= 1 且孔= ”+ h j ，则f 和歹必须要在x z 平面 内分离，否则f 会压在歹的上面，最p f r o n t 0 ，r i g h t q ，f r o n 巧i ，r 匆j t 中必须有 一个等于l ，且这4 个变量中有一个为1 就能保证f 不会压在歹上面，n 此t o p f f = 1 时，y i = ”+ 吩是没有必要的。所以将式( 4 - 6 ) 改为： 欺+ ( 1 一t o p q ) m y j + 吩 ( 4 1 3 ) 类似的，当有l i f o 约束时，对于任意的f 、j i ，且f 的服务顺序优先于歹，此 时f r o n t j i = 1 是没有意义的，因为如果在f 的前面，则f 和歹必须要在x y 平面 分离，且p r i g h t q ，t o p i j ，r i g h t j f ，d 翰中必须要有1 个为l 。j l t o p f i = 1 时， ) ，= 她+ h i 也是没有意义的，因为若想保证，不在f 的上面，以及在卸f ( f 沿z 轴向外移动) 的过程中歹也不能住f 的上面，f 和歹必须在z 方向上分离或者，在 f 的后面。因此将式( 4 4 ) 改为： l 气 第四章三维装箱问题的数学模型 f r o n t q + r i g h t q + t o p q + r i g h t j i + t o p i i = 1 ( 4 1 4 ) 将式( 4 6 ) 改为： ”+