配送线路划分与电子排单系统建模与算法研究

论文摘要

目前物流配送中心的末端配送主要采取集中统一的送货方式,这种配送模式必须综合考虑配送网点订货情况、物流配送中心规模、道路拥挤度、道路整改等因素对配送效能的影响。本文从衡量配送线路实际工作量大小的“广义工作量”指标入手,在地理信息系统(Geography Information System, GIS)和企业网络数据库系统的支持下,以提高网点客户满意度和降低配送成本为主要目标,进行物流配送中心末端配送线路优化课题的研究工作。研究工作主要包括配送线路广义工作量和送货经济距离概念的提出和应用、配送线路的划分、单车线路优化和电子排单系统的可视化输出等内容。首先,本文提出了衡量配送线路工作量大小的“广义工作量”的概念。广义工作量是配送中心进行配送线路区域划分的一项重要经济指标,它与送货经济距离S、送货量D、零售网点数量N等因素相关,它要求不同配送线路之间广义工作量大小基本均衡,以使所有线路车辆送货员或驾驶员在其配送过程中更好地为客户提供满意的服务。在体现广义工作量大小的影响因素中,客户订货量(即配送中心送货量)、送货经济距离、单车线路的网点客户数量都是物流配送中心送货线路划分的重要因素。送货经济距离是指在考虑路段长短、拥挤程度、车道数量、路面类型等因素基础上,实现两点间配送时间最短的车辆行驶距离值。广义工作量概念的提出是进行配送线路划分的先决条件,也是求解配送成本与网点客户服务水平之间均衡点的前提。其次,在企业配送网络GIS支持下,以广义工作量均衡和车辆容载量为目标值,对所有配送网点进行配送线路的划分,把一个包含几千个配送网点的难点问题,转化为有限个实际可控、可观测的子系统进行求解。本文采用最邻近算法求得物流配送中心送货线路划分的初始解,然后采用插入算法对线路划分初始解进行改进,在GIS平台上的仿真结果表明了改进后线路划分方案的合理性。为了使划分结果进一步符合物流企业的实际应用,本文在常规最邻近算法的基础上,提出了二阶最邻近算法的内涵,证明了该算法每次选择下一个新网点时,其与当前线路上已有的两个次新网点所组成的网点子集都是聚集程度最高的,由此得到的配送线路中的客户网点聚集程度,要高于常规一阶最邻近算法所得到的线路,这为下一阶段的单车线路优化提供了较好的基础。本文在配送线路划分的基础上,在GIS平台上进行了单车配送线路的优化调度,即综合考虑单车线路每次送货的网点数量、订货数量、道路拥挤度等因素的变化,求解出每日每次每条送货车辆的行驶路线安排,实现物流配送中心送货车辆的每日每次动态电子排单的可视化输出。论文在对国内外单车线路优化问题大量调研的基础上,提出了自己独特的、适合国内物流配送中心末端配送的单车线路求解方案:先用最节约插值法构建问题的初始可行解,生成初始解路径集合;然后采用混合遗传算法的全局搜索策略优化最节约插值法得到的初始解,进而得到一个相对满意的解。由于传统遗传算法全局搜索能力很强但局部搜索能力不足,爬山算法则具有很强的局部搜索能力,是一种常用的寻找局部最优解的方法,本文将二者相结合,以期取长补短,实践应用表明这种策略可大大提高配送线路的优化性能。为了使每日每次单车配送线路更加符合实际电子排单和道路交通状况,本文以杭州市某段景区为例,从城市交通网络中道路路段间的地理关联关系入手,在最短路径算法(Dijkstra)基础上,考虑道路畅通度系数,探讨不同配送时间段道路畅通度随机因素对单车线路配送效能的影响,分析结果使送货经济距离数据库的建立和应用更加符合配送线路的实际运营状况。上述研究以杭州市区卷烟配送网络为数据获取源和应用案例,分别建立物流配送中心配送线路划分和单车线路优化两个阶段的系统模型,采用多种算法(或其混合)进行求解。由于大规模配送网络车辆路线问题是一个典型的NP难点,随着网点数量的增加,系统计算的复杂度无论在空间上还是在时间上都将成指数级增长,这对于规模较大的即时配送调度问题的优化计算是难以接受的。据我们调研,物流配送企业对网点客户订单的有效反应要求很高,节拍很短,有时甚至不允许电脑计算时间过长,因此有必要进行本课题的系统建模与算法研究,解决物流配送中心末端配送的复杂配送网络求解时间过长、计算工作量过高的现实问题。本文采用MapInfo、VB、SQL Server 2000等开发技术将上述模型与算法集成到企业配送网络GIS环境下,完成物流配送中心末端配送系统的设计与实现。通过与GIS系统的集成,将线路划分结果与单车线路电子排单结果,直观地输出在电子地图上,从而实现物流配送中心末端配送车辆路线问题的可视化输出控制。研究成果在烟草、百货、医药、油料等企业的物流配送中心末端集中配送领域,具有普适性和推广应用前景。本文研究内容的创新性主要体现在以下几个方面:(1)在定义物流配送中心送货线路“广义工作量”和“送货经济距离”概念的基础上,根据不同配送线路工作量均衡和送货经济距离最短的多目标决策问题求解期望,采用改进后的二阶最邻近算法和插入法进行送货线路划分,从而兼顾了配送成本降低与客户满意度提高两者之间的“二律背反”关系;(2)单车线路优化应用了标准遗传算法与爬山算法相结合的混合遗传算法,在其中的同化操作中,首次提出并应用能综合体现单车线路网点数N、送货量D和总经济距离S三个指标的个体适应度函数,作为判断单车线路同化操作优劣的尺度标准;(3)根据道路拥挤度的随机变化,确定单车配送线路任意两个网点间不同时间段的送货经济距离,及时调整配送计划和配送路线,采用概率模型替代传统确定性模型;(4)研究成果已应用于杭烟物流配送中心配送网络,取得了明显的应用效果,弥补了国内车辆线路问题研究大多停留在理论层次的不足。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 基于工作量均衡理论企业送货车辆路线问题的提出
• 1.1.1 物流配送企业末端配送面临的问题
• 1.1.2 基于工作量均衡理论的物流配送中心末端配送车辆路线问题
• 1.1.3 车辆路线问题的遍历性
• 1.2 物流配送中心末端配送VRP 的研究现状
• 1.2.1 国外末端配送VRP 研究
• 1.2.2 国内末端配送VRP 研究
• 1.3 本文的主要研究工作
• 1.4 论文的结构
• 第二章 物流配送中心末端配送线路优化问题一般描述
• 2.1 末端配送VRP 问题的计算复杂度
• 2.1.1 基本VRP 问题的描述
• 2.1.2 末端配送VRP 问题的分类
• 2.1.3 VRP 问题的计算复杂度
• 2.2 末端配送VRP 问题的求解策略
• 2.2.1 精确算法
• 2.2.2 启发式算法
• 2.3 大规模末端配送VRP 问题的启发式算法
• 2.3.1 启发式初始解法
• 2.3.2 传统交换改善法
• 2.3.3 现代优化算法
• 2.4 几种VRP 算法的的分析对比
• 2.5 物流配送中心送货线路实际应用算法描述
• 第三章 基于工作量均衡的配送线路划分系统模型与算法
• 3.1 广义工作量的提出
• 3.1.1 广义工作量的定义
• 3.1.2 工作量均衡的定义
• 3.1.3 企业真实送货过程跟踪分析
• 3.1.4 权值的确定与调整
• 3.2 网点间的送货经济距离
• 3.2.1 送货经济距离概念的提出
• 3.2.2 两点间送货经济距离的求解
• 3.3 配送线路划分系统模型建立
• 3.3.1 线路划分的基本原则
• 3.3.2 线路划分系统的运行前提
• 3.3.3 线路划分系统的模型建立
• 3.4 线路划分系统的求解算法研究
• 3.4.1 一阶邻近算法与二阶邻近算法
• 3.4.2 插入算法对划分初始解的改进
• 第四章 基于真实街道单车线路优化问题的模型与算法
• 4.1 单车线路优化问题动态网络模型
• 4.2 最节约插值法
• 4.3 混合遗传算法
• 4.3.1 基本遗传算法
• 4.3.2 爬山算法
• 4.3.3 混合遗传算法
• 4.4 最节约插值法与混合遗传算法的结合
• 4.5 考虑道路畅通度的单车线路优化随机模型与算法
• 4.5.1 路网流量分析
• 4.5.2 考虑道路畅通度的最佳路径算法
• 第五章 基于GIS 平台的系统设计与实现
• 5.1 系统基础设计
• 5.1.1 GIS 与MapInfo 技术应用
• 5.1.2 道路网络拓扑结构设计
• 5.2 系统集成结构设计
• 5.2.1 系统集成设计
• 5.2.2 系统主要工作流程
• 5.3 系统总体设计
• 5.3.1 系统功能设计
• 5.3.2 数据库设计
• 5.3.3 系统基本输出设计
• 第六章 应用案例分析与电子排单系统可视化输出
• 6.1 杭烟配送网络车辆线路优化问题
• 6.1.1 问题描述
• 6.1.2 杭烟配送主要流程分析
• 6.1.3 杭烟末端配送课题的求解思路
• 6.2 电子排单系统的可视化输出
• 6.2.1 主界面输出
• 6.2.2 线路划分结果输出
• 6.2.3 单车线路优化结果输出
• 6.3 计算机仿真结果分析
• 6.3.1 线路划分仿真结果分析
• 6.3.2 单车线路优化仿真结果分析
• 6.3.3 考虑道路畅通度因素的单车线路优化仿真结果分析
• 第七章 研究结论与展望
• 7.1 主要研究结论
• 7.2 主要关键性问题
• 7.3 主要技术理论创新
• 7.4 研究展望
• 附录F.1 求解送货经济距离Dijkstra 算法源代码
• 附录F.2 杭烟物流配送中心末端配送实验数据仿真流程
• 参考文献
• 致谢
• 攻读博士学位期间发表的科研成果
• 一、论文著作
• 二、课题项目
• 三、获奖