带时间窗取送货问题的混合算法
【摘要】 为解决带时间窗的取送货问题，建立了集合划分模型，设计列生成算法与启发式规则相结合的CGA混合算法进行求解。首先，放松约束构建主问题及受限主问题，运用单纯形法与分支定界进行求解;其次，建立时空网络以构建子问题，基于修正的Dijkstra`s算法，设计包含算法A、B1、B2的求解算法;最后，通过启发式算法解决节点重复覆盖问题。为验证算法有效性，进一步构建了OPT近似最优解算法;并基于CGA提出三种求解策略C1、C2、C3，做单因素方差分析，采用算例分析算法的性能。实验结果表明，对于客户点数量小于30的小规模算例，CGA与OPT所得结果相近，但CGA求解效率更显著;针对客户点数量为600的大规模算例，CGA至多在20分钟内求得结果，可见本文算法的精度和效率较高。而针对不同类型及规模的
