（管理科学与工程专业论文）考虑车辆满载率的车辆路径与三维装箱混合问题研究.pdf

学位论文版权使用授权书 江苏大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件和电 f 文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 n 的内容和纸质论文的内容相一致，允许论文被查阅和借阅，同时授 ? 中国科学技术信息研究所将本论文编入中国学位论文全文数据库 托向社会提供查询，授权中国学术期刊( 光盘版) 电子杂志社将本论 之编入中国优秀博硕士学位论文全文数据库并向社会提供查询。 论文的公布( 包括刊登) 授权江苏大学研究生处办理。 本学位论文属于不保密一。 学位论文作者签名：爿乏雀 矽j j 年6 月d 日 指导教师签 矶lf 年 考虑车辆满载率的车辆路径与三维装箱混合问题研究 r e s e a r c ho n3 l c v r pw i t hc o n s i d e r i n gt h e u t i l i z a t i o nr a t e 江苏大学 2 0 11 年6 月 江苏大学硕士学位论文 摘要 将车辆路径问题与三维装箱问题结合起来研究，旨在保证以最短 距离对所有客户进行配送的前提下，提高每台车辆的满载率，最大限 度的降低车辆的使用数量，进而减少配送中心的物流成本。到目前为 止，车辆路径问题与三维装箱问题都分别得到了较广泛的研究，取得 了众多研究成果，但是将两者集合起来优化的研究比较少。 文章首先介绍选题背景与研究目的，详述了车辆路径问题、装箱 问题的概念、分类，并对其各自的研究现状进行综述，进而提出在研 究车辆路径与三维装箱混合问题时保证车辆满载率最大这一思想。 其次，文章在约束条件上考虑到了货物的旋转、后进先出法则以 及易碎货物的装载等合符实际的情况，将车辆满载率作为目标函数之 一来建立数学模型，建立了一个双目标规划的数学模型。在模型的求 解上，设计了一种禁忌搜索和局部搜索相结的算法，通过算例验证了 该模型与算法，得到的结果证明了该算法是求解该问题的有效算法。 再次，文章通过上述模型和算法对镇江烟草物流配送中心的实际 数据进行具体计算，结果进一步验证了模型及算法的有效性。同时， 对镇江烟草物流配送中心烟草物流配送系统进行构架，以利于即将进 行的物流配送系统设计。 最后，对全文内容及研究结论进行了总结，并展望了进一步研究 的方向。 关键词：物流管理，车辆路径与三维装箱混合问题，禁忌搜索算法， 局部搜索算法，烟草配送 a b s t r a c t t h ep a p e rs t u d i e dt h ev e h i c l e r o u t i n gp r o b l e mt o g e t h e rw i t ht h et h r e e d i m e n s i o n a l c o n t a i n e rl o a d i n gp r o b l e m ，i no r d e rt o i m p r o v et h el o a d i n gf a c t o rf o re a c hv e h i c l e ， r e d u c et h em a x i m u mn u m b e ro fv e h i c l e s ，a n dt h e nr e d u c et h ec o s t so fd i s t r i b u t i o n c e n t e ru n d e rt h ep r e m i s eo ft h es h o r t e s td i s t a n c ed i s t r i b u t i o nf o ra l lc u s t o m e r s s of a r , v e h i c l er o u t i n gp r o b l e ma n dt h et h r e e - d i m e n s i o n a lc o n t a i n e rl o a d i n gp r o b l e m sw e r e m o r ee x t e n s i v e l ys t u d i e d ，a n dh a v eg o tan u m b e ro fr e s e a r c hr e s u l t s ，b u tt h er e s e a r c ho f t h ec o m b i n a t i o no nt h e s et w op r o b l e m sh a sl e s sr e s u l t s a tf i r s t ，t h i sp a p e ri n t r o d u c e dt h eb a c k g r o u n da n dt h er e s e a r c h p u r p o s e s ，d e t a i l so f t h er o u t i n gp r o b l e m ，t h ec o n c e p to fp a c k i n gp r o b l e m ，c l a s s i f i c a t i o n , a n ds u m m a r i z e d t h es t a t u so ft h e i rr e s e a r c h ，a n dt h e n p r o p o s e dt h ei d e ao fh o wt og u a r a n t e et h e m a x i m u ml o a d i n gf a c t o ro ft h ev e h i c l e sw h e ns t u d i e dt h em i x e d p r o b l e mo f t h r e e - d i m e n s i o n a lp a c k i n ga n dt h ev e h i c l er o u t i n gp r o b l e m s e c o n d l y ，t h ep a p e rt o o ki n t oa c c o u n tt h er o t a t i o no fg o o d s ，l a s ti nf i r s to u tr u l e a n dt h e l o a d i n go ff r a g i l eg o o d s ，t h ev e h i c l el o a d i n gf a c t o r , w h i c hw e r ea l li n a c c o r d a n c ew i t ht h er e a l i s t i cc o n d i t i o n s ，a n dp u tt h el o a d i n g f a c t o ra so n eo ft h e o b j e c t i v et ob u i l dab i o b j e c t i v ep l a n n i n gm a t h e m a t i c a lm o d e l i no r d e rt os o l v et h i s p r o b l e m ，t h i sp a p e rp r e s e n t e dan e wa l g o r i t h mw h i c hc o m b i n e dt a b us e a r c h ( t s ) w i t h l o c a ls e a r c h ( l s ) f i n a l l y , t h ef e a s i b i l i t ya n de f f e c t i v e n e s so ft h em e t h o da n d a l g o r i t h m w a sp r o v e db yt h ea d o p t i o ne x a m p l e t h e n ，t h ep a p e ru s e dt h ea c t u a ld a t ao nz h e n j i a n gt o b a c c od i s t r i b u t i o nc e n t e rt o c a l c u l a t et h es p e c i f i ct e r m s ，a n dt h er e s u l t sf u r t h e rv a l i d a t e dt h ee f f e c t i v e n e s so ft h e m o d e la n dt h ea l g o r i t h m a tt h es a m et i m e ，t h ep a p e re s t a b l i s h e daf r a m e w o r ko ft h e d i s t r i b u t i o ns y s t e mo fz h e n j i a n gt o b a c c od i s t r i b u t i o nc e n t e r , i no r d e rt of a c i l i t a t et h e d e s i g no ft h ed i s t r i b u t i o ns y s t e m a tl a s t ，t h ef u l l - t e x tc o n t e n ta n dc o n c l u s i o n sw e r es u m m a r i z e d a n dt h ep r o s p e c t s f o rt h ef u r t h e rr e s e a r c hw e r ea l s op r o p o s e d k e yw o r d s ：l o g i s t i c s m a n a g e m e n t ，3 l c v r p ，t a b us e a r c h ，l o c a ls e a r c h ， t o b a c c od i s t r i b u t i o n i i 江苏大学硕士学位论文 目录 第1 章绪论1 1 1 选题背景1 1 2 研究目的和意义2 1 3 研究方法与内容3 第2 章车辆路径问题与装箱问题研究综述6 2 1v i 冲一6 2 1 1v r p 描j 查6 2 1 2v r p 分类8 2 1 3v r p 研究现状1 0 2 2c l p 17 2 2 1c l p 描j 苤17 2 2 2c l p 分类18 2 2 3c l p 研究现状2 2 2 3 车辆路径和装箱混合问题研究现状2 5 第3 章3 l c v r p 建模及求解2 7 3 1 问题描述及模型建立2 7 3 1 1 问题描述2 7 3 1 2 模型中变量的设定2 9 3 1 3 模型的建立2 9 3 2 模型求解算法3 2 3 2 1 算法总流程3 2 3 2 2 求解三维装箱的局部搜索算法3 3 3 2 3 求解3 l c v r p 的禁忌搜索算法3 5 3 3 模型计算3 9 第4 章镇江烟草配送路径优化应用及其物流配送系统构架4 2 4 1 镇江烟草物流配送路径优化问题4 2 三维装箱混合问题研究 4 2 4 4 4 5 4 6 4 6 4 7 4 7 4 8 4 8 4 8 ! ；o 5 l 5 6 ! ；7 6 5 i v 江苏大学硕士学位论文 第1 章绪论 1 1 选题背景 伴随着世界经济的快速发展，物流的作用也越来越重要。现代物流作为一种 先进的组织方式和管理技术，被广泛认为是企业降低能耗、提高生产率以外的重 要的利润源剽。 根据中国物流与采购联合会最近发布的前三季度物流运行形势分析报告 显示f 2 】：2 0 1 0 年前三季度，我国物流运行继续保持平稳较快增长，社会物流总费用 为4 8 1 8 2 亿元，按可比价格计算，比上年同期增长1 4 9 ，与g d p 的比率为1 7 9 ； 从构成情况看，2 0 1 0 年前三季度，运输费用为2 5 4 9 5 亿元，同比增长1 5 5 ，运输 费用占社会物流总费用的比重为5 2 9 ；保管费用为1 6 7 1 7 亿元，同比增长1 3 3 ， 保管费用占社会物流总费用的比重为3 4 7 ，管理费用为5 9 7 1 亿元，同比增长1 7 1 ，占社会物流总费用的比重为1 2 4 t 2 1 ，上述数据可反映出物流需求在经济利好 势头的带动下，继续呈现出较快增长态势，规模将进一步扩大【2 】，其中在社会物流 总费用中所占的比重最大的是运输费用，说明物流配送是物流产业中的关键一环。 物流配送中的一个重要问题是如何根据己知待服务客户的网点布局，设计出合理、 有效的车辆行驶路线，以到达减少车辆数量和行驶路线长度的目的【3 1 ，这就是车辆 路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 。 此外，集装箱是现代物流中的重要工具。在某些发达国家，集装箱运输方式 已经在其全国物流运输量中占很大比重，与此类似的，我国越来越多的物流公司 开始采用厢式车辆进行配送。不管是集装箱还是厢式货车，都存在合理装箱问题 ( c o n t a i n e rl o a d i n gp r o b l e m ，c l p ) 。而对于合理装箱问题的研究就在于充分利用计 算机的能力来设计高质量的装箱方案，减少集装箱的使用数量，从而提高运输工 具的利用率，减少运输成本。c l p 被广泛应用于实际生活、计算机科学、工业领域 以及交通运输领域，例如服装的裁剪、轮船和飞机的装舱、新闻行业中的排版、 计算机科学中的文件分配，内存管理以及任务调度等都是装箱问题的应用。在实 际生活中，c l p 应用最广泛的是物流运输行业，因此c l p 的有效解决对该行业产生 的影响最大【4 】。 在物流相关技术的应用和物流管理理论发展受到越来越重视的今天，如何以 考虑车辆满载的车辆路径与三维装箱混合问题研究 最短的配送距离解决配送到户，并提高每台配送车辆的满载率，进而如何减少派 车数量就成为一个很重要而且迫切需要解决的实际问题。车辆路径问题与装箱问 题作为物流配送过程中的两个关键性技术，对降低配送中心的运行成本、提高配 送业务的服务水平、提高物体装载的优化程度、提高配送业务的工作效率和规范 业务流程都有重要的意义。文章就是在这样的背景下产生的。 1 2 研究目的和意义 在物流配送活动中，如果在减少配送总距离的同时，能够更有效地利用运输 容器的空间，特别是针对当前普遍采用的厢式车辆进行配送的企业配送中心来说， 就可以从整体上大大降低运输成本，节约运输时间，提高物流效率，从而提高物 流相关企业的盈利能力，获得可观的经济和社会效益。 自从1 9 5 9 年由d a n t z i g 和r 锄s e r 提出【5 j v i 冲问题以来，出现了大批学者对此问 题进行研究，并将原始问题扩展，因此出现了很多研究分支。在这些研究分支中， 带装载能力约束的车辆路径问题( 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 ，c v r p ) 是 v r p 众多分支中最常见、最重要的一个研究问题。带装载能力约束的车辆路径问 题指的是在配送过程中，针对每条路径上的运货车辆，都会有装载能力的约束条 件，一般情况为所配送物体的总重量或总体积的约束，即不能超过称量所能承载 的最大重量货体积。当然，在现实生活中，很多情况下不止是这么简单的约束， 约束条件会变的更加复杂。例如，现代物流配送普遍采用的厢式配送，所配送的 物体是成箱包装好的，配送的物体的形状通常为长方体，所配送物体在车厢中的 摆放方案也会成为路线方案设计的一个约束条件，倘若无法找到一个合适的物体 摆放方案把某几个客户所需求的物体都装进同一辆厢式配送车辆中时，就必然不 可以把这几个客户放在同一辆车的行驶路线中，必须派用多辆配送车辆对这些客 户进行配送，或者是把这些客户分布在不同的路线中，以装下所有的物体；又例 如在进行烟草配送时，目前很多烟草配送中心采用的是定时定线路的送货方式， 没有根据每天的需求量变化进行适时的路线更新。并且，在卷烟销售的淡季与旺 季动用同样数量的车辆，就会导致车辆空载率增加和送货成本的增加。如何以最 短的配送距离解决配送到户，并提高每台配送车辆的满载率，进而如何减少派车 数量和做到每条配送线路的工作时间大致均衡是当前众多与烟草配送中心相类似 2 江苏大学硕士学位论文 的其他配送中心应该立即解决的问题。在这种情况下，c v r p 就附加了三维装箱能 力的约束。 通过文献综述可以发现，上述附加三维装箱能力的约束的c v r p 实际上就是 一种车辆路径与三维装箱混合问题( 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 dv e h i c l e r o u t i n gp r o b l e m ，3 l c v r p ，又叫做带三维装箱约束的车辆路径问题) ，3 l c v r p 最先是由g e n d r e a u 等人【6 】在2 0 0 6 年提出，是v r p 中的一个较新的分支，相关研 究的文献较少，出来的成果也不是很丰富，并且当前还需要考虑的约束条件很多， 比如说每辆车的满载率问题、每条配送线路的工作时间问题等。对c v r p 与3 d c l p 的混合问题进行研究具很大的价值，能够将物流配送中的车辆行驶路线设计和装 箱方案设计两者结合，以达到更大程度地优化资源配置、提高配送效率和降低运 输成本的目的。通过本文的研究，建立出更加适合现实环境的数学模型，并寻找 出新的能够有效解决该问题的方法，并为以后车辆路径和装箱混合问题的研究， 以及相关应用系统的开发提供一个很好的借鉴和参考依据。 1 3 研究方法与内容 文章从介绍v r p 与c l p 的基本理论出发，通过大量文献的阅读和梳理，了解物 流配送研究的现状，并同实际配送问题相结合，建立起了考虑车辆满载率的车辆 路径与三维装箱混合问题的数学模型，试图在保证以最短距离对所有客户进行配 送的前提下，提高每台车辆的满载率，最大限度的降低车辆的使用数量，进而减 少配送中心的物流成本。在模型约束条件上考虑到了货物的旋转、后进先出法则 以及易碎货物的装载等合符实际的情况。在求解算法的选择上，为了更加高效的 求出满意解，对建立的数学模型运用了禁忌搜索与局部搜索相结合的算法来进行 求解，并结合实际算例来验证模型和算法。最后，本文通过该模型应用的实例一 一镇江烟草物流配送中心，选取该配送中心某天的实际需求量进行计算，来进一 步验证模型的正确性和有效性，接着对镇江烟草物流配送中心烟草物流配送系统 进行的构架，以利于接下来将进行的物流配送系统设计。 本文将提高每台车辆的满载率也作为一个目标，同配送总距离最短两者结合 起来优化配送，为配送中心物体配送方案的设计提供决策指导，论文的总体结构 如图1 1 所示。 3 考虑车辆满载的车辆路径与三维装箱混合问题研究 图1 1 论文结构图 论文一共分为五章，各章组织如下： 一章绪论 章主要研究内容包括：论文的研究背景，论文研究的目的和意义以及论文 研究方法与内容。 二章相关理论介绍 章主要是介绍v r p 、c l p 的相关理论以及国内外研究现状等。 三章3 l - c v r p 建模及求解 章是全文的核心章节，首先建立了车辆路径与三维装箱混合问题的数学模 了提高车辆满载率( 重量满载率和体积满载率) ，将车辆的满载率最大也作为 标函数，同时在约束条件上考虑到了货物的旋转、后进先出法则以及易碎 装载等合符实际的情况。接下来对模型求解算法进行了分析，选择了计算 4 江苏大学硕士学位论文 效率较高的禁忌搜索与局部搜索相结合的算法来求解改模型，并给出了求解算法 具体流程，本章最后通过算例对模型和算法进行了验证。 第四章镇江烟草配送路径优化应用及其配送系统构架 本章应用上述模型和算法，通过对镇江烟草物流配送中心的实际数据进行具 体计算，验证上述所建立的模型和算法的有效性。同时，对镇江烟草物流配送中 心烟草物流配送系统进行构架，以利于即将进行的物流配送系统设计。 第五章总结与展望 对论文所研究的问题进行总结分析，并对3 l c v r p 的未来研究做出展望。 5 考虑车辆满载的车辆路径与三维装箱混合问题研究 第2 章车辆路径问题与装箱问题研究综述 2 1v r p 2 1 1v r p 描述 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 由d a n t z i g 和r 锄s 一7 1 于1 9 5 9 年提 出，由于其重要的实用价值，在现实中有着非常广泛的应用，在提出之初便受到 了广大学者的关注。车辆路径问题的一般定义可以描述为：对给定的若干客户点 和一个或者多个配送中心，要求在满足某些约束条件下( 约束条件可以是配送车辆 载重量的限制、客户需求量或者客户收发货时间等) ，设计出适当的车辆行驶路线， 使的车辆从配送中心出发，对所有客户进行服务，最后返回( 有时也不需要返回) 配送中心，以达到某个或者某些目标( 目标可以是车辆行驶的总路程最短、配送中 心所需总费用最小或者是车辆所用时间最少等) 【3 1 。可以用图2 1 直观展示出来。 配送中心 客户点 图2 1v r p 问题示意图【3 】 v r p 问题主要构成要素包括客户( c u s t o m e r ) 、物体( g o o d ) 、车辆( v e h i c l e ) 、配 送中- c , ( d i s t r i b u t i o nc e n t e r ) 、运输网络( r o a dn e t w o r k ) 、约束条件( c o n s t r a i n t ) 和目标 函数( o b j e c t i v e ) 等【8 】【9 】： 1 、客户 客户是配送的主体，每个客户包括客户所处的地理位置、所需求物体的种类 和数量、能够接收物体的时间段、需要被服务的时间等属性。在车辆路径问题中， 客户是最主要的构成要素，客户所需求的物体是该问题约束条件的主要来源。 2 、物体 6 江苏大学硕士学位论文 物体是配送的对象，其中可以将每个客户需求的物体看成是一批物体，而每 个物体又包括物体名称、型号、重量、体积、形状、需要的环境、要求送达的时 间和地点、能否分批配送等属性。物体的重量和体积是影响车辆路径安排决策的 重要条件，当物体总重量或体积超过车辆的最大装载量或体积时，则需要安排多 辆车对物体进行配送。 3 、配送中心 配送中心有又俗称车场，指的是进行集货、分拣、配货、送货作业的仓库、 车站、港口、码头等，根据具体情况，配送中心的数量可以是一个，也可以是多 个配送中心。每个配送中心包括配送中心的地理位置、所配备的车辆类型和数量、 需配送的物体类型和数量等。 4 、车辆 车辆是物体的配送工具，每台运输车辆包括车辆的类型、最大装载量、最长 行驶距离或最长行驶时间、所属配送中心、配送前的停放位置及完成配送任务后 的停放位置等属性。 5 、运输网络 运输网络是配送的交通条件，我们可以从图论的角度把物流配送中的运输网 络看成一个无向图g = ( y ，e ) ，对于单配送中心的车辆路径问题，可以用顶点集 v = 1 ，。，v 。，：，。) 表示1 个配送中心和n 客户的集合，用集合 e = ( ( f ，j ) l ( f ，j y ) ，f 0 ，j o ，f 一表示所有路径，假设所有客户与客户、客 户与配送中心之间均存在可连通的道路，则定义矩阵c = c 玎) ，其中c i y 为从协 到”的距离或成本，本文研究的问题就是在这种假设的运输网络中实现的【l o 】。 6 、约束条件 约束条件是车辆路径问题的核心，不同的实际问题拥有不同的约束条件， v r p 的约束条件主要包括客户对物体型号、种类的约束；物体对运输环境的约束； 客户的优先级约束、物体到达客户的时间约束、配送中心拥有车辆型号的约束、 车辆的载重量约束、司机的工作时间约束、交通条件的约束等。 7 、目标函数 目标函数是车辆路径问题要达到的目标，在v r p 中，目标函数可以是单目标 函数，也可以是多目标函数，该问题的目标函数主要包括运输总行驶距离最短、 7 考虑车辆满载的车辆路径与三维装箱混合问题研究 综合费用最低、准时性最高和运力利用最合理等 总行驶距离最短是v r p 最常用的目标函数，也是最基本的目标函数，因为总 行驶距离与运输成本有很大关系，配送车辆的耗油量、磨损程度、司机疲劳程度 以及运输网络状况等都与总行驶距离直接相关；降低配送中心综合费用低是实现 物流配送业务经济效益的基本要求，综合费用主要包括物体的装卸费用、车辆维 护和行驶费用、员工工资待遇费用、配送中心日常运营费用、管理费用等；配送 中心的主要宗旨就是满足客户，因此有些客户，对于交货的准时性有着很严格的 要求，这就需要将准时性最高作为决策车辆行驶路线的第一目标：运力利用最合 理就需要配送中心以一种最合理的方案安排车辆进行配送，这种方案一般是尽可 能的提高车辆的满载率，充分利用配送车辆的运力，使用最少的车辆完成配送任 务【l l 】。 2 1 2v r p 分类 车辆路径问题的广泛应用决定了该问题所涉及到的约束条件和目标函数很 多，由于不同的应用可能有不同的目标和约束条件，因此出现了各种各样的 v r p c i l 】。车辆路径问题可以根据不同的角度分类，例如可以根据配送中心的数量、 配送任务特征、车辆载货情况、时间限制的要求、车辆类型以及车辆对配送中心 的所属关系来对v r p 进行不同的划分，下面简单介绍这几种分类【8 】【1 1 】： 1 、按配送中心的数量进行分类 正如前面所讲到的，配送中心可以有一个，也可以有多个，因此按照配送中 心的数量，可以将车辆路径问题划分成单配送中心问题和多配送中心问题：单配 送中心问题指的是配送所用到的车辆均来自于同一个配送中心；多配送中心问题 指的是配送所用到的车辆均来自于多个配送中心，并且各个配送中心可能拥有不 同型号的配送车辆。 2 、按配送任务特征划分 按配送任务特征划分可以将v r p 分成纯送货、纯取货以及送取货混合的车辆 路径问题： 纯送货v r p 也称为纯卸货v r p ，指的是从配送中心出发，对所有客户进行配送 服务，将客户需求的物体从配送中心送到各个客户手中；纯取货v r p 也称为纯装 货v r p ，指的是从配送中心出发，把各客户供应的物体取回到配送中心( 或者指定 r 江苏大学硕士学位论文 的某个地方) ；送取货混合v r p 问题也称为装卸混合v r p ，指的是将客户需求的物 体从配送中心送到各个客户手中，同时也要各客户供应的物体取回到配送中心【1 2 】。 3 、按车辆载货情况进行分类 按车辆载货情况进行分类可以将v r p 分成满载、非满载以及满载和非满载混 合的车辆路径问题： 满载v r p 指的是在配送过程中，要保证大部分的配送车辆满载运行，这就需 要单个客户的需求量不能大于配送车辆的最大满载量；非满载v r p 指的是在配送 过程中，配送车辆经常处于非满载的状态；满载和非满载混合v r p 指的是在配送 过程中，一部分配送车辆非满载运行，而一部分配送车辆满载运行【1 2 】。 4 、按时间限制的要求进行分类 按时间限制的要求进行分类可以将v r p 分成无时限车辆路径问题和有时限车 “辆路径问题： 无时限v r p 指的是客户对物体的送达时间没有具体要求；有时限v r p 也称为带 时间窗的v r p ，指的是客户要求所需的物体在规定的时间窗内送达，有时限v r p 还可进一步分为带硬时间窗的v r p 、带软时间窗的v r p 和混合时间窗的v r p ： 带硬时间窗的v r p 指要服务的所有客户都要求物体必须在规定的时间窗内送 达( 或者回收) ，不能提前或延后，否则不接受服务；带软时间窗的v r p 指要服务的 所有客户都要求物体尽量在规定的时间窗内送达，允许提前或延后，如果提前或 延后，要对配送中心施以一定的惩罚；混合时间窗的v r p 指的是要服务的客户一 部分要求为硬时间窗，另一部分客户的要求则为软时间窗【1 2 】。 5 、按车辆类型进行分类 按车辆类型进行分类可以将v r p 分成单车型车辆路径问题和多车型车辆路径 问题： 单车型v r p 指的是配送中心在进行配送服务时所使用的配送车辆都属于同一 种类型，车辆的各种参数都相同：多车型v r p 指的是配送中心在进行配送服务时 所使用的配送车辆的类型可以不完全相同，即用不同型号的配送车辆完成对客户 的配送服务【1 2 j 。 6 、按车辆与配送中心的所属关系进行分类 按车辆类型进行分类可以将v r p 分成开放式车辆路径问题和封闭式车辆路径 9 考虑车辆满载的车辆路径与三维装箱混合问题研究 问题： 开放式v r p 指的是车辆在完成对客户的配送服务后不必返回其出发的配送中 心；而封闭式v r p 指的是车辆在完成对客户的配送服务后必须要返回其出发的配 送中心【1 2 1 。 通过上述分析，车辆路径问题的分类可以用图2 2 直观的表示出来。在现实生 活中，这些分类并不是孤立存在的，每个具体的车辆路径问题一般都是上述多个 分类问题的组合问题，因此就更加复杂。 2 1 3v r p 研究现状 图2 2 车辆路径问题的分类 车辆路径问题是现代物流配送中心物流配送研究的一项重要内容，它是指在 一定的约束下，根据己知的待服务客户的网点布局、待服务客户的需求、物流配 送中心的位置、待配送物体属性以及配送车辆属性等信息，设计出适当的车辆行 驶路线，使得在满足客户需求的同时，实现诸如路程最短、成本最小、客户满意 度最高、耗费时间最少等目标【l 3 】【l4 1 。通过相关文献研究发现，车辆路径问题是一 个n p h a r d ，对于这类问题的求解不存在有效的多项式算法，并且在实际环境中这 l o 江苏大学硕士学位论文 些问题往往涉及到更多的约束条件，因此实际问题不可能求得最优解，只能求得 满意解【1 5 】。车辆路径问题最早由d a n t z i g 和r 锄s 一1 7 - t 1 9 5 9 年提出，目前国内外对 v r p 已经做了大量的理论研究并进行了实际应用的探索，并形成了众多研究分支。 车辆路径问题提出后，由于其具有重要的现实价值，能广泛应用于在物流配送以 及工业行业领域，因此涌现出了众多学者对此问题进行研究，取得了丰富的研究 成果。 c l a r k 和w r i g h t i l 8 】为了解决v r p 问题，在1 9 6 4 年提出- 了c l a r k e w r i g h t 节约算法， 该算法现在被广泛应用于求此类问题的初始解；为了解决较大规模的模型，g i l l e t 和m i l l e r 1 9 】在1 9 7 4 年提出了扫描法，是一种先分组再安排路径的启发式算法，该方 法能有效的解决较简单的v r p 问题；c h r i s o f i d e s 等人【2 0 】在1 9 7 9 年建立了不完全树搜 索算法；f i s h e r 和j a i k a m a r 2 1 1 在1 9 8 1 年建立了一般分配算法；l a p o r t e 等人【2 2 在1 9 8 6 年提出了使用分枝定界法来求解v r p ：b r a m e l 等人【2 3 】在1 9 9 5 年在求解较大规模的 车辆路径问题时提出了基于选址问题转化的l b h b 法等。 随着人工智能技术的不断发展，引入禁忌搜索算法、模拟退火算法和遗传算 法等新方法及人工神经网络和专家系统等新技术，为解决大规模、多目标v r p 提 供了新的解决方法【13 1 。p a r e z a 等人【2 4 藿e 1 9 9 1 年研究的禁忌搜索( t a b us e a r c h ) 算 法，g e n d r e a u 等, k t 2 5 】在19 9 4 年最先将禁忌搜索( t a b us e a r c h ，t s ) 算法应用于解决 冲；姜大立等人【2 6 】为了以较快的速度地找到问题的优化解或近似优化解，在1 9 9 6 年根据问题本身的性质，建立了基于遗传算法的车辆路径的启发式算法，并构造 了车辆路线问题的染色体表达，并对染色体进行可行性映射；a b d o l h a m i d 等人【2 。刀 在1 9 9 7 年最先使用一种自组织的神经网络算法来解决v r p ；l u i z 等人【2 8 】在1 9 9 8 年提 出了一种改进的遗传算法( 即平行遗传算法) 来解决冲：t i m t 2 9 】在1 9 9 8 年对禁忌搜 索和遗传算法两种基于邻域的算法进行分析比较发现，两者虽然各有利弊，但是 禁忌搜索算法效率更高；罗上远等人【3 0 】在2 0 0 0 年首先通过对零售业的实际情况的 分析，建立了符合大多数零售现实的单个配送中心多零售网点的库存分布数学模 型，在模型的求解上运了一种全新的求解算法思路，先划分区域，再进行路径的 生成，使用的方法是节约值插入法，直到将所有的零售点划分完毕，这种分区配 送算法，其难点在于初始点的选择，因为初始点选择的好坏对最后计算的结果影 响很大：t a n 等人【3 l 】在2 0 0 1 年结合了遗传算法和拓扑树搜索算法的优点，在实现过 考虑车辆满载的车辆路径与三维装箱混合问题研究 程中运用所形成的知识库，采用用人工智能的方法来求解车辆路径问题；袁庆达 等人【3 2 】在2 0 0 1 年将t s 算法运用到车辆调度冲问题中，详细介绍了算法的设计过 程。通过数值模拟，验证了算法的可行性。t a r a n r i l i s 等人【3 3 】在2 0 0 2 年使用空间决 策支持系统来解决车辆路径问题；郎茂祥【3 4 】在2 0 0 2 年针对扫描法、节约法等启发 式算法在计算过程中存在组合点零乱、边缘点难以组合、非渐近优化等诸多问题 以及车辆路径问题是n p 的性质，对所构建的车辆路径问题数学模型，运用遗传算 法来求解车辆路径问题，通过具体实验，表明遗传算法算法可以方便地求得该问 题的满意解；同年，郎茂祥和胡思继【35 】针对遗传算法在局部搜索能力方面的不足， 构造了求解车辆路径问题的混合遗传算法，即对所建立的车辆路径问题的数学模 型，运用爬山算法与遗传算法相结合的算法来求解该类问题，计算结果表明用这 种混合遗传算法求解v r p ，可以在一定程度上克服爬山算法在全局搜索能力方面 的不足，同时也能够克服遗传算法在局部搜索能力方面的不足，从而得到质量较 高的解；陈子侠【3 6 】在2 0 0 4 年以杭烟物流6 4 0 0 多户卷烟零售网点配送网络为研究对 象，提出l l o 多条送货线路的网格划分和求解算法；f e i y u el i 等人【37 1 2 0 0 5 年在分析 了4 5 年的文献基础上，对大规模的车辆路径问题进行了研究，设计了一个具有1 2 0 0 个客户的v p r 解决方案；刘云忠，宣慧玉【38 】在2 0 0 5 年对所有的v p r 问题做了一个 综述性研究报告，介绍了车辆路径问题的分类和限制条件，并全面综述了国内外 关于车辆路径问题的模型及算法研究现状，重点探讨了车辆路径问题的模型构造、 求解算法及其适用范围，最后展望了其研究的前景；s u k - t a eb a e 等人【3 9 】在2 0 0 7 年 运用改进的遗传算法对多目标v p r 问题进行了研究，并用仿真给出了实例；陈子 侠【l3 】在2 0 0 7 年的以杭烟物流配送作为研究背景的博士论文中，提出了两阶段法求 解v r p ，并在模型的构件上考虑了诸多因素，包括工作量的界定、配送网点的经 济距离、实际的交通信息等，首先根据将6 4 0 0 多户卷烟零售网点用聚类方法进行 区域的划分，然后再进行单车线路的优化，单车线路的确定用的算法是爬山算法 与遗传算法相结合的算法，最后设计了一个基于g i s 的系统，获得了较满意的成果， 为后人针对大规模v r p 的研究提供了研究思路；曹二保等人【4 0 】在2 0 0 7 年研究了大 规模车辆路径问题，建立了整数规划数学模型，把大规模车辆路径问题转化为区 域划分问题和单车线路优化问题两个子问题进行求解，在区域划分问题上运用改 进的基地启发式分区算法，在单车线路优化问题上运用混合遗传算法，这种改进 1 2 江苏大学硕士学位论文 的两阶段算法有效地解决了此类问题，在可接受时间内能够得到较满意解，并将 该方法运用到现实的物流企业，取得了明显的经济效益；李辉【4 1 2 0 0 8 年在对苏果 超市马群配送中心调研的基础上，根据实际情况，在进行车辆路径安排时，为了 尽量优先满足需求量较大的客户，考虑到了每个客户所需物体的需求量，从而建 立了带有物体权重的单配送中心、单一车型、车辆有载重限制、纯送货、有时间 窗约束的v r p 模型，随后针对模型的特点，通过对一种改进的遗传算法进行求解， 结果表明了模型和算法是正确和有效的；黄敏芳等人【4 2 】在2 0 0 9 年提出一种求解 v r p 的三阶段求解方法，第一阶段采用模糊聚类分析方法对客户进行划分划分， 第二阶段主要是生成备选的车辆路径方案，所用到的方法就是带控制策略的深度 优先搜索算法，第三阶段就是实际路线的映射，文章最后将此三阶段法应用到实 际算例中，验证了算法有效性；覃运梅等人【4 3 】在2 0 0 9 年对v r p 问题进行了研究， 在模型的建立上，建立了一个双目标函数的v r p 数学模型，由于作者深知多派车 所耗的成本巨大，因此主目标函数是所需车辆数最少，次目标函数才是车辆总行 程最短，在模型的求解上面，同样采用两阶段法，第一阶段运用改进的动态聚类 算法分派车辆的配送任务，第二阶段用动态规划方法求出单车行驶路线，文章最 后通过实例证明了算法能够降低问题的复杂性，使问题在合理的时间内得到满意 解，模型和算法均具有较大的参考意义；b u r a ke k s i o g l u 等j k 4 4 1 毛e 2 0 0 9 年对所有的 v p r 问题做了一个综述性研究报告，并把v p r 进行了分类。 通过文献综述研究，针对车辆路径问题的求解算法，可以将其分为精确算法、 启发式算法以及亚启发式算法三类，下面简单介绍这几种算法。 l 、精确算法 精确算法( e x a c ta l g o r i t h m ) 是指一种可以求出问题最优解的算法，该种算法主 要利用数据结构或数学方法来求解基于严格的数学模型或计算机数据结构的规划 问题，在能够求解的情况下，该算法得到的解通常要好于其他算法【l5 1 。求解车辆 路径问题的精确算法主要包括分枝定界法( b r a n c ha n db o u n da l g o r i t h m s ，b b a ) 、动 态规划法( d y n a m i cp r o g r a m m i n g ，d p ) 、集分割算法、网络流算法( n e t w o r kf l o w a l g o r i t h m ，n f a ) 以及割平面法( c u t t i n gp l a n ea l g o r i t h m ，c p a ) 掣9 】【3 8 】。但由于车辆路 径问题是一个n p 难点，对于n p 问题，有一个特征就是随着问题规模的增长，求解 所耗时间和求解域会成指数增长，因此，精确算法只能用于求解简单小规模的车 考虑车辆满载的车辆路径与三维装箱混合问题研究 辆路径问题，在实际应用中有一定的局限性【1 6 1 。 车辆路径问题的集分割算法最早由b a l i n s k 4 5 】等人在1 9 6 4 年提出，算法直接考 虑可行解集合，并在此基础上进行优化，在问题的模型较简单时，该算法能很快 的计算出结果，但是当问题模型较复杂或者约束条件范围较大时，用该算法计算 v r p 时，需要的计算量巨大，要求出最优解也变得非常不容易。 分枝定界法是求解组合优化问题最常用的一种方法，所谓分枝，指的是将求 解域反复