中文摘要物流配送车辆调度问题就是指:在给定运输任务的条件下,如何派车、组织循环运输,使空驶里程最少,运输成本最低。
目前我国大多数的物流企业运输资源分配不均、配送路线安排不合理、运力资源浪费严重,而缺乏完善的物流配送车辆调度优化方案就是造成此现象的重要因素之一。
因此对物流配送车辆调度问题的研究具有重要的现实意义。
目前对单车场、封闭式物流配送车辆调度问题研究较多,而对多车场开放式物流配送车辆调度问题研究较少,但就是多车场开放式物流配送车辆调度问题有很强的应用背景。
本文针对此问题,建立了一种灵活的多目标组合优化模型,设计了适合多车场开放式车辆路径问题的通用染色体编码方案,并对遗传算法中的交叉变异操作做了详细说明。
此模型可以方便的增减优化目标值,并通过测试用例验证了本文设计的优化模型与遗传算法在解决多车场多目标开放式物流配送车辆调度问题中的可行性。
自动化立体仓库出库端车辆调度策略的设计就是物流配送车辆调度中的一个关键问题,好的调度策略可以大大缩短出库端的配货时间。
为此本文引入动态优先级理论,并利用该理论对大型AS/RS 出库口车辆调度问题进行了深入研究与分析,提出了基于动态优先级的AS/RS 出库端车辆调度策略,并开发了相应的AS/RS 出库口发货资源监控系统,即AS/RS 出库口车辆调度系统,优化了AS/RS 出库端车辆调度策略,大大提高了物流配送当中的配货效率。
本文建立的多目标组合优化模型以及设计的遗传算法求解方案,可以有效的缩减物流配送中的送货时间;设计的AS/RS 出库端车辆调度优化策略及开发的AS/RS出库端车辆调度系统,可以有效缩减车辆在出库端的配货时间。
本文对以上两种物流配送中的车辆调度问题进行研究,大大提高了物流配送效率、减少了物流配送成本。
关键词:物流配送;车辆调度;多目标组合优化;遗传算法第一章绪论1、1 课题背景物流(Logistics):指在合适时间,将合适的物品以适当的数量准确地送到顾客手中,它就是供应链中最重要的组成部分。
一般意义上就是指在生产与生活中所涉及的各种物质实体由供给方向需求方的物理性转移过程。
这一概念将物流定义在有用的物、供方、需方等几个基本因素之上。
也就就是说,我们通常所指的物流就是指人们在生产与生活中发生的有意义的物流行为。
整个物流过程就是一个物理过程,只改变时间与空间的状态,不改变其使用价值。
其中,时间状态的改变称之为仓储、流通加工等活动,空间状态的改变称之为运输、搬倒等活动。
物流配送就是物流系统中的一个重要环节,它就是指按客户的订货要求,在物流中心进行分货、配工作,并将配好的货物及时送交收货人的物流活动。
配送成本直接关系到物流企业与部门的效益,目前我国的大多数的物流企业运输资源分配不均、配送路线安排不合理、运力资源浪费严重, 根据中国仓储协会对146个企业的调查显示,用于运输的费用占整个物流费用的比例分别为:在生产企业原料物流中占58%,在生产企业成品物流中占73%,在商业物流中占52%。
所以物流配送车辆调度方案的合理优化,对于整个物流运输速度、成本、效益的影响至关重要。
运输就是指“物”的长距离的移动,任何跨越空间的物质实体的流动,都可称为运输。
运输就是物流的中心环节之一,被称为国民经济的动脉与现代产业的支柱,从社会经济的角度讲,运输功能的发挥,缩小了物质交流的空间,扩大了社会经济活动的范围并实现在此范围内价值的平均化、合理化。
在社会经济的发展中,运输的重要性己经被人们所确认,成为国民经济的命脉。
从物流系统的观点来瞧,运输作业的关键因素包括运输成本与运输速度两个方面。
运输成本:就是指为两个地理位置的运输所支付的款项,以及管理与维持转移中存货的有关费用,应采用能把系统总成本降低到最低限度的运输方式。
运输速度:就是指为完成特定的运输作业所需花费的时间。
运输速度与成本的关系,主要表现在以下两个方面:首先,运输商提供的服务越快速,实际需要收取的费用也就越高。
其次,运输服务越快,转移中的存货就越少,可利用的运输间隔时间越短。
因此在选择最合理的运输方式时,至关重要的问题就就是如何平衡其服务的速度与成本。
运输主要目的就就是要以最低的时间、财务与环境资源成本,将产品从原产地转移到规定地点。
同时,产品转移所采用的方式必须能满足顾客有关交付履行与装运信息的可得性等方面的要求。
所以在物流系统中,必须精确地维持运输成本与服务质量之间的平衡。
低成本运输与高质量服务就是令人满意的。
物流配送车辆调度就就是研究怎样合理运输的问题,所谓合理运输就就是在实现物资产品实体从物流中心至消费地转移的过程中,充分有效地运用各种运输工具的运输能力,以最少的人、财、物消耗,及时、迅速、按质、按量与安全的完成运输任务。
其标志就是:运输距离最短、运输环节最少、运输时间最短与运输费用最省。
据统计运输费约占整个物流费用的40%,占销售收入的2、88%。
物流配送车辆调度问题就就是指在给定运输任务的条件下,如何派车、组织循环运输,使空驶里程最少,运输成本最低。
车辆调度就是物流管理最重要的部分,正确合理的调度可以有效减少车辆的空驶率,实现合理路径运输,从而有效减少运输成本,节约运输时间,提高经济效益。
1、2 课题研究的意义物流产业的发展,将从整体上改变经济运行的方式,提高经济运行效率,对增强国际竞争力将起到巨大的推动作用。
我国国民经济的发展呼唤物流的进一步发展,对物流的发展要求如下:(1) 降低流通成本在GDP 中的比重:在我国目前工业企业生产中,直接劳动成本占总成本的比重不到10％,而物流费用占商品总成本的比重,从账面反映约为40％,全社会物流费用支出约占GDP 的20％,而其她发达国家一般在10%左右。
这反映了我国物流系统落后,流通成本太高,反映了我国国民经济运行质量不高。
通过发展现代物流业来促进物流合理化,降低流通成本在GDP 中的比重,无疑将成为我国新的经济增长点。
“十五”期间,如果我国物流费用降低到占GDP 的15％,每年将为社会直接节约2400 亿元的物流成本。
(2) 减少企业流动资金占用:我国工业企业与流通企业由于物流基础设施、技术与管理的落后,原材料、半成品、成品积压严重,大量流动资金被占用,周转速度很慢,物流成本过高。
据统,1992 年,国有独资、控股工业企业流动资金占用1 万多亿元,周转速度为1、62 次/年;1999 年,国有独资、控股工业企业流动资金达31000 亿元,周转速度仅1、2 次/每年,与发达国家相比非常落后。
如果工业企业把物流职能分离出来交给第三方物流企业,通过其先进、科学的专业化服务,就可以减少流动资金占用,提高核心竞争能力,实现从粗放式经营向集约式经营转变。
(3) 电子商务的发展需要物流做基础:电子商务就是流通领域的一场革命,它把3商品买卖虚拟成一个大的市场,使客户在任何地点、任何时间都可以购买商品。
但就是,电子商务需要将网上订的货物及时送到可能在任何地方的客户手里,这就给物流系统带来很大的挑战。
实际上,物流已经成为电子商务发展的瓶颈,需要建立具有响应性、灵活性与可视化的现代物流系统,需要第三方物流企业的服务。
世界500强中相当多的企业都就是通过第三方物流来解决它的供应链与销售问题的,很多跨国公司在欧洲、亚洲、美洲等地分别有不同的第三方物流企业为她服务。
(4) 现代物流产业的发展,将减少由于低水平、条块分割的物流方式造成的巨大物耗:在传统的物流框架下,一件商品从生产出来到最终的消费环节,至少要被搬倒、装运十几次。
实行社会化的多式联运、一单到底,物流过程中的物耗至少可以减少几倍。
我国汽车空驶率达37％左右,意味着全国每年有150 多万辆载重汽车无活可干,这种潜在浪费至少也在数千亿元。
按现代物流要求,合理的流程设计可使空驶率降低到5％以下。
在现代物流集约化、一体化的发展中,配送就是直接与消费者相连的重要环节,其核心部分为配送车辆的集约、货物配装及送货过程,而配送车辆优化调度就是物流系统优化、物流科学化的关键一环,就是货物从配送中心送达收货人的过程。
配送首要解决的就是车辆的调度问题,几十年来这一直就是一个研究的热点,在满足与完成各任务的前提下,正确合理的安排行车路线、提高配送车辆的利用率就可以有效的节省时间从而减少运输成本。
另外对出库口车辆调度问题的研究,将有效减少货物装配的时间。
所以本文对物流配送车辆调度的研究具有重要意义。
1、3 国内外研究现状车辆调度问题最早就是由Dantzig与Ramsert在上个世纪50年代末期提出,该问题一般称之为VehicleRouting Problem(VRP)或者Vehicle Scheduling Problem(VSP),现在我们将车辆调度问题一律简称为VRP。
VRP提出后就很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科专家与运输计划制定者与管理者的极大重视,成为运筹学与组合优化领域的前沿与研究热点问题。
各学科的专家对该问题进行了大量的理论研究及实验分析,取得了很大进展。
国外对物流配送车辆优化调度问题作了大量而深入的研究,例如早在1962年,Balinski等人首先提出VRP的集分割,直接考虑可行解集合,在此基础上进行优化,建立了最简单的VRP模型;1964年,Clarke与Wright提出了一种启发式节约法来建立车队配送路线;1968年,Rao等人在VRP 集分割的基础上引入了列生成方法进行求解,这种算法本质上就是最短路径算法,同时结合了分枝定界算法;1971年,Eilon 等人提出将动态规划法用于固定车辆数的VRP,通过递归方法求解;1981年,针对带能力约束、时间窗以及无停留时间的VRP,Fisher提出了三下标车辆流方程;Thangiah于1991与Joe于l993分别用遗传算法求解VRP,但就是都存在“早熟收敛”的问题;2001年,Tan,Lee,Du结合遗传算法、tabu树搜索算法的优点,形成知识库,用人工智能的方法来求解;2002年,Taranrilis,Kiranondis使用空间决策支持系统来解决车辆路径问题。
在国内,有关车辆调度问题的研究就是在20世纪90年代以后才逐渐兴起的,比国外相对落后。
国内研究对象主要就是旅行商问题(Traveling Salesman Problem,简称TSP)、中国邮递员问题(Chinese Postman Problem,简称CPP)、有向中国邮递员问题(DirectedChinese Postman Problem,简称DCPP)等,系统性研究还很少见到。
西南交通大学的李军教授与郭耀煌教授对车辆优化调度的基础理论及各类问题进行了系统的研究;李大为等以TSP的最近距离启发式为基础,通过设置评价函数来处理时间窗约束,求解了简单的VRP。