改进的粒子群算法在VRP中的应用

将粒子群算法和禁忌搜索算法相结合构造禁忌搜索粒子群算法。提出一种对粒子群算法中全局最优解进行禁忌搜索的混合算法,扩展了粒子群算法进化方式。将其用于车辆路径优化问题求解。与基本粒子群算法相比较,结合禁忌搜索算法的粒子群算法明显提高了算法收敛速度和优化性能。     

一种多目标置换流水车间调度问题的优化算法

针对最大完工时间最小和总流经时间最小的多目标置换流水车间调度问题(permutation flow shopscheduling problem, PFSP), 提出一种粒子群优化算法与变邻域搜索算法结合的混合粒子群优化(hybrid particleswarm optimization algorithm, HPSO)算法, 并使算法在集中搜索和分散搜索之间达到合理的平衡. 在该混合算法中,采用NEH 启发式算法进行种群初始化, 以提高初始解质量;运用随机键表示法设计基于升序排列规则(ranked-order-value, ROV), 将连续PSO 算法应用于置换流水车间调度问题;引入外部档案集存贮Pareto 解, 并采用强支配关系和聚集距离相结合的混合策略保证解集的分布性;采用Sigma 法和基于聚集距离的轮盘赌法进行全局最优解的选择;提出变邻域搜索算法, 对外部集中的Pareto 解作进一步地局部搜索. 最后, 运用提出的混合算法求解Taillard 基准测试集, 并将测试结果与SPEA2 算法进行比较, 验证该调度算法的有效性.     

Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem

This paper presents a new hybrid algorithm that executes large neighbourhood search algorithm in combination with the solution construction mechanism of the ant colony optimization algorithm (LNS–ACO) for the capacitated vehicle routing problem (CVRP). The proposed hybrid LNS–ACO algorithm aims at enhancing the performance of the large neighbourhood search algorithm by providing a satisfactory level of diversification via the solution construction mechanism of the ant colony optimization algorithm. Therefore, LNS–ACO algorithm combines its solution improvement mechanism with a solution construction mechanism. The performance of the proposed algorithm is tested on a set of CVRP instances. The hybrid LNS–ACO algorithm is compared against two other LNS variants and some of the formerly developed methods in terms of solution quality. Computational results indicate that the proposed hybrid LNS–ACO algorithm has a satisfactory performance in solving CVRP instances.     

A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem

Job shop scheduling problem (JSP) which is widespread in the real-world production system is one of the most general and important problems in various scheduling problems. Nowadays, the effective method for JSP is a hot topic in research area of manufacturing system. JSP is a typical NP-hard combinatorial optimization problem and has a broad engineering application background. Due to the large and complicated solution space and process constraints, JSP is very difficult to find an optimal solution within a reasonable time even for small instances. In this paper, a hybrid particle swarm optimization algorithm (PSO) based on variable neighborhood search (VNS) has been proposed to solve this problem. In order to overcome the blind selection of neighborhood structures during the hybrid algorithm design, a new neighborhood structure evaluation method based on logistic model has been developed to guide the neighborhood structures selection. This method is utilized to evaluate the performance of different neighborhood structures. Then the neighborhood structures which have good performance are selected as the main neighborhood structures in VNS. Finally, a set of benchmark instances have been conducted to evaluate the performance of proposed hybrid algorithm and the comparisons among some other state-of-art reported algorithms are also presented. The experimental results show that the proposed hybrid algorithm has achieved good improvement on the optimization of JSP, which also verifies the effectiveness and efficiency of the proposed neighborhood structure evaluation method.     

Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem

This paper introduces a new algorithmic nature-inspired approach that uses particle swarm optimization (PSO) with different neighborhood topologies, for successfully solving one of the most computationally complex problems, the permutation flowshop scheduling problem (PFSP). The PFSP belongs to the class of combinatorial optimization problems characterized as NP-hard and, thus, heuristic and metaheuristic techniques have been used in order to find high quality solutions in reasonable computational time. The proposed algorithm for the solution of the PFSP, the PSO with expanding neighborhood topology, combines a PSO algorithm, the variable neighborhood search strategy and a path relinking strategy. As, in general, the structure of the social network affects strongly a PSO algorithm, the proposed method using an expanding neighborhood topology manages to increase the performance of the algorithm. As the algorithm starts from a small size neighborhood and by increasing (expanding) in each iteration the size of the neighborhood, it ends to a neighborhood that includes all the swarm, and it manages to take advantage of the exploration abilities of a global neighborhood structure and of the exploitation abilities of a local neighborhood structure. In order to test the effectiveness and the efficiency of the proposed method, we use a set of benchmark instances of different sizes and compare the proposed method with a number of other PSO algorithms and other algorithms from the literature.     

融合可行基规则的粒子群优化算法及其应用

基本粒子群优化算法对于离散的优化问题处理不佳,容易陷入局部最优。针对基本粒子群优化算法处理离散型优化问题时的缺陷,提出了一种融合可行基规则的改进型粒子群优化算法,并用该算法求解车辆路径问题。实验结果表明,该算法的优化性能和求解精度均优于其他文献算法,在求解车辆路径问题中具有较高的应用价值。     

A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery

Vehicle routing problem (VRP) is an important and well-known combinatorial optimization problem encountered in many transport logistics and distribution systems. The VRP has several variants depending on tasks performed and on some restrictions, such as time windows, multiple vehicles, backhauls, simultaneous delivery and pick-up, etc. In this paper, we consider vehicle routing problem with simultaneous pickup and delivery (VRPSPD). The VRPSPD deals with optimally integrating goods distribution and collection when there are no precedence restrictions on the order in which the operations must be performed. Since the VRPSPD is an NP-hard problem, we present a heuristic solution approach based on particle swarm optimization (PSO) in which a local search is performed by variable neighborhood descent algorithm (VND). Moreover, it implements an annealing-like strategy to preserve the swarm diversity. The effectiveness of the proposed PSO is investigated by an experiment conducted on benchmark problem instances available in the literature. The computational results indicate that the proposed algorithm competes with the heuristic approaches in the literature and improves several best known solutions.     

多目标动态车辆路径问题建模及优化

针对物流配送中动态车辆路径优化问题,综合考虑动态需求、路网影响、车辆共享、时间窗以及客户满意度,建立了多目标动态数学规划模型,该模型能更好地描述现代物流配送问题.同时,提出一种两阶段求解策略,第一阶段采用多目标混合粒子群优化算法获取预优化阶段Pareto最优解,采用改进的粒子状态更新策略并融合模拟退火操作提升粒子群搜索性能,采用自适应网格技术保持解的分布性;第二阶段对客户的需求变化采用贪婪插入和变邻域搜索进行实时路径调整.实验表明,该算法在解空间中有更好的探寻能力,并能快速收敛到全局最优,满足动态路径优化实时性要求.     

多中心半开放式送取需求可拆分的车辆路径优化

针对多中心半开放式送取需求可拆分的车辆路径问题,构建了以车辆配送距离最短为目标的多中心半开放式送取需求可拆分的数学模型。设计大变异邻域遗传算法进行求解,采用二维染色体编码及顺序交叉策略,同时运用大变异策略和邻域搜索策略提高算法全局和局部的寻优能力,通过算例对比验证了所提模型与算法的有效性。算例实验表明,大变异邻域遗传算法在求解多中心物流配送车辆路径问题上求解质量较优、求解效率较高、求解结果较为稳定,同时验证了联合配送下多中心半开放式送取需求可拆分的配送模式优于独立配送下单中心送取需求可拆分的配送模式。研究成果不仅拓展了车辆路径问题,还可为相关快递物流企业配送优化提供决策参考。     

A hybrid scatter search meta-heuristic for delay-constrained multicast routing problems

This paper investigates the first hybrid scatter search and path relinking meta-heuristic for the Delay-Constrained Least-Cost (DCLC) multicast routing problem. The underpinning mathematic model of the DCLC multicast routing problem is the constrained Steiner tree problem in graphs, a well known NP-complete problem. After combining a path relinking method as the solution combination method in scatter search, we further explore two improvement strategies: tabu search and variable neighborhood search, to intensify the search in the hybrid scatter search algorithm. A large number of simulations on some benchmark instances from the OR-library and a group of random graphs of different characteristics demonstrate that the improvement strategy greatly affects the performance of the proposed scatter search algorithm. The hybrid scatter search algorithm intensified by a variable neighborhood descent search is highly efficient in solving the DCLC multicast routing problem in comparison with other algorithms and heuristics in the literature.     

结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题EI北大核心CSCD

针对带时间窗的低能耗多车场多车型车辆路径问题(Low-energy-consumption multi-depots heterogeneousfleet vehicle routing problem with time windows,LMHFVPR_TW),提出一种结合聚类分解策略的增强蚁群算法(Enhanced ant colony optimization based on clustering decomposition,EACO_CD)进行求解.首先,由于该问题具有强约束、大规模和NP-Hard等复杂性,为有效控制问题的求解规模并合理引导算法在优质解区域搜索,根据问题特点设计两种基于K-means的聚类策略,将LMHFVPR_TW合理分解为一系列带时间窗的低能耗单车场单车型车辆路径子问题(Low-energy-consumption vehicle routing problem with time windows,LVRP_TW);其次,本文提出一种增强蚁群算法(Enhanced ant colony optimization,EACO)求解分解后的各子问题(LVRP_TW),进而获得原问题的解.EACO不仅引入信息素挥发系数控制因子进一步动态调节信息素挥发系数,从而有效控制信息素的挥发以提高算法的全局搜索能力,而且设计基于4种变邻域操作的两阶段变邻域局部搜索(Two-stage variable neighborhood search,TVNS)来增强算法的局部搜索能力.最后,在不同规模问题上的仿真和对比实验验证了所提EACO_CD的有效性.     

混合粒子群算法求解带软时间窗的VRPSPD问题

针对带软时间窗的同时集配货车辆路径问题（VRPSPD）,建立了以车辆派遣成本、行驶成本和时间窗惩罚成本之和最小为目标的车辆路径优化模型;设计混合粒子群算法进行求解,该算法结合以变邻域下降搜索为主体的适应性扰动机制,采用适应性选择邻域策略,并在每个邻域搜索中应用可变的循环次数,以此提高对解空间的探测能力和搜索效率。数值实验结果表明了该算法的可行性和有效性。     

An efficient variable neighborhood search heuristic for very large scale vehicle routing problems

In this paper, we present an efficient variable neighborhood search heuristic for the capacitated vehicle routing problem. The objective is to design least cost routes for a fleet of identically capacitated vehicles to service geographically scattered customers with known demands. The variable neighborhood search procedure is used to guide a set of standard improvement heuristics. In addition, a strategy reminiscent of the guided local search metaheuristic is used to help escape local minima. The developed solution method is specifically aimed at solving very large scale real-life vehicle routing problems. To speed up the method and cut down memory usage, new implementation concepts are used. Computational experiments on 32 existing large scale benchmarks, as well as on 20 new very large scale problem instances, demonstrate that the proposed method is fast, competitive and able to find high-quality solutions for problem instances with up to 20,000 customers within reasonable CPU times.     

A simple and effective evolutionary algorithm for the vehicle routing problem

The vehicle routing problem (VRP) plays a central role in the optimization of distribution networks. Since some classical instances with 75 nodes resist the best exact solution methods, most researchers concentrate on metaheuristics for solving real-life problems. Contrary to the VRP with time windows, no genetic algorithm (GA) can compete with the powerful tabu search (TS) methods designed for the VRP. This paper bridges the gap by presenting a relatively simple but effective hybrid GA. In terms of average solution cost, this algorithm outperforms most published TS heuristics on the 14 classical Christofides instances and becomes the best solution method for the 20 large-scale instances generated by Golden et al.Scope and purposeThe framework of this research is the development of effective metaheuristics for hard combinatorial optimization problems met in vehicle routing. It is surprising to notice in the literature the absence of effective genetic algorithms (GA) for the vehicle routing problem (VRP, the main capacitated node routing problem), contrary to node routing problems with time windows or arc routing problems. Earlier attempts were based on chromosomes with trip delimiters and needed a repair procedure to get feasible children after each crossover. Such procedures are known to weaken the genetic transmission of information from parents to children. This paper proposes a GA without trip delimiters, hybridized with a local search procedure. At any time, a chromosome can be converted into an optimal VRP solution (subject to chromosome sequence), thanks to a special splitting procedure. This design choice avoids repair procedures and enables the use of classical crossovers like OX. The resulting algorithm is flexible, relatively simple, and very effective when applied to two sets of standard benchmark instances ranging from 50 to 483 customers.     

求解带时间窗车辆路径问题的改进粒子群算法

通过分析已有粒子群算法对有时间窗约束的车辆路径问题求解质量不高的原因,提出了一种基于粒子交换原理的整数粒子更新方法。采用构造的双层粒子进化算法分别对8个和20个任务点的有时间窗约束的车辆路径问题求解,数值实验结果表明算法的求解精度和耗时均优于已有算法。     

车辆路径问题的改进混合粒子群算法研究

针对各种启发式算法在求车辆路径问题(VRP)中的缺陷,提出了改进的混合粒子群算法(MHPSO)的求解方法.分析了基于速度-位置更新策略传统粒子群算法在解决离散的和组合优化问题的不足.考虑到算法在求解过程中种群多样性的损失过快,引进了种群的多样性测度参数-平均粒距,以保持种群的多样性.同时利用混沌运功的随机性、遍历性和规律性等特性,采用混沌初始化粒子编码.详细讨论了该算法在车辆路径问题中的求解策略.针对同一个实例,将改进的混合粒子群算法与遗传算法从多个角度进行比较.仿真结果表明,论文所提出的算法性能较好,可以快速、有效求得车辆路径问题的优化解或近似优化解.     

基于改进粒子群算法的物流配送车辆调度优化

车辆优化调度是提高物流企业运营效益的重要因素,针对标准粒子群优化算法存在的不足,提出一种改进粒子群算法（IPSO）的物流配送车辆调度优化方法。建立物流配送车辆调度优化的数学模型,将车辆与车辆路径编码成粒子,通过粒子之间的协作找到最优物流配送车辆调度优化方案,并对粒子群算法存在的不足进行了相应的改进,最后给出仿真实验对其性能进行测试。实验结果表明,IPSO算法不仅加快了物流配送车辆调度优化问题求解的速度,而且获得了最优解的概率,具有比其他调度算法更明显的优势。     

Hybrid column generation and large neighborhood search for the dial-a-ride problem

Demographic change towards an ever aging population entails an increasing demand for specialized transportation systems to complement the traditional public means of transportation. Typically, users place transportation requests, specifying a pickup and a drop off location and a fleet of minibuses or taxis is used to serve these requests. The underlying optimization problem can be modeled as a dial-a-ride problem. In the dial-a-ride problem considered in this paper, total routing costs are minimized while respecting time window, maximum user ride time, maximum route duration, and vehicle capacity restrictions. We propose a hybrid column generation and large neighborhood search algorithm and compare different hybridization strategies on a set of benchmark instances from the literature.     

METAHEURISTIC APPROACH FOR THE MULTI-DEPOT VEHICLE ROUTING PROBLEM

Distribution logistics comprises all activities related to the provision of finished products and merchandise to a customer. The focal point of distribution logistics is the shipment of goods from the manufacturer to the consumer. The products can be delivered to a customer directly either from the production facility or from the trader's stock located close to the production site or, probably, via additional regional distribution warehouses. These kinds of distribution logistics are mathematically represented as a vehicle routing problem (VRP), a well-known nondeterministic polynomial time (NP)-hard problem of operations research. VRP is more suited for applications having one warehouse. In reality, however, many companies and industries possess more than one distribution warehouse. These kinds of problems can be solved with an extension of VRP called multi-depot VRP (MDVRP). MDVRP is an NP-hard and combinatorial optimization problem. MDVRP is an important and challenging problem in logistics management. It can be solved using a search algorithm or metaheuristic and can be viewed as searching for the best element in a set of discrete items. In this article, cluster first and route second methodology is adapted and metaheuristics genetic algorithms (GA) and particle swarm optimization (PSO) are used to solve MDVRP. A hybrid particle swarm optimization (HPSO) for solving MDVRP is also proposed. In HPSO, the initial particles are generated based on the k-means clustering and nearest neighbor heuristic (NNH). The particles are decoded into clusters and multiple routes are generated within the clusters. The 2-opt local search heuristic is used for optimizing the routes obtained; then the results are compared with GA and PSO for randomly generated problem instances. The home delivery pharmacy program and waste-collection problem are considered as case studies in this paper. The algorithm is implemented using MATLAB 7.0.1.     

A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests

Combinatorial optimization problems are usually modeled in a static fashion. In this kind of problems, all data are known in advance, i.e. before the optimization process has started. However, in practice, many problems are dynamic, and change while the optimization is in progress. For example, in the dynamic vehicle routing problem (DVRP), new orders arrive when the working day plan is in progress. In this case, routes must be reconfigured dynamically while executing the current simulation. The DVRP is an extension of a conventional routing problem, its main interest being the connection to many real word applications (repair services, courier mail services, dial-a-ride services, etc.). In this article, a DVRP is examined, and solving methods based on particle swarm optimization and variable neighborhood search paradigms are proposed. The performance of both approaches is evaluated using a new set of benchmarks that we introduce here as well as existing benchmarks in the literature. Finally, we measure the behavior of both methods in terms of dynamic adaptation.