The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP) is a well known problem which has long been tackled by researchers for several decades now, not only because of its potential applications but also due to the fact that CVRP can be used to test the efficiency of new algorithms and optimization methods. The objective of our work is to present SR-GCWS, a hybrid algorithm that combines a CVRP classical heuristic with Monte Carlo simulation using state-of-the-art random number generators. The resulting algorithm is tested against some well-known benchmarks. In most cases, our approach is able to compete or even outperform much more complex algorithms, which is especially interesting if we consider that our algorithm does not require any previous parameter fine-tuning or set-up process. Moreover, our algorithm has been able to produce high-quality solutions almost in real-time for most tested instances. Another important feature of the algorithm worth mentioning is that it uses a randomized constructive heuristic, capable of generating hundreds or even thousands of alternative solutions with different properties. These alternative solutions, in turn, can be really useful for decision-makers in order to satisfy their utility functions, which are usually unknown by the modeler. The presented methodology may be a fine framework for the development of similar algorithms for other complex combinatorial problems in the routing arena as well as in some other research fields.     

An improved hybrid firefly algorithm for capacitated vehicle routing problem

Firefly algorithm (FA) is a new meta-heuristic which is successfully applied to solve several optimization problems. However, it suffers from a drawback of easily getting stuck at local optima. This paper proposes a new hybrid FA, called CVRP-FA, to solve capacitated vehicle routing problem. In CVRP-FA, FA is integrated with two types of local search and genetic operators to enhance the solution’s quality and accelerate the convergence. The experiments are conducted over 82 benchmark instances. The results demonstrate that CVRP-FA has fast convergence rate and high computational accuracy. It significantly outperforms the other state-of-the-art FA variants in majority of the tested instances.     

A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints

The capacitated vehicle routing problem with three-dimensional loading constraints combines capacitated vehicle routing and three-dimensional loading with additional packing constraints concerning, for example, unloading operations. An efficient hybrid algorithm including a tabu search algorithm for routing and a tree search algorithm for loading is introduced. Computational results are presented for all publicly available test instances. Most of the best solutions previously reported in literature have been improved while the computational effort is drastically reduced compared to other methods.     

混合分散搜索算法求解带容量约束车辆路径问题

设计一种解决带容量约束车辆路径问题的混合分散搜索算法. 在基本分散搜索的基础上, 保留参考集更新策略和组合策略的全局搜索能力. 采用随机插入法作为解的多样性产生方法, 以扩大搜索空间, 避免陷入局部最优.应用简化的变邻域搜索作为改进策略进行局部开发, 引入邻域半径减少策略提高开发效率. 对改进后的新种群实施精英保留策略, 保证算法收敛. 实验结果分析表明, 混合分散搜索算法优于所对比的算法, 寻优能力可靠.

     

随机需求车辆路径问题及混合变邻域分散搜索算法求解

随机需求车辆路径问题(capacitated vehicle routing problem with stochastic demand,CVRPSD)是对带容量约束车辆路径问题(capacitated vehicle routing problem,CVRP)的扩展,需求不确定的特点使其较CVRP更复杂,对求解方法要求更高.基于先预优化后重调度思想,提出两阶段的混合变邻域分散搜索算法(variable neighborhood scatter search,VNSS)对该问题进行求解:预优化阶段构建随机机会约束规划模型,对客户点随机需求作机会约束确定型等价处理,生成最优预优化方案;重调度阶段采用新的点重优化策略进行线路调整,降低因失败点而产生的额外成本,减少对人工和车辆的占用.算例验证表明,随机机会约束模型和两阶段变邻域分散搜索算法在求解CVRPSD时较为有效,点重优化策略调整效果较佳.     

Heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem in a carrier

In this paper, we present heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem arising in a real-world situation. In this problem, customers make requests of goods, which are packed in a sortment of boxes. The objective is to find minimum cost delivery routes for a set of identical vehicles that, departing from a depot, visit all customers only once and return to the depot. Apart of the usual 3D container loading constraints which ensure that the boxes are packed completely inside the vehicles and that the boxes do not overlap each other in each vehicle, the problem also takes into account constraints related to the vertical stability of the cargo and multi-drop situations. The algorithms are based on the combination of classical heuristics from both vehicle routing and container loading literatures, as well as two metaheuristic strategies, and their use in more elaborate procedures. Although these approaches cannot assure optimal solutions for the respective problems, they are relatively simple, fast enough to solve real instances, flexible enough to include other practical considerations, and normally assure relatively good solutions in acceptable computational times in practice. The approaches are also sufficiently generic to be embedded with algorithms other than those considered in this study, as well as they can be easily adapted to consider other practical constraints, such as the load bearing strength of the boxes, time windows and pickups and deliveries. Computational tests were performed with these methods considering instances based on the vehicle routing literature and actual customers’ orders, as well as instances based on a real-world situation of a Brazilian carrier. The results show that the heuristics are able to produce relatively good solutions for real instances with hundreds of customers and thousands of boxes.     

An adaptive tabu search algorithm for the capacitated clustering problem

In the Capacitated Clustering Problem, a given set of customers with distinct demands must be partitioned into p clusters with limited capacities. The objective is to find p customers, called medians, from which the sum of the distances to all other customers in the cluster is minimized. In this article, a new adaptive tabu search approach is applied to solve the problem. Initial solutions are obtained by four constructive heuristics that use weights and distances as optimization criteria. Two neighborhood generation mechanisms are used by the local search heuristic: pairwise interchange and insertion . Computational results from 20 instances found in the literature indicate that the proposed method outperforms alternative metaheuristics developed for solving this problem.     

An improved heuristic for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is an important and practical problem in the OR literature. In short, the problem is to identify routes to service (e.g., pickup or deliver) demand located along the edges of a network such that the total cost of the routes is minimized. In general, a single route cannot satisfy the entire demand due to capacity constraints on the vehicles. CARP belongs to the set of NP-hard problems; consequently numerous heuristic and metaheuristic solution approaches have been developed to solve it. In this paper an “ellipse rule” based heuristic is proposed for the CARP. This approach is based on the path-scanning heuristic, one of the mostly used greedy-add heuristics for this problem. The innovation consists basically of selecting edges only inside ellipses when the vehicle is near the end of each route. This new approach was implemented and tested on three standard datasets and the solutions are compared against: (i) the original path-scanning heuristic; (ii) two other path-scanning heuristics and (iii) the three best known metaheuristics. The results indicate that the “ellipse rule” approach lead to improvements over the three path-scanning heuristics, reducing the average distance to the lower bound in the test problems by about 44%.     

Statistical analysis of distance-based path relinking for the capacitated vehicle routing problem

In this paper we develop an intelligent path relinking procedure for the capacitated vehicle routing problem, based on the relocate distance. This procedure transforms an incumbent solution into a guiding solution in a minimal number of relocate moves. In each step of the path relinking procedure, one customer is removed from the solution and re-inserted in another position.     

A cooperative parallel metaheuristic for the capacitated vehicle routing problem

This paper introduces a cooperative parallel metaheuristic for the capacitated vehicle routing problem. The proposed metaheuristic consists of multiple parallel tabu search threads that cooperate by asynchronously exchanging best-found solutions through a common solution pool. The solutions sent to the pool are clustered according to their similarities. The search history information identified from the solution clusters is applied to guide the intensification or diversification of the tabu search threads. Computational experiments on two sets of large-scale benchmark instance sets from the literature demonstrate that the suggested metaheuristic is highly competitive, providing new best solutions to ten of those well-studied instances.     

A two-phase metaheuristic for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem, which aims to minimize the total arrival time at customers, is a relatively new variant of vehicle routing problem. It can be used to model many real-world applications, e.g., the important application arisen from the humanitarian aid after a natural disaster. In this paper, an approach, called two-phase metaheuristic, is proposed to deal with this problem. This algorithm starts from a solution. At each iteration, two interdependent phases use different perturbation and local search operators for solution improvement. The effectiveness of the proposed algorithm is empirically investigated. The comparison results show that the proposed algorithm is promising. Moreover, for nine benchmark instances, the two-phase metaheuristic can find better solutions than those reported in the previous literature.     

一种求解两级车辆路径问题的Memetic 算法

两级车辆路径问题是指物资必须先由中心仓库配送至中转站(第1级),再由中转站配送至客户(第2级)的一种车辆路径问题。针对该NP难问题提出一种Memetic算法通过自底向上的方式进行求解。首先利用改进的最优切割算法MDVRP-Split将客户合理分配至中转站;然后采用局部搜索解决第1级问题,交叉产生的精英个体通过局部搜索改进。标准算例的测试结果表明,所提出算法更注重求解质量与求解效率的平衡,性能优于其他现有的两种算法。     

Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO

Two solution representations for solving the generalized multi-depot vehicle routing problem with multiple pickup and delivery requests (GVRP-MDMPDR) is presented in this paper. The representations are used in conjunction with GLNPSO, a variant of PSO with multiple social learning terms. The computational experiments are carried out using benchmark test instances for pickup and delivery problem with time windows (PDPTW) and the generalized vehicle routing problem for multi-depot with multiple pickup and delivery requests (GVRP-MDMPDR). The preliminary results illustrate that the proposed method is capable of providing good solutions for most of the test problems.     

Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem

This paper presents two solution representations and the corresponding decoding methods for solving the capacitated vehicle routing problem (CVRP) using particle swarm optimization (PSO). The first solution representation (SR-1) is a (n + 2m)-dimensional particle for CVRP with n customers and m vehicles. The decoding method for this representation starts with the transformation of particle into a priority list of customer to enter route and a priority matrix of vehicle to serve each customer. The vehicle routes are then constructed based on the customer priority list and vehicle priority matrix. The second representation (SR-2) is a 3m-dimensional particle. The decoding method for this representation starts with the transformation of particle into the vehicle orientation points and the vehicle coverage radius. The vehicle routes are constructed based on these points and radius. The proposed representations are applied using GLNPSO, a PSO algorithm with multiple social learning structures, and tested using some benchmark problems. The computational result shows that representation SR-2 is better than representation SR-1 and also competitive with other methods for solving CVRP.     

需求可拆分车辆路径问题的禁忌搜索算法

为解决实际配送运输中的车辆路径问题（Vehicle Routing Problem,VRP）,通过改进传统的数学模型,解除每个客户需求只能由l辆车配送的约束,建立改进的可拆分车辆路径问题（Split Delivery VRP,SDVRP）数学模型,并利用禁忌搜索算法（Taboo Search Algorithm,TSA）进行求解．在TSA的设计中,根据SDVRP模型的特点对初始解、邻域搜索和解的评价等进行特殊处理．算例表明,该模型不仅可以解决VRP模型中不允许配送点需求量超出装载量的限制,而且通过相应配送点需求量的拆分和重新组合,可节省车辆数目、缩短路线长度、提高车辆装载率．     

An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a variation of the classical capacitated vehicle routing problem in which the objective is the minimization of the sum of arrival times at customers, instead of the total routing cost. This paper presents an adaptive large neighborhood search heuristic for the CCVRP. This algorithm is applied to a set of benchmark instances and compared with two recently published memetic algorithms.     

A matheuristic for the MinMax capacitated open vehicle routing problem

In this paper, the MinMax‐COVRP (where COVRP is capacitated open vehicle routing problem) is considered as a variation of the COVRP where the objective is to minimize the duration of the longest route. For the purpose of producing high‐quality solutions, elements from the fields of mathematical programming and metaheuristics are combined, resulting in a matheuristic for solving the MinMax‐COVRP. The matheuristic benefits from the diversification produced by a metaheuristic and the intensification from mixed‐integer linear programming (MILP). The initial solution provided by a multistart heuristic is used to seed and accelerate the MILP in which a local branching framework and the separation of k‐path inequalities are suitably combined. Computational experience shows promising results not only improving the initial solution provided by the multistart algorithm, but also ensuring optimality for most of the small‐ and medium‐sized instances.     

An improved fireworks algorithm for the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP), which aims at minimizing travel costs, is a wellknown NP-hard combinatorial optimization. Owing to its hardness, many heuristic search algorithms have been proposed to tackle this problem. This paper explores a recently proposed heuristic algorithm named the fireworks algorithm (FWA), which is a swarm intelligence algorithm. We adopt FWA for the combinatorial CVRP problem with several modifications of the original FWA: it employs a new method to generate "sparks" according to the selection rule, and it uses a new method to determine the explosion amplitude for each firework. The proposed algorithm is compared with several heuristic search methods on some classical benchmark CVRP instances. The experimental results show a promising performance of the proposed method. We also discuss the strengths and weaknesses of our algorithm in contrast to traditional algorithms.     

Combining biased randomization with iterated local search for solving the multidepot vehicle routing problem

This paper proposes a hybrid approach for solving the multidepot vehicle routing problem (MDVRP) with a limited number of identical vehicles per depot. Our approach, which only uses a few parameters, combines “biased randomization”—use of nonsymmetric probability distributions to generate randomness—with the iterated local search (ILS) metaheuristic. Two biased‐randomized processes are employed at different stages of the ILS framework in order to (a) assign customers to depots following a randomized priority criterion—this allows for fast generation of alternative allocation maps and (b) improving routing solutions associated with a “promising” allocation map—this is done by randomizing the classical savings heuristic. These biased‐randomized processes rely on the use of the geometric probability distribution, which is characterized by a single and bounded parameter. Being an approach with few parameters, our algorithm does not require troublesome fine‐tuning processes, which tend to be time consuming. Using standard benchmarks, the computational experiments show the efficiency of the proposed algorithm. Despite its hybrid nature, our approach is relatively easy to implement and can be parallelized in a very natural way, which makes it an interesting alternative for practical applications of the MDVRP.