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 multi-phase oscillated variable neighbourhood search algorithm for a real-world open vehicle routing problem

The aim of this study is to solve the newspaper delivery optimization problem for a media delivery company in Turkey by reducing the total cost of carriers. The problem is modelled as an open vehicle routing problem (OVRP), which is a variant of the vehicle routing problem. A variable neighbourhood search-based algorithm is proposed to solve a real-world OVRP. The proposed algorithm is tested with varieties of small and large-scale benchmark suites and a very large-scale real-world problem instance. The results of the proposed algorithm provide either the best known solution or a competitive solution for each of the benchmark instances. The algorithm also improves the real-world company’s solutions by more than 10%.     

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 fast two-level variable neighborhood search for the clustered vehicle routing problem

In this paper, we present an improved two-level heuristic to solve the clustered vehicle routing problem (CluVRP). The CluVRP is a generalization of the classical capacitated vehicle routing problem (CVRP) in which customers are grouped into predefined clusters, and all customers in a cluster must be served consecutively by the same vehicle. This paper contributes to the literature in the following ways: (i) new upper bounds are presented for multiple benchmark instances, (ii) good heuristic solutions are provided in much smaller computing times than existing approaches, (iii) the CluVRP is reduced to its cluster level without assuming Euclidean coordinates or distances, and (iv) a new variant of the CluVRP, the CluVRP with weak cluster constraints, is introduced. In this variant, clusters are allocated to vehicles in their entirety, but all corresponding customers can be visited by the vehicle in any order.The proposed heuristic solves the CluVRP by combining two variable neighborhood search algorithms, that explore the solution space at the cluster level and the individual customer level respectively. The algorithm is tested on different benchmark instances from the literature with up to 484 nodes, obtaining high quality solutions while requiring only a limited calculation time.     

A variable neighborhood search for the multi-depot vehicle routing problem with loading cost

The purpose of this paper is to propose a variable neighbourhood search (VNS) for solving the multi-depot vehicle routing problem with loading cost (MDVRPLC). The MDVRPLC is the combination of multi-depot vehicle routing problem (MDVRP) and vehicle routing problem with loading cost (VRPLC) which are both variations of the vehicle routing problem (VRP) and occur only rarely in the literature. In fact, an extensive literature search failed to find any literature related specifically to the MDVRPLC. The proposed VNS comprises three phases. First, a stochastic method is used for initial solution generation. Second, four operators are randomly selected to search neighbourhood solutions. Third, a criterion similar to simulated annealing (SA) is used for neighbourhood solution acceptance. The proposed VNS has been test on 23 MDVRP benchmark problems. The experimental results show that the proposed method provides an average 23.77% improvement in total transportation cost over the best known results based on minimizing transportation distance. The results show that the proposed method is efficient and effective in solving problems.     

The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation

The multi-depot fleet size and mix vehicle routing problem, also known as the multi-depot routing with heterogeneous vehicles, is investigated. A mathematical formulation is given and lower as well as upper bounds are produced using a three hour execution time of CPLEX. An efficient implementation of variable neighborhood search that incorporates new features in addition to the adaptation of several existing neighborhoods and local search operators is proposed. These features include a preprocessing scheme for identifying borderline customers, a mechanism that aggregates and disaggregates routes between depots, and a neighborhood reduction test that saves nearly 80% of the CPU time, especially on the large instances. The proposed algorithm is highly competitive as it produces 23 new best results when tested on the 26 data instances published in the literature.     

A multistart adaptive memory-based tabu search algorithm for the heterogeneous fixed fleet open vehicle routing problem

This paper addressed the heterogeneous fixed fleet open vehicle routing problem (HFFOVRP), in which the demands of customers are fulfilled by a fleet of fixed number of vehicles with various capacities and related costs. Moreover, the vehicles start at the depot and terminate at one of the customers. This problem is an important variant of the classical vehicle routing problem and can cover more practical situations in transportation and logistics. We propose a multistart adaptive memory programming metaheuristic with modified tabu search algorithm to solve this new vehicle routing problem. The algorithmic efficiency and effectiveness are experimentally evaluated on a set of generated instances.     

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.     

Genetic algorithm and large neighbourhood search to solve the cell formation problem

We first introduce a local search procedure to solve the cell formation problem where each cell includes at least one machine and one part. The procedure applies sequentially an intensification strategy to improve locally a current solution and a diversification strategy destroying more extensively a current solution to recover a new one. To search more extensively the feasible domain, a hybrid method is specified where the local search procedure is used to improve each offspring solution generated with a steady state genetic algorithm. The numerical results using 35 most widely used benchmark problems indicate that the line search procedure can reduce to 1% the average gap to the best-known solutions of the problems using an average solution time of 0.64 s. The hybrid method can reach the best-known solution for 31 of the 35 benchmark problems, and improve the best-known solution of three others, but using more computational effort.     

A large neighbourhood search heuristic for ship routing and scheduling with split loads

The purpose of this paper is to present and solve a new, important planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies are committed to carrying some contract cargoes and will try to derive additional revenue from optional spot cargoes. In most of the literature on ship routing and scheduling problems a cargo cannot be transported by more than one ship. By introducing split loads this restriction is removed and each cargo can be transported by several ships. In this paper we propose a large neighbourhood search heuristic for the ship routing and scheduling problem with split loads. Computational results show that the heuristic provides good solutions to real-life instances within reasonable time. It is also shown that introducing split loads can yield significant improvements.     

Variable neighbourhood search for the variable sized bin packing problem

The variable sized bin packing problem is a generalisation of the one-dimensional bin packing problem. Given is a set of weighted items, which must be packed into a minimum-cost set of bins of variable sizes and costs. This problem has practical applications, for example, in packing, transportation planning, and cutting. In this work we propose a variable neighbourhood search metaheuristic for tackling the variable sized bin packing problem. The presented algorithm can be seen as a hybrid metaheuristic, because it makes use of lower bounding techniques and dynamic programming in various algorithmic components. An extensive experimentation on a diverse set of problem instances shows that the proposed algorithm is very competitive with current state-of-the-art approaches.     

面向动态车辆路径的改进变邻域搜索算法

为了切实求解带时间窗的车辆动态路径问题,提出一种改进变邻域搜索算法,并建立了相应数学模型。算法运用聚类方法完成客户分配和路线规划的初始解构建。插入一交换混合算子实现抖动过程,提出后优化过程改进解空间,并采用最佳改进策略实现算法在求解质量和运行时间上的最佳平衡,引入模拟退火思想控制新解接受、地理位置分布等,并对路径选择进行了分析。通过与其他算法的实验结果比较表明该算法的可行性和高效性。     

A variable neighbourhood search for fast train scheduling and routing during disturbed railway traffic situations

This paper focuses on the development of metaheuristic algorithms for the real-time traffic management problem of scheduling and routing trains in complex and busy railway networks. This key optimization problem can be formulated as a mixed integer linear program. However, since the problem is strongly NP-hard, heuristic algorithms are typically adopted in practice to compute good quality solutions in a short computation time. This paper presents a number of algorithmic improvements implemented in the AGLIBRARY optimization solver in order to improve the possibility of finding good quality solutions quickly. The optimization solver manages trains at the microscopic level of block sections and at a precision of seconds. The solver outcome is a detailed conflict-free train schedule, being able to avoid deadlock situations and to minimize train delays. The proposed algorithmic framework starts from a good initial solution for the train scheduling problem with fixed routes, obtained via a truncated branch-and-bound algorithm. Variable neighbourhood search or tabu search algorithms are then applied to improve the solution by re-routing some trains. The neighbourhood of a solution is characterized by the set of candidate trains to be re-routed and the available routes. Computational experiments are performed on railway networks from different countries and various sources of disturbance. The new algorithms often outperform a state-of-the-art tabu search algorithm and a commercial solver in terms of reduced computation times and/or train delays.     

A guided cooperative search for the vehicle routing problem with time windows

We have developed a pattern-identification mechanism that endows cooperative search with capabilities to create new information and guide the global search. The proposed mechanism sends information to independent metaheuristics about promising and unpromising patterns in the solution space. By fixing or prohibiting specific solution attribute values in certain search metaheuristics, we can focus the search on desired regions. The mechanism thus enforces better coordination between individual methods and controls the global search's diversification and intensification. An enhanced cooperative-search mechanism creates new information from exchanged solutions and guides the global search with a pattern-identification mechanism.     

A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem

In the heterogeneous fixed fleet vehicle routing problem there are different types of vehicles and a given number of vehicles of each type. The resolution of this problem consists of assigning the customers to the existing vehicles and, in relation to each vehicle, defining the order of visiting each customer for the delivery or collection of goods. The objective is to minimize the total costs, satisfying customers’ requirements and visiting each customer exactly once. In this paper a tabu search algorithm is proposed and tested on several benchmark problems. The computational experiments show that the proposed algorithm produces high quality solutions within an acceptable computation time. Four new best solutions are reported for a set of test problems used in the literature.     

Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows

Motivated by a situation faced by infrastructure service providers operating in urban areas with accessibility restrictions, we study the truck and trailer routing problem with time windows (TTRPTW). In this problem the vehicle fleet consists of trucks and trailers which may be decoupled. A set of customers has to be served and some of the customers can only be accessed by the truck without the trailer. This gives rise to the planning of truck-and-trailer routes containing truck-only subroutes, in addition to truck-only routes and truck-and-trailer routes without subroutes. We propose a branch-and-price algorithm for the TTRPTW, using problem specific enhancements in the pricing scheme and alternative lower bound computations. We also tailor an adaptive large neighborhood search algorithm to the TTRPTW in order to obtain good initial columns. When compared to existing metaheuristic algorithms we obtain highly competitive results. Some instances with up to 100 customers are solved to optimality with the proposed branch-and-price algorithm.     

Genetic clustering: An adaptive heuristic for the multidepot vehicle routing problem

A generalized clustering method based on a Genetic Algorithm is proposed. The Genetic Clustering (GenClust) method is used for solving the multidepot vehicle routing problem. The solution obtained by the genetic clustering method is improved using an efficient postoptimizer. A set of problems obtained from the literature are used to compare the efficiency of the genetic clustering method for solving the multidepot vehicle routing problem. The genetic clustering method found 11 new best known solutions from the 23 problems in the literature set.     

A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem

This paper addresses an extension of the capacitated vehicle routing problem where customer demand is composed of two-dimensional weighted items (2L-CVRP). The objective consists in designing a set of trips minimizing the total transportation cost with a homogenous fleet of vehicles based on a depot node. Items in each vehicle trip must satisfy the two-dimensional orthogonal packing constraints. A GRASP×ELS algorithm is proposed to compute solutions of a simpler problem in which the loading constraints are transformed into resource constrained project scheduling problem (RCPSP) constraints. We denote this relaxed problem RCPSP-CVRP. The optimization framework deals with RCPSP-CVRP and lastly RCPSP-CVRP solutions are transformed into 2L-CVRP solutions by solving a dedicated packing problem. The effectiveness of our approach is demonstrated through computational experiments including both classical CVRP and 2L-CVRP instances. Numerical experiments show that the GRASP×ELS approach outperforms all previously published methods.     

A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service

The vehicle routing problem with simultaneous pick-up and delivery (VRP_SPD) is a variant of the classical vehicle routing problem (VRP) where clients require simultaneous pick-up and delivery service. Deliveries are supplied from a single depot at the beginning of the vehicle's service, while pick-up loads are taken to the same depot at the conclusion of the service. One important characteristic of this problem is that a vehicle's load in any given route is a mix of pick-up and delivery loads.     

A self-adaptive memeplexes robust search scheme for solving stochastic demands vehicle routing problem

In this article, we proposed a self-adaptive memeplex robust search (SAMRS) for finding robust and reliable solutions that are less sensitive to stochastic behaviours of customer demands and have low probability of route failures, respectively, in vehicle routing problem with stochastic demands (VRPSD). In particular, the contribution of this article is three-fold. First, the proposed SAMRS employs the robust solution search scheme (RS ³) as an approximation of the computationally intensive Monte Carlo simulation, thus reducing the computation cost of fitness evaluation in VRPSD, while directing the search towards robust and reliable solutions. Furthermore, a self-adaptive individual learning based on the conceptual modelling of memeplex is introduced in the SAMRS. Finally, SAMRS incorporates a gene-meme co-evolution model with genetic and memetic representation to effectively manage the search for solutions in VRPSD. Extensive experimental results are then presented for benchmark problems to demonstrate that the proposed SAMRS serves as an efficable means of generating high-quality robust and reliable solutions in VRPSD.