（运筹学与控制论专业论文）物流拼车配送中的线路优化.pdf

浙 江 大擘硕 士 学位论丈 摘要 作为“第三利润源”的现代物流业已经被全世界广泛关注，随着我国国民 经济的高速发展，推进现代物流发展，推动物流管理、物流技术的进步已成为 目前我国社会经济发展中的一项重要内容。随着“第三方物流”的发展成熟 配送作为一种特殊的、综合的物流活动形式正扮演者越来越重要的角色。 如何制定配送计划并选择配送线路是配送业务巾面临的最大难题，目前人 们已经尝试了精确式算法和启发式算法，但这两种算法存实际应用中都存在着 很大的不足，因此有效解决配送线路的选择和配送计划的制定就成为当前物流 配送业务中的迫切要求。 本文着眼于拼车配送线路的优化，以数学模型为工具来描述问题，以网络 单纯形法、拉格朗日松弛算法以及试探法为主要研究方法，有效地得到该问题 一个近似程度较高的可行解，从而很好的解决了货物的“配”与“送”，即配送 计划的制定和配送线路的选择。 本文首先对物流配送的现状做出概述，然后以配送中的最小运送成本为目 标建立了一个混合整数规划模型，并分析最优解应该满足的条件。 考虑到问题的复杂性，对最优解的求解既不实际也不实用，本文主要着眼 于如何有效地得到其近似解。网络单纯形法是解决通常网络流问题的一类有效 算法，而拉格朗| = 1 松弛是解决各类整数规划、组合优化、非线性规划的少数有 效算法之一。本文中将拉格朗日松弛与网络单纯形法相结合有效地得到原问题 的一个下界，并利用该下界结合试探法有效地得到该问题一个可行解作为上界， 如此反复迭代逐步缩小上下界的区间范围并最终找到一个近似程度较高的可行 浙 江大 学硕 士 学 住 论 文 解。 本文在建立模型并给出算法的基础上又以一实例来验证所给算法的有效 性，并以附表的形式给出其运算步骤。最后又对该模型的实际应用价值进行了 描述，说明了本文所给出的算法能够很好地解决物流配送中配送线路的选择以 及配送计划的制定。 关键词：拼车配送混和整数规划网络单纯形法拉格朗日松弛试探法 浙江大学硕 士 学位 论文 a b s t r a c t m o d e ml o g i s t i c s ，w h i c hi sc a l l e dt h et h i r ds o u r c eo fp r o f i t ，h a sb e e nc a r e db y a l lo ft h ew o r l d w i t ht h ed e v e l o p m e n to fo u rc o u n t r y se c o n o m na d v a n c i n gt h e d e v e l o p m e n to fm o d e ml o g i s t i c sa n dt h el o g i s t i c sm a n a g e m e n ta n dt h ep r o g r e s so f t h el o g i s t i c st e c h n o l o g yb e c o m em o r ea n dm o r ei m p o r t a n tp a r to ft h ed e v e l o p m e n t o fo u rs o c i e t ye c o n o m yn o w a st h ed e v e l o p m e n to f h i r d - p a r t yl o g i s t i c s ( t p l ) ”， d i s t r i b u t i o ni s b e c o m i n g m o r ea n dm o r ei m p o r t a n t ，w h i c hi sas p e c i a la n d c o m p o s i t i v el o g i s t i c sa c t i v i t y h o wt oi n s t i t u t et h ep l a no fd i s t r i b u t i o na n dc h o o s et h ed i s t r i b u t i o nr o u t ea r e t h em o s td i f f i c u l tp r o b l e m si nt h ed i s t r i b u t i o na c t i v i t i e s b yt h i st i m ea c c u r a c y a l g o r i t h ma n dh e u r i s t i ca l g o f t h mh a db e e nt r i e d b u tt h e s et w ok i n d so fa l g o r i s m s a l le x i s tv e r yb i gs h o r t a g ei np h y s i c a l l ya p p l i e d t h e r e f o r ee f l b c t i v e l ys o l v i n gt h e t w op r o b l e m sb e c o m et h eu r g e n tr e q u e n i nt h i sp a p e ra t t e n t i o ni sf i x e do no p t i m i z i n gt h er o u t eo fd i s t r i b u t i o nb yl e s s t h a nc o n t a i n e rl o a d t a k i n gm a t h e m a t i c sm o d e la sat o o lt od e s c r i b et h ep r o b l e m ， w i t hn e t w o r ks i m p l e xm e t h o da n dl a g r a n g i a nr e l a x a t i o na n dh e u r i s t i cm e t h o df o r m a i nr e s e a r c hm e t h o d ，aa p p r o x i m a t es o l u t i o nc a nb eg o a e n t h u st h ep r o b l e m sa r e w e l ls o l v e d f i r s t l yt h es i t u a t i o no fc u r r e n tp h y s i c a ld i s t r i b u t i o n ( p d ) i ss u m m a r i z e di nt h i s p a p e r t h e nam i x e di n t e g e rp r o g r a m m i n gm o d e lw i t ht h eg o a lo fm i n i m i z i n gt h e d e l i v e r i n g c o s ti s b u i l t ，a f t e r w a r dt h eo p t i m a ls o l u t i o no ft h em o d e la n dw h a t 3 浙江大学硕 士 学位论文 c o n d i t i o nt h es o l u t i o ns h o u l ds a r i s f yi sa n a l y z e d i nc o n s i d e r a t i o no ft h ec o m p l e x i t yo ft h ep r o b l e m ，t os o l v ei t so p t i m a ls o l u t i o n i sp h y s i c a l l yu s e l e s s w ef i xa t t e n t i o no nh o wt og e ti t sa p p r o x i m a t es o l u t i o n n e t w o r ks i m p l e xm e t h o di sa ne f f e c t i v em e t h o dt os o l v en e t w o r kf l o wp r o b l e ma n d l a g r a n g i a nr e l a x a t i o ni so n eo ft h ev e r yf e ws o l u t i o nm e t h o d si no p t i m i z a t i o nt h a t c u t sa c r o s st h ed o m a i n so fl i n e a ra n di n t e g e rp r o g r a m m i n g ，c o m b i n a t o r i a l o p t i m i z a t i o n ，a n dn o n l i n e a rp r o g r a m m i n g i nt h i sp a p e rw eg e tt h el o w e rb o u n do f t h ep r i m a lp r o b l e mb yn e t w o r ks i m p l e xm e t h o dt o g e t h e rw i t hl a g r a n g i a nr e l a x a t i o n f u r t h e r m o r ew ec a l lg e taf e a s i b l es o l u t i o na st h eu p p e rb o u n do f t h ep r i m a lp r o b l e m b yh e u r i s t i cm e t h o dt o g e t h e rw i t ht h el o w e rb o u n d w ei t e r a t et h ep r o c e s sa g a i na n d a g a i nt or e d u c et h es c o p eo f t h eu p p e ra n dl o w e rb o u n du n t i lw eg e ta na p p r o x i m a t e s o l u t i o nw h i c hi sa v a i l a b l e i nt h i sp a p e r , a ne x a m p l ei s g i v e nt o t e s t o u ra l g o r i t h ma n dt h eo p e r a t i o n p r o c e s si sg i v e nt h r o u g hat a b l e a tl a s t w ee x p a t i a t et h ea c t u a lv a l u eo ft h e a p p l i c a t i o no ft h em o d e lw h i c he x p l a i no u ra l g o r i t h mc a ne f f e c t i v e l ys o l v et h a th o w t oi n s t i t u t et h ep l a no f d i s t r i b u t i o na n dc h o o s et h ed i s t r i b u t i o nr o u t e k e yw o r d ：d i s t r i b u t i o nb yl e s st h a nc o n t a i n e rl o a d ；m i x e di n t e g e rp r o g r a m m i n g ； n e t w o r ks i m p l e xm e t h o d ；l a g r a n g i a nr e l a x a t i o n ；h e u r i s t i c 4 浙 江大 学 硕士 学位论文 第一章物流配送业务综述 1 1 现代物流与物流配送概述 上世纪七十年代末、八十年代初，我国引进了“物流”概念和理论，但在 很长一段时间里没有引起足够的重视。随着我国市场经济体制的逐步完善，市 场上的商品不断丰富，短缺经济基本结束，己逐步形成买方市场，市场一体化、 竞争国际化趋势十分明显。被普遍认为企业在降低物质消耗、提高劳动生产率 以外的“第三利润源”“”的现代物流业开始为各界广泛关注。 我国“物流标准”中的基本概念术语对物流的定义为：“物流( 1 0 9 is t i c s ) 是物品从供应地向接收地的实体流动过程。根据实际需要，将运输、储存、装 卸、搬运、包装、流通加工、配送、信息处理等基本功能实施有机结合。”随着 第三方物流的蓬勃发展，配送作为种特殊的、综合的物流活动形式正扮演者 越来越重要的角色”。 配送是指将从供应者手中接受的多品种、大批量货物，进行必要的储存保 管，并按用户的订货要求进行分货、配货后，将配好的货物在规定的时间内 安全、准确地送交需求用户的一项物流活动。配送是“配”和“送”的结合， 是运输与其它活动共同构成的组合体，它几乎包括了所有的物流功能要素，是 物流的一个缩影或在某一小范围中物流全部活动的体现。 配送的意义和作用重大： ( 1 ) 配送是实现流通社会化的重要手段 ( 2 ) 配送通过集中库存使企业实现低库存或零库存，提高保证供应程度； 浙 江大 学 硕士 学 位论文 ( 3 ) 配送有利于实现运输的合理化； ( 4 ) 配送是为消费者提供方便、优质服务的重要方式。 1 2 现代物流配送业务的发展要求 由于现代物流追求运输合理化，而运输合理化则要求物流企业应尽可能的 提高运输的提高运输工具的实载率，为此现在的配送中心人多采用“拼车配送” ”来提高配送车辆的利用效率、减少运送成本进而降低配送成本。 所谓“拼车配送”就是物流企业为了提高运输车辆的实载率，在不降低物 流服务水平的情况下尽可能的将多个客户的货物拼装到一辆汽车进行运送。然 而如何制定配送计划并选择配送线路是配送业务中面临的最大难题，即货物的 “配”与“送”的问题。 1 2 t 当前关于配送计划制定的研究 配送i 、u j 题的研究与实施一般先作如下假设 ( 1 ) 被配送的是同一种物资； ( 2 ) 各用户的位置及需求量已知 ( 3 ) 从配送中心到各用户的运输距离或运输成本已知 ( 4 ) 配送中心有足够的资源以供配送，且有足够的运力。 配送计划追求的目标是总成本最小，含义可以是距离、费用、时间等，视 实际情况而定。 配送计划要满足的约束条件有：必须及时满足用户的需求；发送的车辆不 允许超载运行；发送的车辆每天的总运行时间( 或总运行距离) 有上限等等”。 浙 江大 学 硕士 学 位论文 目前物流行业解决配送车辆调度问题时主要考虑如下的数学模型 配送中心使用同类型的配送车，配送中，心记为标号0 ；可用的车辆集合是 q ，k = l ，m ，q 为载重量；用户 g 。，i = 1 ，n ，g ，为用户i 的货运量，如 果可以混装，则有m a ) ( 毋q ：用户i 到用户j 之间的最短距离记为吃； 定义o l 变量如下： y k ，= i ，表示点i 的用户由车辆k 完成，否则记儿= 0 = 1 ，表示车辆k 从i 行驶到点j ，否则记= 0 r a i n z = q 。 s t g ，y k ，吼 v k 儿= 1o r0 x i k = y 魂； x m = 1 o r0 i = 1 ，- ，n ， i = 0 t nv k ，= 0 ，挖 v k i = 0 ，以 v k i ，= 0 ，疗 vk 公式中e 表示每一辆车从结点f 经过( f ，) 弧到达结点_ 的成本，含义可以 是距离、费用、时间等，视实际情况而定。一般地，增发一辆汽车的边际费用 较高，故当i 为配送中心( 标号是0 ) 时有c 0 ，= c o + c 。d o ，w = 1 ，胛；当i 为 客户点时有q = c o d , j ，i 0 且w = o ，”。其中c o 是增加一辆汽车的固定费用， c 1 表示相对于行车距离的费用系数。 不难看出，配送计划的制定是在一定约束条件下的优化问题，或更进一步 浙 江大 学 硕士 学位 论文 i 丁理解成一个合理有效的运输问题，历史上曾尝试了多种方法试图解决这类问 题。 1 3 1 精确式算法 精确式算法一般运用线性规划( 包括经过了专门处理的分枝定界法、割平 面方法和标号法) 和非线性规划等数学规划技术，以便求得问题的最优解。精 确式算法一般有以下几种方法：1 分枝定界法( b r a n c ha n db o u n da p p r o a c h ) ； 2 岩4 平面法( c u t t i n g p l a n e s a p p r o a c h ) ；3 网络流算法( n e t w o r kf l o w a p p r o a c h ) 4 动态规划方法( d y n a m i cp r o g r a m m i n g a p p r o a c h ) 等。由于问题的复杂性，精 确式算法随着运输系统的复杂和调度目标的增加，其计算量呈指数递增，使得 获取整个系统的精确最优解越来越困难，而用计算机求解人型优化问题的时间 和费用又太大，因此，此类优化方法和算法现在一般仪用于求解规模较小的运 输调度的局部优化问题。 1 3 2 启发式算法 启发式算法是运用一些经验法则来降低优化模型的数学精确程度，其中最 具有代表性的就是南c l a r k e 和w r i g h t 于1 9 6 4 年提出的节约法( s a v i n gm e t h o d ) 下面，引用c l a r k e 和w r i g h t 的论文中的例子说明节约法思考的基本方法。 漫配送中心是咒，m 个用户分别是e ，巴；e 和只之间的最短距 离是吒，且吒已知( i ，j 3 1 ，2 ，) 。 如果发送车辆的吨位已知，并且每一辆车都可以满载，则研究的目标转化 为使所有参加发送的车辆的总发送距离在满足约束条件的基础上最小。 浙 江 大学硕 士 学位 论文 在考虑配送计划时，首先假定在任何情况下，运输网络中的任意两点都有 路径可以连通，并且都有最短路线。 如图1 所示，如果把原来图1 ( a ) 的运输路线由r 一只，一e 一晶和昂一p + 。 一0 昂改为图1 ( b ) 的r 一只一，一只一0 0 + 。一r ，则改动之后的节约量 是：毛= 矗，+ d o ，一噍，这就是有名的节约量公式。 ( a ) p 0 图1 ( b ) 当前比较成熟的启发式算法很多，一般可以分成以下四类 p 0 ( 1 )构造算法。根据一些规则，将不在线路上的点逐次增加到线路中去， 直到所有的点都被安排进线路为止。该方法最早提出用来解决旅约 售货商( t s p ) ，求解速度比较快，也很灵活，但有时找到的解离最 优解相差很远。 ( 2 1两阶段算法。对构造算法进行改进，提出了两阶段算法。第一阶段 得到一个可行解，第二阶段对解进行调整。在保持解是可行的基础 上，尽力向最优解接近，每一步都用产生的新可行解取代原来的可 浙江大 学 硕 士 学 位论文 行解，使得目标函数值得到改进，一直进行到目标函数值不能改进 为止。该方法经常运用交互式优化技术，充分发挥人在求解问题过 程中的主观能动性。 ( 3 )不完全优化算法。精确算法中的决策原则，在规模很大的问题中 导致计算量的指数增长。在不完全优化算法中，用启发式准则代替 可以有效缩小解的收缩空间。 ( 4 )改进算法。从一个初始解开始，通过对当前的解进行反复的局部调 整，以求得问题的满意解。 由于启发式算法在收敛速度和收敛程度卜- 的缺陷，故在配送线路的优化问 题上也有一定的局限性。 目前，用并行计算机进行的并行算法、基于生物遗传原理的遗传算法、神 经网络理论等在配送线路优化问题中也有一定的应用和发展【1 8 1 f 1 9 1 。 本文主要针对现在物流配送的现状，以拼车配送为背景建立了一个混和整 数规划模型，并对所建立的模型给出其有效算法，然后以实例加以验证比较。 浙江大学硕 士 学位论丈 第二章预备知识 2 1 拉格朗日松弛 十八世纪拉格朗日对非线性优化问题提出了拉格朗日乘子方法，g e o f f r i o n t 7 1 与s h a p i r 0 1 8 1 分别于1 9 7 4 年和1 9 7 9 年提出了拉格朗日方法并讨论了在整数规划 中的应用，f i s h e r 在1 9 8 1 年也讨论了拉格朗日松弛在整数规划中的应用【5 1 并于 1 9 8 5 年将其推广应用到了更多的问题当中9 1 。 考虑如下优化问题： z 十。m i n c x s t a x _ b ，( p ) x 爿 引入拉格朗日非负乘子旯，可得优化问题p 的拉格朗日松弛问题即： m i n “+ a ( a x - b ) s t x 称三( a ) = m i n c x + 五( a x 一6 ) ：x x 为拉格朗日函数。 2 0 引理1 ：五为任一拉格朗| 非负乘子，x 为优化问题p 茎的任一可行解， 1 拉格朗同函数的函数值工( a ) 是优化问题p 的最优目标函数值z + 的下界； 2 若( a ) = c x ，则x 是优化问题p 的最优解。 证明： 1 因为x 为优化问题p 的可行解，则a x 6 ，又a o ，故五( 爿x 一6 ) 墨o ， 贝z + = n f l i n “：a x 0 ，i = 1 ，2 代表 相应客户点对货物的需求量，这里当然有一b ( o ) = 6 ( 1 ) + 6 ( 2 ) ；。此处考虑的是 由配送中心0 向两个客户1 ，2 分别发送1 单位货物的情形，不妨设配送车辆 的容量为2 单位，则显然为了尽可能的降低运输费用，可以用一辆汽车先将2 单位货物出配送中心0 运送到客户点2 ，在客户点2 卸下所需l 单位货物之后 再将剩下的1 单位货物沿着客户点2 到客户点l 的最短路( 2 ，1 ) 运送到客户点1 。 可以看出送货车辆的运输线路如图2 中粗线所示，从而在进行货物装载时 就可以考虑先装客户1 的货物然后再装客户2 的货物，这样既节约了成本又提 高了运输车辆的利用效率还方便了货物的装卸搬运。 浙江大学硕士学位论文 以上我们考虑的是拼车配送中最简单的情形，现实的情况是一个配送中心 往往要向很多客户送货，比如一个城市烟草配送中心的客户有上千家，形成一 个庞大的配送网络，这时要对“配”或者“送”进行优化以降低配送成本就是 一个相当困难的问题。以下将运用数学模型来描述这类问题。 3 2 数学模型的建立 在引入模型之前，首先做如下的假设： ( 1 ) 假设各客户点的需求量都是整数 ( 2 ) 考虑理想状态下的车辆调度，即配送中心使用同类型的配送车，且容量 为整数； ( 3 ) 总假设任意两结点之间的弧都代表这两结点之间的最短路或者实际生 活中被普遍接受的“最短路”； ( 4 ) 不考虑货物的装卸过程； ( 5 ) 每条弧对于车辆无容量限制； ( 6 ) 假设配送中心的可调度的车辆数量有限 ( 7 ) 所有配送车辆完成配送后都要返回配送中心； 如图3 所示，表示图3 中所有结点的集合，a 代表图3 中所有弧的集合 其中每条弧表示关联两结点的最短路，令b a 表示图3 中虚线弧的集合即返 回到配送中心的弧的集合，吒表示( f ) 弧的距离，显然有毛= d j ，任一结点f 旁边的6 ( f ) 代表结点f 对货物的需求量，若结点f 为配送中心则有6 0 ，否则 b ( i ) 0 ；考虑由配送中心向多个客户点供应货物，货物是通过拼车运送且车辆 浙江大 学 硕 士 学 位论文 最后要返回配送中心，目标是在满足各客户点需求量的同时尽可能的降低运输 b ( o ) b ( 1 ) 成本。为此建立如下模型： 模型1 ： m i n q x , j ( ，j ) e s t x o ，蔓u ， ( 0 ，1 ) e 瓦一乃= o k ，一巧= 6 ( f ) ( ，】【i , j ) e a 巧k x f ， 置，i n t ， k 0 ， 蹬3g = ( n a ) v f n v f v f n v ( i ) a ， v ( i ) a ， v ( i ，) a ， b ( 3 ) 模型l 是以配送中运送成本最小为目标建立的混和整数网络流规划模型， 其中与k 分别代表经过( f ，) 弧上的车辆的数量和货物量，k 为一辆车的容 量，u 为配送中心拥有的车辆数量，c , j 表示每辆车从结点f 经过( f ，) 弧到达 结点，的成本。考虑到一般情况下，增发一辆汽车的边际费用较高，故当f 为配 d q 嫡 力 q 嫡 浙 江大 学 硕士 学 位论文 送中心时有c o ，= c o + c , d o ，v j n ；当i 为客户点时有q = c l 办，f 0 且 w n ，其中c o 是增加一辆汽车的固定费用。c l 表示相对于行车距离的费用系 数，且c 0 与c 1 均为己知常数，从而g 可经简单计算求得。 约束条件( 2 ) 保证所用车辆的数量不会超过限制；约束条件( 3 ) 和( 4 ) 分别保 证通过各个结点总的车辆和货物量的平衡：约束条件( 5 ) 保证每条弧上经过的货 物量肯定能被经过的车辆所装载；约束条件( 6 ) 保证车辆数量的整数性；这里考 虑配送中心只有一个结点0 ，其余结点都是客户的情形，对于多个配送中心的 情形，可以建立类似的模型。 定理2 ：若= p h 删为模型1 的最优解，则0 瓦1 ，v i ， o ： 证明：若模型l 的最优解中存在一 1 ，i 、j n o ， i 妨设焉= 2 ， 则k c o ，故我们可以调整货物的装载，使得该车不经过结点i 而直接由供 应点0 经( o ，) 弧到达结点，从而降低了运输成本，这显然与为最优解矛盾。 故定理1 成立。 由于混和整数网络流问题是n p 难的，本文考虑其近似解求解的有效算法。 浙 江大 学 硕 士 学 位 论 文 第四章算法以及求解过程 求解模型1 的基本思路是：首先对约束条件( 5 ) 进行松弛得到拉格朗日松弛 问题并利用网络单纯形法求解得到原问题的一个下界；其次由试探法得到原问 题的一个上界；然后调整拉格朗e t 乘子得到原问题的上下界并校正，直到得到 一个可接受的近似解或者迭代次数足够多则算法停止。 4 1 最优解的下界 引入拉格朗日非负乘子松弛模型1 中约束条件( 5 ) 可得其拉格朗日松弛问 题模型： 模型2 ： m i n q + ( 巧一k x ，) ， ( ，) “( i ，) e a s t x o 。 - u ， f 0 ，j ) e n 扎一= o ( ，j ) e ( f ，j ) e a 巧= 蛔 ( j ，j ) e a x o i m 0 ， v i n v i n v f v ( i ，_ ，) a v ( i ，u ，) a 模型2 的最优目标函数值是模型1 的一个下界。 将模型2 分解成两个相互独立的优化问题模型3 ，4 得 模型3 ： m i n ( q 一世乃) ， ( z ，j ) e s t x o ，茎u ， v f n ， ( o ，j ) 五。一 = o ， v j en 晴，i ) e a( z ，j ) e a x 。i n t 模型4 ： v ( i ，j ) a m i n 乃巧， ( f ) c a s t 圪一= 6 ( f ) ， v i n k 0 ， v ( i ，j ，) a 对于具体的拉格朗日乘子 = 凡 ”j ) 。而言，模型3 ，4 为两个纯网络流问 题，可借助9 四络单纯形法分别求解，将所得两最优值相加即可得到拉格朗日松 弛问题即模型2 的最优值。 4 2 最优解的上界 利用模型4 每次迭代所得的最优解 巧) 。忆肛。出发利用试探法来确定模型 1 的可行解x = 五) 。删，从而得到原问题即模型l 本次迭代的一个上界。 1 确定 局) 州。，使其满足k ( x 。一1 ) ，v ( i ，) a b 。 2 若 ) 即庙。满足定理l ，则转3 o 否则必存在 乃2 ，i 、j o ) ， l g = l 匕k j ，调整，= r o ，一k l ，巧= 巧一k l o ，k ，= k ，+ 足岛；并 返回1 。 3 确定 置。) 。，其中置。=瓦一。若置。o ，v ，e n ，i ) e a b( t , j ) e a b 则已得到可行解x = 哳。；否则转4 。 4 若存在i n ，置。 o ，使得i ( 一z l ) l z “l 目，或者迭代次数已经 达到了某个限制，则停止算法； 第5 步：调整拉格朗日乘子； 笱“= 力+ & ( 一瓯) + ，其中 o k = 总( z “一z ( ) ) “】 肌一1 1 2 进，则“= 2 第6 步：令= k + 1 ，返回第二步。 0 胁2 ；若下界在连续三次迭代中没有改 浙 江 犬擘硕 士 学位论文 第五章实例验证 通过一个实例来验证我们的算法的有效性。 b ( 2 )b ( 3 ) 4 1 图4 如图4 所示，考虑由一个配送中心0 向四个客户点1 、2 、3 、4 供应货物 由容量为1 0 单位的车辆进行运送，配送中心0 拥有的车辆数量为l o 辆，各客 户需求量与结点问最短距离分别是b ( 1 ) = 1 1 ，b ( 2 ) = 1 3 ，b ( 3 ) = 2 4 ，b ( 4 ) = 1 2 ， a 0 1 = 5 ，d 0 2 = 8 ，a 0 3 = 8 ，d 0 4 = 1 0 ，一2 = 5 ，d j 3 = 3 ，吐4 = 5 ，d 2 3 = 4 ，d 2 4 = 8 ， 屯= 4 。 若c o = 0 、c 1 = 1 时，我们呵建立类似1 的模型，经过平均3 5 0 0 次左右迭代 得其最优目标值即最小运输成本为1 0 4 ；而通过本文的算法只经过4 次迭代就 找到了一个目标值为1 0 4 的可行解，即该问题的最优解。迭代过程见附表1 。 若c 0 = 5 0 、q = l ，同样可建立类似模型1 的模型，经过平均3 0 0 0 次左右迭 代得其最优目标值即最小运输成本为4 0 4 ；通过本文的算法只经过了1 次迭代 就找到一个目标值为4 0 4 的可行解，即该问题的最优解，迭代过程见附表2 。 浙 江大 学硕 士 学位论文 若考虑用c l a r k e 和w r i g h t 提出的节约法来求解该问题，得到的配送计划总的费 用为4 0 6 ，其配送线路为： 0 一l o o 一2 o o 一3 o o 一4 o ( 1 ) ( 1 ) ( 2 ) ( 1 ) 其中括弧里数字代表该条线路上的行车数量。 浙 江大 学硕 士 学位 论文 o五。= 刀) = 0 ，01 4 0 v ( i ) a 石i = 3 0 4 9 5 硝z = 3 6 0 4 0 01 2 0 硝3 = 6 6 5 3 5 砧= 3 3 2 6 7 碥= 3 6 2 6 2 箍= 3 6 0 4 0 砧= 5 6 9 2 3 9 4 ：3 3 2 6 7 01 2 0 罨= 0 2 3 0 7 硝= o 2 4 0 3 砭= o 1 2 5 0 础= 1 1 瑶= 1 3 瑶= 2 4 瑶= 1 2 瑶= 6 0 呓= 2 4 i 扛2 5 壤= 1 3 瑶= 6 0 瑶= 1 3 瑶= 2 4 瑶= 2 4 x o o l = 2 靠= 2 砖= 3 戢= 2 肆= 2 x 品= 2 x o o = 3 碥= 2 嗣。= 6 捌，= 3 x k = 3 f ：= 2 雹。= 2 x l 。= 3 列。= 1 砥4 _ 6 靠= 2 矗= 3 瑶= 3 x ? o = 1 碥= 2 x 磊= 3 2 3 浙 江太 学 硕士 学 位论文 kz 。 z ux 4 召l = 3 6 2 6 2 罨= 3 6 0 4 0 砧= 5 2 1 0 8 砧= 3 6 1 5 6 稚= 0 0 6 2 6 01 2 0 砧= o 2 3 0 7 碥= o 2 4 0 3 碥= o 1 1 5 6 砭= o 1 2 5 0 = 0 1 1 5 6 砧= 3 6 2 6 2 砧= 3 8 9 8 6 砧= 4 7 1 9 8 砧= 3 ，6 1 5 6 砧= o 0 6 2 6 露= o 0 5 4 0 砧：0 2 3 0 7 01 0 4 咒= o 2 4 0 3 矗= o 1 1 5 6 砭= o 1 1 7 8 9 4 = o 0 5 8 9 砭= o 1 2 5 0 砧= o 1 1 5 6 瑶= 6 0 瑶= 1 1 圪= 2 4 圪= 1 2 瑶= 2 4 瑶= 3 6 瑶= 1 3 圪= 2 4 碥= 7 雹。= 2 焉= 3 疋= 2 x ? o = 2 x 嘉= 3 碥= 2 x ；。= 3 晶= 4 碥= 2 x 2 4 = 3 碌= 1 商= 1 2 4 浙 江 太 学 硕 士 学 位论文 0五。= 饼 = 0 ，05 9 0 v ( i ，) a 砧= 3 0 4 9 5 硝：23 6 0 4 0 04 0 4 砧= 6 6 5 3 5 砧= 3 3 2 6 7 瑶= 1 1 y o o = 1 3 瑶= 2 4 瑶= 1 2 瑶= 6 0 x 卜2 4 瑶= 2 5 瑶= 1 3 础= 2 磙= 2 端= 3 x g , = 2 x ? o = 2 砖= 2 x 3 0 0 = 3 砖= 2 矗，= 6 砧= 3 砧= 3 嗣：= 2 x 知= 2 x l 。= 3 z 。= 1 2 5 浙江大 学 硕士 学 住论 文 第六章结论与展望 该模型可以解决的主要问题有： 1 知道各个客户点的需求量之后能够计算出相应的拼车计划以及每辆汽车各自 的行车线路； 2 在有一定业务数据支持下能够计算出配送中心在保证服务的情况下可以拥有 的尽可能少的车辆数目，避免资源浪费； 3 该模型并不是一成不变的，它可以根据配送前顾客临时的需求变化相应的作 出调整。 随着现代物流业务的发展，个性化的服务要求越来越强烈，这就要求配送 中心要在配送成本不增加或少增加的前提下尽可能地满足客户各种个性化的要 求。在现实生活中单纯追求最小运送成本往往会造成时间上的延误，当前客户 对于配送时间上的要求越来越高，这就对配送中心关于配送计划的制定以及配 送线路的选择提出了新的挑战即考虑动态的配送计划的制定以及配送线路选 择。 浙江大 学 硕士 学 位论文 参考文献 【1 】a h u j ark ，m a g n a n t itl ，o r l i njb n e t w o r kf l o w s ：t h e o r y ，a l g o r i t h m s a n da p p l i e a t i o n s n j ，p r e n t i e eh a l l ，e n g l e w o o dc 1 i f f s ，1 9 9 3 2 y a nsy ，c h e nhl as c h e d u l i n gm o d e la n das o l u t i o na t g o r i t h mf o r i n t e r c i t yb u sc a r r i e r s t r a n s p o r t a t i o nr e s e a r c hp a r ta ，2 0 0 2 。 3 6 ：8 0 5 - 8 2 5 3 y a nsy ，l i ncg a i r l i t i es c h e d u li n gf o r t h et e m p o r a r yc l o s u r eo f a i r p o r t s t r a n s p o r t a t i o ns c i e n c e , 1 9 9 7 ，3 1 ：7 2 8 3 4 y a nsy ，y o u n ghf ad e c i s i o ns u p p o r tf r a m e w o r kf o rm u l t i f l e e t r o u t i n ga n dm u t i s t o pf l i g h ts c h e d u l i n g t r a n s p o r t a t i o nr e s e a r c h 助，ta ，1 9 9 6 ，3 0 ：3 7 9 3 9 8 5 i a r s h a l l1 。，f i s h e r t h el a g r a n g i a nr e l a x a t i o nm e t h o df o rs o l v i n g i n t e g e rp r o g r a m m n gp r o b l e m s m a n a g e m e n ts c i e n c e , 1 9 8 1 2 7 ：l 1 8 6 c l a r k eg ，w r i g h tj w s c h e d u li n go fv e h i e l e sf r o mac e n t r a ld e p o tt o an u m b e ro fd e li v e r yp o i n t s o p e r a t i o n sr e s e a r c h , 1 9 6 4 ，1 2 ：5 6 8 5 8 1 7 g e o f f r i o n ，a l a g r a n g a n r e l a x a t i o n sf o r i n t e g e rp r o g r a m m n g 舶t h e m a t c a p r o g r a m m i n g 1 9 7 4 ，2 ：8 2 1 1 4 8 s h a p l r ojf m a t h e m a t i c a lp r o g r a m m i n g ：s t r u c t u r e sa n da l g o r i t h m s w i l e y ，n e wy o r k ，1 9 7 9 9 m a r s h a l ll ，f i s h e r a na p p l i c a t i o n so r i e n t e dg u i d et ol a g r a n g i a n r e l