A Novel Decoder Based on Parallel Genetic Algorithms for Linear Block Codes

Genetic algorithms offer very good performances for solving large optimization problems, especially in the domain of error-correcting codes. However, they have a major drawback related to the time complexity and memory occupation when running on a uniprocessor computer. This paper proposes a parallel decoder for linear block codes, using parallel genetic algorithms (PGA). The good performance and time complexity are confirmed by theoretical study and by simulations on BCH(63,30,14) codes over both AWGN and flat Rayleigh fading channels. The simulation results show that the coding gain between parallel and single genetic algorithm is about 0.7 dB at BER = 10﹣5 with only 4 processors.

The schema deceptiveness and deceptive problems of genetic algorithms

Genetic algorithms (GA) are a new type of global optimization methodology based on na-ture selection and heredity, and its power comes from the evolution process of the population of feasi-ble solutions by using simple genetic operators. The past two decades saw a lot of successful industrial cases of GA application, and also revealed the urgency of practical theoretic guidance. This paper sets focus on the evolution dynamics of GA based on schema theorem and building block hypothesis (Schema Theory), which we thought would form the basis of profound theory of GA. The deceptive-ness of GA in solving multi-modal optimization problems encoded on {0,1} was probed in detail. First, a series of new concepts are defined mathematically as the schemata containment, schemata compe-tence. Then, we defined the schema deceptiveness and GA deceptive problems based on primary schemata competence, including fully deceptive problem, consistently deceptive problem, chronically deceptive problem, and fundamentally deceptive problem. Meanwhile, some novel propositions are formed on the basis of primary schemata competence. Finally, we use the trap function, a kind of bit unitation function, and a NiH function (needle-in-a-haystack) newly designed by the authors, to dis-play the affections of schema deceptiveness on the searching behavior of GA.

Development of an Efficient Genetic Algorithm for the Time Dependent Vehicle Routing Problem with Time Windows

This research considers the time-dependent vehicle routing problem (TDVRP). The time-dependent VRP does not assume constant speeds of the vehicles. The speeds of the vehicles vary during the various times of the day, based on the traffic conditions. During the periods of peak traffic hours, the vehicles travel at low speeds and during non-peak hours, the vehicles travel at higher speeds. A survey by TCI and IIM-C (2014) found that stoppage delay as percentage of journey time varied between five percent and 25 percent, and was very much dependent on the characteristics of routes. Costs of delay were also estimated and found not to affect margins by significant amounts. This study aims to overcome such problems arising out of traffic congestions that lead to unnecessary delays and hence, loss in customers and thereby valuable revenues to a company. This study suggests alternative routes to minimize travel times and travel distance, assuming a congestion in traffic situation. In this study, an efficient GA-based algorithm has been developed for the TDVRP, to minimize the total distance travelled, minimize the total number of vehicles utilized and also suggest alternative routes for congestion avoidance. This study will help to overcome and minimize the negative effects due to heavy traffic congestions and delays in customer service. The proposed algorithm has been shown to be superior to another existing algorithm in terms of the total distance travelled and also the number of vehicles utilized. Also the performance of the proposed algorithm is as good as the mathematical model for small size problems.

Vehicle routing optimization algorithm based on time windows and dynamic demand

To provide the supplier with the minimizum vehicle travel distance in the distribution process of goods in three situations of new customer demand,customer cancellation service,and change of customer delivery address,based on the ideas of pre-optimization and real-time optimization,a two-stage planning model of dynamic demand based vehicle routing problem with time windows was established.At the pre-optimization stage,an improved genetic algorithm was used to obtain the pre-optimized distribution route,a large-scale neighborhood search method was integrated into the mutation operation to improve the local optimization performance of the genetic algorithm,and a variety of operators were introduced to expand the search space of neighborhood solutions;At the real-time optimization stage,a periodic optimization strategy was adopted to transform a complex dynamic problem into several static problems,and four neighborhood search operators were used to quickly adjust the route.Two different scale examples were designed for experiments.It is proved that the algorithm can plan the better route,and adjust the distribution route in time under the real-time constraints.Therefore,the proposed algorithm can provide theoretical guidance for suppliers to solve the dynamic demand based vehicle routing problem.

A novel genetic algorithm for vehicle routing problem with time windows

A novel genetic algorithm with multiple species in dynamic region is proposed,each of which occupies a dynamic region determined by the weight vector of a fuzzy adaptive Hamming neural network. Through learning and classification of genetic individuals in the evolutionary procedure,the neural network distributes multiple species into different regions of the search space. Furthermore,the neural network dynamically expands each search region or establishes new region for good offspring individuals to continuously keep the diversification of the genetic population. As a result,the premature problem inherent in genetic algorithm is alleviated and better tradeoff between the ability of exploration and exploitation can be obtained. The experimental results on the vehicle routing problem with time windows also show the good performance of the proposed genetic algorithm.

Improved ant colony optimization for multi-depot heterogeneous vehicle routing problem with soft time windows

Considering that the vehicle routing problem （VRP） with many extended features is widely used in actual life, such as multi-depot, heterogeneous types of vehicles, customer service priority and time windows etc., a mathematical model for multi-depot heterogeneous vehicle routing problem with soft time windows （MDHVRPSTW） is established. An improved ant colony optimization （IACO） is proposed for solving this model. First, MDHVRPSTW is transferred into different groups according to the nearest principle, and then the initial route is constructed by the scanning algorithm （SA）. Secondly, genetic operators are introduced, and crossover probability and mutation probability are adaptively adjusted in order to improve the global search ability of the algorithm. Moreover, the smooth mechanism is used to improve the performance of the ant colony optimization （ACO）. Finally, the 3-opt strategy is used to improve the local search ability. The proposed IACO was tested on three new instances that were generated randomly. The experimental results show that IACO is superior to the other three existing algorithms in terms of convergence speed and solution quality. Thus, the proposed method is effective and feasible, and the proposed model is meaningful.

An Alternative Algorithm for Vehicle Routing Problem with Time Windows for Daily Deliveries

This study attempts to solve vehicle routing problem with time window (VRPTW). The study first identifies the real problems and suggests some recommendations on the issues. The technique used in this study is Genetic Algorithm (GA) and initialization applied is random population method. The objective of the study is to assign a number of vehicles to routes that connect customers and depot such that the overall distance travelled is minimized and the delivery operations are completed within the time windows requested by the customers. The analysis reveals that the problems experienced in vehicle routing with time window can be solved by GA and retrieved for optimal solutions. After a thorough study on VRPTW, it is highly recommended that a company should implement the optimal routes derived from the study to increase the efficiency and accuracy of delivery with time insertion.

A Hybrid Genetic Algorithm for Vehicle Routing Problem with Complex Constraints

Most research on the Vehicle Routing Problem （VRP） is focused on standard conditions, which is not suitable for specific cases. A Hybrid Genetic Algorithm is proposed to solve a Vehicle Routing Problem （VRP） with complex side constraints. A novel coding method is designed especially for side constraints. A greedy algorithm combined with a random algorithm is introduced to enable the diversity of the initial population, as well as a local optimization algorithm employed to improve the searching efficiency. In order to evaluate the performance, this mechanism has been implemented in an oil distribution center, the experimental and executing results show that the near global optimal solution can be easily and quickly obtained by this method, and the solution is definitely satisfactory in the VRP application.

家电送装一体/送装分离混合模式下的车辆路径问题

结合送装分离模式的灵活性和配送效率,研究家电送装一体和送装分离模式相结合的车辆路径问题,以寻求兼顾客户服务体验和整体送装效率的最优送装路径方案。基于混合整数线性规划方法建立了以送装总成本最小化为目标、带软时间窗的家电送装路径优化模型,并根据模型特点针对性设计了改进的遗传算法进行求解,通过算例验证了所提模型和算法的有效性。最后,结合实例比较了上述混合送装模式相对于送装一体和送装分离模式的优化方案绩效,以期为家电送装路径优化提供辅助决策支持。

考虑模糊质检时间的柔性作业车间动态调度问题

为解决更符合现实情形的模糊质检时间柔性作业车间动态调度问题,以最小化完工时间为目标,立足紧急插单、机器在空载运行时发生故障和机器在加工工件时发生故障的三种故障情形,建立了带模糊质检时间的机器故障、紧急插单重调度模型。设计了基于元胞自动机邻域搜索和随机重启爬坡算法的改进遗传算法求解模型,即针对车间调度问题中存在的订单排序和机器选择双决策问题特征,设计包含工序码和机器码的双层编码方案,并基于遗传算法思想对工序码和机器码设计相应的交叉、变异等遗传操作。同时,将遗传操作应用于基于元胞自动机的邻域搜索算法框架中以增强算法全局搜索能力,整合基于关键工序的随机重启爬坡算法以提高算法局部开发能力。实验选取10个柔性车间调度算例验证了所提算法的有效性,同时,测试1个模糊质检时间柔性车间调度算例验证了模型的有效性。另外,实验也测试了不同故障场景,得出该动态调度方法优于实际场景中常使用的“工件后移”调度策略。

多中心半开放式同时送取货的车辆路径问题研究

研究了带软时间窗约束的多配送中心半开放式同时送取货的车辆路径问题,所有客户点均存在送取两种需求,并采用同一辆车同时提供送取服务.车辆服务完路线上所有客户点后,不一定返回起始配送中心,可就近返回任意配送中心.在此条件下,构建了以车辆运输成本、车辆租赁成本、时间窗惩罚成本等总和最小为目标的优化模型.根据问题特征,设计了自适应精英遗传算法对该问题进行求解,引入自适应机制,根据个体的适应度动态地调节交叉和变异概率,采用精英保留策略将优秀个体进行遗传保留,不仅增强了算法的全局优化能力,还均衡了算法的局部搜索能力.通过案例仿真,验证了模型和算法的可行性和有效性.研究成果丰富了车辆路径问题的相关研究,为物流企业提供了一种决策参考.

动态环境下基于换电模式的电动车路径问题研究

在实际配送中,考虑车速受不同天气、不同时段的影响,根据电动车辆行驶速度与能耗之间的函数关系,以电动车固定行驶成本、能耗成本、时间惩罚成本构成的总运输费用最小为目标,以车辆载重、车辆电池容量、客户时间窗、车辆速度为约束条件,构建动态环境下基于换电模式和时变速度的电动汽车路径优化模型。用遗传算法对模型求解,采用实数编码、轮盘赌选择算子、随机单点交叉、随机变异的方式,并以小变异率提高局部搜索能力,然后与车辆速度恒定时的几种情况进行对比。试验结果表明,所建立的优化模型更符合实际情况,能够根据客户属性和动态环境下的路网特性,合理安排发车、规划配送路径和顺序,从而降低配送成本,为物流企业运营车辆和优化配送提供参考。

有禁飞区的时间依赖型车辆与无人机协同配送路径优化

本文针对有禁飞区的时间依赖型车辆与无人机协同配送路径问题,综合考虑分时段禁飞的无人机禁飞区域、车辆行驶速度连续变化、车辆及无人机能耗等因素,以车辆派遣成本、车辆能耗成本、无人机能耗成本之和最小为目标建立优化模型.根据问题特征,设计遗传变邻域搜索算法对其进行求解.针对遗传算法易早熟、局部搜索能力较差等缺陷,将变邻域搜索算法与其结合以增强算法的局部搜索能力,引入自适应邻域搜索次数以增强对种群的搜索深度,采用精英保留策略不断改进最优解.通过多组算例验证了算法的有效性,并分析了配送模式、禁飞区数量、车辆行驶速度变化对配送方案的影响,结果表明禁飞区及车辆速度等因素在很大程度上影响物流配送成本.研究成果不仅丰富了车辆与无人机协同配送的场景,拓展了VRP问题的研究,也为物流企业制定配送方案提供了依据.

基于GA-ALNS算法的带可容忍时间窗的VRP求解

针对带可容忍时间窗的车辆路径规划问题,建立最小化配送总成本的规划模型,结合遗传算法构造改进自适应大邻域搜索算法对该问题求解.利用遗传算法构建高质量解开始自适应大邻域搜索寻优,减小算法计算时间成本;加入3种破坏算子和3种修复算子,以增加种群多样性;嵌入模拟退火接受准则以一定概率接受较差解,自适应更新破坏和修复算子权重,避免算法陷入局部最优.选取Solomon标准测试集进行3组实验,与已知最优解比较距离成本验证算法可行性;在单边容忍度时间窗模型下,与基础ALNS算法对比验证算法改进效果;在双边可容忍时间窗模型下,与相关文献的最优结果对比.实验结果表明,提出的GA-ALNS算法改进效果较为显著,求得的最优解同其他算法相比优化率较好,计算得到的最优方案能实现更低的车辆配送总成本,具有一定的可行性和有效性.

转向限制网络下考虑订单平均配送时间的取送货路径优化

研究考虑城市通行限制的即时配送策略对减少订单平均配送时间,提高配送时间一致性及客户满意度具有重要意义。通过设置可转向节点构建转向限制性配送网络,以平均配送时间最小化为目标,在具有转向限制的配送网络下,建立考虑订单动态性的多车辆实时取送货路径优化模型,并基于滚动时域设计IGNORE和W&R(wait&return)两种延迟配送策略。在算例分析中,调整可转向节点个数及距离模拟密集型、稀疏型两种道路网络。通过数值仿真及遗传算法求解,验证了模型的稳定性及策略的适用性,得到了IGNORE和W&R策略分别在这两种网络及不同订单数量、配送员人数和滚动时域的时长下的平均配送时间,并分析了平均配送时间波动的原因。结果表明:IGNORE策略适用于网络小订单少的情形,且随着滚动时域时长缩短,订单平均配送时间减少;W&R策略适用于配送网络较大的情形,网络可转向节点数越多,订单平均配送时间减少。研究结论对即时配送平台优化配送策略和提升客户满意度有一定的参考意义。

考虑交通拥堵和有限制时段的冷链物流车辆路径问题

针对生鲜农产品冷链配送环节中存在的成本高、货损严重等问题,考虑到日益严重的交通拥堵,通过分析时变路网下的动态行驶速度和受温度影响的货物腐败情况,在配送车辆容量等限制条件下,构建了以配送总成本最低为目标的冷链物流路径优化模型。在此基础上,通过设计全天候和有限制时段的车辆通行模式进行比对分析,利用遗传算法进行求解。通过不同规模的企业案例进行分析,验证了模型与算法的有效性。计算结果表明:冷链企业采用有限制时段的车辆通行模式可以降低配送成本,提高货物到货质量。

基于客户软时间窗的社区团购配送路径优化

文中主要研究社区团购配送路径优化问题,针对社区团购车辆调度普遍存在的效率低、成本高、配送时间不确定等问题,以配送时间与总配送费用帕累托最优、顾客满意度最高为目标,构建基于客户软时间窗的社区团购配送车辆路径优化模型,将遗传算法进行改进后对模型求解。经过算例验证,发现通过遗传算法找到的路径能够有效地降低成本,使配送时间更有保障,提高顾客满意度,验证了算法的可行性和有效性。

时变环境下基于自适应遗传算法的模糊绿色车辆路径问题

针对时变环境下的模糊绿色车辆路径问题,同时考虑了车速连续时变、客户需求量为模糊变量等特性,在目标函数中引入与绿色低碳有关的燃油成本,以极小化燃油成本、车辆使用成本并极大化客户满意度为目标,建立了相应的模糊规划模型,并运用自适应遗传算法进行了求解。采用仿真实例,分析了决策者主观偏好值对各个目标函数的影响,以及各个目标函数之间的相互影响。

基于混合冗余策略的k-out-of-n:G系统可靠性优化模型

很多对可靠性要求极高的系统通常被设计成k-out-of-n:G结构,然而对该类系统的可靠性优化是一个相当困难的问题。为进一步扩展模型的适用性,提出一种采用混合冗余策略的可靠性优化新模型。该模型首次在k-out-of-n:G系统的可靠性优化中引入混合冗余策略,可以为每个子系统选择(积极、冷备份或混合)冗余策略中的任何一个。首先,基于连续时间马尔可夫链为k-out-of-n:G系统建立精确计算系统可靠性的数学模型。其次,提出一个冗余分配问题和一个工程案例问题,并设计一种伪并行遗传算法进行求解。最后,为评估新模型的性能,通过对提出的两个问题进行数值分析来评估新模型的性能。实验证明,相比以往模型研究,所提新模型得到更高的系统可靠性值,具有良好的应用前景。

舰载机模块化弹药调度方案优化设计

舰载机模块化弹药存储和调度是未来发展的主要趋势之一。模块化弹药调度与整弹调度相比,调度对象的数量成倍增加并且多了一个弹药装配环节,使调度工作的难度呈指数级增长。针对模块化弹药调度问题,建立以任务完成时间最小化和各舱室与升降机平均工作时间最小化为优化目标,以各模块调度次序、机器选择和调度起始时间为约束条件的舰载机模块化弹药调度模型,设计递推法计算任务完成时间,并使用改进的遗传算法对模型进行求解,结合模块化弹药特点优化多层编码方式,使染色体更加完整地表达弹药在各个阶段的信息。通过仿真验证,所提的舰载机模块化弹药调度方法生成的调度方案具有可行性。