（交通运输规划与管理专业论文）基于随机需求的道路货物调运方法研究.pdf

摘要 现代物流己被公认为是企业降低物资消耗、提高劳动生产率以外的第三利润 源泉，也是企业降低经营成本，提高产品竞争力的重要途径。因而倍受各国的重 视，并得到快速的发展。配送是物流系统运行的一个重要环节，具有不可替代的 作用。随着经济的发展和市场竞争的激烈，顾客对货物运输在时间上和数量上的 需求随机性愈来愈强，要求越来越高。如何在满足市场需求的前提下做好适时、 适量的供给对配送的科学性和合理性提出了新的挑战，也是道路货物运输业者面 临的新课题。因此，加强在随机需求条件下的道路货运调度研究具有十分重要的 理论和实践意义。 本文以道路货物运输为研究对象，主要从道路货物运输调度的相关问题研究 入手，分析了调运系统结构及特征、不同需求量的道路货物调运要求：随机需求 的调运方法和网络结构；随机需求的调运数学模型及算法设计、模拟运算与分析 等。通过对确定需求的道路货物调运问题和随机需求的道路货物调运问题的软、 硬件进行对比分析，找出了确定需求的道路货物调运方式中存在的阎题，针对存 在的问题采用随机规划( s t o c h a s t i cp r o g r a m m i n g ) 的方法，根据货物运输市场需 求的随机性特点，提出了多频次调度的思路；以道路运输业者的内部营运网络为 背景，基于运输总成本和时间两个方面建立一种考虑城市交通状况的模型：根据 模型特点采用组合方法将随机需求多频次调运问题，转化为确定性需求的多频次调运 问题，进而采用粒子群算法进行求解；最后进行算例分析，以验证本文所构建的模 型的合理性及可行性。 本论文的目的，旨在通过对随机需求的研究，从而找出调度的优化模型和算 法。为道路货物运输业者在提高配送效率和更好地满足顾客的需求方面，提供调 度方法上的借鉴和理论指导。 关键词：随机需求量；多频次；随机规戈l j ；货运调度；微粒群算法 a bs t r a c t m o d e r nl o g i s t i c si sg e n e r a l l ya c k n o w l e d g e da st h et h i r dp r o f i tr e s o u r c eb e s i d e s r e d u c i n gt h ec o m m o d i t yc o n s u m p t i o na n de n h a n c i n gl a b o rp r o d u c t i v i t y i ti sa l s o r e g a r d e d a sa n i m p o r t a n tw a yi nd e c r e a s i n g t h e o p e r a t i o nc o s t a n d r a i s i n g c o m p e t i t i v e n e s sf o re n t e r p r i s e t h u st h e r ea r cm a n yc o u n t r i e sp a y i n gm o r ea n dm o r e a t t e n t i o no ni t ，a n di ts t e p si n t oar a p i dp r o g r e s sd e v e l o p m e n t a sa ni m p o r t a n tl i n ko f o p e r a t i n gl o g i s t i c ss y s t e m ，d i s t r i b u t i o ni su n r e p l a c e a b l e w i t ht h ed e v e l o p m e n to f e c o n o m i ca n d s h a r pc o m p e t i t i o no fm a r k e t ，c u s t o m e r sr e q u e s t s f o r f r e i g h t t r a n s p o r t a t i o no nt i m ea n dq u a n t i t yg e ts t r o n g e ra n ds t r o n g e r s oh o w t od e a lw i t ht h e s u p p l i e sa tt h er i g h tm o m e n ta n dt h er i g h ta m o u n ti ns a t i s f i e st h em a r k e td e m a n di s p u t t i n gan e wc h a l l e n g et ot h ed i s t r i b u t i o n ss c i e n t i f i ca n dr a t i o n a la n da l s ob e c o m e t h en e wt a s kw h i c hr o a df r e i g h tf o r w a r d e rs h o u l df a c e t h e r e f o r et or e i n f o r c et h e r e s e a r c ho fr o a df r e i g h tt r a n s p o r t a t i o np r o b l e mu n d e rt h ec o n d i t i o nt h a td e m a n di s u n c e r t a i nh a v ev e r yi m p o r t a n c em e a n i n go nt h es i d eo ft h e o r ya n d p r a c t i c e s i nt h i st h e s i s ，t h er o a df r e i g h tf o r w a r d e ri st a k e na st h er e s e a r c ho b i e c t s t a r t i n g w i t ht h er e l a t e dp r o b l e m so fr o a df r e i g h tt r a n s p o r t a t i o n ，t h et r a n s p o r t a t i o ns y s t e m s t r u c t u r ea n dc h a r a c t e r i s t i c ，t h er o a df r e i g h tt r a n s p o r t a t i o nc l a i m so fd i s t i n c td e m a n d s ， t h e t r a n s p o r t a t i o n m e t h o da n dn e t w o r ks t r u c t u r eo fs t o c h a s t i c d e m a n d ，t h e o p t i m i z a t i o nm o d e l ，a l g o r i t h m ，a n a l o gc a l c u l a t i o na r ea n a l y z e d t h r o u g hc o m p a r a t i v e a n a l y z i n gt h eh a r d w a r ea n ds o f t w a r eo fr o a df r e i g h tt r a n s p o r t a t i o np r o b l e m sw h e n d e m a n di sc e r t a i na n ds t o c h a s t i c ，t h ew e a k n e s s e so ft h et r a n s p o r t a t i o np r o b l e m sw h e n d e m a n di sc e r t a i na r ef o u n do u t a c c o r d i n gt ot h ew e a k n e s s e s ，t h es t o c h a s t i c p r o g r a m m i n gm e t h o di su s e d ，t h e no nt h eb a s i so ft h es t o c h a s t i cd e m a n d ，t h et h o u g h t o fm u l t i f r e q u e n c yg o o d ss c h e d u l i n gi sp u tf o r w a r d b a s e do nt o t a lt r a n s p o r t a t i o n c o s ta n dt i m e ，t h em o d e li nw h i c ht h eu r b a nt r a f f i cc o n d i t i o n a r ei sc o n s i d e r e di sb u i l t w i t ht h eb a c k g r o u n do ft h er o a df o r w a r d e r si n t e r n a lo p e r a t i o nn e t w o r k a c c o r d i n gt o t h ec h a r a c t e r i s t i c so ft h em o d e l ，t h ep r o b l e mo fs t o c h a s t i cd e m a n dm u l t i - f r e q u e n c y s c h e d u l i n gi st r a n s f o r m e di n t om u l t i f r e q u e n c ys c h e d u l i n gp r o b l e mw h i c hd e m a n di s c e r t a i nb yu s i n gc o m b i n a t o r i a lm e t h o d t h e n ，i ti ss o l v e db yu s i n gp s o a l g o r i t h m f i n a l l y ，a ne x a m p l ei sp e r f o r m e dt op r o v et h er a t i o n a l i t ya n df e a s i b i l i t yo ft h em o d e l t h ep u r p o s eo ft h et h e s i sl i e si nf i n d i n gt h eo p t i m i z a t i o nm o d e la n da l g o r i t h m t h r o u g hs t u d y i n go ft h es t o c h a s t i cd e m a n d t h er e s e a r c hc a np r o v i d er e f e r e n c ea n d t h e o r e t i c a l g u i d a n c e i nt h ea r e ao fi m p r o v i n gd i s t r i b u t i o n e f f i c i e n c ya n db e t t e r s a t i s f y i n gt h em e e t i n gt h en e e do fc u s t o m e r sf o rr o a dg o o d sf o r w a r d e r k e yw o r d s ：s t o c h a s t i cd e m a n d ；m u l t i - f r e q u e n c y ；s t o c h a s t i cp r o g r a m m i n g ：f r e i g h t t r a n s p o r t a t i o n ；p s o n 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 渤 ， 日期：扣5 年月矿日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“v ”) 作者签名： 号猫 日期：册f - 月矿日 导师签名：才伽3 芦鼍 日期：小巧年j ，月，j 。日 第一章绪论 社会生产力和社会经济的发展使经济全球化的速度进一步加快，也推动了物 流业的迅猛发展。在产品差异化生产不断变化的情况下，传统上以生产厂商为主 导的市场局面发生了根本性的改变，消费者成为了市场的主导，其对物流服务的 产品货物递送的选择性和要求也越来越高，使得运输产业的竞争更加激烈。 道路货物运输运作为物流服务的重要组成部分，在当前买方市场环境下，企业如 何制定有效的运营计划，以节省营运成本、最大程度地满足消费者的需求，为顾 客提供高时效的运输服务，是道路运输业者获得顾客、提高企业效益的关键。在 道路货物运输过程中，其调运方案的制定，是整个营运计划的核心，方案的优劣 直接关系到货运从业者所提供的运输服务的质量与货运企业的利润和市场竞争能 力，因此，对道路货物调运问题的研究具有重要的理论和现实意义。 本章主要叙述研究的背景、目的和意义，国内外研究现状以及研究的主要内 容和技术路线等。 1 1 研究背景 近年来，物流作为“第三利润的源泉”受到国内外各行业的极大重视，并得到 了较快的发展。物流配送是现代先进的物流形式，随着现代商业经营环境和经营 形式的变化，大量经营规模较大的制造企业和商业企业纷纷建立起配送中心，进 行配送作业，向商品流通效率化发展挑战。与此同时，相当部分的大型运输、仓 储和航运企业开始转向第三方物流经营。物流己经成为许多企业的共同话题。在 物流业蓬勃发展的同时，互联网技术、电子商务技术也获得了巨大的发展，伴随 第三方物流公司的出现，人们越来越关注运输环节的工作效率，以更好的获得“第 三利润源”，强化国际竞争力。 卖方市场的出现，无论是生产企业还是服务企业都将更多的注意力放在了吸 引顾客上。随着国民经济的快速增长，居民的可支配收入不断增加，生活水平不 断提高，消费者消费心理和消费行为随之发生了相应的变化。消费者对生活的追 求从原来温饱型、数量型开始转向小康型，越发重视生活的质量。在经济社会向 国际化、信息、化急剧转变的基础上，消费者价值观趋于多元化和多样化，喜欢 购买具有差别化的商品。中国社会调查事务进行的消费心里调查研究表明，3 5 岁 以下的年轻人8 2 2 的人有求新求奇心理，认为商品的款式、流行样式很重要， 讲究新颖、独特。为了最大程度的吸引顾客，商品生产呈现个性化、多品种、小 批量现象，产品生命周期也大大缩短。消费个性化、多样化及厂商多品种生产使 得零售商倾向于无在库经营，对物流配送提出了更高的要求，配送过程中需求量 的随机性也随着消费者行为的改变而变得更加明显。与市场需求相适应，物流配 送企业必须考虑顾客需求，将配送方式由传统的大批量、少批次配送，转向小批 量、多批次配送。 此外，目前e d i ( 电子数据交换) ，b a r c o d e ( 条形码) ，r f ( 射频技术) 、g p s ( 全 球定位系统) 、a i s ( 地理信息系统) 、a s r s ( 自动存储和分拣系统) 等先进技术发 展非常迅速，其直接的效果便是能够更快地满足顾客对商品的需求，商品交易量 也随之大幅度上升。而随着生产技术的不断提高，产品的附加值和技术含量逐步 提高，小批量、高附加值的产成品运输需求逐步加大，导致了以承运大宗货物为 主的铁路、水运等传统方式在运输市场的份额有所下降，公路运输市场份额不断 上升。交通部的数据显示，2 0 0 6 年，我国完成公路货运量1 4 6 亿吨，比上年增长 8 8 。公路货物运量的增长，一方面促进了道路货物运输业的繁荣量的增加，但 另一方面，货运量的增长。伴随而来的是站场货物处理量的增加，使得运输业者 必须提高站场的面积，以提供货物的装卸、理货，但由于政策、环境、房地产价 格等原因，特别在大都市中，由于人口密度大、地价高昂、消费更新快、环境规 制严格，限制了站场空间的扩大。 因此，对道路货物运输方式进行研究，在满足现代生产和消费的需求的同时， 缓解货运量的增长给站场带来的负担，对货物运输企业而言是一个非常紧迫而重 要的研究课题。 1 2 研究的目的及意义 1 2 1 研究的目的 物流配送是适合我国国情的一种能够实现企业的资源有效配置，以及为推动我 国经济发展做出巨大贡献的非常有价值的方式。2 1 世纪是经济全球化的世纪，中 国要适应市场经济全球化的大浪潮，对于“第三利润源泉”的物流业务，就应从我 国的实际情况出发，在物流的若干理论、方法和技术中，找到一个合适的立足点， 使得物流业成为我国国民经济增长点。但是目前我国物流管理仍然比较落后，物流 行业普遍面临着专业化程度低、高耗低效等问题。优化物流配送作为发展物流的一 个重要组成部分，是实现物流现代化的基础和前提条件，有助于改变我国物流管理 落后的现状，实现效率、资源和价值观念各方面的内在统一，促进物流业的进步。 随着经济的发展，道路货物运输作为物流配送的具体表现形式，其需求的时 问和数量更为复杂，如何在满足市场需求的前提下做好适时、适量的供给对配送 的科学性和合理性提出了新的要求。而目前，对货物运输的大部分相关研究，皆 是在假设市场需求量为已知的情况下进行的，这与市场需求的实时性不相符合。 2 因此，在货物调运过程中考虑需求的随机性，才能使得货物调运问题符合实际。 本研究拟采用随机规划( s t o c h a s t i cp r o g r a m m i n g ) 的方法，提出道路货运量变动 条件下的多频次调运方法，通过建立更加科学、优化的道路货物调运模型来满足 道路货运业从业者的要求以及顾客对于产品服务的高质量需求，并明确在不确定 运输需求下，多频次的次数如何设定、货物路径如何安排及车辆路线如何制定， 从而有助于企业节约运输成本，改善车辆利用效率，缩短生产周期，加速资金周 转，实现资源的合理配置。 1 2 2 研究的意义 从应用方面看，多频次调运是物流配送优化的一种，货物路径安排及车辆路 线制定是物流配送中的关键，也是电子商务活动不可缺少的内容。对货运车辆进 行路径安排，可以提高物流经济效益、实现物流科学化。需求不确定性多频次调 运与消费者的个性化和多样化相适应，与生产的少批量和多样化相适应，因而可 以促进社会经济的增长。 从理论研究上看，当前车辆调度问题中路径优化在动态信息处理这方面还不 是很及时、完善，而且其模型、算法与现实车辆调度问题还有一段距离，这使对 车辆问题有了更大的研究空间。本文采用组合方法将随机需求多频次调运问题， 转化为确定性需求的多频次调运问题，进而采用粒子群算法进行求解。粒子群算 法是一种高效的启发式算法，具有简洁、容易实现且功能强大的有点，为车辆优 化调度的计算机实现打下了基础。 1 3 国内外研究现状 1 3 1 国外研究现状 1 、v s p 问题 国外对v s p 问题作了大量而深入的研究。早在1 9 8 3 年，b o d i n 、g o l d e n 等人在 他们的综述文章中就列举了7 0 0 余篇文献。在c h r i s t o f i d e s ，g o l d e n 和a s s a d 编译的 论文种，以及a l t i n k e m e r 和g a v i s h ，l a p o r t e ，s a l h i 等的综述文章中做了详尽的阐述。 c r a i n i c 提出了以路线服务频率和货物路径为决策变量，求取目标函数包括运 输成本、货物装卸成本、站场容量拥挤惩罚成本以及服务延误成本的总和为最小 的模型，这是一个非线性、大型的混和整数规划问题的货物调运问题，其在零担 货物运输与铁路货物运输领域得到应用| 2 j 。 e c k s t e i na n ds h e f f i 利用拉格朗日松弛法为下限值的分支界定法( b r a n c ha n d b o u n d ) ，求解单一中转站、单一类型集装箱至多托挂集装箱连接车( t w i nt r a i l e r s ) 的集装箱选择与均衡问题1 3 】。 p o w e l la n ds h e f f i 利用分解启发式算法，在仅考虑选择单一类型集装箱的情况 3 下，对非实效性零担货物运输业者的载运问题，将模式分解为货物调运、集装箱 空箱平衡与运输车辆行驶频率的网络设计等三个子问题，并分别进行求解1 4 1 。 l e u n g 等人针对实效性货物运输业的运输计划问题进行研究，并且构建路线 规划( r o u tp l a n n i n g ) 模型 s l ，该模型是一个同时考虑站场或者站场处理容量、车辆 或集装箱的装载容量的大型混和整数规划问题，但是该模型仅考虑单一类型货车 或者集装箱。该模型主要着重于货物路线的选择与集装箱数量的指派问题，作者 将整合性问题分解为站场起讫对指派至中转站起讫对的指派问题与中转站起讫对 之间的多元商品流量等两个子问题，并以拉格朗日松弛法( l a g r a g i a nr e l a x a t i o n m e t h o d ) 进行求解。该模型是在两个重要的假设前提下进行的，这两个假设为： 1 、有相同起讫对的所有货物，皆有相同的路线；2 、货物的运送必须在顾客托运 合同上所规定的时间内送达。 l i n 提出，将运输计划分为货物路径与集装箱的均衡与数量两个子问题，并 且各自提出了合适的拉格朗日松弛算法1 6 1 。但是缺点是上述的分解算法缺乏回馈 的关系。直到1 9 9 8 年，l i n 提出了e 差距的修正式穷举法( i m p l i c i te n u m e r a t i o nw i t h e o p t i m a l i t y ) t t i 。通过整合性求解法考虑各模组之间相互影响与回馈的关系，不但 可以求更优的解，同时当e 设为零时，便可得到最优解。 a k y i l m a z 以网络结构、站场位置不变、具有固定的车辆与人员的前提下，利 用简单的启发式算法，探讨道路货物运输业者如何通过货物在站场经过拼装的功 能，重新考虑货物的路径问题，以降低营运成本，说明了中转站的功能是在于减 少空车的里程数i s 】。 2 、v s p 求解问题 v s p 问题是n p 难题，其求解过程一直以来都受到极大的关注，作为组合优 化问题，v s p 问题的主要求解方法有精确算法和启发式、亚启发式算法等几类。 k o l e n 、d e s r o c h e r s 等人使用了分枝定界算法等精确算法解决v r p 问题1 9 1 1 1 0 1 1 1 1 1 。 s o l o m o n 将用于求解简单v r p 的路径构造方法扩展应用到v r p t w 的求解中d 2 1 。 用于求解v r p 的启发式方法还有p o t v i n 的并行插入法1 1 3 1 ，k o n t o r a v d i s 的贪婪随 机自适应搜索算法1 1 4 1 以及k o s k o s i d i s 的一般分配法1 1 5 1 等。在这些方法的基础上， 后来的研究者提出了各种改进解的方法d 6 1 i i t d s i l l 9 1 。 1 3 2 国内研究现状 国内在车辆路径问题模型的建立和算法的研究上，最初参考国外对该类问题 的研究成果。近年来，随着研究的深入进行，国内的学者逐步发展出一套适合国 内车辆行驶状况，且与国际接轨的理论和方法。 西南交通大学的郭耀煌教授，李军教授，谢秉磊博士在该领域做了相当的研 究，从1 9 8 9 年起对对车场、多车型等类型的问题进行了研究并出版了国内v r p 4 研究领域的第一部专著车辆优化调度，其主要研究领域包括了对该类问题的分 类以及解决问题的算法，如启发式算法：c w 节约算法；亚启发式算法：模拟退 火算法、遗传算法；随机实时的配送调度求解等。 随着“物流热”的升温，国内学者对v r p 的研究也开始重视起来。北方交通大 学的朗茂祥教授在文献中对配送车辆调度问题进行了综述f 2 0 】，用遗传算法与爬山 算法构成的混合遗传算法来求解此类问题i 2 1 1 ，取得了一定的成就；祝崇隽等较全 面地回顾了配送车辆调度优化领域的最新发展1 2 2 1 ；袁庆达和汪寿阳等分别对库存 路径问题 2 3 l 和定址路径问题1 2 4 l 进行了分析评述。 1 4 研究的范围 1 、本研究主要是以货物运输网络型态较为明显的道路货物运输业为探讨对 象，在此以外的运输方式则不在本研究的讨论范围之内。 2 、道路货物运输业者在拟定运输计划时，由于问题过于庞大复杂，决策因素 过多，故采用分层式决策方式( s e q u e n t i a ld e c i s i o np r o c e s s ) 。通常是在运输市场 需求和公司运输网络结构已知的情况下，从业者先决定货物路径( f r e i g h tr o u t i n g p l a n n i n g ) ，再决定运输车辆的类型与数量，最后决定货车的时刻和司机的行车时 间表。本研究所要讨论的问题，除了包含货物路径选择问题外，也同时考虑货车 数量与车辆路径问题，因此称为调运问题。 3 、本研究将道路货物运输业的营运网络分为内部营运网络和外部服务网络两 个部分，考虑到整个路网的复杂性，本研究探讨的范围是道路货物运输的内部营 运网络，并且以未来网络发展趋势的轴辐射式网络为主要的网络结构。 4 、目前众多道路货物运输从业者，如u n i t e dp a r c e ls e r v i c e ( u p s ) ，为简化营运 作业，减少运输设备管理成本，已经趋向于使用单车型最为装载工具。故本研究为 简化优化数学模型的表示，在车辆类型的选择上，也采取单一车型提供运输作业。 5 、道路货物运输随机需求下调运问题的研究，是在货物运输市场需求不确定 的前提下，提高货物的运输频率，故以多频次运输网络为主。由于必须考虑时间 因素，故本研究属于动态网络问题。 1 5 研究的主要内容及技术路线 1 5 1 研究的主要内容 本研究以我国道路货物运输业为主要的研究对象，并仅针对道路运输业者的 内部营运网络，在考虑顾客需求量的随机性情况下，对道路货物运输的调运问题 进行深入的探讨，即是在货运量为不停变动的情况下，考虑有限车种( 单一车型) 均衡调派及货车数量，进而拟定货物运送路线与车辆路径，其目标是使营业站场 5 和中转站场的作业成本、运输车辆的运输成本与车辆固定成本最小化。 1 、阐述本文的研究背景、研究的意义和目的，通过阅读相关文献，了解国内 外研究现状，分析道路货物运输调运的相关研究，为运输网络设计优化和数学优 化模型的建立提供参考依据，并提出研究范围和研究的技术路线。 2 、研究道路货物调运的相关理论，分析道路货物调运系统的结构及不同需求 的道路货物调运问题，了解我国道路货物运输的系统的构成和特征，进而了解我 国道路货物运输从业者的运输网络及其改善的情况，并探讨我国道路货物运输以 轴辐射式网络为架构所构建货物运输网络的未来营运方式。 3 、探讨运输需求量不确定的调运方法，提出随机需求的多频次调运方法，构 建多频次调运网络，并阐述其构成要素和结构。 4 、构建道路货物运输随机需求多频次运输的数学模型。 5 、采用组合方法将随机需求多频次调运问题，转化为确定性需求的多频次调运 问题，进而采用粒子群算法进行求解，使得本研究所构建的数学模型得到有效求解。 6 、进行实证研究，以验证优化模型及算法的可行性。 7 、提出本研究的具体研究成果及未来的研究方向，以供后续相关研究参考。 1 5 2 技术路线 i 坌堑兰竺苎望塑兰墨竺竺望 l1 i 阐述道路货物调运的相关理论l 孓1 分析道路货物运输调运问题 l 1 分析不同需求最的货物调运闯题 ii_lji 。一 = = = = = = 二= = = 二= 二= 二：= ll = j，_ l 阐述随机需求的多频次调运方法l 。f 兰竺竺! ! 要兰竺兰竺兰竺望兰垄兰l 之 丽面磊鬲西孬磊面磊圈 厂罩罚磊孬西弱西舂蠡函嚣磊磊；覆豆 ll 竺兰竺竺至兰翌至竺竺兰兰! l i 构建随机需求多频次调运网络模型 i 1一 i 匪堕囹 圈 臣四 1 6 本章小结 本章分析了基于道路货运量动态变化条件下的调运方法研究的背景，阐述了 本研究的研究主要目的和意义，确定了问题的研究范围，提出了本研究的主要内 容和技术路线图。 6 第二章道路货物运输调运问题分析 如今，激烈的市场竞争和快速多变的市场需求使企业面临不断缩短交货期、 提高产品质量、降低成本和改进服务的压力，迫使供应商、制造商、分销商和零 售商走向合作。这就要提高企业的敏捷性，以保证企业在变幻莫测的市场下，能 及时向顾客提供低成本、高质量的商品。对道路运输业来说，由于运输需求是一 种派生性需求1 2 5 1 ，运输活动是工商企业生产经营过程中的有机组成部分，因而同 样面临着降低成本，提高服务水平的压力。在我国，运输业还同时面临来自国外 同业的强大竞争，压力更为巨大。如何面对压力，提高道路货物运输业的效益及 道路运输服务水平，是我们现在面对的重要任务之一。 道路货货物运输与其他运输方式相比，具有灵活性、快速性和经济性等特点， 因而其市场需求在日益增加。但由于运输市场竞争日趋激烈，从业者如何在提高 企业效益的同时，提升自身的竞争力和提供高质量的运输服务，是运输企业获得 顾客的关键。货物调运，是整个货物运输的关键，也是成本的最大耗费环节，因 而货物调运方案的制定是整个营运过程中至关重要的一环。 由于调运问题庞大复杂，道路货物运输业者一般在拟定营运计划时，将整个 营运策略分为以下三个层次的决策：( 1 ) 长期战略规划( s t r a t e g i cp l a n n i n 曲，这一 层次属于高层管理者的决策问题和长期资本投资需求问题，其中包含了实体网络、 主要站场设施位置、服务水平的制定等，这个层次主要可以整理为实体系统设计 ( 1 0 9 i s t i c ss y s t e md e s i g n ) ：其中包括有区位模式( 1 0 c a t i o nm o d e l s ) 和网络设计模式 ( n e t w o r kd e s i g nm o d e l s ) ：( 2 ) 中期战术规划( t a c t i c a lp l a n n i n g ) ，这个阶段是合理 和有效的分配资源以提高系统的整体绩效，主要包含服务网络的设计( s e r v i c e n e t w o r kd e s i g n ) 及车辆路径问题( v e h i c l er o u t i n gp l a n n i n g ) ；( 3 ) 短期作业规划 ( o p e r a t i o n a lp l a n n i n g ) ，任何营运者都希望使得利润最大化或者至少维持于较有利 的竞争位置。由于在的营运过程中，可能货运量的变化很大或者很小，路面的运 输时间也是无法准确估计的，因此先前所制定的方案便无法进行的很顺畅，所以 短期的营运决策需将随机( s t o c h a s t i c ) 司素放在系统中考虑。 本研究所探讨的道路货物调运问题，也就是道路运输业者在其营运网络中货 物的运输路径与车辆的调度相结合的优化问题。此问题属于道路货物运输业者营 运计划中的中期战术规划和短期作业规划，是整个营运决策的核心问题。 本章将叙述道路货物调运的基本理论，分析道路货物调运系统的目标、构成 及特征，并分析不同需求的道路货物调运问题的区别，从而提出随机需求的道路 货物调运问题。 7 2 1 道路货物调运的相关理论 2 1 1 物流配送 当前，现代物流己被公认是企业在降低物资消耗、提高劳动生产率以外的第 三利润源泉，也是企业降低经营成本，提高产品竞争力的重要途径，因而受到国 内外各行业的极大重视，并得到较快的发展。配送是物流系统中的一个重要环节， 由于它直接与消费者相连，具有十分重要的作用。 物流配送指的是：在经济合理区域范围内，根据用户的要求，对物品进行拣、 选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。 配送不仅仅是送货，它还是配货、分货、送货等活动的有机结合体，是在恰 当的时间，通过恰当的方式和恰当的费用将商品最终传递给需求者，将最优质的 服务传递给需求者，是物流过程中的关键环节。它是物流中的一种特殊的、综合 的活动形式l ：t i ，其送的一般流程如图2 i 所示： 工 r 随着电子商务的发展以及新物流配送模式的出现，存贮已不是必然的环节1 2 7 l 。 因此，配送工作主要包括以下几个部分： ( 1 ) 集货作业。从生产工厂进货，并集结的过程。 ( 2 ) 配货作业。即货物的分拣作业，根据各用户的不同需求，在配送中心将 所需要的货物挑选出来的过程。 ( 3 ) 配装作业。由于配装作业本身的特点，配装工作所需车辆一般为汽车， 由于配送货物的质量和体积的差异，在配装货物时要考虑车辆的载重和容积，为 使车辆的载重和容积得到充分的利用，还要考虑一次多送几户的问题。 ( 4 ) 送货作业。即按着预先确定的配送路线和时刻表将货物送到用户的手中。 其中，配送线路合理与否对配送速度、成本、客户满意度影响很大，特别是多用 户配送路线的确定更为复杂。采用科学合理的方法来确定配送路线，是配送活动 中非常重要的一项工作。 随着物流配送集约化、一体化的发展，常将配送的各环节综合起来，核心部 分为配送车辆的集货、货物配装及送货过程。进行配送系统优化，主要就是配送 车辆路线优化，包括集货线路优化、送货线路优化，以及集货送货一体化优 化。在国外，类似的工作已广泛的运用于生产、生活的各个方面，如报纸投递及 8 线路的优化、牛奶配送及送货路线的优化、电话预定货物的车辆载货和线路设计， 垃圾车的线路优化、连锁店的送货及线路优化等。 物流配送路线优化问题涉及面广，需要考虑的因素较多，对配送企业提高服 务质量，降低服务成本、增加经济效益的影响较大，是物流配送系统优化的关键。 2 1 2 车辆优化调度 物流配送车辆优化调度，是物流配送优化中关键的环，也是电子商务活动 不可缺少的内容。对货运车辆进行优化调度，可以提高物流经济效益、实现物流 科学化。国外将物流配送车辆优化调度问题归结为或称为v e h i c l er o u t i n g p r o m b l e m 和v e h i c l es c h e d u l i n gp r o m b l e m ( v s p ) 1 2 s l ，最早是由d a n t i g 和r a m s e r 于1 9 5 9 年提出的。由于这一问题的理论涉及多学科，很多实际问题的理论抽象都 可以归结为这一类问题，应用前景广阔，所以很快便引起运筹学、应用数学、图 论与网络分析、物流科学、交通运输工程、管理科学与工程、计算机应用等学科 的专家、工程技术人员和管理者的极大重视，自此，一直成为运筹学与组合优化 领域的前沿与研究热点问题。各学科的专家对该问题进行了大量的理论研究及试 验分析，取得了很大的进展。 v s p 问题一般定义为：对一系列装货点和( 或) 卸货点，组织适当的行车路 线，使车辆有序地通过它们，在满足一定的约束条件( 如货物需求量、发送量、 交货时间、车辆容量限制等) 下，达到一定的目标( 如路程最短、费用最少、使 用的车辆数尽量少等) 。 在配送系统中，管理者需要采取多种有效的配送策略以提高服务水平、降低 货运费用，最大限度的降低车辆空驶率，提高配送作业的柔性和灵活度i z g l 。其中 车辆路径问题是需要解决的一个重要问题。车辆优化调度的任务是为车辆安排发 送、集货的路线，也就是通过优化路线，为车辆设定给客户发送货物或从客户处 集货的次序，使得车辆完成配送作业的总行驶路程、时间、总费用最少。通常分 为集货优化和送货优化两类。其中集货优化问题是指在若干厂家生产一些产品， 需要运送到配送中心，车辆从配送中心出发，到各个厂家去装货，装满后返回配 送中心，在满足各厂家发货要求的情况下，按照一定的路线行驶，使总费用最少。 送货优化是指按照顾客的需求，将运输车辆装满货物，按照拟定的线路行驶，将 货物送到客户处后再返回到配送中心的过程中总费用最小。总费用可以是成本， 也可以是时间、路程。在配送中，集货和送货的实质是相同的，本文只研究送货 的情况。 车辆优化调度的实质就是在配送中事先根据有关道路情况、客户需求情况、 车辆情况，根据一定的目标，为车辆设定最佳路线。 车辆的最佳路线必须满足如下条件： 9 满足所有用户的需求； 不使任一辆车超载； 每一辆车每天的总运行时间或行驶里程不超过规定的上限； 能够满足用户到货时间的要求。 在车辆优化调度中，根据因素是否确定，可分为两种情况：第一种为确定型 的车辆调度，第二种为随机型的车辆调度1 3 0 l 。 1 、确定型的车辆调度 确定型的车辆调度是指，在配送中的因素都是确定的情况下，如客户需求是 确定的，车辆在各路段的行驶时问是确定的，车辆的数量是确定的，以及车辆要 访问的客户也是在确定的情况下，优化车辆配送路线，使得总费用最少。 在确定型的车辆调度中，配送中心管理人员为车辆确定访问客户的最佳路线 必须满足： 车辆从配送中心出发，完成配送任务，回到配送中心； 每个客户由一辆车完成配送任务，且每辆车只能访问客户一次； 车辆线路上的配送总任务不能超过车辆容量； 发生费用总最少( 或总路程最短、总时间最短) 。 2 、随机型的车辆调度 由于确定型的道路货物调运问题，在处理的过程中设定所有影响因素均为固 定的，因此在处理过程中设定所有参数都是确定性的，没有涉及不确定性因素， 所以在开始安排车辆路径时认为可能得到所有关于车辆路线选择和调度的信息， 但在实际调度过程中，车辆数量、车辆容量、客户的需求、客户的位置等随机因 素是普遍存在的，这就使得确定型车辆调度所获得的解具有很大的局限性。从而 提出随机型的车辆调度问题。在车辆调度中所遇到的所有因素，或者部分因素是 随机的而非确定的，如各路段车辆行驶时间是不确定的，以及客户的需求是不确 定的等等，这类车辆调度问题称为随机型的车辆调度问题f s t o c h a s t i cv e h i c l e s c h e d u l i n gp r o b l e m ，简记s v s p ) 。 在随机型的道路货物调运中，当车辆空车时，如果未完成配送任务，可回到 配送中心装货，然后继续配送。但是，其车辆路线优化，必须考虑车辆回到配送 中心装载货物，会产生一些费用或增加车辆的行驶里程。而在确定型的车辆优化 中，没有这种情况的出现。因此确定型和随机型两种车辆路线优化的结果是不同 的。如图2 2 所示。 1 0 确 定 型 随 机 型 图2 2 确定型和随机型车辆线路问题图 由图2 2 可知，尽管确定需求的v r p 是随机需求的v r p 的特殊情况，但车 辆路线是完全不同的。 当车辆调度中顾客的需求为不确定因素时，该随机型车辆调度问题就称为需 求不确定型车辆调度问题。需求不确定型车辆调度问题又可以分为需求点不确定 和需求量不确定两种情况。其中，需求点不确定下的随机性车辆优化调度的特点 在于顾客需求点逐一出现，对尚未出现资料则毫无所悉，已出现的顾客则依其顺 序安排车辆提供服务，且须满足顾客的服务时窗与车辆的最大载重与路线总时间 等限制。需求量不确定下的随机性车辆调度问题不同于需求点不确定下的随机性 车辆调度问题，它是在事先己经确定的配送路线中的各个需求点中，尚未配送的 需求点在车辆未到达前可能发生需求量的变化，可能是需求量增加也可能是减少， 其特征是各个需求点事先己经知道且己经知道其有一定的需求量。本论文主要研 究客户的需求量不确定的随机型车辆调度问题。 在需求量不确定的随机型车辆调度问题中，车辆也必须从各个站场出发，完 成配送任务后，回到各自所属的站场。当货物量较少时，用一辆车完成一项任务， 车辆不能满载，利用率较低，可考虑用一辆车完成多项任务( 如图2 3 所示) 。调 度的目标是车辆完成配送的总时间期和总费用最少。 图2 3 配送任务分配和车辆路线图 2 2 道路货物调运系统结构分析 2 2 1 道路货物调运的目标 在道路货物运输的运营过程中，货物的调度运输是非常重要的环节，也是整 个运营过程的核心1 3 1 i 。当货物量产生时，如何利用各种调运资源进行合理、高效 的货物调运，在体现道路货物运输的“快速、及时”这一明显特性的同时，使得运 1 1 输企业所付出的成本最小、顾客得到十分满意的服务，是所有道路货物运输从业 者所追求的共同目标。因此，研究调运问题的目标是实现道路货物运输的快速及 时、最大程度满足顾客和成本最小化三大目标。 2 2 1 1 快速及时 “快速及时”是最能体现道路货物运输特征的品质参数，道路货物运输作为一 种运输服务，当顾客选择了购买这种服务产品时，其最主要的目的是需要它的“快 速及时”这一服务特点。在我国，有的专家提出了“快速”的标准是“在网络覆盖范 围内，保证货物从发货人到收货人运距在5 0 0 k m 以内的运输时间不得超过2 4 h ， 运距每增加6 0 0 k m ，运达时间增加2 4 h ”。这一量化的品质参数，可以供制定调运 方案参考。在国外，运输经营者采用先进运输技术和合理运输手段，通常在1 0 0