（系统工程专业论文）物流配送车辆优化调度问题研究.pdf

沈阳丁业大学硕士学位论文 摘要 在经济全球化和信息化的浪潮中，现代的物流业已经成为以现代科技、管理和信息 技术为支柱的综合物流系统。物流配送是物流企业增加利润的关键所在，而车辆调度问 题是物流配送的核心问题，因此，对车辆优化调度问题的研究具有重要的意义。 车辆优化调度问题是一个典型的n p 难题，应用纯粹的数学方法难以求解。随着智 自吕优化技术的发展，越来越多的研究人员用智能方法做出决策和判断，以使运输系统费 用最低、效益最大。蚁群算法是一种新兴的搜索寻优技术，是从蚁群行为的研究中产生 的。蚁群算法根据个体产生信息素，借助选择策略、信息素更新等操作，逐步逼近最优 解。 本文对现代物流配送车辆优化调度问题的理论、方法与模型进行了深入的研究。首 先在回顾车辆优化调度问题研究现状的基础上，从模型分析和求解算法的角度研究了车 辆优化调度问题：对容量限制车辆优化调度问题、有时间窗车辆优化调度问题、顾客满 意度车辆优化调度问题以及随机车辆优化调度问题的模型进行了探讨，并介绍了求解车 辆优化调度问题的算法。 介绍了蚁群算法的基本思想、原理和模型实现，进行了算法分析，总结了一些参数 选择的经验，并对一些典型的改进蚁群算法进行了简单介绍。然后针对蚁群算法在求解 问题过程中容易出现停滞现象、收敛速度慢的缺点，提出了一种改进的蚁群算法，并将 其应用于旅行商问题进行验证，结果表明了算法的有效性。 最后在分析蚁群算法求解旅行商问题与车辆优化调度问题区别的基础上，设计了一 种混合蚁群算法来求解车辆优化调度问题。编写了优化调度程序，应用实例对算法进行 验证，通过与同类文献比较，表明了该算法对求解车辆优化调度问题的可行性。 关键词：物流配送，车辆优化调度，数学模型，蚁群算法，混合蚁群算法 竺亟些圭塑垡些塑星囹壑婴塑 s t u d yo nl o g i s t i c sd i s 订i b u t i o nv e h i c l er o u t i n gp r o b l e m a b s t r a c t w i t l lt h e 斟o b a l i 蒯o no fe c o n o m y ，m o d e i l ll o 舀s t i c sh a sb c 瑚m em ei n t e 孕砷甜l o 百s t i c 科s t e mm 砒谢t l l 邺n _ o fm o d 锄i e n c c ，i i l i 砌o nt c c h n o l o g ya n dm 卸a g 删l 0 百s t i c s d s n i 嘶o np l a y s a v e f y i l i l p o 衄l t f 0 1 e i l l l o 百s t i c se 1 1 删s 鼯肌d i t i s t l l e k e y p o m t f o r i n c = r e 舾i n g m cp r o 矗t f u m l 锄1 0 r e ，v 砌c l er o 砸1 1 9p f o b l 锄i st 1 1 ek e yp r o b l e i i lo fl o 百毗sd i 矧b u l i o n m 烈娟琳，i t i s m e a 疵a 酬【o d o 黜健鼬吼她p r o b l e m v e l l i c l er o u t i l 】g p i u b l 呦i sa t ) ，p i c a l n p - h 砌p f o b l e m a n d i sd i m c u l t t ob es 0 1 v e d b y l l s i i l g p u r em a 廿确m 血c a lm e t l l o d s w i l l lt l l e 撕e l o p r n e mo fi i l t e l l i g e i l tt e c l l l l o l o g y ，m o r ea i 】【dm o r c p e o p l eb e g i l lt ou s ci i l t e l l i g e mm e 山o d st om a k es c i e m i f i cd e c i s i o l l sa n dg e tt h eo p t i i r l a ls o l u t i o n w i ml e s sc o s to r a n dn l o r eb e n e f i t si 1 1 唧r 嘶o ns y s t e r 璐t h ea n cc 0 l o i l ya l g o f i t l l l l l st 1 1 a t b 鹤e d o n m er e s e a r c h o n 跚t c o l 讲l y i sa n e w m e l 王l o d f o r o p t i i l l i z 撕o n n i t e r a t e s t o m eb e s ta l 】s w 盯 a c c o r d i n gt 0 l c c t i v es 妇魄锄di 1 1 1 酬o ne l 锄e mw i l i c hi sg e n e m l 硝b ye a c ha n t ad e e pr e s e a r c hi nt 1 1 e o r i e s ，m e i l l o d sa n dm o d e l so fm ep r e s e n tl o 百s t i c sd i s 砸b i i 【i o nv e t l i c l e r o u t i n gp r o b l e mi sm a d ei i lm i sm e s i s f i r s t l y ，m e0 p t i n l i z a l i o no f v e h i d er o u t t m gp r o b l e m 丘d ms t a n d p o 皿so fi n o d e l s 删y s i s 锄d a l g o r i t l l l l li ss t u d i e db a s e do nr e 、，i e w m gt h ea c m a lr e s e a r c hs 扭h j so f v e | l i c l er o u 血培p r o b l 锄a d e t a i l c dd i s c l l s s i o no nv c 抽c l er o u t i n gp m b i e mm o d e l sa i i ds o l u t i o na i g 砸t m l si s 舀v e r lt h e s e m o d e l si 1 1 d u d ec a p a c i t yv e l l i c kr o u t i l l gp m b l 锄，v e h j c l er o u t i n gp r o b l e m 谢t 1 1m n ew m d o w s _ v e 城c l er 伽廿1 1 9p m b l 咖谢也c u s 蛐e r s s a d s 白c t i o n 锄ds t o c l l a s t i cv e i l i c i ei o u 矗n gp r o b l e m s e c 删y ，a 髓ri n 舡o d u c i l l gt l l eb 嬲i ci d e a 硼n c i p l e 趾dm o d e l 坞a i 铡o no fa n tc b l o n y 越9 0 r i 血m ，t h ea 1 9 0 r i t i l ：mi sa 1 1 a i y z e d 锄das u i l i i l a i yo fe x p 舒e n c 部i 1 1t l 】ep a r 锄e t e rs e l 。c t i n gi s 1 1 1 a d ei i lt h i st t l e s i s 舢s 0s o m e 卯i c a li i l l p f o v c d 趾tc 0 1 0 n y 啦p t 1 1 i n sa r ei n 廿o d u c e d f 吲h e 删， t h e 把砌i t i o r l a la i l ta l g o r i m mh a st l l es h 嘴so f 蛔葩i n gt og oi i 】_ c os t l g 雠i o nb e l l a 啊o ra n d n e e d i r 培1 0 n g e rc o m p u t i n gt m l e a - 埘_ i i l ga tt h c s es h o r 吼g e s ，觚i m p m v e d 舳tc o l o n ya l g 嘶m mi s p r o p o s e d ，a 1 1 dm e na p 科i e s i t m t o 幽v e l i l l gs a l e 锄a i lp m b l 锄t ov 嘶分砖a l g o d t l l m t h e s i m u l a 虹o n 硼机n t s g h o w n l e v a l i d i t y o f a l g 滩弛“l l a s u y ，a 1 1h y b 谢a mc o i o n ya l g o r i t l l l l li sb i l i l tt 0s o l v ev e i l i c l er o u t i i l gp r o b l e m o nt i l eb 够i so f a 1 1 a l 河n gt 1 1 es i i l l i l 耐t ya n dd i 蔬r e n c eb 叽v e e nl l s i l l ga m l o n ya l g o r i m mt 0s o l v ev e h i c l ei d u t i i l g 沈r 1 工业大学硕士学位论文 p r o b l e ma 1 1 d 仃a v e l i n gs a l e s m 觚p m b l e m a l s om 妇gp m c e d u r e si sp r o 铲猢c dm l d | m s t a l l c e s a r e l l s e d t 0v 商母m ea l g o 甜嘲ns h o w s 血c f e a s i b i l 毋o f m ea i g o 甜i i l l i l l 叩t i m i z 吨t l l ev e i l i c l e 衙u t i n gp r o b i e mt h r o u 曲c o m l ) a r i n g 螂u l 乜w i 也c o n g e n e rl i t e i a n 船s k e yw o r d s ：l o 幽t i c sd i s t r i b u t i o n ，v e h i c l er 心u t i gp m b i e m ，m a t h e m a t km o d e i ta n t c o i o n ya i g o r i t h m ，h y b r i da n tc o l o n ya i g o t h m 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 签名：揖日期：刎呸址 关于论文使用授权的说明 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵循此规定) 躲缉聊龆牲嘲 与l u 沈阡j 工业大学硕十学位论文 1 绪论 1 1 课题研究的背景与意义 1 1 1 课题背景 物流与商流、信息流并称为现代经济的三大支柱，由于物流对国民经济的重大影响， 物流系统化、合理化能刨造巨大经济利益，因此物流被认为是继劳动力、资源之后的“第 三利润源泉”。 传统的物流配送系统中，由于商品的需求量及种类较少，零售商可凭借较多的存货 及较长的订货周期来减少供货商的配送频率，以降低运输成本。但是，现代物流系统中， 物流配送将朝着少批量、多品种、多批次的即时配送方向发展，物流企业应根据客户的 个性化需求，提供“量体裁衣”式的优质、灵活的物流配送服务。因此在如何满足客户 需求的前提下，进一步降低物流成本已经成为国外许多理论、应用学者们关注的焦点。 我国的研究要相对国外滞后，随着改革开放进程的纵深发展，我国国民经济、对外贸易 迅速发展，日益融入世界经济体系中，对物流的研究也因此具有非比寻常的意义。 电子商务广阔的发展前景和连锁商业的迅速发展为物流配送提供了巨大的发展契 机，大量的第三方物流企业和连锁商业企业以往采取的手工作业，或简单的计算机作业 处理方式已经不能满足迅速发展的业务要求。由于物流网络规模的扩大，物流量的巨大 增加，企业在进行物流配送时面临一系列的问题，如何经济合理组织送货，如何保证配 送系统高效及低成本的运作，如何为客户提供传统物流业务之外的增值物流服务等问 题，都是企业在激烈的市场竞争中面临的难题。 综合人以及计算机两方面的优势，配送调度系统能有效辅助处理配送过程中的大量 的决策问题，因此是解决这一系列问题的良好方案。 对物流配送的研究当中，以有效的控制配送中发生的库存成本，运输成本和运输时 间为内容的运输调度问题成为研究的核心和目标。物流配送车辆优化调度是在满足客户 需求的条件下，为客户配送合理的数量，派遣最少的车辆数量并为配送车辆指派运输时 间和运输费用最省的路线，通过利用最优化数学方法并用计算机来实现配送调度计划， 它可以很好的实现降低配送成本，满足提高配送效率的要求。 物流a a 送车辆优化调度问题研究 目前，一般意义上的物流配送车辆优化调度问题，指配送中心按照不同客户多频度、 小批量的订货要求进行组织配送，其中主要内容是根据确定的货物量进行车辆的分配和 配送路线的生成，亦即广受研究的车辆路径问题。 1 1 2 课题意义 由于从事物流配送的汽车货运工作，尤其是从事城市配送的汽车货运工作条件复 杂，不仅货运点多、货物种类繁多、道路网复杂，而且运输服务地区内运输网点分布不 均匀。因此，如何应用现代数学方法及计算机快速求解路线优化方案是国内外专家学者 探索的重要课题。 为实现运输成本的降低，必须对运输进行合理规划。运输的合理规划涉及到时间、 财务、环境三方面的因素，首先从时间要考虑准时性、快速响应：财务上要考虑运输涉 及的各种开支：环境上要尽可能减少不必要的行驶，避免交通拥挤、空气以及噪音等污 染。这些可以通过改进运输方式、线路规划等交通管理来加以改善。其中运输方式属于 “硬”技术的问题，是可以通过设施的完善来提高运输的效率，降低相应成本。而运输 的线路规划主要是利用各种先进的信息技术对车辆及其路线进行规划，实现对车辆合理 有效的利用，从而节省大量的时间和成本。 本课题从为物流配送企业提供智能化、决策化支持的目标出发，对车辆优化调度问 题进行数学分析，提出了混合蚁群算法解决车辆的配送线路问题。应该说，课题的研究 具有十分重要的理论与实际意义。 1 2 国内外研究现状 物流配送车辆优化调度问题最早是由d a n t z i g 和r 锄s e r 于1 9 5 9 年首次提出，他们 描述了一个将汽油送往各加油站的实际问题，并提出了相应的数学规划模型及其求解算 法【l 】ob o d i n 、g o l d e n 等人在他们的综述文章中对一般的车辆优化调度问题做了详尽的 论述【2 l 。随着研究的深入发展，如何使研究的理论模型更贴近现实中的运输调度问题开 始成为研究焦点。 l a p o n e 和n o b e r t 等人( 1 9 8 5 年) 主要研究了带容量和距离限制的车辆优化调度问 题【3 j s o l o m o n 和d e s m s i e r s 等人( 1 9 8 7 年) 考虑将时i 白j 约束加入到一般的车辆优化调 度问题中，最早对带时间约束的车辆优化调度问题进行了研究州。9 0 年代以后车辆优化 沈阳工业大学硕士学位论文 调度问题引起了运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应 用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的 前沿与研究热点问题。随着现代物流的不断发展，多车场车辆优化调度问题【5 ，6 】、随机车 辆优化调度问题吲、装卸混合车辆优化调度问题【8 i 等更加复杂的路径问题被不断的提出 和研究。 目前国内外用于解决该问题的现代数学方法主要分为以下几类：精确优化方法、启 发式方法、模拟方法、交互式优化方法。以往广泛采用的是第一种方法，另外三种方法 则代表了较近的研究思想。尤其是启发式方法，作为一种逐次逼近的算法，虽然不一定 得到最优解，但可以高效地得到具有较高精度的解，而且也易于考虑各种各样的实际问 题，因此，现已成为解决物流配送问题的重要方法。 随着人工智能技术的引入和不断发展，模拟退火算法和遗传算法等新的方法以及人 工神经网络和专家系统等新技术，为解决大规模、多目标车辆优化调度问题提供了新的 辅助手段。目前，算法研究集中在对启发式规则和搜索方法的改进，以便提高搜索速度 和质量。主要有混合遗传算法0 1 ( 如与禁忌搜索相结合) 、部分自适应遗传算法1 2 i 、 先聚类分析再优化的两阶段法【1 3 1 4 1 、蚁群算法【1 5 。1 7 l 、免疫算法【l s 】、粒子群算澍1 9 1 等算 法在车辆路径优化问题中的应用。 随着高性能计算机的迅速发展，国外应用计算机及现代数学方法调度车辆以优化运 输管理效果的研究工作正在较大范围内展开，在车辆调度的形式、构造、分析以及求解 方法的实现上都有了许多突破【2 0 1 。并且某些常用且比较成熟的算法已被人们运用于实际 配送调度系统，如美国i b m 以最短路算法和启发式算法为核心算法的v s p x 系统，日 本以节约法为主要算法的v s s 系统，美国美孚利用扫描法调度车辆的h p c a d 系统等。 另外，与先进技术的结合也是物流配送车辆优化调度问题的一个突破。例如在国外 一些国家将地理信息系统、全球定位系统、智能交通系统等技术应用于物流配送车辆优 化调度问题中，更加有助于直观的、实时的反映配送状况，使得该系统更加智能化。 物流配送车辆优化调度问题的形式已有很大发展，该问题不仅仅局限于汽车运输领 域，在水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用，其算 物流配送车辆优化调度问题研究 法已用于航空乘务员轮班安排，轮船公司运送货物经过港口与货物安排的优化设计，连 锁商店的送配货等等，并已经取得了极大的经济效益。 1 3 本文的主要内容 对配送车辆优化调度的理论和方法进行系统的研究是物流集约化发展、构建综合物 流系统、建立现代调度指挥系统和开展电子商务的基础。本文在对物流配送业务进行详 细研究的基础上，针对物流配送中对成本影响较大的车辆优化调度问题进行了集中的研 究。建立物流配送车辆优化调度问题的数学模型，通过对一种启发式算法蚁群算法 的学习与研究，将蚁群算法应用于物流配送车辆优化调度问题中，借助计算机编程，对 该问题求解。 本文的主要内容如下： ( 1 ) 在问题模型建立方面，通过对运输实际问题的分析，介绍了几种典型的车辆优 化调度问题模型，并从实际角度考虑，建立了基于顾客满意度的带时窗车辆优化调度问 题和随机车辆优化调度问题的数学模型。 ( 2 ) 在总结车辆优化调度问题的几种启发式算法基础上，介绍了本文讨论的核心算 法蚁群算法。通过对蚁群算法的学习与研究，提出了一种改进的蚁群算法，旨在扩 大蚂蚁的搜索空间，防止出现停滞现象，同时利用迭代过程中的有用信息，来提高算法 的全局搜索能力，并将其应用于t s p 标准测试实例中来检验算法的有效性。 ( 3 ) 研究分析蚁群算法应用于v i 冲与t s p 问题的区别与联系，利用该算法应用在 t s p 上的经验，针对c v r p 问题设计了一种混合蚁群算法。该算法采用a c s 算法，即 利用其伪随机选择规则和局部、全局更新信息素规则，结合2 o p t 局部优化策略，并考 虑车辆优化调度问题中配送中心的作用，引入节约值，采用每只蚂蚁都构造可行解的路 径构造方式，并将该算法应用于实例中，来测试算法的可行性和有效性。 沈阳工业大学硕士学位论文 2 物流配送的概述 2 1 物流的概念 对于物流尚没有统一的定义，但普遍认为物流有广义和狭义之分【2 1 】。 狭义的物流，指为满足消费者需要而进行从起点到终点间的原材料、中间过程库存、 最后产品和相关信息有效流动和储存的计划、实施和控制管理过程。它的目的是提高企 业的效益，任务是以尽可能低的成本为顾客做出最好的服务，方法是在恰当的时间，恰 当的地点，以恰当的方式向顾客提供恰当数量的服务。 广义的物流，是指从企业的经营战略角度出发，将物流过程与客户需求、企业内部 生产过程以及供应商的制造资源整合在一起，形成联合影响力量，从而达到快速反应市 场、降低风险成本、实现高效益、赢得竞争优势的一种管理过程，即现在人们通常所说 的供应链管理。 2 2 物流配送 2 2 1 物流配送的概念 物流配送指的是物流过程中的转型送货( 也称二次输送、支线输送、终端输送) 。 也就是将货物从物流结点送达收货人的过程，是在集货、配货基础上，完全按用户要求， 包括种类、品种搭配、数量、时间等方面的要求所进行的运送。配送是物流系统中的一 个重要环节。 工厂用户 图2 1 配送流程圈 f 嘻2 1f l o w c l a n o f d i s 砸b 删0 n 物流配送车辆优化调度问题研究 随着物流配送集约化、一体化的发展，常将配送的各环节综合起来，核心部分为配 送车辆的集货、货物配装及送货过程。进行配送系统优化，主要就是配送车辆优化调度。 2 2 2 物流配送的分类和模式 物流配送按配送主体的不同可划分为： ( 1 ) 大型生产厂商主导型物流配送 大型生产厂商主导型物流配送指规模较大，有着分布较广的营销网络的生产厂商直 接将产品按零售商的时间、数量等要求送至零售商的一种配送方式。如海尔、联想、宝 沽等企业通过与第三方物流公司合作进行网上销售与产品配送业务。 地区配送中心 零售商( 专卖店) 图2 。2 大型生产厂商主导型物流配送 f i g2 2d o m i n a n tl o g i s t i c sd i s t 抽l | l i o ns t y l eo f l a 唱e - s c a l em a j l u f a c t u r c r s ( 2 ) 大型连锁企业自组织型物流配送 在连锁配送方面，美国零售业巨头w 小m a n 堪称零售配送的典范，有近2 0 个大型 配送中心，拥有2 0 0 0 多辆长途运输卡车和1 1 万辆以上配送车，并拥有私家通讯卫星和 完善的货物采购、跟踪、库存、配送等管理系统。 沈阳工业大学硕士学位论文 图2 3 大型连锁企业自组织型物流配送 f 培2 3s e l 硒r 鲫i z a 士i o n1 0 9 i 吼i c sd i s 研b 嘶o ns l y l e0 f l a r g e - s c a l ec h 咖叫【c 删瞄 ( 3 ) 大型批发企业主导型物流配送 大型批发商从各生产企业批来商品。并将之批发配送给地域内小型超市、便民店、 百货店等中、小零售企业。 图2 4 大型批发企业主导型物流配送 f i 晷2 4d o 岫瑚c1 晒s t i c sd i 蛐b i l t i o ns i y l eo f l a 塔e s c a l em 燃 ( 4 ) 专业物流企业开展的社会化物流配送 专业物流企业开展的社会化物流配送指诸如中国邮政、快递公司等已有准物流企 业，由原大型生产厂商、批发、零售企业等储运部门脱离母体单独分化出去，或通过不 物流配送车辆优化调度问题研究 同企业间储运部门的联合兼并共同成立的物流公司，以及从公路运输、仓储企业转化而 来的专门从事社会第三方物流服务物流企业。 幽2 5 专业物流企业开展的社会化物流配送 f 培2 5s o c i a l i z a t i o l ll o 舀s t i c sd i s 埘b l l c i 明，i y l eo f p r o 角s s i o n a ll o g i s t i c se n t e 州s c s 物流配送的模式主要包括集中配送模式、即时配送模式、计划配送模式、共同配送 模式和一体化配送模式。 2 2 3 物流配送的功能 物流配送环节在物流系统中占有重要地位，其功能主要体现在以下几个方面。 ( 1 ) 推行配送制有利于合理配置资源 由于实施配送可以做到以配送企业的库存取代社会上的零散库存，或者说可以使库 存相对集中，因此，有条件也可能按照统一计划合理分配和使用资源，做到物尽其用。 ( 2 ) 推行配送制可以降低物流成本，促进生产快速发展 由于各种流通要素相对集中，有益于开展规模经营活动，并且流通的物质要素相对 集中，也便于合理安排各环节上的物流活动，使总体运动协调一致，最终会减少物流领 域内的劳动消耗和费用支出。 ( 3 ) 推行配送制能够充分发挥专业流通组织的综合优势 推行配送很容易使不同的流通组织联系在一起，从而构成多功能的、一体化的物流 运动。这种以配送作为媒介而形成的一体化运作较之各个专业企业独立运作更能发挥流 通组织的整体优势和综合优势 2 2 】。 一8 一 沈阳工业大学硕士学位论文 2 3 物流配送的发展现状 物流配送在不同的国家其发展水平和特点不同，下面介绍美国、日本以及我国台湾 和大陆的物流配送发展现状。 ( 1 ) 美国现代物流配送的发展状况 从2 0 世纪6 0 年代起，商品配送的合理化在美国普遍得到重视。为了在流通领域产 生效益，美国企业采取了以下措施： 1 ) 将老式的仓库改为配送中心； 2 ) 引进电脑管理网络，对装卸、搬运、保管实行标准化操作，提高作业效率； 3 ) 连锁店共同组建配送中心，促进连锁店效益的增长。美国连锁店的配送中心有 多种，主要有批发型( 配送中心主要靠计算机管理) 、零售型( 为某零售商独资兴建， 专为本公司的连锁店按时提供商品，确保各店稳定经营) 和仓储型( 接受独立杂货商联 盟的委托业务，为该联盟在该地区的若干家加盟店负责商品配送) 三种类型。 ( 2 ) 日本现代物流配送的发展状况 在日本，零售业是首先建立先进物流系统的行业之一。便利店作为一种新的零售业 迅速成长，现已遍及日本，正影响着日本其他的零售商业形式。这种新的零售业需要利 用新的物流技术，以保证店内各种商品的供应顺畅。因此日本的物流配送具有以下特点： 1 ) 分销渠道发达。为了保证有效地供应商品，日本许多物流公司不得不对原有的 分销渠道进行合理化改造，更好地做到与上游或下游公司的分销一体化； 2 ) 频繁、小批量进货。日本的物流配送企业的很大一部分服务需求来自便利店， 依靠的是小批量的频繁进货，只有利用先进的物流系统才可能发展连锁便利店； 3 ) 物流配送体现出共同化、混载化的趋势。麸同化、，混载化的商品配送使原来按 照不同生产厂、不同商品种类划分开来的分散的商品物流转变为将不同厂家的产品和不 同种类的商品混合起来的聚合的商品物流，从而得以发挥商品物流的批量效益，大大提 高了运货车辆的装载率： 4 ) 合作型物流配送。在日本，生产企业、零售企业与综合商社、综合物流公司之 间基本上都存在一种长期的物流合作关系。并且，这种合作关系还随着日本工业生产的 国际化延伸到国外； 物流配送车辆优化调度问题研究 5 ) 政府规划在现代物流配送发展过程中具有重要作用。 ( 3 ) 我国台湾现代物流配送的发展状况 台湾地区的配送中心多为中小规模、平房仓库，并采用适合本地区特点的设施设备， 创造了自己的“本土化物流”。他们认为“自动化”不一定适应所有国家和地区的物流 产业发展，引进技术必须考虑企业的财力规模、土地成本、建筑成本、设备成本等条件。 因此，台湾地区没有完全照搬美国和日本的发展经验，而是融合这些国家物流现代化的 经验，根据自己的需求，尽量完善自己的物流薄弱环节。另外，物流人才的培养，也是 台湾物流企业形成自己特色的重要原因之一，他们认为物流现代化不仅在于逐步实现物 流设施的现代化，更重要的是在于人才素质的提高。 目前，台湾的物流配送发展趋势是从整合到聚集。在物流配送的发展初期，企业是 凭借自身力量与外部竞争；在发展的阶段，则是通过若干企业白j 的互助合作与其他企业 竞争：而在联合的阶段则是通过资源共享的结盟来与其他企业竞争，也就是使自己的竞 争对手通过聚集成为自己的一部分，这样就达到了高层次竞争的阶段，即通过提供有差 异的服务进行竞争，而非仅通过硬件进行竞争。 ( 4 ) 我国内地的现代物流配送发展状况 物流配送是现代流通的重要组成部分。近年来，我国内地物流配送发展出现了积极 趋势：各级政府部门采取措施积极推动物流配送的发展；在生活资料领域和生产资料领 域出现了各具特色的不同类型的现代物流企业；连锁企业内部的配送中心在硬件设施、 管理水平、管理信息系统等方面的建设，获得较大发展；现代物流技术的开发引进研究 取得一定的进展，如条形码技术、计算机支持的信息管理技术、e d i 、m i 冲等。但与发 达国家相比还处在起步阶段，存在着物流配送市场化程度低，第三方物流配送发展滞后； 物流基础设施落后，物流配送的整体功能低；物流配送管理体制和相关制度不完善；专 业的物流配送管理和技术人才短缺等问题。 2 4 小结 本章首先介绍了物流的一般性概念，然后对物流中的重要环节物流配送的概 念、分类、模式和功能进行了描述，最后阐述了物流配送的发展现状。 1 0 沈阳工业大学硕士学位论文 3 配送车辆优化调度问题 3 1 车辆优化调度问题概述 对物流配送的研究当中，以有效的控制配送中发生的库存成本、运输成本和运输时 间为内容的运输调度问题成为研究的核心和目标。 大多数的物流配送运输调度问题可以归结为车辆优化调度问题，即根据不同要求一 一目标函数( 例如运距最短、配送时间最短、费用最少等) ，将配送运输过程归结为表 述问题的数学模型，设计求解问题的算法，然后用计算机求得合理可行的优化方案。车 辆优化调度问题主要内容是车辆分配和配送线路的生成。j 车辆优化调度问题一般可根据空间特性和时间特性分为车辆路径规划问题( v e h i c l e r o u t i n gp r o b l 咖，v r p ) 和车辆调度问题( v e h i c l es c h e d u l i n gp r o b l 锄，v s p ) 。目前多 数研究该领域的学者将车辆优化调度问题统称为v i 冲，而具体的问题会加约束限制来命 名，如将有时间要求的车辆调度问题称为v r p t w ( v 出c l er o u t i n gp r o b 】e m 谢t 1 1t i m e w i n d o w s ) ，还有c v r p ( c a p a c 姆v e l l i c l e r o u t i n g p r o b l e m ) 、m d v r p ( m u l t i d 印o t v e l l i c j e r o u t i n gp f o b l 锄) 、d v r p ( d y n 锄i cv e h i c j er o u t i n gp r o b 】e m ) 等。 车辆优化调度问题一般可描述为对一系列装货点和( 或) 卸货点，组织适当的行车 线路，使车辆有序地通过它们，在满足一定的约束条件( 如货物需求量、发送量、交发 货时间、车辆容量限制、行驶里程限制、时间限制等) 下，达到一定的目标( 如路程最 短、费用最少、时间尽量少、使用车辆数尽量少等) a 3 2 车辆优化调度问题分类 配送车辆优化调度问题可按照其构成要素划分为不同的种类【2 3 2 4 】。 ( 1 ) 按任务特征分，有纯装问题或纯卸问题( 车辆在所有任务点装货或卸货，即集 货或送货问题) 及装卸混合问题( 每项任务有不同的装货点和卸货点，即集货、送货一 体化问题) ； 物流a b 送车辆优化调度问题研究 ( 2 ) 按车辆载货状况分，有满载问题( 货运量不小于车辆容量，完成一项任务需要 不只一辆车) 、非满载问题( 货运量小于车辆容量，多项任务用一辆车) ，以及满载和 非满载混合问题； ( 3 ) 按车场( 或货场、配送中心等) 数目分，有单车场问题和多车场问题； ( 4 ) 按车辆类型数分，有单车型问题( 执行任务的所有车辆容量相同) 和多车型问 题( 车辆的容量不全相同) ； ( 5 ) 按车辆对车场的所属关系分，有车辆开放问题( 车辆可以不返回其发出车场) 和车辆封闭问题( 车辆必须返回其发出车场) ； ( 6 ) 按优化目标数来分，有单目标问题和多目标问题。 实际中的车辆优化调度问题可能是以上分类中的一种或几种的综合，根据情况的不 同，问题的模型构造及算法有很多差别。 3 3 车辆优化调度问题模型分析与建立 3 3 1 一般描述 不考虑时间窗的车辆优化调度问题，在实际应用中非常广泛。在日常生活和生产实 际当中，许多类似的问题都可归结为集货或送货车辆路径优化问题。如有一个中心货场， 向一些顾客送货物，每个顾客对货物有一定的需求，运送货物的车辆在货物装满货后出 发，把货物送到各顾客处，完成任务后返回货场，如何确定满足用户需求的费用最小的 车辆行驶路线，即送货车辆优化调度。又如，若干厂家生产一些产品，需要运到中心仓 库，车辆从仓库出发，到各厂家去装货，装满后返回仓库，在满足厂家发货要求的情况 下，按什么路线行驶可使总费用最小，即集货车辆优化调度2 5 1 。 这两个问题实质是相同的，只有装货任务或只有卸货任务。在实际物流运输过程中， 如批量大的货物( 可以满载的) 可以直接运往需求点( 或配送中心) 【2 甜，批量小的( 不 能满载的) 可以在网点进行配载，来提高车辆的利用率，即考虑用一辆车完成多项任务。 形成图3 1 所示的配送线路。 3 3 2 数学模型分析与建立 按照不同的分类原则可将v r p 细分为多种子问题，不同的子问题建立不同的数学 模型，便于采用相应的数学算法进行优化。国内外专家已经对该问题进行了大量的理论 沈阳t 业大学硕士学位论文 研究和试验分析，如单车型车辆路径问题，多车型车辆路径问题；单源点车辆路径问题， 多源点车辆路径问题；非满载车辆路径问题，满载车辆路径问题；确定型车辆路径问题， 随机型车辆路径问题等。 图3 1 配送路径图 f 毽3 1d i s 一b 嘣o n i d u t em 卵 运用v r p 模型，对实际问题进行研究时，需要考虑以下几个方面的问题。 ( 1 ) 配送中心：配送中心的级数，每级配送中心的数量、地点和规模； ( 2 ) 车辆：车辆的型号和数量，每种车的容积和运作费用，出发时间和返回时间 司机休息时间，最大里程和时间限制； ( 3 ) 顾客：，顾客需求、装载或卸载、所处的地理位置、优先等级； ( 4 ) 道路信息：车辆密度，道路交通费用，距离或时间属性； ( 5 ) 货物信息：货物的种类多少，兼容性，货物的保鲜； ( 6 ) 运输规章：工人每天的工作时间，车辆的周期维护。 典型的v i 冲模型可以表述如下； ( 1 ) 基本条件 现有吖辆相同的车辆停在一个共同的源点( 或物流中心) v 。，它需要给一个顾客提 供货物，并且源点和客户的坐标已知。 物流配送车辆优化调度问题研究 ( 2 ) 模型目标 确定所需要的车辆数目m ，并指派这些车辆到一个回路中，同时包括回路内的路径 安排和调度，使得运输总距离s ( 或总费用c ) 最小。 ( 3 ) 约束条件 1 ) 所m ： 2 ) 每个订单都要完成； 3 ) 每辆车完成任务之后都要回到源点v 。； 4 ) 不能超过车辆的容量限制； 5 ) 特殊问题还需要考虑时间窗的限制； 6 ) 运输规章的限制。 为构造数学模型方便，引入图论中的表述。给定一个有向图g = ( 矿，爿) ，y 是配送 点与任务点集，矿= o ，1 ，n ) ，爿为有向边集，爿= ( f ，州f ，矿，f 办，任务点f 到，的 运距为矾。 下面针对以下几种典型的车辆优化调度问题的模型进行分析与建立。 ( 1 ) 单源点单车型非满载车辆优化调度问题模型 单源点单车型非满载车辆优化调度问题描述为：有车场，拥有容量为g 的车辆， 现有 项货物运输任务，以1 ，”表示，已知任务点f 的位置坐标和货运量为晶 ( f = 1 ，2 ) ，且0 g ，g ，求满足货运要求的总费用最小或总运距最短的车辆行驶 路线：车场可以是泛指车辆发出地，也可以是车库、货场、仓库或配送中心等。 要求每个任务点的货运量必须满足，且只能由一辆车装( 卸) 货，每条配送路径上 各任务点的货运量之和不超过车载重量。 为了使路线安排具有一定的弹性，可预先估计一个完成任务所需要的车辆肌。 ( 3 1 ) 沈阳 ：业大学硕士学位论文 其中，f 】表示不大于括号内数字的最大整数，o 五 0 ， 则模型目标是使用的车辆数最小。 ( 2 ) 单源点单车型满载和非满载混合车辆优化调度问题模型 单源点单车型满载和非满载混合c v r p 描述为：有一车场，拥有容量为g 的车辆， 现有”项货物运输任务，以1 ，珂表示，已知任务点j 的位置坐标和货运量为g f ( f = 1 ，疗) ，且j g ，q ，求满足货运要求的总费用最小或总运距最短的车辆行驶路 线。 对于g ，g 的任务点，完成货物运输任务的满载车数为 旦】，设【鱼 为数值不大 qq 于兰2 的最大整数。 g 则单源点单车型满载和非满载混合c v r p 问题就可以分为两个部分：一部分是计算 g 。q 的任务点f 所需的整车数，进行车辆运输配送，不需要优化策略；另一部分是剩 下的不足车辆满载的货物可以与其它货物一同进行非满载配送，可利用( 1 ) 所述的非 满载车辆优化调度模型进行配送。 ( 3 ) 有时间窗的非满载车辆优化调度问题模型 在现今的市场竞争环境下，随着企业j i t ( j u s 卜i n t i m e ) 战略的实施，零库存成为 许多企业追求的目标，于是市场对物流的各方面的要求很高。主要体现在其敏捷性、柔 性方面，实际表现在提高客户的满意度，减少客户投诉。而实现以上目标的最佳途径就 是要在准确的时间或合适的时间将产品送到客户手中。可见研究有时限配送车辆调度问 题具有十分重要的现实意义。而企业最终要达到的目标是利润最大，成本最小。所以有 时间窗的车辆优化调度问题( v s p 或称v r p t w ) 就是一个多目标规划问题。 有时白j 窗的非满载车辆优化调度问题的描述为：有一车场，拥有容量为q 的车辆， 现有押项货物运输任务，以1 ，n 表示，已知任务点f 的位置坐标和货运量为 沈阳工业大学硕士学位论文 ( j _ l ， ) ，且o 蜀q ，以及完成点f 任务需要的时间表示为，且任务f 必须在 时间窗口【e z ，z 】开始执行，其中e t 为任务f 允许的最早开始时间，l z 为任务f 允许 的最迟开始时间。如果车辆到达点f 的时间早于e z ，则车辆需在f 处等待；如果车辆到 达时间晚于工z ，则任务j 将被延迟进行。车场的时间窗范围较大，基本可以不作约束。 求满足货运要求的总费用最小或总运距最短的车辆行驶路线。 根据时间约束的严格与否，有时间窗的车辆优化调度问题可分为两类： 硬时间窗v r p 是指每项任务必须在要求的时间范围内完成，时间不在这个时间范 围，则得到的解为不可行解。 软时间窗v r p 是指如果某项任务不能在要求的时间范围内完成，则给予一定的惩 罚。 在前面的c v r p 的基础上，考虑时间窗约束，建立有时间窗的车辆优化调度模型。 定义变量如下： y 。倦嚣任务蚌辆皖成 1 1 ，车辆女从点圻亍驶到点， x 水2 1 0 ，否则 1 ) 一般的有时间窗的车辆优化调度问题模型 车辆到达任务点，的服务开始时间是： r = x 舭( f f + 勺+ z + m a x ( e 正一f 。，o ) ) ( 3 6 ) 式中表示车辆从点f 到点_ ，的行驶时间。 白表示从点f 到点_ ，的费用，根据具体实际情况确定。只表示在e z 之前到达任务点 j 等待的单位时间成本，只表示在上z 之后到达任务点j 的单位时间所得的罚金成本；若 车辆在e 之前到达点，则增加机会成本日( 明一，1 ) ，若车辆在上z 之后到达点，则 增加罚金成本县( ，i 一三z ) 。 物流配送车辆优化调度问题研究 要求每个任务点的货运量必须满足，且只能由一辆车装( 卸) 货，每条配送路径上 各任务点的货运量之和不超过车载重量。则有时间窗的车辆优化调度模型如下： m i n z = 勺工舭+ 只m a x ( e 正一，o ) + 只m a x ( r ，一上z ，o ) ( 3 ，7 ) ， l = 1悻l “ & 耽g 讹 儿= l f _ 1 ，刀 嘞= 均_ ，= 1 ，；v 七 二2 i - 1 ，疗；v 】 1 ( 3 8 ) 蚓一1 凇 1 ，一，胛 ；v 七 m = o 或l j ，= 0 ，l ，胛；v 后 此= o 或1 f _ 0 ，l ，疗；v | 当只= 只专。o 时，以上模型为硬时间窗v i 心问题。 2 ) 基于顾客满意度的有时间窗的车辆优化调度问题模型 传统的基于顾客满意度车辆优化调度模型对于运输服务的时间约束用时间窗表示。 其中e t 为任务f 允许的最早开始时间，工r 为任务j 允许的最晚开始时间，而 五z ，上7 ：】表 示任务f 在该时间范围内开始，顾客满意度最大值为1 ，否则顾客满意度为o