动态车辆路径问题的算法设计与系统实现

《动态车辆路径问题的算法设计与系统实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文动态车辆路径问题的算法设计与系统实现ALGORITHMDESIGNANDSYSTEMIMPLEMENTATIONFORDYNAMICVEHICLEROUTINGPROBLEM杨丹哈尔滨工业大学2015年12月国内图书分类号：TP399学校代码：10213国际图书分类号：621.3密级：公开工程硕士学位论文动态车辆路径问题的算法设计与系统实现硕士研究生：杨丹导师：黄荷姣教授申请学位：工程硕士学科：计算机技术所在单位：深圳研究生院答辩日期：2015年12月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP399U.D.C:621.3Dissertationf

2、ortheMaster’sDegreeofEngineeringALGORITHMDESIGNANDSYSTEMIMPLEMENTATIONFORDYNAMICVEHICLEROUTINGPROBLEMCandidate：DanYangSupervisor：Prof.HejiaoHuangAcademicDegreeAppliedfor：Master’sDegreeofEngineeringSpecialty：ComputerTechnologyAffiliation：ShenzhenGraduateSchoolDateofDefense：December,2015Degree-

3、Conferring-Institution：HarbinInstituteofTechnology哈尔滨工业大学工程硕士学位论文摘要车辆路径问题是为一系列结点规划最优访问路径的组合优化问题，其广泛应用于物流配送等领域。随着科技的发展和人们生活水平的提高，现实生活中的物流配送要求其能够接收并处理动态出现的新顾客，且配送司机有固定的工作时间区间。因此，研究动态的、带时间期限的车辆路径问题成为现实需要。针对当前物流配送的实际情况，本课题研究了带时间期限的动态车辆路径问题，并设计了始发结点的选取策略和一种混合大邻域搜索算法。该算法引入周期性优化策略将工作时间区间划分成多个等长的时间片，

4、在每个时间片末采用一种基于邻域分析的插入算法处理新顾客。同时，选取有效的始发结点组成当前的静态子问题，对其建立以车辆行驶总路程为优化目标的数学模型并采用一种基于三个remove策略和随机贪婪re-insert策略的大邻域搜索算法进行优化。本课题对22组包含顾客数为50-385的数据集分别进行了静态实验和动态模拟实验。在10次静态实验中，算法求得所有数据集的目标值相比于当前已知最优解的平均相对误差为3.11%，超过80%的数据集其目标值的相对误差低于5%，通过结合顾客的位置分布分析得出本算法在求解聚集分布的顾客方面有较好的表现；在5次动态实验中，本算法求得的最优结果、平均结果和方差

5、分别与遗传算法GA求得的最优解、平均解和方差相比，其中有13个数据集的最优解优于GA，10个数据集的平均解优于GA，11个数据集的方差低于GA，综合对比22组结果的最优值、平均值和方差之和，可以得出本课题设计的算法在求得最优值方面和算法的稳定性方面具有有效的竞争力。本课题还设计了一个基于混合大邻域搜索算法的物流配送系统。该系统结合WebGIS技术、百度地图API、JavaScript、PHP和Java等分别实现了PC客户端和安卓客户端的功能。其中PC端主要用于收集顾客信息、接收反馈消息、规划配送路径并在百度地图上显示；安卓端主要用于向配送司机提供相应的配送方案和反馈操作。关键词：

6、动态车辆路径问题；时间期限；大邻域搜索；插入算法I哈尔滨工业大学工程硕士学位论文AbstractVehicleroutingproblemisacombinatorialoptimizationproblemoforganizingappropriateroutesforaseriesofnodes,anditiswidelyusedinlogisticsareas.Withthedevelopmentoftechnologyandtheimprovementofpeople'slivingstandard,thelogisticsdistributioninreallifere

7、quiresthatitcanreceiveanddealwiththenewcustomers,andthedeliverydrivershavefixedworkingtimeinterval.Therefore,thestudyofthedynamicvehicleroutingproblemwithtimedeadlineisarealneed.Fortheactualsituationofcurrentlogisticsdistribution,thissubjects