An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries

The Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) is an extension to the classical Vehicle Routing Problem (VRP), where customers may both receive and send goods simultaneously. The Vehicle Routing Problem with Mixed Pickup and Delivery (VRPMPD) differs from the VRPSPD in that the customers may have either pickup or delivery demand. However, the solution approaches proposed for the VRPSPD can be directly applied to the VRPMPD. In this study, an adaptive local search solution approach is developed for both the VRPSPD and the VRPMPD, which hybridizes a Simulated Annealing inspired algorithm with Variable Neighborhood Descent. The algorithm uses an adaptive threshold function that makes the algorithm self-tuning. The proposed approach is tested on well-known VRPSPD and VRPMPD benchmark instances derived from the literature. The computational results indicate that the proposed algorithm is effective in solving the problems in reasonable computation time.     

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

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

An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup

In this paper we use an ant colony system (ACS) algorithm to solve the vehicle routing problem with simultaneous delivery and pickup (VRPSDP) which is a combinatorial optimization problem. ACS is an algorithmic approach inspired by the foraging behavior of real ants. Artificial ants are used to construct a solution for the problem by using the pheromone information from previously generated solutions. The proposed ACS algorithm uses a construction rule as well as two multi-route local search schemes. The algorithm can also solve the vehicle routing problem with backhaul and mixed load (VRPBM). An extensive numerical experiment is performed on benchmark problem instances available in literature. It is found that ACS gives good results compared to the existing algorithms.     

Vessel routing with pickups and deliveries: An application to the supply of offshore oil platforms

This paper presents a new routing problem, the Vessel Routing Problem with Selective Pickups and Deliveries (VRPSPD), an extension of existing pickup and delivery problems that arises in the planning of logistics operations in the offshore oil and gas industry. The VRPSPD is a single-vessel model that can lead to significant economic improvements to the current planning scheme without having a very large impact on the operations. In addition, we formulate a Multi-Vessel Routing Problem with Pickups and Deliveries (mVRPPD) that leads to even larger economical gains, but also entails more important changes in the current planning and operations. To quantify and justify the benefits of the VRPSPD and mVRPPD, an industry case based on real data was constructed and solved for 300 days. The VRPSPD is solvable with a commercial solver for most real-size instances. However, for the mVRPPD on the largest instances, it was necessary to develop a state-of-the-art adaptive large neighborhood heuristic search to reduce computational time.     

改进变邻域搜索算法求解动态车辆路径问题

针对动态车辆路径问题DVRP(Dynamic Vehicle Routing Problem)的优化问题,提出一种改进算法。该算法在分析路径寻优问题的局部特性的基础上,利用变邻域搜索算法VNS(Variable Neighbourhood Search)对路径空间进行"局部探索",结合变异机制对路径空间进行"全局开采",最后根据近邻优先原则将动态路径片段安插到适宜的路径中。实验结果验证了算法的有效性。     

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.     

A Glowworm Swarm Optimization algorithm for the Vehicle Routing Problem with Stochastic Demands

The Glowworm Swarm Optimization (GSO) algorithm is a relatively new swarm intelligence algorithm that simulates the movement of the glowworms in a swarm based on the distance between them and on a luminescent quantity called luciferin. This algorithm has been proven very efficient in the problems that has been applied. However, there is no application of this algorithm, at least to our knowledge, in routing type problems. In this paper, this nature inspired algorithm is used in a hybrid scheme (denoted as Combinatorial Neighborhood Topology Glowworm Swarm Optimization (CNTGSO)) with other metaheuristic algorithms (Variable Neighborhood Search (VNS) algorithm and Path Relinking (PR) algorithm) for successfully solving the Vehicle Routing Problem with Stochastic Demands. The major challenge is to prove that the proposed algorithm could efficiently be applied in a difficult combinatorial optimization problem as most of the applications of the GSO algorithm concern solutions of continuous optimization problems. Thus, two different solution vectors are used, the one in the continuous space (which is updated as in the classic GSO algorithm) and the other in the discrete space and it represents the path representation of the route and is updated using Combinatorial Neighborhood Topology technique. A migration (restart) phase is, also, applied in order to replace not promising solutions and to exchange information between solutions that are in different places in the solution space. Finally, a VNS strategy is used in order to improve each glowworm separately. The algorithm is tested in two problems, the Capacitated Vehicle Routing Problem and the Vehicle Routing Problem with Stochastic Demands in a number of sets of benchmark instances giving competitive and in some instances better results compared to other algorithms from the literature.     

带多软时间窗VRP及其禁忌搜索算法

分析了带多软时间窗VRP实际应用背景和特点,以使用的车辆数、行驶费用和偏离时间窗的惩罚费用为优化目标,结合车辆载重、最大路长等限制,建立该问题的数学模型,并设计求解该问题的自适应禁忌搜索算法。为增强算法的全局寻优能力,设计了多邻域结构并在算法中嵌入一种有限地接受不可行解的自适应机制。分别用文献中的算例和以Solomon标准算例为基础构建的新算例测试该算法,并将结果与其他方法进行对比分析。对比结果表明,所提出的算法性能较好,能在可接受的时间内求出运输成本更少、满意度更高的解。     

An effective tabu search approach with improved loading algorithms for the 3L-CVRP

In this paper, we consider the Three-Dimensional Loading Capacitated Vehicle Routing Problem(3L-CVRP) which combines the routing of a fleet of vehicles and the loading of three-dimensional shaped goods into the vehicles while minimizing the total travel distance incurred. Apparently, 3L-CVRP is a combination of capacitated vehicle routing and three-dimensional bin packing problem and thus of high complexity. Different from most of previous works, we propose an innovative approach, called improved least waste heuristic for solving the loading subproblem, which is iteratively invoked by a simple tabu search algorithm for the routing. The good performance in terms of the solution quality and computational efficiency of our approach is shown through the numerical experiments on the benchmark instances from literature.     

新型遗传模拟退火算法求解带VRPTW问题

为了克服现有遗传算法不能有效求解时间窗车辆路径问题的缺陷,提出了一种由遗传算法结合模拟退火算法的混合算法求解该问题,并与遗传算法进行了比较。该算法利用了模拟退火算法具有较强的局部搜索能力的特性,有效地克服了传统遗传算法的“早熟收敛”问题。实验结果表明,该算法具有计算效率高、收敛速度快和求解质量优的特点,是解决车辆路径问题的有效方法。     

The customer-centric,multi-commodity vehicle routing problem with split delivery

In this paper, we present the Customer-centric, Multi-commodity Vehicle Routing Problem with Split Delivery (CMVRPSD) whose objective is to minimize total waiting time of customers in distributing multiple types of commodities by multiple capacitated vehicles. It is assumed that a customer's demand can be fulfilled by more than one vehicle. Two classes of decisions are involved in this problem: routing vehicles to customers and quantifying commodities to load and unload. The CMVRPSD can be applied to distributing commodities in customer-oriented distribution problems for both peacetime and disaster situations. The problem is formulated in two Mixed-Integer Linear Programming (MILP) models, and a heuristic method is proposed by adapting and synthesizing Simulated Annealing (SA) and Variable Neighborhood Search (VNS) for large-scale problems. Experimental results show that the proposed hybrid algorithm outperforms other applicable algorithms such as SA, VNS, and Nearest Neighborhood heuristic.     

求解UCARPP问题的变邻域搜索算法

针对无向网络中带有收益值有容限的弧路径问题,提出一种变邻域搜索算法。生成需求边的有序列,以相同概率初始化每条边的方向,采用分割算法构造初始解,运用6种邻域结构进行广域搜索,使用局部搜索算法改进解,利用旋轮法选择邻域结构。实验结果表明,该算法能提高效率,避免早期陷入局部最优,稳定性较好。     

不确定车辆数的有时间窗车辆选径问题的混合算法

针对标准遗传算法在求解车辆选径问题中出现的早熟、收敛、易陷入局部极值点的问题，提出了一种由遗传算法结合模拟退火算法的混合算法求解车辆选径问题，并与遗传算法进行了比较。该算法利用了模拟退火算法具有的较强的局部搜索能力的特性，有效地克服了传统遗传算法的“早熟收敛”问题。实验结果表明，该算法具有计算效率高、收敛速度快和求解质量优的特点，是解决车辆选径问题的有效方法。     

Variable Neighborhood Search heuristic for the Inventory Routing Problem in fuel delivery

In this paper we observe the extension of the vehicle routing problem (VRP) in fuel delivery that includes petrol stations inventory management and which can be classified as the Inventory Routing Problem (IRP) in fuel delivery. The objective of the IRP is to minimize the total cost of vehicle routing and inventory management. We developed a Variable Neighborhood Search (VNS) heuristic for solving a multi-product multi-period IRP in fuel delivery with multi-compartment homogeneous vehicles, and deterministic consumption that varies with each petrol station and each fuel type. The stochastic VNS heuristic is compared to a Mixed Integer Linear Programming (MILP) model and the deterministic “compartment transfer” (CT) heuristic. For three different scale problems, with different vehicle types, the developed VNS heuristic outperforms the deterministic CT heuristic. Also, for the smallest scale problem instances, the developed VNS was capable of obtaining the near optimal and optimal solutions (the MILP model was able to solve only the smallest scale problem instances).     

多目标同时取送货车辆路径问题的改进蚁群算法

为使同时取送货车辆路径问题(vehicle routing problem with simultaneous pickup and delivery, VRPSPD)的运输成本和各路径间最大长度差最小化,建立同时考虑车辆容量和距离约束的VRPSPD双目标模型,通过软件测试验证了模型准确性.针对问题的特点构造一个嵌入禁忌表、且具有贪婪转移准则的多目标蚁群算法,对蚂蚁产生的解执行多目标迭代局部搜索程序,以在多个邻域上优化该解或产生新的Pareto解.采用响应曲面法拟合算法参数对目标值影响的数学关系,确定最优参数组合.用该算法求得文献中12组Solomon算例的Pareto解集,并以绝对偏向最小化总成本的解与文献中仅最小化总成本的几种算法的计算结果进行比较,结果表明算法可求得权衡各目标且使单一目标近似最优的Pareto解.     

蜂群优化算法在车辆路径问题中的应用

车辆路径问题（VRP）是组合优化中典型的NP难题。根据车辆路径问题的实际情况,考察车辆数和总行程两个目标函数,给出了该问题的一种新的算法,蜂群算法。通过计算若干benchmark问题,并将结果与其他算法相比较与分析,验证了算法的有效性。蜂群算法是刚刚起步的智能优化算法,目前国内外关于蜂群算法的文献较少,故不仅是拓宽蜂群算法的应用范围的有效的尝试,同时也给车辆路径问题提供了一种新的解决方法。     

A List Based Threshold Accepting Algorithm for the Capacitated Vehicle Routing Problem

The aim of this study is to describe a new stochastic search meta-heuristic algorithm for solving the Capacitated Vehicle Routing Problem (CVRP), termed as the List Based Threshold Accepting (LBTA) algorithm. The main advantage of this algorithm over the majority of other meta-heuristics is that it produces quite satisfactory solutions in reasonable amount of time by tuning only one parameter of the algorithm. This property makes this algorithm a reliable and a practical tool for every decision support system designed for solving real life vehicle routing problems.     

An adaptive large neighborhood search heuristic for Two-Echelon Vehicle Routing Problems arising in city logistics

In this paper, we propose an adaptive large neighborhood search heuristic for the Two-Echelon Vehicle Routing Problem (2E-VRP) and the Location Routing Problem (LRP). The 2E-VRP arises in two-level transportation systems such as those encountered in the context of city logistics. In such systems, freight arrives at a major terminal and is shipped through intermediate satellite facilities to the final customers. The LRP can be seen as a special case of the 2E-VRP in which vehicle routing is performed only at the second level. We have developed new neighborhood search operators by exploiting the structure of the two problem classes considered and have also adapted existing operators from the literature. The operators are used in a hierarchical scheme reflecting the multi-level nature of the problem. Computational experiments conducted on several sets of instances from the literature show that our algorithm outperforms existing solution methods for the 2E-VRP and achieves excellent results on the LRP.     

A lower bound for the Node,Edge, and Arc Routing Problem

The Node, Edge, and Arc Routing Problem (NEARP) was defined by Prins and Bouchenoua in 2004, although similar problems have been studied before. This problem, also called the Mixed Capacitated General Routing Problem (MCGRP), generalizes the classical Capacitated Vehicle Routing Problem (CVRP), the Capacitated Arc Routing Problem (CARP), and the General Routing Problem. It captures important aspects of real-life routing problems that were not adequately modeled in previous Vehicle Routing Problem (VRP) variants. The authors also proposed a memetic algorithm procedure and defined a set of test instances called the CBMix benchmark. The NEARP definition and investigation contribute to the development of rich VRPs. In this paper we present the first lower bound procedure for the NEARP. It is a further development of lower bounds for the CARP. We also define two novel sets of test instances to complement the CBMix benchmark. The first is based on well-known CARP instances; the second consists of real life cases of newspaper delivery routing. We provide numerical results in the form of lower and best known upper bounds for all instances of all three benchmarks. For three of the instances, the gap between the upper and lower bound is closed. The average gap is 25.1%. As the lower bound procedure is based on a high quality lower bound procedure for the CARP, and there has been limited work on approximate solution methods for the NEARP, we suspect that a main reason for the rather large gaps is the quality of the upper bound. This fact, and the high industrial relevance of the NEARP, should motivate more research on approximate and exact methods for this important problem.     

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

This paper proposes a formulation of the vehicle routing problem with simultaneous pickup and delivery (VRPSPD) and a particle swarm optimization (PSO) algorithm for solving it. The formulation is a generalization of three existing VRPSPD formulations. The main PSO algorithm is developed based on GLNPSO, a PSO algorithm with multiple social structures. A random key-based solution representation and decoding method is proposed for implementing PSO for VRPSPD. The solution representation for VRPSPD with n customers and m   vehicles is a (n+2m)$(n+2m)$-dimensional particle. The decoding method starts by transforming the particle to a priority list of customers to enter the route and a priority matrix of vehicles to serve each customer. The vehicle routes are constructed based on the customer priority list and vehicle priority matrix. The proposed algorithm is tested using three benchmark data sets available from the literature. The computational result shows that the proposed method is competitive with other published results for solving VRPSPD. Some new best known solutions of the benchmark problem are also found by the proposed method.