A new and efficient ant-based heuristic method for solving the traveling salesman problem

Abstract: In this paper, we present an efficient metaheuristic approach for solving the problem of the traveling salesman. We introduce the multiple ant clans concept from parallel genetic algorithms to search solution space using different islands to avoid local minima in order to obtain a global minimum for solving the traveling salesman problem. Our simulation results indicate that the proposed novel traveling salesman problem method (called the ACOMAC algorithm) performs better than a promising approach named the ant colony system. This investigation is concerned with a real life logistics system design which optimizes the performance of a logistics system subject to a required service level in the vehicle routing problem. In this work, we also concentrate on developing a vehicle routing model by improving the ant colony system and using the multiple ant clans concept. The simulation results reveal that the proposed method is very effective and potentially useful in solving vehicle routing problems.     

A two phase variable neighborhood search for the multi-product inventory routing problem

We address a multi-product inventory routing problem and propose a two-phase Variable Neighborhood Search (VNS) metaheuristic to solve it. In the first phase, VNS is used to solve a capacitated vehicle routing problem at each period to find an initial solution without taking into account the inventory. In the second phase, we iteratively improve the initial solution while minimizing both the transportation and inventory costs. For this, we propose two different algorithms, a Variable Neighborhood Descent and a Variable Neighborhood Search. We present an heuristic and a Linear Programming formulation, which are applied after each local search move, to determine the amount of products to collect from each supplier at each period. During the exploration, we use priority rules for suppliers and vehicles, based on the current delivery schedule over the planning horizon. Computational results show the efficiency of the proposed two-phase approach.     

A heuristic method for the vehicle routing problem with mixed deliveries and pickups

The vehicle routing problem with deliveries and pickups is a challenging extension to the vehicle routing problem that lately attracted growing attention in the literature. This paper investigates the relationship between two versions of this problem, called “mixed” and “simultaneous”. In particular, we wish to know whether a solution algorithm designed for the simultaneous case can solve the mixed case. To this end, we implement a metaheuristic based on reactive tabu search. The results suggest that this approach can yield good results.     

多中心联合配送模式下集货需求随机的VRPSDP问题

针对多中心联合配送模式下集货需求随机的同时配集货车辆路径问题(MDVRPSDDSPJD), 构建了两阶段MDVRPSDDSPJD模型. 预优化阶段基于随机机会约束机制以及车载量约束为客户分配车辆, 生成预优化方案; 重优化阶段采用失败点重优化策略对服务失败点重新规划路径. 根据问题特征, 设计了自适应变邻域文化基因算法(Adaptive memetic algorithm and variable neighborhood search, AMAVNS), 针对文化基因算法易早熟、局部搜索能力弱等缺陷, 将变邻域搜索算法的深度搜索能力运用到文化基因算法的局部搜索策略中, 增强算法的局部搜索能力; 提出自适应邻域搜索次数策略和自适应劣解接受机制平衡种群进化所需的广度和深度. 通过多组算例验证了提出模型及算法的有效性. 研究成果不仅深化和拓展了VRP (Vehicle routing problem)相关理论研究, 也为物流企业制定车辆调度计划提供一种科学合理的方法.     

An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen

The vehicle routing problem with time windows and multiple deliverymen (VRPTWMD) is a variant of the vehicle routing problem with time windows in which service times at customers depend on the number of deliverymen assigned to the route that serves them. In particular, a larger number of deliverymen in a route leads to shorter service times. Hence, in addition to the usual routing and scheduling decisions, the crew size for each route is also an endogenous decision. This problem is commonly faced by companies that deliver goods to customers located in busy urban areas, a situation that requires nearby customers to be grouped in advance so that the deliverymen can serve all customers in a group during one vehicle stop. Consequently, service times can be relatively long compared to travel times, which complicates serving all scheduled customers during regular work hours. In this paper, we propose a hybrid method for the VRPTWMD, combining a branch-price-and-cut (BPC) algorithm with two metaheuristic approaches. We present a wide variety of computational results showing that the proposed hybrid approach outperforms the BPC algorithm used as standalone method in terms of both solution quality and running time, in some classes of problem instances from the literature. These results indicate the advantages of using specific algorithms to generate good feasible solutions within an exact method.     

Variable neighborhood search for the inventory routing and scheduling problem in a supply chain

The inventory, routing and scheduling decisions are three major driving factors for supply chain performance. Since they are related to one another in a supply chain, they should be determined simultaneously to improve the decision quality. In the past, the inventory policy, vehicle routing and vehicle scheduling are determined sequentially and separately. Hence, the total cost (inventory, routing and vehicle costs) would increase. In this paper, an integrated model for the inventory routing and scheduling problem (IRSP) is proposed. Since searching for the optimal solution for this model is a non-polynomial (NP) problem, a metaheuristic, variable neighborhood search (VNS), is proposed. The proposed method was compared with other existing methods. The experimental results indicate that the proposed method is better than other methods in terms of average cost per day.     

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.     

Optimizing a bi‐objective vehicle routing problem that appears in industrial enterprises

In this paper, a new solution method is implemented to solve a bi‐objective variant of the vehicle routing problem that appears in industry and environmental enterprises. The solution involves designing a set of routes for each day in a period, in which the service frequency is a decision variable. The proposed algorithm, a muti‐start multi‐objective local search algorithm (MSMLS), minimizes total emissions produced by all vehicles and maximizes the service quality measured as the number of times that a customer is visited by a vehicle in order to be served. The MSMLS is a neighbourhood‐based metaheuristic that obtains high‐quality solutions and that is capable of achieving better performance than other competitive algorithms. Furthermore, the proposed algorithm is able to perform rapid movements thanks to the easy representation of the solutions.     

A large neighbourhood metaheuristic for the risk-constrained cash-in-transit vehicle routing problem

In this paper, we propose a new metaheuristic to solve the Risk constrained Cash-in-Transit Vehicle Routing Problem (Rctvrp). The Rctvrp is a variant of the well-known capacitated vehicle routing problem and models the problem of routing vehicles in the cash-in-transit sector. In the Rctvrp, the risk associated with a robbery represents a critical aspect that is treated as a limiting factor subject to a maximum risk threshold.A new metaheuristic, called aco-lns is developed. It combines the ant colony heuristic for the travelling salesman problem and a variable neighbourhood descent within an large neighbourhood search framework.A new library of Rctvrp instances with known optimal solutions is proposed. The aco-lns is extensively tested on small, medium and large benchmark instances and compared with all existing solution approaches for the Rctvrp.     

需求可拆分车辆路径问题的聚类求解算法

针对传统的车辆路径问题通常假设客户的需求不能拆分,即客户的需求由一辆车满足,而实际上通过需求的拆分可使需要的车辆数更少,从而降低配送成本的问题,分析了需求可拆分的车辆路径问题的解的特征,证明了客户需求不宜拆分应满足的条件,设计了符合解的特征的聚类算法,并对其求解.通过实验仿真,将所提出的聚类算法与蚁群算法和禁忌搜索算法进行比较,所得结果表明了所提出的算法可以更有效地求得需求可拆分车辆路径问题的优化解,是解决需求可拆分车辆路径问题的有效方法.     

A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet

Nowadays genetic algorithms stand as a trend to solve NP-complete and NP-hard problems. In this paper, we present a new hybrid metaheuristic which uses parallel genetic algorithms and scatter search coupled with a decomposition-into-petals procedure for solving a class of vehicle routing and scheduling problems. The parallel genetic algorithm presented is based on the island model and its performance is evaluated for a heterogeneous fleet problem, which is considered a problem much harder to solve than the homogeneous vehicle routing problem.     

嵌套分割算法在随机需求车辆路径问题中的应用研究

对需求量满足二项分布的随机需求车辆路径问题进行了研究,在服务失败时采取允许部分服务的策略,并将嵌套分割算法与扫描算法相结合,给出了一种新的求解随机需求车辆路径问题的两阶段算法,数值试验验证了该算法的有效性。同时,该算法也拓展了车辆路径问题的算法空间。     

An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem

In this paper, an enhanced ant colony optimization (EACO) is proposed for capacitated vehicle routing problem. The capacitated vehicle routing problem is to service customers with known demands by a homogeneous fleet of fixed capacity vehicles starting from a depot. It plays a major role in the field of logistics and belongs to NP-hard problems. Therefore, it is difficult to solve the capacitated vehicle routing problem directly when solutions increase exponentially with the number of serviced customers. The framework of this paper is to develop an enhanced ant colony optimization for the capacitated vehicle routing problem. It takes the advantages of simulated annealing and ant colony optimization for solving the capacitated vehicle routing problem. In the proposed algorithm, simulated annealing provides a good initial solution for ant colony optimization. Furthermore, an information gain based ant colony optimization is used to ameliorate the search performance. Computational results show that the proposed algorithm is superior to original ant colony optimization and simulated annealing separately reported on fourteen small-scale instances and twenty large-scale instances.     

基于免疫算法的车辆路径优化问题

分析了车辆路径问题的研究方法和免疫算法相对于其它进化算法的优势,提出了用免疫算法求解车辆路径问题的方法。在算法的求解过程中,构造了一种新的编码方式,在减少编码长度的基础上能够提高算法的运行效率。通过免疫记忆库的设计以及抗体之间浓度的促进和抑制机制,本算法可以实现解的多样性,避免收敛于局部最优解,同时可以有效地防止在进化的过程中失去最优解的可能性。实验结果表明,本算法可以快速求得优化解,是求解车辆路径问题的一种有效算法。     

A novel two-phase heuristic method for vehicle routing problem with backhauls

This paper raises a novel two-phase heuristic method to solve vehicle routing problems with backhauls. Differing from other vehicle routing problems, we consider the travel speed of vehicle to be time dependent, which will be used for the model of rush hour in an urban city. In the first phase, the original solution is generated by extending traditional heuristic methods and in the second phase, the reactive tabu search algorithm is used to optimize the original solution. We verified that this algorithm is efficient in a number of standard test cases. After comparison with the closest neighboring search algorithm, we found that the results of two-phase heuristic methods are more reasonable.     

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%.     

Active guided evolution strategies for large-scale vehicle routing problems with time windows

We present a new and effective metaheuristic algorithm, active guided evolution strategies, for the vehicle routing problem with time windows. The algorithm combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure. More precisely, guided local search is used to regulate a composite local search in the first stage and the neighborhood of the evolution strategies algorithm in the second stage. The vehicle routing problem with time windows is a classical problem in operations research, where the objective is to design least cost routes for a fleet of identical capacitated vehicles to service geographically scattered customers within pre-specified time windows. The presented algorithm is specifically designed for large-scale problems. The computational experiments were carried out on an extended set of 302 benchmark problems. The results demonstrate that the suggested method is highly competitive, providing the best-known solutions to 86% of all test instances within reasonable computing times. The power of the algorithm is confirmed by the results obtained on 23 capacitated vehicle routing problems from the literature.     

An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery

Along with the progress in computer hardware architecture and computational power, in order to overcome technological bottlenecks, software applications that make use of expert and intelligent systems must race against time where nanoseconds matter in the long-awaited future. This is possible with the integration of excellent solvers to software engineering methodologies that provide optimization-based decision support for planning. Since the logistics market is growing rapidly, the optimization of routing systems is of primary concern that motivates the use of vehicle routing problem (VRP) solvers as software components integrated as an optimization engine. A critical success factor of routing optimization is quality vs. response time performance. Less time-consuming and more efficient automated processes can be achieved by employing stronger solution algorithms. This study aims to solve the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) which is a popular extension of the basic Vehicle Routing Problem arising in real world applications where pickup and delivery operations are simultaneously taken into account to satisfy the vehicle capacity constraint with the objective of total travelled distance minimization. Since the problem is known to be NP-hard, a hybrid metaheuristic algorithm based on an ant colony system (ACS) and a variable neighborhood search (VNS) is developed for its solution. VNS is a powerful optimization algorithm that provides intensive local search. However, it lacks a memory structure. This weakness can be minimized by utilizing long term memory structure of ACS and hence the overall performance of the algorithm can be boosted. In the proposed algorithm, instead of ants, VNS releases pheromones on the edges while ants provide a perturbation mechanism for the integrated algorithm using the pheromone information in order to explore search space further and jump from local optima. The performance of the proposed ACS empowered VNS algorithm is studied on well-known benchmarks test problems taken from the open literature of VRPSPD for comparison purposes. Numerical results confirm that the developed approach is robust and very efficient in terms of both solution quality and CPU time since better results provided in a shorter time on benchmark data sets is a good performance indicator.     

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.     

求解非满载车辆调度问题的改进遗传算法

车辆路径问题(VRP)是一个典型的NP问题,采用传统方法求解往往找不到满意解.在分析现有求解该问题的遗传算法的基础上,对现有的变异算子进行了改进,并设计了基于自然数编码的遗传算法,用来求解非满载的车辆路径问题.计算结果表明,该算法可以更有效地求得车辆路径问题的优化解,是解决车辆路径问题的有效方法.