基于图着色模型的零担物流调度优化问题研究

发布时间：2020-08-27 10:45

【摘要】：零担物流调度优化问题一直以来都是众多物流企业重点关注的核心问题,其基本含义是通过零担运输的方式对现有的物流资源进行合理分配和使用,从而进一步达到缩减成本费用和获取规模经济效应的目的。一般来说,针对零担物流调度优化问题的研究工作主要集中在货物、车辆和人员等物流资源的调度决策领域,并且相关调度方案的制定需要结合具体的应用环境和客户需求来完成。在对零担物流调度优化的相关问题进行决策制定时,最为重要的一项内容是根据当前的优化目标和约束条件,合理而高效的解决物流资源使用时出现的冲突现象,从而为物流活动的各个参与者提供可靠的运营环境。与此同时,零担物流相比整车物流而言具备了许多全新的特征,相关调度问题的决策流程也更为复杂,因此有必要根据问题的实际应用环境,立足于新的研究视角对其进行重新描述和建模。本文选取了零担物流调度优化领域当中的货物装箱、路线规划和司机排班三类典型问题展开研究,并分别将其建模为不同形式的图着色问题进行表示和求解。本文的主要研究内容包括以下三个部分:(1)带冲突关系货物装箱问题的建模与求解。针对零担物流货物配装调度优化环节,对一类考虑货物间冲突关系约束的装箱问题展开研究,具体包含以下五部分内容:首先,结合零担物流配装业务进行需求分析,并根据研究工作的需要对与装箱问题相关的假设条件进行归纳总结;其次,根据需求分析结果,创建带冲突关系货物装箱问题的数学规划模型,并且在对模型复杂性进行深入探讨的基础之上,将其转换成为顶点着色模型进行表示;第三,针对上述问题模型,设计并实现基于贪心着色操作的两阶段启发式算法;第四,根据对偶转换的基本思想,设计并实现基于最大团计算操作的两阶段启发式算法;最后,通过算例数据计算结果的比较分析,验证了相应建模方法和求解算法的有效性。(2)多货栈取送货旅行商问题的建模与求解。针对零担物流货物配送调度优化环节,对一类考虑货物装卸顺序约束的集中配送路线规划问题展开研究,具体包含以下四部分内容:首先,结合零担物流集中配送业务进行需求分析,并根据研究工作的需要对与路线规划问题相关的假设条件进行归纳总结;其次,根据需求分析结果,创建多货栈取送货旅行商问题的数学规划模型,并且在对模型可行解特征进行深入研究的基础之上,将其转换成为排列图结构的形式进行表示,然后将模型可行解的判定过程转换成为相应排列图结构上的有界图着色问题;第三,针对上述问题模型,设计并实现了禁忌搜索算法对其进行求解;最后,通过算例数据计算结果的比较分析,验证了相关问题模型和禁忌搜索算法的有效性。(3)带时间延迟干扰的司机排班问题的建模与求解。针对零担物流人员调度优化环节,对一类存在运输任务时间延迟干扰影响的司机排班问题展开研究,具体包含以下四部分内容:首先,结合零担物流司机排班业务进行需求分析,并根据研究工作的需要对排班过程中可能出现的干扰事件及其对排班方案造成的影响进行归纳总结;其次,根据需求分析结果,将运输任务集合转换成为区间图结构的形式进行表示,并且将带时间延迟干扰的司机排班问题转换成为相应区间图上的鲁棒图着色问题进行建模;第三,针对上述问题描述,设计并实现了遗传算法对其进行求解;最后,通过算例数据计算结果的比较分析,验证了相关问题模型和遗传算法的有效性。
【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：F259.23

【参考文献】