动态环境下的车辆调度问题研究.pdf

⑧动态环境下的车辆调度问题研究培养单位：指导教师：经济与管理学院管理科学与工程郭凤鸣申请同济大学管理学硕士学位论文一级学科：二级学科：研究生：霍佳震教授二晔摘要在物流研究领域内车辆调度和物流配送一直是物流理论研究和实践工作关注的焦点这是因为运输成本在整个物流成本中占有很高的比例优化后的运输作业不但能带来巨大的成本节约还能提高顾客服务水平。另一方面由于车辆调度问题具有组合优化问题的基本特点也成为应用数学、运筹学、物流管理和计算机科学等领域的研究热点。然而以往的大量车辆调度研究往往建立静态的假设上即所有的任务或需求在调度决策和线路规划之前已知调度决策一旦开始执行以后所有的情合实际了因此学者们也开始关注起动态车辆调度这一新的研究方向。本文在简单回顾已有的动态车辆调度研究基础上将关注点放在新需求在调度决策执行过程中不断实时产生这样的环境下将车辆调度问题分为纯集货文章首先对动态车辆调度问题的研究现状和基本问题进行阐述确立了本文的研究内容。在对动态集货或送货车辆调度问题的研究中本文考虑了多车辆、容量约束、时问窗约束建立了基于动态时问轴的数学模型并分静态解的构造和动态解的插入两个阶段设计了相应的启发式算法最后给出算例及实现。基础上提出了基于蹽＼亩盗镜鞫认低车纳杓品桨福庑┘关键词：实时需求动态车辆调度问题启发式算法集货或送货集送货一况不再发生更改。这一假设在电子商务和物流高速发展的今天已经越来越不符或纯送货问题和集送货一体化问题两大类进行新的研究。对动态集送货一体化问题本文也构建了相应的数学模型并设计了两阶段的求解算法并在随后对可拼装的动态集送货一体化问题本文以分组策略为基础详细设计了问题的求解策略。文章的最后以实际课题为例在简单介绍和分析了和际醯术与动态车辆调度理论研究相结合既有一定的理论意义又有较强的实践价值。体化．．猵琌．瓸疍瑃甅琺琫．瑃甐籵—·琧．⑽鰐一叩篟猅瑆甀．猵琣．珿甌．琀第滦髀研究背景随着市场经济的发展作为企业“第三利润源泉”的物流对经济活动的影响日益明显越来越引起人们的重视成为当前“最重要的竞争领域”。未来的市场竞争物流将起着举足轻重的作用。对大多数企业来讲运输通常代表物流成本中最大的单项成本。据观察货物运输费用一般占物流总成本的三分之一到三分之二Ｒ虼俗畲蠡迷耸渖璞负腿嗽保诒Ｖぢ阋欢ǖ目突Х水平的基础上对物流配送车辆进行优化调度成为企业特别关注的问题。物流配送车辆优化调度是物流系统优化中关键的一环也是电子商务活动不可缺少的内容。通过对配送车辆进行优化调度企业可以降低运输成本提高顾客服务水平和经济效益从而获得更多的利润。闯盗镜鞫任侍和和】提出后很快便引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视并一直是运筹学与组合优化领域的前沿与热点问题。在以往几十年研究的问题中大部分属于经典的车辆调度问题。在这些问题中人们一般假定在路径规划之前所有的信息如顾客的地理位置、顾客的请求服务时『日⒐丝颓肭蟮姆窳俊⑾殖〉姆袷蔽省⒙眯惺蔽实龋诼肪豆随时间推移而变化。在这样的假定下安排的路径也是相对固定的因而这类国外将配送车辆调度问题归结为闯盗韭肪问题炊嗦仿眯猩涛侍【。该问题于年由划前足已知的调度员对所有信息掌握在胸并且这些信息均与时间无关不车辆调度问题被称为静态车辆调度问题。研究意义然而近年来电子商务在全国和世界范围内迅速增长。而电子商务的兴起使得传统的物流配送发生了很大的变化它改变了人们习以为常的消费活动内容与形式。凭借网络的便利性消费者可以经过上网来完成交易的动作再加上电子资料交换际醯某墒欤邢喙氐亩┗跣畔⒛芄辉诘谝皇奔浯ǖ莸整个供应链系统也就是消费者可以进行实时的订货。这样就将车辆调度问题黄入了一个新需求随时产生的动态环境中在这种情况下静态车辆路径规划问题的理论和方法不再具有处理这些问题的能力需要研究一套新的与静态车辆调度问题相对应的动态车辆调