A vehicle routing problem with time windows and stochastic demands

Abstract

This study presents an approach for considering a vehicle routing problem where customers’ pickup demands are uncertain and require serving within some settled time windows. Customers’ demands are assumed to follow given discrete probability distributions. This study proposes a nonlinear stochastic integer program with recourse to formulate the vehicle routing problem with stochastic demands and time windows (VRPTW‐SD, for short). The objective of the VRPTW‐SD is to minimize the total cost of the first‐stage solution and expected recourse cost of the second‐stage solution. The total cost of the first‐stage problem includes the total travel cost for all links and the total waiting cost at all nodes. When a vehicle capacity is attained or exceeded, recourse actions are needed and recourse costs incurred in order to finish the planned route schedules. Two categories of schedule failure are introduced in this work; the recourse costs derive from the variations in travel time travel time, waiting time, and penalties of late arrival for time windows. In addition, an optimization algorithm is developed for solving the VRPTW‐SD, according to the framework of the L‐shaped method. Numerical results are given to demonstrate its validity.     

A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty

In this paper we introduce a robust optimization approach to solve the Vehicle Routing Problem (VRP) with demand uncertainty. This approach yields routes that minimize transportation costs while satisfying all demands in a given bounded uncertainty set. We show that for the Miller-Tucker-Zemlin formulation of the VRP and specific uncertainty sets, solving for the robust solution is no more difficult than solving a single deterministic VRP. Our computational results on benchmark instances and on families of clustered instances show that the robust solution can protect from unmet demand while incurring a small additional cost over deterministic optimal routes. This is most pronounced for clustered instances under moderate uncertainty, where remaining vehicle capacity is used to protect against variations within each cluster at a small additional cost. We compare the robust optimization model with classic stochastic VRP models for this problem to illustrate the differences and similarities between them. We also observe that the robust solution amounts to a clever management of the remaining vehicle capacity compared to uniformly and non-uniformly distributing this slack over the vehicles.     

A capacitated vehicle routing problem with order available time in e-commerce industry

In this article, a variant of the well-known capacitated vehicle routing problem (CVRP) called the capacitated vehicle routing problem with order available time (CVRPOAT) is considered, which is observed in the operations of the current e-commerce industry. In this problem, the orders are not available for delivery at the beginning of the planning period. CVRPOAT takes all the assumptions of CVRP, except the order available time, which is determined by the precedent order picking and packing stage in the warehouse of the online grocer. The objective is to minimize the sum of vehicle completion times. An efficient tabu search algorithm is presented to tackle the problem. Moreover, a Lagrangian relaxation algorithm is developed to obtain the lower bounds of reasonably sized problems. Based on the test instances derived from benchmark data, the proposed tabu search algorithm is compared with a published related genetic algorithm, as well as the derived lower bounds. Also, the tabu search algorithm is compared with the current operation strategy of the online grocer. Computational results indicate that the gap between the lower bounds and the results of the tabu search algorithm is small and the tabu search algorithm is superior to the genetic algorithm. Moreover, the CVRPOAT formulation together with the tabu search algorithm performs much better than the current operation strategy of the online grocer.     

A hybrid algorithm for the vehicle routing problem with backhauls,time windows and three-dimensional loading constraints

OR Spectrum - This paper deals with a special vehicle routing problem with backhauls where customers may want to receive items from a depot and, at the same time, return items back to the depot....     

A capacitated vehicle routing problem for just-in-time delivery

This paper focuses on the formulation and solution of the problem of planning vehicle routes for material delivery within the premises of a plant working under a just-in-time production system. The unique characteristic of this problem is that the quantity to be delivered at each of the demand nodes is a function of the route taken by the vehicle assigned to serve that node. The problem is modeled by adding a non-linear capacity constraint to the standard vehicle routing model, such that vehicle idle times and inventories at the customer locations are minimized. A heuristic solution procedure is outlined, and the formulation of a lower-bound relaxation is suggested. The performance of the heuristic solution procedure is evaluated in comparison to the lower-bound relaxation, and the heuristic procedure is shown to provide generally good results.     

Indirect search for the vehicle routing problem with pickup and delivery and time windows

The vehicle routing problem with pickup and delivery and time windows (VRPPDTW) is one of the prominent members studied in the class of rich vehicle routing problems and it has become one of the challenges for developing heuristics which are accurate and fast at the same time. Indirect local search heuristics are ideally suited to flexibly handle complex constraints as those occurring in rich combinatorial optimization problems by separating the problem of securing feasibility of solutions from the objective-driven metaheuristic search process using simple encodings and appropriate decoders. In this paper we show that the approach of indirect local search with greedy decoding (GIST) is not only flexible and simple but when applied to the VRPPDTW it also gives results which are competitive with state-of-the-art VRPPDTW-methods by Li and Lim, as well as Pankratz.     

Integrated production scheduling and vehicle routing problem with job splitting and delivery time windows

In this paper, we study a production scheduling and vehicle routing problem with job splitting and delivery time windows in a company working in the metal packaging industry. In this problem, a set of jobs has to be processed on unrelated parallel machines with job splitting and sequence-dependent setup time (cost). Then the finished products are delivered in batches to several customers with heterogeneous vehicles, subject to delivery time windows. The objective of production is to minimize the total setup cost and the objective of distribution is to minimize the transportation cost. We propose mathematical models for decentralized scheduling problems, where a production schedule and a distribution plan are built consecutively. We develop a two-phase iterative heuristic to solve the integrated scheduling problem. We evaluate the benefits of coordination through numerical experiments.     

Variable neighbourhood simulated annealing algorithm for capacitated vehicle routing problems

This article presents the variable neighbourhood simulated annealing (VNSA) algorithm, a variant of the variable neighbourhood search (VNS) combined with simulated annealing (SA), for efficiently solving capacitated vehicle routing problems (CVRPs). In the new algorithm, the deterministic ‘Move or not’ criterion of the original VNS algorithm regarding the incumbent replacement is replaced by an SA probability, and the neighbourhood shifting of the original VNS (from near to far by k← k+1) is replaced by a neighbourhood shaking procedure following a specified rule. The geographical neighbourhood structure is introduced in constructing the neighbourhood structures for the CVRP of the string model. The proposed algorithm is tested against 39 well-known benchmark CVRP instances of different scales (small/middle, large, very large). The results show that the VNSA algorithm outperforms most existing algorithms in terms of computational effectiveness and efficiency, showing good performance in solving large and very large CVRPs.     

A cloud theory-based particle swarm optimization for multiple decision maker vehicle routing problems with fuzzy random time windows

This article puts forward a cloud theory-based particle swarm optimization (CTPSO) algorithm for solving a variant of the vehicle routing problem, namely a multiple decision maker vehicle routing problem with fuzzy random time windows (MDVRPFRTW). A new mathematical model is developed for the proposed problem in which fuzzy random theory is used to describe the time windows and bi-level programming is applied to describe the relationship between the multiple decision makers. To solve the problem, a cloud theory-based particle swarm optimization (CTPSO) is proposed. More specifically, this approach makes improvements in initialization, inertia weight and particle updates to overcome the shortcomings of the basic particle swarm optimization (PSO). Parameter tests and results analysis are presented to highlight the performance of the optimization method, and comparison of the algorithm with the basic PSO and the genetic algorithm demonstrates its efficiency.     

A memetic algorithm with iterated local search for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a difficult vehicle routing problem, where given an undirected graph, the objective is to minimize the total cost of all vehicle tours that serve all required edges under vehicle capacity constraints. In this paper, a memetic algorithm with iterated local search (MAILS) is proposed to solve this problem. The proposed MAILS incorporates a new crossover operator, i.e., the longest common substring crossover (LCSX), an iterated local search (ILS) and a perturbation mechanism into the framework of the memetic algorithm (MA). The proposed MAILS is evaluated on the CARP benchmark instances and computational results show that the MAILS is very competitive.     

Multi-attribute label matching algorithms for vehicle routing problems with time windows and backhauls

We consider the class of vehicle routing problems with backhauls and time window constraints. Our motivating application is the land transportation of air-cargo freight forwarders, which requires fast solution times and the ability to handle various operational issues such as heterogeneous vehicles, multiple trips per vehicle, and penalty for early arrival at customer sites. We formulate the problem in the framework of label matching where the labels have multiple attributes representing the states of vehicles at customer locations or possible routes that vehicles may continue to cover. Two optimization-based heuristics are developed. Experimental tests on random problems and real data show that the methods can produce quality solutions quickly and are flexible in incorporating complex constraints.     

A column generation based heuristic for the capacitated vehicle routing problem with three-dimensional loading constraints

This paper addresses an integrated problem of vehicle routing and three-dimensional loading with additional practical constraints such as stability, fragility and LIFO. A column generation (CG) technique-based heuristic is proposed to handle this problem. To generate new columns in CG technique, first, an elementary shortest path problem is solved to find routes with negative reduced cost. Then an extreme point-based heuristic method is employed to verify feasibility of obtained routes in terms of loading and other constraints. To speed up the CG technique, fast column generation is also performed by applying an efficient heuristic pricing method. The CG technique, tested on the benchmark instances, outperforms the efficient tabu search method developed in the literature in terms of solution quality and computation time.     

Field services design and management of natural gas distribution networks: a class of vehicle routing problem with time windows approach

Service operations management of metropolitan gas networks at operational level implies the optimisation of decisions related to logistic activities, taking into account multi-objectives and operational constraints. This paper proposes a metaheuristic approach for the operational planning of the daily logistic activities based on vehicle routing with time window model. Experimental results for a real planning case in a gas distribution network demonstrate the approach effectiveness.     

Particle swarm optimization for the multi-period cross-docking distribution problem with time windows

Cross-docking has emerged as a new technique in supply chain management to replace the warehouse concept in the retail industry. This paper proposes a multi-period cross-docking distribution problem that consists of manufacturers, cross-docks and customers. This model is formulated for cases that consider multiple products, consolidation of customer orders and time windows that are available in multiple periods. The objective function is to minimise the total cost, which includes transportation cost, inventory cost and penalty cost. The penalty cost arises when demand remains in each period that cannot be satisfied. To deal with the complexity of the problem, an algorithm is developed based on particle swarm optimisation (PSO) with multiple social learning terms, GLNPSO, with two solution representations. The solution representations are a one-period solution representation (OP-SR) and a multi-period solution representation (MP-SR). The GLNPSO-based algorithm performs well in solving this problem. Moreover, both representations are proven effective when comparing the solution quality and computational time with those results obtained from CPLEX. In terms of quality, the MP-SR solution is better than the OP-SR solution for both stable and fluctuating demand instances. However, MP-SR requires more computational effort than OP-SR.     

A matching-based approach for solving a delivery/pick-up vehicle routing problem with time constraints

Summary In this paper we deal with the following special vehicle routing problem with time window constraints: Given a non-homogeneous fleet of vehicles and a fixed set of customers, during one time period, i.e. a day or a week, these customers have to be delivered in the first half of the period with a certain amount of goods. Thereby delivery may start at timet _start say at the depot and for every customer there is a so-called cut-off-time for the latest possible delivery. In addition to travel time there is a certain delivery-time associated with every customer. In the second half of the time period the vehicles have to pick-up certain amounts of goods and to ship them to the depot. Again there is a cut-off time for the earliest possible pick-up and a certain time-span consumed for every pick-up. We show how this problem can be formulated as a (highdimensional) set partitioning problem with two additional nontrivial sets of side-constraints. Assuming that the number of customers that can be served by a single vehicle on a delivery or pick-up-pass is at most two, the problem reduces to a matching problem with side-constraints. Although the problem is still NP-complete it becomes practicable in the sense that by relaxation and applying effective optimization techniques from non-smooth optimization and efficient matching software good approximate solutions are constructed in acceptable time.This work was partially supported by a grant from the Deutsche Forschungsgemeinschaft (DFG)     

A hybrid genetic algorithm for the multi-depot open vehicle routing problem

This paper studies the multi-depot open vehicle routing problem (MDOVRP), a variant of the vehicle routing problem (VRP), in which vehicles start from several depots and are not required to return to the depot. Despite the vast amount of literature about VRPs, the MDOVRP has received very little attention from researchers. In this paper, a new hybrid genetic algorithm is presented for finding the routes that minimize the traveling cost of the vehicles. Computational results on a number of test instances indicate the proposed algorithm dominates the CPLEX solver and the existing approach in the literature. Meanwhile, experiments are conducted on multi-depot VRP benchmarks, and the results are compared with a sophisticated tabu search approach and an exact method.     

A coordinated algorithm for integrated production scheduling and vehicle routing problem

In this paper, the integrated production scheduling and vehicle routing problem is considered for a Make-to-Order manufacturer, who has a single machine for production and limited vehicles with capacity constraints for transportation. The objective is to determine production scheduling and vehicle routing, which are two interacted decisions, to minimise the maximum order delivery time. A property on optimal production sequence is proposed first, based on which backward and forward batching methods are developed and are embedded into a proposed genetic algorithm. The proposed genetic algorithm is capable of providing high-quality solutions by determining the two decisions simultaneously. For comparison purpose, a two-stage algorithm is developed, which decomposes the overall problem into two successively solved sub-problems. The experiments show that the proposed genetic algorithm can provide higher quality solutions than the proposed two-stage algorithm and two published algorithms studying related problems.