随机分批配送车辆路径问题研究

《随机分批配送车辆路径问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、国内图书分类号：F253.4密级：公开国际图书分类号：U658西南交通大学研究生学位论文随机分批配送车辆路径问题研究年级二零一一级姓名石建力申请学位级别工学博士专业物流工程指导老师张锦教授二零一八年五月十五日ClassifiedIndex:F253.4U.D.C:U658SouthwestJiaotongUniversityDoctorDegreeDissertationRESEARCHONSTOCHASTICVEHICLEROUTINGPROBLEMWITHSPLITDELIVERYGrade:2011Candidate:ShiJianl

2、iAcademicDegreeAppliedfor:PH.D.Speciality:LogisticsEngineeringSupervisor:ZhangJinMay.15,2018西南交通大学博士学位论文创新性声明本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本节的研究做出贡献的个人和集体，均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。本学位论文的主要创新点如下：1.对两种不同的需求点随机分批配送车辆

3、路径问题进行研究。首先对需求点需求随机出现的分批配送车辆路径问题(thesplitdeliveryvechicleroutingproblemwithstochasticcustomers，SDVRPSC)，建立带修正的随机规划模型(见2.2.1节)，将需求点是否出现的组合向量引入模型，使用跳过不出现需求的需求点的策略进行修正。根据分批配送问题特点，设计改进的自适应大邻域搜索算法(adaptivelargeneighborhoodserach，ALNS)进行求解，对分批插入算子进行改进，使得单个需求点的配送服务不局限在两辆车之间，而是根据需

4、要确定分批次数(见2.2.2节)。通过算例测试验证模型和算法的可行性和有效性，分析随机需求点所占比例对分批配送的影响和分批配送对问题解的影响(见2.2.3节)。其次，对需求点位置随机的分批配送车辆路径问题(thesplitdeliveryvehicleroutingproblemwithstochasticcustomers’location，SDVRPSCL)进行研究，建立多目标随机规划模型(见2.3.1节)，设计改进的局部迭代搜索算法(iteratedlocalsearchheuristic，ILS)将多目标转化为单目标进行求解，对初始

5、解生成算法和局部搜索算法进行改进以适应分批配送(见2.3.2节)；并通过算例测试说明算法有效性，分析分批配送的影响(见2.3.3节)。2.对需求量随机的分批配送车辆路径问题(thesplitdeliveryvechicleroutingproblemwithstochasticdemands，SDVRPSD)分别建立不同的模型进行研究。首先，建立带修正的随机规划模型(见3.2.1节)，结合分批配送特点，设计改进的粒子群算法(theparticleswarmoptimization，PSO)进行求解，由于分批配送时编码中存在多次出现的需求点，

6、对PSO中编码、解码、最短路径分隔算法、速度更新、位置更新和局部搜索等模块进行改进(见3.2.2节)；通过算例测试验证算法的有效性，与现有结果进行对比分析(见3.2.3节)。其次，建立双层马尔可夫决策过程(MarkovDecisionProcess，MDP)模型(见3.3.1节)，设计基于近似动态规划(theapproximatedynamicprogramming，ADP)西南交通大学博士研究生学位论文第I页摘要配送问题是物流学科的核心科学问题之一，是物流管理和服务的关键问题。随着市场竞争加剧、经济增长放缓，配送业务量和配送利润均呈现下降

7、趋势，促使配送企业引进先进的车辆调度和配送管理的新技术，以提高企业运营效率，提高客户满意度，增强企业竞争力。分批配送车辆路径问题(thesplitdeliveryvehicleroutingproblem，SDVRP)是近十多年来逐步受到关注的研究领域，通过对需求点需求量进行拆分能有效降低车辆使用量，降低行驶费用，提高配送效率。在实际配送中，需求点位置、需求量、行驶时间和服务时间等信息均不是确定不变的。随着计算机技术和信息技术的发展，研究随机车辆路径问题的成果越来越多。但目前对随机SDVRP的研究较少，有待进一步完善和改进，分别对需求点随机

8、、需求量随机和时间随机的SDVRP进行研究。首先，对两种不同的需求点随机的SDVRP进行研究：需求点需求随机出现和需求点位置随机。对需求点需求随机出现的情形，将需求点出现概率引入