车辆装载和路径安排联合优化问题研究

摘要

随着物流在社会中的地位越来越重要，物流系统的优化问题也成为了研究热点。车辆装载问题(Vehicle Filling Problem)和车辆路径规划问题(Vehicle RoutingProblem)属于物流运营管理中的优化问题，也是当前物流配送服务的两个核心问题，它们直接关系到整个物流系统的效率和效益，需从理论到应用全面研究。VFP和VRP两个过程之间的联系是非常紧密的，如VFP中的待装货物的装卸顺序是由VRP的结果直接决定的，而VRP的求解过程中又必须考虑对应VFP的装载过程中车辆的载重情况以及空间利用情况，所以应该将车辆货物装载问题(VFP)与车辆路径规划问题(VRP)统一考虑。
　　 本文将两个问题整合，通过找到VFP和VRP联合优化的切入点，建立了联合优化模型，并提出了一种适合于模型求解的交互式启发算法。在联合优化的VFP部分考虑了货物的易损性、装载的稳定性、物品不可倒置、车辆平衡性、先下后装等现实约束条件，这样不仅可以保证货物运输的安全性，同时避免了卸货时货物的翻倒而导致的卸货效率低下以及造成货损货差的情况，而且可以保证VRP的求解方案的可行性，即在车辆的装载过程中不会出现一条运输线路上所要经过的卸货点的货物不能全部装进车厢的情况。
　　 本文采用的交互式启发算法(CA)是装载启发式算法(MLH)和基于节约值蚁群算法(MCW-ACO)的有效结合，即在MCW-ACO搜索路径解空间的同时通过MLH判断装载的可行性，其中，MLH算法采用了剩余空间合并和多次搜索空隙规则，使每辆车的空间都得到了充分利用，提高了车辆的有效装载率；MCW-ACO在标准蚁群算法的基础上，引入了C-W算法，更改了线路转移规则和信息素更新规则，提高了搜索速度并改善了搜索结果。本文对提出的算法进行了Bench-mark数据测试，结果表明交互式联合优化算法不仅能够解决大规模的VFP&VRP问题，而且得到了令人满意的解。