Tabu Search heuristics for the Vehicle Routing Problem with Time Windows

This paper surveys the research on the Tabu Search heuristics for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes for a fleet of vehicles from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval; all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. In addition to describing basic features of each method, experimental results for Solomon’s benchmark test problems are presented and analyzed. This work was partially supported by the Emil Aaltonen Foundation, Liikesivistysrahasto Foundation, the Canadian Natural Science and Engineering Research Council and the TOP program funded by the Research Council of Norway. This support is gratefully acknowledged.     

A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints

We present a metaheuristic methodology for the Capacitated Vehicle Routing Problem with two-dimensional loading constraints (2L-CVRP). 2L-CVRP is a generalisation of the Capacitated Vehicle Routing Problem, in which customer demand is formed by a set of two-dimensional, rectangular, weighted items. The purpose of this problem is to produce the minimum cost routes, starting and terminating at a central depot, to satisfy the customer demand. Furthermore, the transported items must be feasibly packed into the loading surfaces of the vehicles. We propose a metaheuristic algorithm which incorporates the rationale of Tabu Search and Guided Local Search. The loading aspects of the problem are tackled using a collection of packing heuristics. To accelerate the search process, we reduce the neighbourhoods explored, and employ a memory structure to record the loading feasibility information. Extensive experiments were conducted to calibrate the algorithmic parameters. The effectiveness of the proposed metaheuristic algorithm was tested on benchmark instances and led to several new best solutions.     

A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem

This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP generalizes the classical Capacitated Vehicle Routing Problem by considering the existence of different vehicle types, with distinct capacities and costs. The objective is to determine the best fleet composition as well as the set of routes that minimize the total costs. The proposed hybrid algorithm is composed by an Iterated Local Search (ILS) based heuristic and a Set Partitioning (SP) formulation. The SP model is solved by means of a Mixed Integer Programming solver that interactively calls the ILS heuristic during its execution. The developed algorithm was tested in benchmark instances with up to 360 customers. The results obtained are quite competitive with those found in the literature and new improved solutions are reported.     

一种带时间窗和容量约束的车辆路线问题及其Tabu Search算法

本文提出一种带时间窗和容量约束的车辆路线问题（CVRPTW），并利用Tabu Search快速启式算法，针对Solomon提出的几个标准问题，快捷地得到了优良的数值结果。     

带集货和配送的多站点VRP优化算法研究

带集货和配送的多站点车辆路线问题(M DVRPPD)是经典VRP的扩展,是多个站点和若干客户既有需求又有供给的VRP问题.研究了该问题的模型并提出了求解该问题的多阶段启发式算法,即先用临界客户的思想把多站点转换为单一站点问题,再使用基于SFC的分组方法来构造初始解,并运用3-opt算法优化回路,之后采用插入算法改善解的可行性,从而得到最终优化解.最后通过实例计算证明了该方法解决M DVRPPD问题的实用可行性和科学有效性.     

High-Level Relay Hybrid Metaheuristic Method for Multi-Depot Vehicle Routing Problem with Time Windows

This paper presents an efficient hybrid metaheuristic solution for multi-depot vehicle routing with time windows (MD-VRPTW). MD-VRPTW involves the routing of a set of vehicles with limited capacity from a set of depots to a set of geographically dispersed customers with known demands and predefined time windows. The present work aims at using a hybrid metaheuristic algorithm in the class of High-Level Relay Hybrid (HRH) which works in three levels and uses an efficient genetic algorithm as the main optimization algorithm and tabu search as an improvement method. In the genetic algorithm various heuristics incorporate local exploitation in the evolutionary search. An operator deletion- retrieval strategy is executed which shows the efficiency of the inner working of the proposed method. The proposed algorithm is applied to solve the problems of the standard Cordeau??s Instances. Results show that proposed approach is quite effective, as it provides solutions that are competitive with the best known in the literature.     

A Neural-Tabu Search Heuristic for the Real Time Vehicle Routing Problem

The Real Time Vehicle Routing Problem RTVRP is a dynamic routing problem where requests are generated dynamically during the operation horizon without any previous knowledge. Received requests need to be answered as fast as possible and then assigned to a vehicle to be served. Due to timing constraints of the RTVRP, a solving approach should give the best compromise between the cost of the provided solution and the computation time needed to find it. In this paper, we present a neural-tabu search solving scheme for the RTVRP. The developed approach is composed by two phases; The first part consists of learning and reproducing previous routing decisions using a feed forward neural network with a particular structure. The second phase is based on a tabu search heuristic that takes its initial solution from the assignment provided by the neural module. If the reaction time is still available, the tabu search module will continue ameliorating the final solution. To evaluate the proposed approach a set of problems are simulated and solved. The obtained results are compared to those given by the First Come First Served FCFS and Nearest Neighbor NN policies and also to the optimal solutions provided by the GNU Linear Programming Kit GLPK.      

A memetic algorithm for the Multi Trip Vehicle Routing Problem

We consider the Multi Trip Vehicle Routing Problem, in which a set of geographically scattered customers have to be served by a fleet of vehicles. Each vehicle can perform several trips during the working day. The objective is to minimize the total travel time while respecting temporal and capacity constraints.     

A Tabu Search Algorithm for the Quadratic Assignment Problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). One of the most important features of our tabu search implementation is an efficient use of mutations applied to the best solutions found so far. We tested this approach on a number of instances from the library of the QAP instances—QAPLIB. The results obtained from the experiments show that the proposed algorithm belongs to the most efficient heuristics for the QAP. The high efficiency of this algorithm is also demonstrated by the fact that the new best known solutions were found for several QAP instances.     

基于GIS和禁忌搜索集成技术的农产品物流配送路径优化

分析农产品物流配送模式,对带时间窗的车辆路径问题进行描述,建立有时限的配送路径优化模型,应用GIS与禁忌搜索算法集成技术求解该模型,开发农产品物流配送路径优化系统,并以晋安区农产品物流配送基础数据为范例,进行系统的初步应用研究.     

A Tabu Search Algorithm for the Resource-Constrained Assignment Problem

Efficient algorithms are availabe to solve the unconstrained assignment problem. However, when resource or budgetary restrictions are imposed, the problem becomes difficult to solve. We consider such a resource-constrained assignment problem and present a tabu search heuristic to solve it. Extensive computational results are presented which establish the superiority of the proposed algorithm over the existing algorithms. Our adaptation of tabu search uses strategic oscillation, randomized short-term memory and multiple start as a means of search diversification.     

带服务优先级车辆路径问题的扫描禁忌搜索算法

提出了一种带服务优先级车辆路径问题的模型(Vehicle Routing Problem with Precedence Constraints,VRPPC),和一种扫描—禁忌搜索算法(sweep-Taboo Search Algorithm,S-TSA).然后,运用S-TSA对郑煤物资供销有限公司的带有服务优先级的危险物资配送进行优化求解,并与扫描遗传算法(sweep-Genetic Algorithm,SGA),禁忌搜索算法(Taboo Search Algorithm,TSA),人工鱼群算法(Artificial Fish Algorithm,AFA)进行比较研究,研究结果显示:扫描禁忌搜索算法能在满足服务优先级的前提下,使配送费用最少.     

A multi-start algorithm for a balanced real-world Open Vehicle Routing Problem

The aim of this paper is to solve a real-world problem proposed by an international company operating in Spain and modeled as a variant of the Open Vehicle Routing Problem in which the makespan, i.e., the maximum time spent on the vehicle by one person, must be minimized. A competitive multi-start algorithm, able to obtain high quality solutions within reasonable computing time is proposed. The effectiveness of the algorithm is analyzed through computational testing on a set of 19 school-bus routing benchmark problems from the literature, and on 9 hard real-world problem instances.     

有时间窗的车辆路径问题的局部下降搜索算法

介绍了一个求解有时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW)的启发式算法——基于λ-交换的局部下降搜索算法(Local search descent method based on λ-interchange).VRPTW是指合理安排车辆行驶路线,为一组预先设定有时间限制的客户运送货物,在不违反时间要求和车辆容量限制的条件下使得成本最小.它是一个典型的NP-难题,可以通过启发式算法获得近优解来解决.通过两个实验验证,显示了局部下降搜索算法的优良性能,取得了很好的效果,可以作为进一步研究复杂算法的基础.     

A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows

The aim of this paper is to propose an algorithm based on the philosophy of the Variable Neighborhood Search (VNS) to solve Multi Depot Vehicle Routing Problems with Time Windows. The paper has two main contributions. First, from a technical point of view, it presents the first application of a VNS for this problem and several design issues of VNS algorithms are discussed. Second, from a problem oriented point of view the computational results show that the approach is competitive with an existing Tabu Search algorithm with respect to both solution quality and computation times.     

An Iterated Local Search heuristic for the Heterogeneous Fleet Vehicle Routing Problem

This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP is $\mathcal{NP}$ -hard since it is a generalization of the classical Vehicle Routing Problem (VRP), in which clients are served by a heterogeneous fleet of vehicles with distinct capacities and costs. The objective is to design a set of routes in such a way that the sum of the costs is minimized. The proposed algorithm is based on the Iterated Local Search (ILS) metaheuristic which uses a Variable Neighborhood Descent procedure, with a random neighborhood ordering (RVND), in the local search phase. To the best of our knowledge, this is the first ILS approach for the HFVRP. The developed heuristic was tested on well-known benchmark instances involving 20, 50, 75 and 100 customers. These test-problems also include dependent and/or fixed costs according to the vehicle type. The results obtained are quite competitive when compared to other algorithms found in the literature.     

Tabu Search Heuristics for the Arc Routing Problem with Intermediate Facilities under Capacity and Length Restrictions

This paper deals with the Arc Routing Problem with Intermediate Facilities under Capacity and Length Restrictions(CLARPIF), a variant of the classical Capacitated Arc Routing Problem(CARP), in which vehicles may unload or replenish at intermediate facilities and the length of any route may not exceed a specified upper bound. Three heuristics are developed for the CLARPIF: the first is a constructive procedure based on a partitioning approach while the second and the third are tailored Tabu Search procedures. Computational results on a set of benchmark instances with up to 50 vertices and 92 required edges are presented and analyzed.     

A Tabu Search Approach for the Resource Constrained Project Scheduling Problem

An appropriate tabu search implementation is designed to solve the resource constrained project scheduling problem. This approach uses well defined move strategies and a structured neighbourhood, defines appropriate tabu status and tenure and takes account of objective function approximation to speed up the search process. A sound understanding of the problem has helped in many ways in designing and enhancing the tabu search methodology. The method uses diversification, intensification and handles infeasibility via strategic oscillation.The above methodology is tested on existing problems from the literature and also on parametrically generated problems with encouraging results. For comparison of results, optimal solutions are used in the former and lower bounds obtained by Lagrangian heuristics are used in the latter.     

A General Vehicle Routing Problem

In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.     

A Tabu Search Algorithm for Quadratic 0—1 Programming Problem

1.IntroductionThemathematicalmodelofaquaduatico-1programmingproblemisasfollows:MinimizesubjecttwhereI,AsfaraspaperL1'2Jcanseemedel(I)(fordu=O)isveryimPOrtantinthemarshallingofsinglegrouptrainbetweenmarshallingstationsinrailwaynetworkandthemarshallingoftraininnetw0rkwiththetw0types0fvehiclefl0w,butproblem(I)isNP-C.C0nsiderarelax-ationproblemasf0llows:MinimizeIngeneral,solvingrelaxati0nproblemiseasierthansolvingcombinatiorial0ptimalpr0b-lem,thesameaslinearpr0grammingproblemissolvableinPOly…