【作者】 李剑；

【导师】 王乘；

【作者基本信息】 华中科技大学 ， 系统分析与集成， 2008， 博士

【摘要】 物流被称为企业的“第三利润源泉”。在“自然资源领域”和“人力资源领域”利润开拓越来越困难的情况下,物流领域的潜力被人们发现并受到重视。通过优化物流系统可以降低成本,从而增加企业利润及市场竞争力,因此通过优化算法对物流系统进行优化具有十分重要的意义和应用价值。微粒群算法(Particle Swarm Optimization,PSO)是一种拥有收敛速度快和简便易行优点的随机全局优化算法。论文对标准微粒群算法进行了深入的研究和分析,针对其缺陷提出了相应的改进方法,在此基础上采用遗传算法编码、交叉和变异的遗传微粒群算法求解物流系统中的库存优化和车辆路径优化问题,并分别设计了启发式算子提高遗传微粒群算法的性能,仿真试验的结果证实了算法的有效性和稳定性。对于微粒群算法改进的工作在于:(1)对于无约束优化问题,提出基于对个体评价的动态个体惯性权重调整策略,其中也包含对多种变异算子的研究。仿真结果显示,这种方法对于提高微粒群算法的性能有非常明显的帮助。(2)对于约束优化问题,通过仿真计算比较了多种变异算子的效果,在此基础上尝试了多变异算子串行融合,然后为了克服多变异算子相互间的干扰并减少计算量,提出了自适应的变异算子选取策略。最后,本文提出了将标准微粒群算法与遗传微粒群算法相融合的双重微粒群算法,仿真计算显示,这种算法在与两种微粒群算法计算量相当的情况下展现出明显高效的搜索效率和精度。对于物流系统优化的贡献在于:(1)采用遗传微粒群算法求解背包问题,采用1-2opt启发式算子融入遗传微粒群算法,仿真结果显示本算法要优于本文提到的标准微粒群算法和遗传算法。在此基础上,对一个典型货运中转业务建模,通过综合运用双重微粒群算法和求解背包问题的遗传微粒群算法求解,仿真结果验证了算法的有效性,并对于物流业务的实际运行有一定的参考价值。(2)提出采用混合遗传微粒群算法求解旅行商问题的框架结构。针对微粒群算法特有的三条染色体交叉的特性,设计改进的顺序交叉算子,它能够在交叉的同时保留优质解的信息;此外采用基于2-opt的变异算子显著的增强算法的收敛性能。通过以上改造,提出了求解旅行商问题的遗传微粒群算法结构,此结构相对于标准微粒群算法更加简单、直观、易于实现并且可扩展性好。仿真实验显示了此算法的可行性和有效性。(3)采用混合遗传微粒群算法对带车辆能力约束的车辆路径优化问题求解,其中采用了求解旅行商问题的交叉和变异算子,并采用了启发式算子处理其约束条件,仿真结果表示它具有精度高和速度快的优点。(4)采用两段式混合微粒群算法对于由多个仓库同时配送的多车场路径问题进行求解。第一阶段中采用分配规则将客户节点分配到各个仓库,将问题简化为多个单仓库的车辆路径优化子问题;第二阶段采用混合遗传微粒群算法对每个子问题进行求解,仿真结果验证算法的可行性。仿真结果显示算法不仅能在满足配送要求下优化配送线路减少行驶里程,还可以对公司货车的购置调度和仓库选址等提供决策支持。更多还原

【Abstract】 The logistics has been considered as the‘third source of the profit’. Sicne it is hard to increase profit with using the“natural resources”and the“human resources”now, the potential of the logistics gains more and more attentions. With the optimizations of the logistics enterprises can increase their profit and competitiveness by decreasing cost. Hence, it is significative to optimize logistics systems with optimization algorithms.The particle swarm optimization (PSO) is a stochastic optimization algorithm, it is easy to perform and can converge very fast. The dissertation studied and anlysised PSO deeply to improve performances. Based on which, a new approach was introduced, where the genetic particle swarm optimization (GPSO) was employed to address the inventory optimization problems and the Vehicle Routing Problem (VRP) instead of the traditional PSO. GPSO was derived from the original continuous particle swarm optimization and incorporated with the genetic reproduction mechanisms, namely crossover and mutation. The simulation results have shown that with heuristic algorithms, GPSO presented its effecitiveness and consistence.The achievements of the dissertation in PSO as follows:(1) An adaptive individual inertia weight strategy with mutation operators were proposed for high-dimensional optimization problems. The methods were proved to be effectiveness.(2) Kinds of mutation operators were incorporated to PSO. The results have shown no mutation operator could outperform others on all problems. Hence a multi-mutations operator was introdued, it was more consistent than single mutations, while performed worse on few problems. Based on which an adaptive mutation operator selection strategy was proposed, where the particles were divided in to groups with different probability to employ various mutation operators. The probabilities were adjust by comparision the evolutionary results between groups, the results have shown it outperformed the above mutation strategies. At last, a dual particle swarm optimization (Dual-PSO) was proposed, where the standard PSO and GPSO were incorporated, the simulation results have shown it outperformed both standard PSO and GPSO along with the genetic algorithm, the evolutionary strategy and the differential evolution. The achievements of the dissertation in logistics sytems as follows:(1) An approach for knapsack problem (KP) was proposed based on GPSO with a 1-2opt heuristic algorithm (GPSO-Opt) , the simulation results shows it outperformed the standard PSO and genetic algorithms introduced in the dissertation. A typical storage system was modeled and addressed with Dual-PSO and GPSO-Opt, simulation results have shown the effectiveness of the algorithms, and provided useful references.(2) The dissertation proposed a frame to solve traveling salesman problem (TSP) with GPSO. In the frame, a modified ordere crossover (MOX) was proposed to maintain information mainly from the high quality solutions during the crossover. A mutation operator based on 2-opt was introduced for local search. A two-stage crossover was proposed for the crossover among three chromosomes. Based on the above approach, a novel GPSO frame for TSP was propsed, which is simple, intuitionistic, flexible and easy to impletement. The simulation results have shown its feasibility and effectiveness.(3) A hybrid GPSO method was proposed to solve the capacitated vehicle routing problem (CVRP) , where MOX and 2-opt operator were employed along with a heuristic operator to deal with the constraints. The simulation results have shown its feasibility and effectiveness.(4) A two stage hybrid GPSO method was employed to solve the multi-depot vehicle routing problem (MDVRP). In the first stage the customers were assignmented to the depots and transformed the MDVRP to a set of CVRP problems; in the second stage the hybrid GPSO method was employed to solve the CVRP problems. The simulation results have shown the feasibility. Moreover, the results not only optimized the routings, but also provided supports for the decision-makings of truck purchase and depots placement.更多还原