现代，企业为了提高竞争力，对供应链管理提出了更高的要求，如何高效率地完成从原材料采购，产品生产到产品配送，已成为各公司研究的重点。现代物流系统作为供应链的重要环节，主要包括运输、存储、包装、装卸和搬运等若干相互依赖、相互制约的子系统，其中物流配送是一个与消费者相连的重要环节。 本文主要研究了一类车辆优化调度问题――PDPTW问题（Pickup and Delivery Problem with Time Windows，带时间窗口的装卸货问题）及其扩展问题的优化调度算法。有时间窗口的装卸货问题（PDPTW）是一个典型的NP-hard问题，因此成为运筹学与组合优化领域的研究的难点与热点。 本文主要在两方面对PDPTW问题开展研究，首先，针对静态的PDPTW问题，相关文献中介绍的一些优化算法在计算时间和解的质量方面缺乏良好的平衡，如文献[15]提到的自适应方法，虽然能得到很好的解，但计算时间过长，难以满足实时性要求。本文通过合理平衡计算时间和解质量，提出了一种快速LNS（Large Neighborhood Search,大规模邻域搜索）算法，这种方法具有求解速度快、求解质量好、对初始解的依赖性小的特点。在保持快速求解的前提下，利用模拟退火在全局寻优中的优势，进一步提出了类模拟的快速LNS算法，改进了单一采用LNS算法的不足。其次，本文结合实际应用时车辆在行驶过程中可能损坏的情况研究了动态PDPTW问题，给出了求解策略。 本文的研究工作和成果如下： 1．分析了PDPTW问题的标准算例，对已有的相关算法进行了测试，理解其优缺点，为寻求和改进算法打下基础。 2．提出了改进的LNS算法，在保持解质量的情况下，缩短了求解过程。求解过程主要以减少车辆为目标，通过优先选出短路径中的客户和与之有较大相关性的客户，来调整邻域搜索方向，使之能快速收敛到一个较优的解上，然后加入随机扰动，充分利用LNS算法本身邻域空间较大的优势，寻找在其它空间内更优的解。 3．对比了采用上述改进LNS算法所得到的解与其他相关文献所得到的解的质量，分析了影响解质量的因素，提出了类模拟退火的LNS算法，该算法在保持了改进LNS算法快速性的前提下，利用模拟退火在全局寻优能力上的优点，进一步改进原有解的质量，对不同算例的仿真结果表明，该算法对提高随机分布算例的解的质量，具有极大的优势，并且减小了对于初始解的依赖性。 4．参考当前车辆调度领域文献中对动态车辆调度问题的研究，对动态PDPTW问题进行讨论，结合实际执行调度过程中车辆可能损坏的情况，给出解决此类问题的策略，在尽量不新增车辆（即使新增车辆，可能到达事故点取货后，仍然会延期交货）的前提下，依靠剩下的车辆来完成所有客户需求，问题的目标定义为最小化客户不满意度，其中客户不满意度包括延迟客户的总数目和所有客户的延迟时间和。 5．通过大量仿真测试，给出了静态PDPTW的问题算法解质量的分析，对比不同算法，不同初始解对问题求解的影响，并通过加入动态PDPTW的概念，分析各个算法的解结构对抗突发事件的鲁棒性。 本文的研究工作得到了上海市科技发展基金的支持。
展开▼
