0000000000132676
AUTHOR
Olli Bräysy
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, …
A well-scalable metaheuristic for the fleet size and mix vehicle routing problem with time windows
This paper presents an efficient and well-scalable metaheuristic for fleet size and mix vehicle routing with time windows. The suggested solution method combines the strengths of well-known threshold accepting and guided local search metaheuristics to guide a set of four local search heuristics. The computational tests were done using the benchmarks of [Liu, F.-H., & Shen, S.-Y. (1999). The fleet size and mix vehicle routing problem with time windows. Journal of the Operational Research Society, 50(7), 721-732] and 600 new benchmark problems suggested in this paper. The results indicate that the suggested method is competitive and scales almost linearly up to instances with 1000 custome…
The potential of optimization in communal routing problems: case studies from Finland
Abstract: In many European countries, municipalities offer their inhabitants a wide variety of social services. In this paper we will focus on efficiently scheduling home care, transportation of the elderly, and home meal delivery. These so-called municipal or communal routing problems can be modeled as different variants of the vehicle routing problem, a well-known optimization problem from the literature. We present a focused literature review and report on case studies using Finnish data. The computational results show that there is a significant potential for cost savings for all applications considered.
Using a TSP heuristic for routing order pickers in warehouses
In this paper, we deal with the sequencing and routing problem of order pickers in conventional multi-parallel-aisle warehouse systems. For this NP-hard Steiner travelling salesman problem (TSP), exact algorithms only exist for warehouses with at most three cross aisles, while for other warehouse types literature provides a selection of dedicated construction heuristics. We evaluate to what extent reformulating and solving the problem as a classical TSP leads to performance improvements compared to existing dedicated heuristics. We report average savings in route distance of up to 47% when using the LKH (Lin-Kernighan-Helsgaun) TSP heuristic. Additionally, we examine if combining problem-sp…
An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows
This paper presents a new deterministic annealing metaheuristic for the fleet size and mix vehicle-routing problem with time windows. The objective is to service, at minimal total cost, a set of customers within their time windows by a heterogeneous capacitated vehicle fleet. First, we motivate and define the problem. We then give a mathematical formulation of the most studied variant in the literature in the form of a mixed-integer linear program. We also suggest an industrially relevant, alternative definition that leads to a linear mixed-integer formulation. The suggested metaheuristic solution method solves both problem variants and comprises three phases. In Phase 1, high-quality init…
Vehicle Routing Problem with Time Windows, Part II: Metaheuristics
This paper surveys the research on the metaheuristics for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes 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. Metaheuristics are general solution procedures that explore the solution space to identify good solutions and often embed some of the standard route construction and improvemen…
A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows
In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instance…
Efficient Local Search Limitation Strategies for Vehicle Routing Problems
In this paper we examine five different strategies for limiting the local search neighborhoods in the context of vehicle routing problems. The vehicle routing problem deals with the assignment of a set of transportation orders to a fleet of vehicles, and the sequencing of stops for each vehicle to minimize transportation costs. The examined strategies are applied to three standard neighborhoods and implemented in a recently suggested powerful memetic algorithm. Experimental results on 26 well-known benchmark problems indicate significant speedups of almost 80% without worsening the solution quality. On the contrary, in 12 cases new best solutions were obtained.
A Simple Metaheuristic for the FleetSize and Mix Problem with TimeWindows
This paper presents a powerful new single-parameter metaheuristic to solve the Fleet Size and Mix Vehicle Routing Problem with Time Windows. The key idea of the new metaheuristic is to perform a random number of random-sized jumps in random order through four well-known local search operators. Computational testing on the 600 large-scale benchmarks of Bräysy et al. (Expert Syst Appl 36(4):8460–8475, 2009) show that the new metaheuristic outperforms previous best approaches, finding 533 new best-known solutions. Despite the significant number of random components, it is demonstrated that the variance of the results is rather low. Moreover, the suggested metaheuristic is shown to scale almost…
Joint Route Planning under Varying Market Conditions
Purpose - To provide empirical evidence on the level of savings that can be attained by joint route planning and how these savings depend on specific market characteristics.Design/methodology/approach - Joint route planning is a measure that companies can take to decrease the costs of their distribution activities. Essentially, this can either be achieved through horizontal cooperation or through outsourcing distribution to a Logistics Service Provider. The synergy value is defined as the difference between distribution costs in the original situation where all entities perform their orders individually, and the costs of a system where all orders are collected and route schemes are set up s…
Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem
Abstract: The traveling repairman problem is a customer-centric routing problem, in which the total waiting time of the customers is minimized, rather than the total travel time of a vehicle. To date, research on this problem has focused on exact algorithms and approximation methods. This paper presents the first metaheuristic approach for the traveling repairman problem.
Joint route planning under varying market conditions
PurposeTo provide empirical evidence on the level of savings that can be attained by joint route planning and how these savings depend on specific market characteristics.Design/methodology/approachJoint route planning is a measure that companies can take to decrease the costs of their distribution activities. Essentially, this can either be achieved through horizontal cooperation or through outsourcing distribution to a logistics service provider. The synergy value is defined as the difference between distribution costs in the original situation where all entities perform their orders individually, and the costs of a system where all orders are collected and route schemes are set up simulta…
Communal Transportation: Challenges for Largescale Routing Heuristics
In this report we review the central transportation logistics problems arising in the communal sector, using information gathered from several large communes in Finland and previous literature. Most of the communal transportation problems can be modelled as different variants of the vehicle routing problem. The basic features of the problems are described, modelled and analyzed, and the relevant previous research on the topics is reviewed. In addition, some possible new solution strategies are suggested.
The mixed capacitated general routing problem with turn penalties
In this paper we deal with the mixed capacitated general routing problem with turn penalties. This problem generalizes many important arc and node routing problems, and it takes into account turn penalties and forbidden turns, which are crucial in many real-life applications, such as mail delivery, waste collection and street maintenance operations. Through a polynomial transformation of the considered problem into a Generalized Vehicle routing problem, we suggest a new approach for solving this new problem by transforming it into an Asymmetric Capacitated Vehicle routing problem. In this way, we can solve the new problem both optimally and heuristically using existing algorithms. A powerfu…
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 use…
An optimization approach for communal home meal delivery service
Abstract: This paper is the first to discuss the communal home meal delivery problem. The problem can be modelled as a multiple travelling salesman problem with time windows, that is closely related to the well-studied vehicle routing problem with time windows. Experimental results are reported for a real-life case study from Central Finland over several alternative scenarios using the SPIDER commercial solver. The comparison with current practice reveals that a significant savings potential can be obtained using off-the-shelf optimization tools. As such, the potential for supporting real-life communal routing problems can be considered to be important for VRP practitioners.
Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms
This paper presents a survey of the research on the vehicle routing problem with time windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes 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. Both traditional heuristic route construction methods and recent local search algorithms are examined. The basic features of each method are described, and experimental results for Solom…
A hybrid evolution strategy for the open vehicle routing problem
This paper presents a hybrid evolution strategy (ES) for solving the open vehicle routing problem (OVRP), which is a well-known combinatorial optimization problem that addresses the service of a set of customers using a homogeneous fleet of non-depot returning capacitated vehicles. The objective is to minimize the fleet size and the distance traveled. The proposed solution method manipulates a population of @m individuals using a (@m+@l)-ES; at each generation, a new intermediate population of @l offspring is produced via mutation, using arcs extracted from parent individuals. The selection and combination of arcs is dictated by a vector of strategy parameters. A multi-parent recombination …
Improved route planning and scheduling of waste collection and transport
The collection of waste is a highly visible and important municipal service that involves large expenditures. Waste collection problems are, however, one of the most difficult operational problems to solve. This paper describes the optimization of vehicle routes and schedules for collecting municipal solid waste in Eastern Finland. The solutions are generated by a recently developed guided variable neighborhood thresholding metaheuristic that is adapted to solve real-life waste collection problems. Several implementation approaches to speed up the method and cut down the memory usage are discussed. A case study on the waste collection in two regions of Eastern Finland demonstrates that sign…
A powerful route minimization heuristic for the vehicle routing problem with time windows
We suggest an efficient route minimization heuristic for the vehicle routing problem with time windows. The heuristic is based on the ejection pool, powerful insertion and guided local search strategies. Experimental results on the Gehring and Homberger's benchmarks demonstrate that our algorithm outperforms previous approaches and found 18 new best-known solutions.
A multi-parametric evolution strategies algorithm for vehicle routing problems
Vehicle routing problems are at the heart of most decision support systems for real-life distribution problems. In vehicle routing problem a set of routes must be determined at lowest total cost for a number of resources (i.e. fleet of vehicles) located at one or several points (e.g. depots, warehouses) in order to efficiently service a number of demand or supply points. In this paper an efficient evolution strategies algorithm is developed for both capacitated vehicle routing problem and for vehicle routing problem with time window constraints. The algorithm is based on a new multi-parametric mutation procedure that is applied within the 1 + 1 evolution strategies algorithm. Computational …