论文部分内容阅读
目前,物流不仅成为了企业在生产领域之外的又一利润源泉,而且也是企业获得市场竞争力的核心力量。车辆优化调度问题是物流系统中一个重要环节,直接与消费者相连,其调度是否合理直接影响到企业的经济效益。现目前我国还是存在因缺乏完善的物流调度技术而造成运输分配和线路不合理,从而导致资源浪费和服务质量低下。因此,研究好车辆调度问题具有十分重要的现实意义。本文研究了几个很典型的车辆调度问题:基本车辆调度问题(Vehicl Routing Problem VRP)、带时间窗的车辆调度问题(Vehicle Routing Problem With Time Windows, VRPTW)和多配送中心车辆调度问题(Multi-Depots Vehicle Routing Problem with Time Windows, MDVRPTW)。三个问题呈现出简单到复杂的关系,都属于复杂的NP难题。对于求解这类问题,智能优化算法已成为主流求解算法,如遗传算法和粒子群算法。随着学者对这些算法的研究深入,发现这些基本算法存在缺陷和不足—遗传算法容易熟练早熟,粒子群算法不太适合求解离散组合优化这类问题等。对此很多学者对算法做了改进或融合,都取得了较好的效果,但是却增加了算法的复杂程度;或是对搜索过程中的解做操作来符合离散问题,但是在一定程度上偏离算法结构而得到的解不是太理想。对此,本文根据前人研究结果,以粒子群算法思想,采用遗传算法的操作手段来确定粒子的下一步运动的更新方式提出粒子碰撞的粒子群算法,来求解本文所研究的车辆调度问题。本论文开展工作如下:1、详细介绍车辆调度问题的研究意义和目的,对研究问题作了描述和定义,并对其进行分类。2、对车辆调度问题的求解算法作一个综述,重点介绍遗传算法和粒子群算法的算法原理和特点,并分析两种算法的异同。3、建立基本VRP问题的数学模型,分别设计和实现遗传算法和粒子群算法,在此基础上提出粒子碰撞的粒子群算法的算法原理,并给出相应的数学理论为支撑。用三种算法分别两种实例进行求解,对结果进行分析比对,结果证明该算法是求解本文研究问题的有效算法。4、建立VRPTW的数学模型,采用Solomon标准VRPTW的实例库作为求解实例,根据问题模型确立了新的初始群体产生方式,分别对C类、R类和RC类问题求解,分析结果。对于不平衡解的问题类,则引入平衡因子对问题加以调整。5、给出MDVRPTW的数学模型。分析了该问题求解思路—分步法和整体法的具体过程,分别设计和实现了两种不同方法对以MDVRPTW求解,从实验结果数据来看两种求解思路并没有优劣之分,说明两种方法的选择对问题求解的结果并没有太大的影响。最后对全文做一个总结,并且对下一步的研究工作进行了展望。