副题名

外文题名

论文作者

樊建华着

导师

王秀峰指导

学科专业

控制理论与控制工程

学位级别

博士论文

学位授予单位

南开大学

学位授予时间

2006

关键字

物资企业 物流 车辆 运输调度 最最佳化算法

馆藏号

F253.4

馆藏目录

2009\F253.4\12

因此研究车辆路径问题的实用、有效的最佳化方法，对于促进物流配送、智慧型交通、运输调度等领域的发展具有重要的理论意义和实际意义，将会获得巨大的社会效益和经济效益。本文在全面、系统研究车辆路径问题的基础上，主要针对实际需求，研究了目前最常见、物流发展迫切需要解决的几种车辆路径问题，给出了相应的求解方法。 本文首先对车辆路径问题的提法、基本概念、研究的发展和现状进行了系统、详细的介绍。然后，主要对以下四种问题进行了深入研究：1．研究了随机需求的多车辆路径问题(MVRPSD)，给出了求解路径长度受限的MVRPSD问题的两种实际可行的求解算法，在路逕行驶费用的计算中引入了“预先”装载方式，避免了现行算法中因车上货物量不足而造成的对顾客重複送货、从而造成行驶费用增加的问题，并使算法的运行时间在可接受的範围内。仿真实验表明本文提出的预最佳化算法和重最佳化算法与其它同类算法相比，不仅克服了上述缺点、更符合当前的实际需求，而且求解效率也明显提高。2．根据实际需求，对传统的脚踏车场带回程车辆路径问题进行了扩展，提出并研究了具有约束的、带回程的多车场路径最佳化问题(MDVRPB)，给出了一套完整的最佳化求解方法和根据问题特徵改进方法的实施策略。该方法给出的结果不仅可以极大的节约行驶费用，而且极大地提高了运算效率。仿真实验表明，在多车场、多车辆路径问题中，引入车辆的回程运输可以极大的节约行驶费用，也证明了本文算法的有效性。3．研究了同时取送货的车辆路径问题(VRPSPD)，提出了同时取送货的车辆路径最佳化问题的算法。根据车辆的剩余容量和顾客的净装载量对于路径构造的影响，建立了一种直观的VRPSPD问题的数学模型，提出了一种基于净装载量的插入準则。插入準则充分考虑了顾客的净装载量和车辆的剩余空间，能够使车辆路径构造有更大的自由度，方便后续顾客插入到路径中。因此，与其它插入準则相比，该方法得到的行车路径可大大缩短。4．根据现代物流的特点，研究了有时间窗的取货送货一体化问题(PDPTW)，分析了车辆在每个顾客处的等待时间、车辆的到达时间、开始服务时间和时间窗对车辆路径的影响，提出了一种并行、同时插入算法，当每个运输需求插入路径时，该算法同时考虑送货位置和取货位置的插入情况，与目前广泛採用的单独插入算法相比，不仅能更好地满足顾客需求，而且在缩短车辆的行驶距离和减少等待时间方面都有显着的效果，有明显的经济效益。