奖金收集车辆调度问题的研究

作     者：陈莹 

作者单位：沈阳航空航天大学 

学位级别：硕士

导师姓名：李琳

授予年度：2020年

学科分类：12[管理学] 02[经济学] 0202[经济学-应用经济学] 1202[管理学-工商管理] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 020205[经济学-产业经济学] 08[工学] 082303[工学-交通运输规划与管理] 082302[工学-交通信息工程及控制] 0823[工学-交通运输工程] 

主      题：奖金收集车辆路径问题 自适应大邻域搜索算法 动态需求 动态行驶时间 时间依赖 

摘      要：随着国家“一带一路政策的实施,在互联网的推动下,电子商务的快速发展使得物流业在全球范围内得到迅猛发展。电子商务环境下的订货种类具有小批量、多批次、多样性的特点,这使得物流配送问题变得越来越复杂,配送难度不断增大。目前,在国内约有一千多家快递公司开展相关业务,竞争尤为激烈。因此,越来越多的企业开始关注如何通过合理规划配送线路来控制企业成本。配送线路的确定可以归结为车辆路径问题（Vehicle Routing Problem,VRP）来研究。本文考虑到实际生活中配送条件等限制,将电子商务环境下的配送问题归结为奖金收集车辆路径问题（Prize Collecting Vehicle Routing Problem,PCVRP）来研究,并从以下两个方面对PCVRP进行讨论:（1）静态PCVRP问题:在现有PCVRP问题模型的基础上,加入软时间窗约束并在送货需求的基础上增加了取货需求,建立了带软时间窗同时取送货的奖金收集车辆路径问题的数学模型。在求解该模型的算法中混合了模拟退火算法和大邻域搜索算法,并在搜索过程中引入了自适应机制。提出了一种基于自适应大邻域搜索算法的启发式算法。通过3组仿真实验验证了算法的有效性。（2）动态PCVRP问题:在静态PCVRP问题的模型上分别建立了动态需求和动态行驶时间的PCVRP模型。在两种动态PCVRP问题模型的求解过程中,将算法分为两个阶段:第一个阶段将动态PCVRP问题转化为静态PCVRP问题,使用自适应大邻域算法求解;第二阶段分别提出了局部搜索算法和2-opt算法进行求解。仿真实验结果表明局部搜索算法和2-opt算法都是可行且有效的。