详情

原文传递物流匹配问题的调度模型和算法研究

论文题名：	物流匹配问题的调度模型和算法研究
关键词：	物流匹配;车辆合乘;启发式算法;时变网络;调度模型;人工智能
摘要：	商务活动的飞速发展加速了物流行业的发展。随着全球经济及电子商务的不断推进，物流成本在整个成本中所占的比重越来越大，物流的有效性问题也变得越来越突出。同发达国家相比，中国的物流绩效指数排名较低，这说明我国的物流效率尚需提高。资料显示，我国公路运输中车辆的空载率约为40％，而美国仅为10%。高空载率不仅带来了资源的浪费，还对交通、环境等带来巨大影响。　　随着信息技术、通信技术及人工智能技术的发展，充分挖掘既有物流资源潜力，提高物流资源利用率，符合目前我国的发展要求。众所周知，车辆资源是非常核心的物流资源，采取有效措施提高车辆满载率，对提高物流效率具有重要意义。国内外学者提出的“协同物流”、“运输协作”等概念，以及政府部门的“共同配送”的建议，都是围绕如何提高车辆满载率而提出的。　　在物流领域中，进行车辆运力搭配，充分挖掘物流运力的问题可归结为一类物流车辆合乘匹配问题，简称车辆合乘匹配问题。如何选择合适线路，使得多辆车在运载过程中发挥最大运力，同时使得平均成本最小化，就是物流匹配问题的研究目标。显而易见，合乘产生的费用分摊到所有参与者，如果调度得当，对物流参与者来说，无疑可大大降低其成本输出，提高经济效益，这对解决我国目前物流行业中存在的运输成本居高不下的问题具有重要意义。在载人交通领域，也存在着同物流领域类似的问题。世界发达国家如美国、德国、新加坡等，早在上个世纪70年代就已开始所谓“合乘”的尝试，其政策、基础设施及技术相对成熟。我国近年来经济飞速发展，汽车保有量呈快速增长趋势，由此带来了一系列社会问题，如交通堵塞、环境污染、噪声污染等，民间团体和学术界也开始探索解决该问题的政策及技术手段，“拼车”、“搭便车”的概念被提出，国内多个一线城市也开始了一些尝试。　　从流通的角度出发，货物和乘客都可合并理解为服务需求，而匹配的目的就是在满足（或尽量满足）服务需求的前提下，以较小的成本，将其从出发地输送到目的地，两者本质上具有相对一致性，均可归结到车辆合乘匹配问题。综上所述，物流匹配问题作为流通领域的关键技术问题，具有重要的理论研究价值和实际应用价值，本文研究就是基于此而展开的。　　本文的主要研究内容包括以下几个方面。　　1、对物流匹配问题中确定性单车辆物流合乘匹配问题进行研究。根据服务需求及车辆的位置关系、时间窗口约束等，将多个服务需求分配到某一辆车上，然后研究车辆如何以低成本方式实现搭乘，并尽量提高搭乘成功率。针对现代物流中的车辆调度问题，提出物流调度问题中的确定性单车辆物流合乘匹配问题—SVLRMP问题。对该问题进行了形式化定义，确定了其目标函数及约束条件；提出基于先验聚类的匹配度聚类启发式算法—MDCA算法；在具体路径优化过程中，构建了多种群的竞争-捕食协同进化混合模型，基于群落之间的均匀性指标指导协同进化遗传算法的执行，并将之应用于单车辆物流合乘匹配问题中。数值实验说明 MDCA算法能以较高的准确性选择服务需求，且能在较短时间内获得搭乘方案，并有效降低车辆自身所承担的成本。　　2、在单车辆物流合乘匹配基础上，考虑车辆之间的协作，将单车辆问题扩展为确定性多车辆问题。研究多车辆物流合乘匹配问题，根据车辆同服务需求的匹配情况，研究服务需求的合理聚类方案，将服务需求唯一分配到一辆车上；研究多车辆物流合乘匹配优化方案。针对现代物流中车辆协同调度问题，在 SVLRMP问题基础上，首次提出物流调度中的确定性多车辆物流合乘匹配问题—MVLRMP问题。对该问题进行了形式化定义，确定了其目标函数及约束条件；针对多车辆协同调度的需求，提出利用两阶段聚类启发式算法—TSCA算法。该算法包括两个聚类过程：第一个过程称为一次聚类过程，基于匹配度的启发式聚类过程生成匹配度矩阵，经过行列变换后生成聚集矩阵，然后利用轮赌策略将服务需求唯一确定到某一车辆上；第二个过程称为二次聚类过程，基于解决 SVLRMP问题的先验聚类算法实现单车辆的合乘匹配过程。考虑一次聚类过程的概率性特点，为提高聚类准确性并增加车辆间的协同性，提出服务需求的主动迁移（包括迁出过程及迁入过程）及扰动策略。通过对中国济南市的10辆车及30个搭乘服务需求的案例结果分析，TSCA算法能够在较快时间给出优秀的搭乘方案，整体搭乘成本及搭乘成功率较高，且表现出了一定的车辆协同性。　　3、在确定性多车辆物流合乘匹配问题基础上，引入换乘特点，允许一个服务需求先后搭乘多辆车以完成其目标。换乘的引入，增加了路径寻优难度，本研究尝试将服务需求根据时间窗口的松弛程度对客户进行简单分级，先满足优先级高的服务需求，再满足优先级低的服务需求，研究尽量提高搭乘成功率的方法。针对物流调度过程中经常出现的服务需求换乘现象，将换乘的概念引入多车辆物流合乘匹配中，提出支持换乘的多车辆合乘匹配问题--MVLRMP-T问题。该问题摒弃一个服务需求只能接受一个车辆的服务的约束，可进一步提高搭乘成功率。对该问题进行了形式化定义，研究了换乘点的确定方法，确定了其目标函数及约束条件。本文提出通过MVLRMP的寻优结论形成MVLRMP-T问题的路网结构，并基于改进蚁群算法进行换乘路线的选择和确定。在进行搭乘寻优时采取“先串行寻优，后合并微调”的寻优策略。实验结果表明，改进蚁群算法可有效支持换乘，表现出较强的适应能力。　　4、在确定性多车辆物流合乘匹配问题基础上，引入路网时变特征，将确定性问题扩展为具有一定动态性的物流合乘匹配问题。研究路网时空特征对车辆速度的影响，以及在此特征下如何进行路线寻优的方法。针对实际物流调度过程中路网的时变特征，在前述研究的基础上，提出基于路网时空特征的多车辆物流合乘匹配问题—MVLRMP-ST问题。该问题充分考虑路网的时空特征，同实际应用更为符合。对MVLRMP-ST问题进行了形式化定义，松弛了原MVLRMP问题中有关时间窗口的约束，提出解决该问题的TSCA-ST算法。TSCA-ST算法是TSCA算法的扩展，车辆的速度根据路网特征而变化；对车辆通过路段虚拟行使时间、路段实际行使时间及车辆通过某路段所跨越的时段数K进行了确定，提出车辆速度的确定方法，并考虑了路网环境特征对路径质量的影响。为验证算法的有效性，本研究以山东高速公路网及山东境内的国省道网络为基础，构造了本实验所运行的时变网络，并设计了相关实验。实验中，车辆类型具有异构性，路段特征也具有异构性，同时还考虑了环境变化对车辆路径的可靠性影响，这使得实验结果具有很强的使用价值。我们设计了车辆在不同工作日类型中的搭乘实验，实验效果良好，可为实际物流搭乘提供备选方案，具有很高的实用价值。
作者：	邵增珍
专业：	管理工程与工业工程
导师：	刘弘;王洪国
授予学位：	博士
授予学位单位：	山东师范大学
学位年度：	2013
正文语种：	中文