逆向物流车辆路径问题(Rever Logitical Vehicle Routing Problem,RL_VRP)的研究,对减少逆向物流车辆运输成本,实现逆向物流系统的优化目标,有十分重要的价值。但是,目前该领域的大部分工作都集中在静态RL_VRP问题上,对动态RL_VRP的研究相对较少。同时由于VRP已经被证明是NP-hard问题,当问题规模较大时,很难得到问题的精确解。因此如何设计有效的启发式算法,在较短的计算时间内快速获得较好的解,成为RL_VRP现阶段研究的重点。 本文基于蚁群系统ACS,研究了一种动态路径网络的RL_VRP--时间依赖同时送取货车辆路径问题(Time Dependent Vehicle Routing Problem with Simultaneous Delivery and Pickup,TD-VRPSDP),建立了TD-VRPSDP的混合整数规划模型。 对于TD-VRPSDP的动态性,本文的研究思路是将动态问题静态处理。 首先,对静态的VRPSDP作了深入的研究,分析了VRPSDP的特点与复杂性。设计求解算法时,针对性地对ACS的启发信息做了适应性改进,采用含有载重启发的启发信息。同时为了弥补ACS局部搜索能力较差的不足,本文根据VRPSDP的特性改进了2-OPT局部搜索算法,将其嵌入到ACS的迭代过程中,得到了OPT_ACS算法。对20组VRPSDP基准算例的测试结果表明,OPT_ACS比ACS所用迭代次数更少,得到的结果更好。同时将OPT_ACS同其它四种求解VRPSDP的算法进行对比,OPT_ACS可以有效提高车辆的负载使用率,弱化因为负载波动和最大负载能力约束而导致的车辆总行程的增加趋势,使得算法在可接受的计算时间内收敛到满意解。验证了OPT_ACS的有效性。 其次,在第一部分静态VRPSDP研究的基础上,文章第二部分重点研究了TD-VRPSDP。详细描述了TD-VRPSDP问题,说明了研究这个问题的实际意义,给出问题的混合整数规划模型。在问题的求解上,采用时间分段法,将动态问题静态化来进行求解。在每个时间段内,分析了静态化的TD-VRPSDP特点,设计了含有时间因素的ACS启发信息。为了检验ACS求解TD-VRPSDP的有效性,本文根据VRP-TW和VRPSDP的基准算例,设计了8组舰模为50个客户TD-VRPSDP测试算例。实验结果表明,本文设计的ACS能够有效求解TD-VRPSDP。 在实验部分,本文首先进行了参数分析实验,确定了适用于ACS求解TD-VRPSDP的一组有效参数组合。其次,本文详细分析了实验中车辆旅行时路径信息的变化,验证了本文设计的ACS能够有效平衡车辆的送货载重和取货载重,在服务时间窗内准时到达客户节点,是一种适应性好,收敛性强,全局性优的算法。实验结果表明,本文设计的ACS能够有效求解TD-VRPSDP。