Active-guided evolution strategies for large-scale capacitated vehicle routing problems

We present an adaptation of the active-guided evolution strategies metaheuristic for the capacitated vehicle routing problem. The capacitated vehicle routing problem is a classical problem in operations research in which a set of minimum total cost routes must be determined for a fleet of identical capacitated vehicles in order to service a number of demand or supply points. The applied metaheuristic combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure. The computational experiments were carried out on a set of 76 benchmark problems. The results demonstrate that the suggested method is highly competitive, providing the best-known solutions to 70 test instances.     

A hybrid algorithm for a class of vehicle routing problems

In this work we propose a hybrid algorithm for a class of Vehicle Routing Problems with homogeneous fleet. A sequence of Set Partitioning (SP) models, with columns corresponding to routes found by a metaheuristic approach, are solved, not necessarily to optimality, using a Mixed Integer Programming (MIP) solver, that may interact with the metaheuristic during its execution. Moreover, we developed a reactive mechanism that dynamically controls the dimension of the SP models when dealing with large size instances. The algorithm was extensively tested on benchmark instances of the following Vechicle Routing Problem (VRP) variants: (i) Capacitated VRP; (ii) Asymmetric VRP; (iii) Open VRP; (iv) VRP with Simultaneous Pickup and Delivery; (v) VRP with Mixed Pickup and Delivery; (vi) Multi-depot VRP; (vii) Multi-depot VRP with Mixed Pickup and Delivery. The results obtained were quite competitive with those found by heuristics devoted to specific variants. A number of new best solutions were obtained.     

改进型蚁群算法求解运输调度问题

运输调度问题是一类复杂的组合优化问题，是近年来物流控制优化中的研究热点。通过对基本蚁群算法中的选择策略和信息素挥发速度的改进，提出了一种新的蚁群算法，克服了基本蚁群算法搜索时间长、易陷入局部最优解等缺陷，将其用于求解一类运输调度问题，实验发现算法有效，并且对于规模越大的问题，相对其它算法有更优的解。     

An interactive computerized algorithm for multicriteria vehicle routing problems

The Multicriteria vehicle routing problem (VRP) is a VRP which allows several relevant objectives to be achieved. The use of an interactive computer program combined with a powerful vehicle routing algorithm can be a valuable tool in the hands of a scheduler who can apply his own skills and knowledge to full effect in conjunction with the speed and flexibility of the computer program.

An interactive computerized algorithm is developed that utilizes a heuristic algorithm to determine the most favorable vehicle routes for multicriteria VRPs. This algorithm takes into account that the problem being addressed may in fact be complicated by several conflicting objectives. Although many different objectives could be considered, the specific model presented here consists of the following three relevant objectives: minimization of the travel distance of vehicles, minimization of total deterioration of goods during transportation, and maximization of the total fulfillment of emergent services and conditional dependencies of stations.

The interactive algorithm successfully performs the trade-off between the achievement levels of the objectives through changes of the decision maker's goal priority structure, the target values of the objectives, and the subsets formation of stations.     

A hybrid genetic algorithm that optimizes capacitated vehicle routing problems

This study primarily focuses on solving a capacitated vehicle routing problem (CVRP) by applying a novel hybrid genetic algorithm (HGA) capable of practical use for manufacturers. The proposed HGA has three stages. First, the nearest addition method (NAM) was incorporated into sweep algorithm (SA) that simultaneously accounts for axial and radius relationships among distribution points with the depot to generate a well-structured initial chromosome population, rather than adopting either the NAM OR SA alone. Second, response surface methodology (RSM) was employed to optimize crossover probability and mutation probability via systematic experiments. Finally, an improved sweep algorithm was incorporated into the GA, producing a stir over gene permutations in chromosomes that enhance the exploration diversity of the GA, thereby avoiding convergence in a limited region, and enhancing the search capability of the GA in approaching a close-to-optimal solution. Furthermore, an elitism conservation strategy holding superior chromosomes to replace inferior chromosomes was also performed. As the proposed HGA is primarily used to solve practical problem, benchmark problems with fewer than 100 distribution points from an Internet website were utilized to confirm the effectiveness of the proposed HGA. A real case regarding the mission of local active distribution from armed forces in Taiwan details the analytical process and demonstrates the practicability of the proposed HGA to optimize the CVRP.     

A general heuristic for vehicle routing problems

We present a unified heuristic which is able to solve five different variants of the vehicle routing problem: the vehicle routing problem with time windows (VRPTW), the capacitated vehicle routing problem (CVRP), the multi-depot vehicle routing problem (MDVRP), the site-dependent vehicle routing problem (SDVRP) and the open vehicle routing problem (OVRP).     

求解绿色车辆路径问题的离散乌贼算法

为求解绿色车辆路径问题(green vehicle routing problem),提出一种离散乌贼算法(DCOA).采用轮盘赌机制增强初始解选择的随机性,引入精英片段插入策略指导乌贼细胞群的进化方向,提高搜索效率,利用2-opt法和shift法优化当前细胞,增强最优解的局部开发能力.选取Augerat标准数据集,对...     

A 2-phase constructive algorithm for cumulative vehicle routing problems with limited duration

The Clarke & Wright (C&W) algorithm is one of the most widely used classical heuristics in capacitated Vehicle Routing Problems (VRPs) in which a linear function of distance is considered as the objective function. The C&W algorithm is very simple and easy to implement, and produces fairly good solutions very fast. In this study, the C&W algorithm is adopted for the cumulative VRP with limited duration (CumVRP-LD) where load is also considered in the objective function as well as distance. The most common applications of cumulative VRPs are the determination of routing policies that minimize total fuel consumption. A 2-phase constructive heuristic approach including the K-means clustering algorithm is proposed to improve the computational performance of the modified C&W algorithm for CumVRP-LD. The main contribution of this study is the definition of a new extended formulation that captures truck-load and travel distance by considering the unique characteristics of the problem and to develop a fast and easy implemented constructive algorithm for CumVRP-LD. Such approaches are necessary for the development of systems that respond fast, possibly online, to changes in the real problem situations.     

带时间窗车辆路径问题的差分进化混合算法

研究了带时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW),建立了数学模型,并设计了求解VRPTW的离散差分进化混合算法。算法采用随机车辆配载方法构造初始解,并通过构造新的变异和交叉算子进行改进。进一步,利用插入可行邻域和2-Opt可行邻域两种搜索可行解的邻域结构,引入禁忌搜索进一步进行局部搜索以提高算法的寻优能力。实验结果表明该算法是求解VRPTW的一种有效方法。     

A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows

This paper presents a hybrid evolutionary algorithm (HEA) to solve heterogeneous fleet vehicle routing problems with time windows. There are two main types of such problems, namely the fleet size and mix vehicle routing problem with time windows (F) and the heterogeneous fixed fleet vehicle routing problem with time windows (H), where the latter, in contrast to the former, assumes a limited availability of vehicles. The main objective is to minimize the fixed vehicle cost and the distribution cost, where the latter can be defined with respect to en-route time (T) or distance (D). The proposed unified algorithm is able to solve the four variants of heterogeneous fleet routing problem, called FT, FD, HT and HD, where the last variant is new. The HEA successfully combines several metaheuristics and offers a number of new advanced efficient procedures tailored to handle the heterogeneous fleet dimension. Extensive computational experiments on benchmark instances have shown that the HEA is highly effective on FT, FD and HT. In particular, out of the 360 instances we obtained 75 new best solutions and matched 102 within reasonable computational times. New benchmark results on HD are also presented.     

An effective evolutionary algorithm for the practical capacitated vehicle routing problems

The evolutionary algorithms are extensively adopted to resolve complex optimization problem. Genetic algorithm (GA), an evolutionary algorithm, has been proved capable of solving vehicle routing problems (VRPs). However, the resolution effectiveness of GA decreases with the increase of nodes within VRPs. Normally, a hybrid GA outperforms pure GA. This study attempts to solve a capacitated vehicle routing problem (CVRP) by applying a novel hybrid genetic algorithm (HGA) that is practical for use by manufacturers. The proposed HGA involves three stages. First, a diverse and well-structured initial chromosome population was constructed. Second, response surface methodology (RSM) experiments were conducted to optimize the crossover and mutation probabilities in performing GA. Finally, a combined heuristics containing improved insertion algorithm and random insertion mutation operator was established to stir over gene permutations and enhance the exploration capability of GA diversely. Furthermore, an elitism conservation strategy was implemented that replace inferior chromosomes with superior ones. As the proposed HGA is primarily used to solve practical problems, benchmark problems involving fewer than 100 nodes from an Internet website were utilized to confirm the feasibility of the proposed HGA. Two real cases one for locally active distribution and another for arms part transportation at a combined maintenance facility, both involving the Taiwanese armed forces are used to detail the analytical process and demonstrate the practicability of the proposed HGA for optimizing the CVRP.     

Honey Bees Mating Optimization algorithm for large scale vehicle routing problems

Honey Bees Mating Optimization algorithm is a relatively new nature inspired algorithm. In this paper, this nature inspired algorithm is used in a hybrid scheme with other metaheuristic algorithms for successfully solving the Vehicle Routing Problem. More precisely, the proposed algorithm for the solution of the Vehicle Routing Problem, the Honey Bees Mating Optimization (HBMOVRP), combines a Honey Bees Mating Optimization (HBMO) algorithm with the Multiple Phase Neighborhood Search–Greedy Randomized Adaptive Search Procedure (MPNS–GRASP) and the Expanding Neighborhood Search (ENS) algorithm. Besides these two procedures, the proposed algorithm has, also, two additional main innovative features compared to other Honey Bees Mating Optimization algorithms concerning the crossover operator and the workers. Two sets of benchmark instances are used in order to test the proposed algorithm. The results obtained for both sets are very satisfactory. More specifically, in the fourteen classic instances proposed by Christofides, the average quality is 0.029% and in the second set with the twenty large scale vehicle routing problems the average quality is 0.40%.     

A genetic algorithm for vehicle routing with backhauling

In this paper, a greedy route construction heuristic for a vehicle routing problem with backhauling is described. This heuristic inserts customers one by one into the routes using a fixed a priori ordering of customers. Then, a genetic algorithm is used to identify an ordering that produces good routes. Numerical comparisons are provided with an exact algorithm and with other heuristic approaches.     

A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows

This paper presents a two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows and multiple vehicles (PDPTW). The first stage uses a simple simulated annealing algorithm to decrease the number of routes, while the second stage uses Large neighborhood search (LNS) to decrease total travel cost. Experimental results show the effectiveness of the algorithm which has produced many new best solutions on problems with 100, 200, and 600 customers. In particular, it has improved 47% and 76% of the best solutions on the 200 and 600-customer benchmarks, sometimes by as much as 3 vehicles. These results further confirm the benefits of two-stage approaches in vehicle routing. They also answer positively the open issue in the original LNS paper, which advocated the use of LNS for the PDPTW and argue for the robustness of LNS with respect to side-constraints.     

Stochastic techniques for vehicle routing problems

Vehicle routing problems (VRPs) are resource management problems where the aim is to use the limited number of resources to a large number of jobs so that a maximum number of jobs can be completed with minimum cost. These problems are made complicated by the inclusion of temporal and technological constraints. These problems belong to the class of nondeterministic polynominal-time complete (NP) problems. This paper describes the application of stochastic techniques, namely simulated annealing (SA) and genetic algorithm (GA), to solve VRPs. It is found empirically that SA gives better results than GA for all randomly generated under-, critically- and over-resourced VRPs in almost all cases.     

A particle swarm optimization algorithm for open vehicle routing problem

This paper presents a real-value version of particle swarm optimization (PSO) for solving the open vehicle routing problem (OVRP) that is a well-known combinatorial optimization problem. In OVRP a vehicle does not return to the depot after servicing the last customer on a route. A particular decoding method is proposed for implementing PSO for OVRP. In the decoding method, a vector of the customer’s position is constructed in descending order. Then each customer is assigned to a route with taking into account feasibility conditions. Finally one-point move has been applied on constructed routes that seem promising to result in a better solution. Experimental evaluations on benchmark data sets demonstrate the competitiveness of the proposed algorithm.     

A competitive neural network algorithm for solving vehicle routing problem

This paper describes a self organization Neural Network algorithm for a class of Vehicle Routing Problems. Motivated by the outstanding performance of adaptive Neural Network approach in the Traveling Salesman Problem, we devised an algorithm to extend the domain of applicability of this approach to more complex problems. First, relevant adaptation is proposed to refine the model for the Multiple Traveling Salesman Problem. Then, an additional mechanism to satisfy further constraints are embodied into the algorithm. The effectiveness of the proposed algorithm is evaluated by considering a series of standard problems from the literature. The results show that the algorithm can yield solutions within a few percent of optimality.     

A hybrid algorithm for vehicle routing problem with time windows

Vehicle routing problem with time windows (VRPTW) is a well-known combinatorial problem. Many researches have presented meta-heuristics are effective approaches for VRPTW. This paper proposes a hybrid approach, which consists of ant colony optimization (ACO) and Tabu search, to solve the problem. To improve the performance of ACO, a neighborhood search is introduced. Furthermore, when ACO is close to the convergence Tabu search is used to maintain the diversity of ACO and explore new solutions. Computational experiments are reported for a set of the Solomon’s 56 VRPTW and the approach is compared with some meta-heuristic published in literature. Results show that considering the tradeoff of quality and computation time, the hybrid algorithm is a competitive approach for VRPTW.