A general variable neighborhood search for the swap-body vehicle routing problem

The Swap-Body Vehicle Routing Problem, a generalization of the well known Vehicle Routing Problem, can be stated as follows: the vehicle fleet consisting of trucks, semi-trailers, and swap bodies, is available at a single depot to serve a given set of customers. To serve a subset of customers, one may use either a truck carrying one swap body or a train (a truck with a semi-trailer attached to it) carrying two swap bodies. In both cases, a vehicle (a truck or a train) must perform a route starting and ending at the depot, so to satisfy demands of visited customers, maximal allowed route duration, allowed load on the used vehicle, and accessibility constraint of each customer. The accessibility constraint indicates whether a customer is allowed to be visited by a train or not. In addition, a set of swap locations is given where semi-trailers and swap bodies may be parked or swapped. The goal of the Swap-Body Vehicle Routing Problem is to minimize the total costs consisting of the fixed costs for using vehicles and costs for performing routes. In this paper, we propose two general variable neighborhood search heuristics to solve this problem. The quality of the proposed methods is evaluated on the instances provided by the organizers of VeRolog Solver Challenge 2014.     

Skewed general variable neighborhood search for the location routing scheduling problem

The integrated location routing scheduling problem is a variant of the well-known location routing problem. The location routing problem consists in selecting a set of depots to open and in building a set of routes from these depots, to serve a set of customers at minimum cost. In this variant, a vehicle can perform more than a single route in the planning period. As a consequence, the routes have to be scheduled within the workdays of each vehicle. The problem arises typically when routes are constrained to have a short duration. It happens for example within the boundaries of small geographic areas or in the transportation of perishable goods. In this paper, we propose a skewed general variable neighborhood search based heuristic to solve it. The algorithm is tested extensively and we show that it is efficient and provides the proven optimal solution in a significant number of cases. Moreover, it clearly outperforms a multi-start VND based heuristic that uses the same neighborhood structures.     

Variable neighborhood search for the pharmacy duty scheduling problem

In this paper, we study on the Pharmacy Duty Scheduling (PDS) problem, where a subset of pharmacies should be on duty on national holidays, at weekends and at nights in order to be able to satisfy the emergency drug needs of the society. PDS problem is a multi-period p-median problem with special side constraints and it is an NP-Hard problem. We propose four Variable Neighborhood Search (VNS) heuristics. The first one is the basic version, BVNS. The latter two, Variable Neighborhood Decomposition Search (VNDS) and Variable Neighborhood Restricted Search (VNRS), aim to obtain better results in less computing time by decomposing or restricting the search space. The last one, Reduced VNS (RVNS), is for obtaining good initial solutions rapidly for BVNS, VNDS and VNRS. We test BVNS, VNRS and VNDS heuristics on randomly generated instances and report the computational test results. We also use VNS heuristics on real data for the pharmacies in central İzmir and obtain significant improvements.     

Variable neighborhood descent with iterated local search for routing and wavelength assignment

In this work we treat the Routing and Wavelength Assignment (RWA) with focus on minimizing the number of wavelengths to route demand requests. Lightpaths are used to carry the traffic optically between origin-destination pairs. The RWA is subjected to wavelength continuity constraints, and a particular wavelength cannot be assigned to two different lightpaths sharing a common physical link. We develop a Variable Neighborhood Descent (VND) with Iterated Local Search (ILS) for the problem. In a VND phase we try to rearrange requests between subgraphs associated to subsets of a partition of the set of lightpath requests. In a feasible solution, lightpaths belonging to a subset can be routed with the same wavelength. Thus, the purpose is to eliminate one subset of the partition. When VND fails, we perform a ILS phase to disturb the requests distribution among the subsets of the partition. An iteration of the algorithm alternates between a VND phase and a ILS phase. We report computational experiments that show VND-ILS was able to improve results upon powerful methods proposed in the literature.     

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.     

A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows

This paper presents a new hybrid variable neighborhood-tabu search heuristic for the Vehicle Routing Problem with Multiple Time windows. It also proposes a minimum backward time slack algorithm applicable to a multiple time windows environment. This algorithm records the minimum waiting time and the minimum delay during route generation and adjusts the arrival and departure times backward. The implementation of the proposed heuristic is compared to an ant colony heuristic on benchmark instances involving multiple time windows. Computational results on newly generated instances are provided.     

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.     

Variable neighborhood search for multi-objective resource allocation problems

The Resource Allocation Problem (RAP) is a classical problem in the field of operations management that has been broadly applied to real problems such as product allocation, project budgeting, resource distribution, and weapon-target assignment. In addition to focusing on a single objective, the RAP may seek to simultaneously optimize several expected but conflicting goals under conditions of resources scarcity. Thus, the single-objective RAP can be intuitively extended to become a Multi-Objective Resource Allocation Problem (MORAP) that also falls in the category of NP-Hard. Due to the complexity of the problem, metaheuristics have been proposed as a practical alternative in the selection of techniques for finding a solution. This study uses Variable Neighborhood Search (VNS) algorithms, one of the extensively used metaheuristic approaches, to solve the MORAP with two important but conflicting objectives—minimization of cost and maximization of efficiency. VNS searches the solution space by systematically changing the neighborhoods. Therefore, proper design of neighborhood structures, base solution selection strategy, and perturbation operators are used to help build a well-balanced set of non-dominated solutions. Two test instances from the literature are used to compare the performance of the competing algorithms including a hybrid genetic algorithm and an ant colony optimization algorithm. Moreover, two large instances are generated to further verify the performance of the proposed VNS algorithms. The approximated Pareto front obtained from the competing algorithms is compared with a reference Pareto front by the exhaustive search method. Three measures are considered to evaluate algorithm performance: D1_R, the Accuracy Ratio, and the number of non-dominated solutions. The results demonstrate the practicability and promise of VNS for solving multi-objective resource allocation problems.     

Variable neighborhood search and local branching

In this paper we develop a variable neighborhood search (VNS) heuristic for solving mixed-integer programs (MIPs). It uses CPLEX, the general-purpose MIP solver, as a black-box. Neighborhoods around the incumbent solution are defined by adding constraints to the original problem, as suggested in the recent local branching (LB) method of Fischetti and Lodi (Mathematical Programming Series B 2003;98:23–47). Both LB and VNS use the same tools: CPLEX and the same definition of the neighborhoods around the incumbent. However, our VNS is simpler and more systematic in neighborhood exploration. Consequently, within the same time limit, we were able to improve 14 times the best known solution from the set of 29 hard problem instances used to test LB.     

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.     

Variable neighborhood search variants for Min-power symmetric connectivity problem

We consider the problem of optimal communication tree construction in a given undirected weighted graph. Such a problem occurs while minimizing the power consumption of data transmission in different distributed networks in the case when network elements are able to adjust their transmission ranges. In this paper, the most general strongly NP-hard formulation, when edge weights have arbitrary non-negative values, is considered. We propose new heuristics, mostly based on variable neighborhood search, for getting an approximate solution of the problem. Extensive comparative analysis between the proposed methods was performed. Numerical experiments demonstrated the high efficiency of the proposed heuristics.     

Variable neighborhood search for two-agent flow shop scheduling problem

Multi-agent scheduling in flow shop environment is seldom considered. In this paper flow shop scheduling problem with two agents is studied and its feasibility model is considered, in which the goal is to minimize the makespan of the first agent and the total tardiness of the second agent simultaneously under the given upper bounds. A simple variable neighborhood search (VNS) algorithm is proposed, in which a learning neighborhood structure is constructed to produce new solutions and a new principle is applied to decide if the current solution can be replaced with the new one. VNS is tested on a number of instances and the computational results show the promising advantage of VNS when compared to other algorithms of the problem.     

Variable neighborhood search algorithms for the vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls

In this paper, we explore a vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls. The addressed problem belongs to a subclass of general pickup and delivery problems. Two‐dimensional loading constraints are also considered. These constraints arise in many real‐world situations and can improve efficiency since backhaul customers do not need to be delayed in a route when it is possible to load their items earlier and without rearrangements of the items. To tackle this problem, we report extensive computational experiments to assess the performance of different variants of the variable neighborhood search approaches. The initial solution relies on an insertion heuristic. Both shaking and local search phases resort to 10 neighborhood structures. Some of those structures were specially developed for this problem. The feasibility of routes is heuristically obtained with a classical bottom‐left based method to tackle the explicit consideration of loading constraints. All the strategies were implemented and exhaustively tested on instances adapted from the literature. The results of this computational study are discussed at the end of this paper.     

A two-level self-adaptive variable neighborhood search algorithm for the prize-collecting vehicle routing problem

This paper investigates the prize-collecting vehicle routing problem (PCVRP), which has a strong background in practical industries. In the PCVRP, the capacities of all available vehicles are not sufficient to satisfy the demands of all customers. Consequently it is not a compulsory requirement that all customers should be visited. However, a prize can be collected once a customer is visited. In addition, it is required that the total demands of visited customers should reach a pre-specified value at least. The objective is to establish a schedule of vehicle routes so as to minimize the total transportation cost and at the same time maximize the prize collected by all vehicles. The total transportation cost consists of the total distance of vehicle routes and the sum of vehicles used in the schedule. To solve the PCVRP, a two-level self-adaptive variable neighborhood search (TLSAVNS) algorithm is developed according to the two levels of decisions in the PCVRP, namely the selection of customers to visit and the visiting sequence of selected customers in each vehicle route. The proposed TLSAVNS algorithm is self-adaptive because the neighborhoods and their search sequence are determined automatically by the algorithm itself based on the analysis of its search history. In addition, a graph extension method is adopted to obtain the lower bound for PCVRP by transforming the proposed mixed integer programming model of PCVRP into an equivalent traveling salesman problem (TSP) model, and the obtained lower bound is used to evaluate the proposed TLSAVNS algorithm. Computational results on benchmark problems show that the proposed TLSAVNS algorithm is efficient for PCVRP.     

多目标同时取送货选址–路径问题的多起点变邻域搜索算法

为使同时取送货的选址–路径问题(LRPSPD)的总成本和各路径间最大长度差最小化, 建立同时考虑车辆容量和行驶里程约束的LRPSPD双目标模型. 采用多蚁群算法构造多个以信息素为关联的初始解, 作为多目标变邻域搜索算法搜索的多个起点, 构造四类邻域结构进行变邻域搜索, 并根据最新获得的最优邻域解更新蚂蚁信息素,从而使蚁群算法产生的多个初始解间、以及初始解与变邻域搜索产生的解之间均存在正向影响关系. 用该算法求得文献中4组共128个算例的近似Pareto解集, 结果证明了最小化路径间最大长度差目标对于节点及需求分布不集中算例的重要意义. 以绝对偏向最小化总成本的解与文献中仅最小化总成本的几种算法的算例结果进行比较, 结果表明算法可在极短的运行时间里求得权衡各目标的Pareto解, 并使最小总成本目标值具有竞争性.     

Variable neighborhood search for the workload balancing problem in service enterprises

In this paper, we consider a telecommunication service company facing seasonal demand and time-varying capacity. A uniform lead-time, which is the maximum time span a customer has to wait before receiving the required service, is quoted to all customers. We present a quadratic integer programming model for the problem of scheduling jobs to meet the promised lead-time with the objective of balancing the workload across time. Since in practice solving such a problem to optimality can be very difficult, two variants of a variable neighborhood search approach are proposed. Extensive computational tests show that our heuristics are able to provide high quality solutions efficiently.     

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.     

Variable neighborhood search algorithm for heterogeneous traveling repairmen problem with time windows

The focus of this paper is generalized traveling repairman problem (TRP), a special case of the well known and well studied traveling salesman problem (TSP). Because of its specific objective function, that minimizes the sum of overall time all clients wait for until the end of a service, TRP has great applicability potential in client oriented practical problems. Therefore it has been known in literature as traveling deliveryman problem, minimum latency problem and cumulative capacitated vehicle routing problem. However, most studies that have treated TRP related problems have implied that only one repairman is present in the system and/or that all clients are available for service at the beginning of the planning horizon. In this paper we consider a TRP with a heterogeneous fleet of repairmen serving a set of clients whose arrival times are distributed over a planning horizon, i.e. heterogeneous TRPTW (hetTRPTW). For the hetTRPTW we present a mixed integer linear programming model, and a heuristic algorithm based on a variable neighborhood search (VNS) framework. Additionally, we propose a reduction strategy for neighborhoods in the VNS algorithm and test efficiency of implemented algorithms on four benchmark sets of problem instances. Results show that proposed algorithms could be used in real systems for solving small and moderate problem instances.     

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.     

多舱共配绿色车辆路径问题的改进变邻域搜索算法

针对社区团购前置仓配送场景中“多中心、高时效、多品类、高排放”难题, 本文提出多车场带时间窗的绿色多舱车车辆路径问题(MDMCG-VRPTW), 构建混合整数线性规划模型, 并设计改进的变邻域搜索算法(IVNS)实现求解. 采用两阶段混合算法构造高质量初始解. 提出均衡抖动策略以充分探索解空间, 引入粒度机制以提升局部搜索阶段的寻优效率. 标准算例测试结果验证了两阶段初始解构造算法和IVNS算法的有效性. 仿真实验结果表明,模型与算法能够有效求解MDMCGVRPTW, 且改进策略提高了算法的求解效率和全局搜索能力. 最后, 基于对配送策略和时效性的敏感性分析, 为相关配送企业降本增效提供更多决策依据.