A fast two-level variable neighborhood search for the clustered vehicle routing problem

In this paper, we present an improved two-level heuristic to solve the clustered vehicle routing problem (CluVRP). The CluVRP is a generalization of the classical capacitated vehicle routing problem (CVRP) in which customers are grouped into predefined clusters, and all customers in a cluster must be served consecutively by the same vehicle. This paper contributes to the literature in the following ways: (i) new upper bounds are presented for multiple benchmark instances, (ii) good heuristic solutions are provided in much smaller computing times than existing approaches, (iii) the CluVRP is reduced to its cluster level without assuming Euclidean coordinates or distances, and (iv) a new variant of the CluVRP, the CluVRP with weak cluster constraints, is introduced. In this variant, clusters are allocated to vehicles in their entirety, but all corresponding customers can be visited by the vehicle in any order.The proposed heuristic solves the CluVRP by combining two variable neighborhood search algorithms, that explore the solution space at the cluster level and the individual customer level respectively. The algorithm is tested on different benchmark instances from the literature with up to 484 nodes, obtaining high quality solutions while requiring only a limited calculation time.     

Multicriteria pickup and delivery problem with transfer opportunity

In this research, we develop a multiobjective vehicle routing and scheduling heuristic for a pickup and delivery problem. The problem contains time window, advanced request, multi-vehicle and many-to-many transport. In addition, the fleet size is not predetermined, and customers are allowed to transfer between vehicles. The objectives of scheduling are to minimize vehicle expense, tardiness and travel time. We propose a concurrent scheduling approach, which allocates customers to more than one vehicle and assigns more than one customer to a vehicle at a time. It differs from the usual concurrent approach in three aspects: (i) it uses the look-ahead strategy to construct miniroute; (ii) it adopts the head/tail, head, and tail integration techniques; and (iii) it allows interactivity. The procedure takes full advantage of due time and travel time information and is implemented through a computer program. It is a one-phase heuristic that can be reiterated when necessary. We provide detailed programming procedures and present the computational results of the proposed algorithm through the real data.     

Adaptive granular local search heuristic for a dynamic vehicle routing problem

The advance of communication and information technologies based on satellite and wireless networks have allowed transportation companies to benefit from real-time information for dynamic vehicle routing with time windows. During daily operations, we consider the case in which customers can place requests such that their demand and location are stochastic variables. The time windows at customer locations can be violated although lateness costs are incurred. The objective is to define a set of vehicle routes which are dynamically updated to accommodate new customers in order to maximize the expected profit. This is the difference between the total revenue and the sum of lateness costs and costs associated with the total distance traveled. The solution approach makes use of a new constructive heuristic that scatters vehicles in the service area and an adaptive granular local search procedure. The strategies of letting a vehicle wait, positioning a vehicle in a region where customers are likely to appear, and diverting a vehicle away from its current destination are integrated within a granular local search heuristic. The performance of the proposed approach is assessed in test problems based on real-life Brazilian transportation companies.     

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.     

A multilevel approach for modelling vehicle routing problem with uncertain travelling time

Vehicle routing problem is concerned with finding optimal collection or delivery routes in a transportation network, beginning and ending at a central depot, for a fleet of vehicles to serve a set of customers under some constraints. Assuming the travel times between two customers are uncertain variables, this paper proposes an uncertain multilevel programming model for a vehicle routing problem, of which the leader’s object is to minimize the total waiting times of the customers, and the followers’ objects are to minimize the waiting times of the vehicles for the beginning moments of the customers’ time windows. The uncertain multilevel programming model is transformed into a determinacy programming model, and an intelligent algorithm is designed for solving the crisp model.     

Agile optimization of a two‐echelon vehicle routing problem with pickup and delivery

In this paper, we consider a vehicle routing problem in which a fleet of homogeneous vehicles, initially located at a depot, has to satisfy customers' demands in a two‐echelon network: first, the vehicles have to visit intermediate nodes (e.g., a retail center or a consolidation center), where they deliver raw materials or bulk products and collect a number of processed items requested by the customers in their route; then, the vehicles proceed to complete their assigned routes, thus delivering the processed items to the final customers before returning to the depot. During this stage, vehicles might visit other intermediate nodes for reloading new items. In some real‐life scenarios, this problem needs to be solved in just a few seconds or even milliseconds, which leads to the concept of “agile optimization.” This might be the case in some rescue operations using drones in humanitarian logistics, where every second can be decisive to save lives. In order to deal with this real‐time two‐echelon vehicle routing problem with pickup and delivery, an original constructive heuristic is proposed. This heuristic is able to provide a feasible and reasonably good solution in just a few milliseconds. The constructive heuristic is extended into a biased‐randomized algorithm using a skewed probability distribution to modify its greedy behavior. This way, parallel runs of the algorithm are able to generate even better results without violating the real‐time constraint. Results show that the proposed methodology generates competitive results in milliseconds, being able to outperform other heuristics from the literature.     

A dispatching method for automated lifting vehicles in automated port container terminals

In automated container terminals, containers are transported from the marshalling yard to a ship and vice versa by automated vehicles. The automated vehicle type studied in this paper is an automated lifting vehicle (ALV) that is capable of lifting a container from the ground by itself. This study discusses how to dispatch ALVs by utilizing information about pickup and delivery locations and time in future delivery tasks. A mixed-integer programming model is provided for assigning optimal delivery tasks to ALVs. A procedure for converting buffer constraints into time window constraints and a heuristic algorithm for overcoming the excessive computational time required for solving the mathematical model are suggested. Numerical experiments are reported to compare the objective values and computational times by a heuristic algorithm with those by an optimizing method and to analyze the effects of dual cycle operation, number of ALVs, and buffer capacity on the performance of ALVs.     

A decomposition-based heuristic for the multiple-product inventory-routing problem

The inventory-routing problem is an integrated logistics planning problem arising in situations where customers transfer the responsibility for inventory replenishment to the vendor. The vendor must then decide when to visit each customer, how much to deliver and how to sequence customers in vehicle routes. In this paper, we focus on the case where several different products have to be delivered by a fleet of vehicles over a finite and discrete planning horizon. We present a three-phase heuristic based on a decomposition of the decision process of the vendor. In the first phase, replenishment plans are determined by using a Lagrangian-based method. These plans do not specify delivery sequences for the vehicles. The sequencing of the planned deliveries is performed in the second phase in which a simple procedure is employed to construct vehicle routes. The third phase incorporates planning and routing decisions into a mixed-integer linear programming model aimed at finding a good solution to the integrated problem. Computational experiments show that our heuristic is effective on instances with up to 50 customers and 5 products.     

Heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem in a carrier

In this paper, we present heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem arising in a real-world situation. In this problem, customers make requests of goods, which are packed in a sortment of boxes. The objective is to find minimum cost delivery routes for a set of identical vehicles that, departing from a depot, visit all customers only once and return to the depot. Apart of the usual 3D container loading constraints which ensure that the boxes are packed completely inside the vehicles and that the boxes do not overlap each other in each vehicle, the problem also takes into account constraints related to the vertical stability of the cargo and multi-drop situations. The algorithms are based on the combination of classical heuristics from both vehicle routing and container loading literatures, as well as two metaheuristic strategies, and their use in more elaborate procedures. Although these approaches cannot assure optimal solutions for the respective problems, they are relatively simple, fast enough to solve real instances, flexible enough to include other practical considerations, and normally assure relatively good solutions in acceptable computational times in practice. The approaches are also sufficiently generic to be embedded with algorithms other than those considered in this study, as well as they can be easily adapted to consider other practical constraints, such as the load bearing strength of the boxes, time windows and pickups and deliveries. Computational tests were performed with these methods considering instances based on the vehicle routing literature and actual customers’ orders, as well as instances based on a real-world situation of a Brazilian carrier. The results show that the heuristics are able to produce relatively good solutions for real instances with hundreds of customers and thousands of boxes.     

The green vehicle routing problem: A heuristic based exact solution approach

This paper develops a simulated annealing heuristic based exact solution approach to solve the green vehicle routing problem (G-VRP) which extends the classical vehicle routing problem by considering a limited driving range of vehicles in conjunction with limited refueling infrastructure. The problem particularly arises for companies and agencies that employ a fleet of alternative energy powered vehicles on transportation systems for urban areas or for goods distribution. Exact algorithm is based on the branch-and-cut algorithm which combines several valid inequalities derived from the literature to improve lower bounds and introduces a heuristic algorithm based on simulated annealing to obtain upper bounds. Solution approach is evaluated in terms of the number of test instances solved to optimality, bound quality and computation time to reach the best solution of the various test problems. Computational results show that 22 of 40 instances with 20 customers can be solved optimally within reasonable computation time.     

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.     

Heuristic solutions to multi-depot location-routing problems

This paper presents a method for solving the multi-depot location-routing problem (MDLRP). Since several unrealistic assumptions, such as homogeneous fleet type and unlimited number of available vehicles, are typically made concerning this problem, a mathematical formulation is given in which these assumptions are relaxed. Since the inherent complexity of the LRP problem makes it impossible to solve the problem on a larger scale, the original problem is divided into two sub-problems, i.e., the location-allocation problem, and the general vehicle routing problem, respectively. Each sub-problem is then solved in a sequential and iterative manner by the simulated annealing algorithm embedded in the general framework for the problem-solving procedure. Test problems from the literature and newly created problems are used to test the proposed method. The results indicate that this method performs well in terms of the solution quality and run time consumed. In addition, the setting of parameters throughout the solution procedure for obtaining quick and favorable solutions is also suggested.Scope and purposeIn many logistic environments managers must make decisions such as location for distribution centers (DC), allocation of customers to each service area, and transportation plans connecting customers. The location-routing problems (LRPs) are, hence, defined to find the optimal number and locations of the DCs, simultaneously with the vehicle schedules and distribution routes so as to minimize the total system costs. This paper proposes a decomposition-based method for solving the LRP with multiple depots, multiple fleet types, and limited number of vehicles for each different vehicle type. The solution procedure developed is very straightforward conceptually, and the results obtained are comparable with other heuristic methods. In addition, the setting of parameters throughout the solution procedure for obtaining quick and favorable solutions is also suggested.     

A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows

This paper addresses a variant of the vehicle routing problem in which customers require simultaneous pickup and delivery of goods during specific individual time windows (VRPSPDTW). A general mixed integer programming model is employed to minimize the routing cost due to: the cost of vehicles and the travel cost of vehicles. A parallel Simulated Annealing (p-SA) algorithm that includes a Residual Capacity and Radial Surcharge (RCRS) insertion-based heuristic is developed and applied to solve this NP-hard optimization problem. Computational results are reported for 65 test problems from Wang and Chen’s benchmark and compared with the results from a Genetic Algorithm (GA) that minimizes the number of vehicles (NV) as the primary objective. Experimental results demonstrate the effectiveness of the p-SA algorithm, which is able to achieve the same objective response as 100% of the Wang and Chen small-scale benchmarks (number of customers from 10 to 50). For the Wang and Chen medium-scale benchmarks (number of 100 customers), the p-SA algorithm obtains better NV solutions for 12 instances and the same NV solutions for the remaining 44 instances. For the 44 instances with the same NV solutions, a secondary objective, travel distance (TD), the p-SA provides better solutions than the GA for 16 instances, and equal solutions for 7 instances. In addition, solutions are found for 30 large-scale instances, with customers of 200, 400, 600, 800 and 1000, which may serve as a new benchmark for the VRPSPDTW problem.     

Packing first,routing second—a heuristic for the vehicle routing and loading problem

The Vehicle Routing and Loading Problem (VRLP) results by combining vehicle routing, possibly with time windows, and three-dimensional loading. Some packing constraints of high practical relevance, among them an unloading sequence constraint and a support constraint, are also part of the VRLP. Different formulations of the VRLP are considered and the issue is discussed under which circumstances routing and packing should be tackled as a combined task. A two-stage heuristic is presented following a “packing first, routing second” approach, i.e. the packing of goods and the routing of vehicles is done in two strictly separated stages. High quality results are achieved in short computation times for the 46 VRLP instances recently introduced by Moura and Oliveira. Moreover 120 new large benchmark instances including up to 1000 customers and 50,000 boxes are introduced and results for these instances are also reported.     

The min–max split delivery multi-depot vehicle routing problem with minimum service time requirement

The min–max Split Delivery Multi-Depot Vehicle Routing Problem with Minimum Service Time Requirement (min–max SDMDVRP-MSTR) is a variant of the Multi-Depot Vehicle Routing Problem. Each customer requires a specified amount of service time. The service time can be split among vehicles as long as each vehicle spends a minimum amount of service time at a customer. The objective is to minimize the duration of the longest route (where duration is the sum of travel and service times).We develop a heuristic (denoted by MDS) that solves the min–max SDMDVRP-MSTR in three stages: (1) initialize a feasible solution without splits; (2) improve the longest routes by splitting service times; (3) ensure all minimum service time requirements are satisfied. The first stage of MDS is compared to an existing heuristic to solve the min–max Multi-Depot Vehicle Routing Problem on 43 benchmark instances. MDS produces 37 best-known solutions. We also demonstrate the effectiveness of MDS on 21 new instances whose (near) optimal solutions can be estimated based on geometry. Finally, we investigate the savings from split service and the split patterns as we vary the required service times, the average number of customers per route, and the minimum service time requirement.     

A generalized exchange heuristic for the capacitated vehicle routing problem

We consider the problem of dispatching the minimum number of vehicles from a central depot to make deliveries to a set of clients with known demands. The objective is to minimize the total distance travelled, subject to vehicle capacity requirements. We present a new heuristic algorithm for solving this problem. The algorithm is based on generalized edge-exchange search procedures, and relaxation of the capacity requirements. Computational results, based upon standard test problems with up to 249 customers, indicate that our heuristic compares favourably with known heuristics in terms of solution quality.     

Iterated local search heuristics for the Vehicle Routing Problem with Cross-Docking

This work addresses the Vehicle Routing Problem with Cross-Docking (VRPCD). The problem consists in defining a minimum cost set of routes for a fleet of vehicles that meets the demands of products for a set of suppliers and customers. The vehicles leave a single Cross-Dock (CD) towards the suppliers, pick up products and return to the CD, where products can be exchanged before being delivered to their customers. The vehicle routes must respect the vehicle capacity constraints, as well as the time window constraints. We adapted a constructive heuristic and six local search procedures from the literature of VRP, and made them efficient in the presence of the synchronization constraints of VRPCD. Besides, we propose three Iterated Local Search (Lourenço et al., 2010) heuristics for VRPCD. The first heuristic is a standard implementation of ILS, while the second extends the classic ILS framework by keeping a set of elite solutions, instead of a single current solution. The latter set is used in a restart procedure. As far as we can tell, this is the first ILS heuristic in the literature that keeps a population of current elite solutions. The third heuristic is an extension of the second that relies on an intensification procedure based on an Integer Programming formulation for the Set Partitioning problem. The latter allows a neighborhood with an exponential number of neighbors to be efficiently evaluated. We report computational results and comparisons with the best heuristics in the literature. Besides, we also present a new set with the largest instances in the literature of VRPCD, in order to demonstrate that the improvements we propose for the ILS metaheuristic are efficient even for large size instances. Results show that the best of our heuristics is competitive with the best heuristics in the literature of VRPCD. Besides, it improved the best solution known for half of the benchmark instances in the literature.     

A comparison of five heuristics for the multiple depot vehicle scheduling problem

Given a set of timetabled tasks, the multi-depot vehicle scheduling problem consists of determining least-cost schedules for vehicles assigned to several depots such that each task is accomplished exactly once by a vehicle. In this paper, we propose to compare the performance of five different heuristics for this well-known problem, namely, a truncated branch-and-cut method, a Lagrangian heuristic, a truncated column generation method, a large neighborhood search heuristic using truncated column generation for neighborhood evaluation, and a tabu search heuristic. The first three methods are adaptations of existing methods, while the last two are new in the context of this problem. Computational results on randomly generated instances show that the column generation heuristic performs the best when enough computational time is available and stability is required, while the large neighborhood search method is the best alternative when looking for good quality solutions in relatively fast computational times.     

A simulated annealing heuristic for the open location-routing problem

This paper introduces the open location-routing problem (OLRP) that is a variant of the capacitated location-routing problem (CLRP). OLRP is motivated from the rise in contracting with third-party logistic (TPL) companies and is different from CLRP in that vehicles do not return to the distribution center after servicing all customers. The goal of OLRP is to minimize the total cost, consisting of facility operation costs, vehicle fixed costs, and traveling costs. We propose a simulated annealing (SA)-based heuristic for solving OLRP, which is tested on OLRP instances that have been adopted from three sets of well-known CLRP benchmark instances with up to 318 customers and 4 potential depots. The computational results indicate that the proposed heuristic efficiently solves OLRP.     

Time Petri nets as an evaluation tool for handling travel time uncertainty in vehicle routing solutions

Congestion on roads leads to uncertainty in travel times, which is important in delivery of goods, especially in a business environment where high levels of customer service are expected. Delivery periods to customers might be constrained by time windows, which makes the scheduling and routing of vehicles from the supplier’s side more difficult. Operations Research methods turn into heuristics for this type of application. But when, on top, uncertainty on travel times are the case, any hope of a simple and well-performing heuristic is lost. This study applies a methodology in which a heuristic is used to find a solution for scheduling and routing under deterministic travel times and, by means of simulation, though the use of Time Petri nets evaluates the sensitivity of the solution to uncertainties in travel times from one customer to the next in a route.