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 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.     

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.     

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.     

Vehicle routing problem with vector profits with max-min criterion

This article introduces a new routing problem referred to as the vehicle routing problem with vector profits. Given a network composed of nodes (depot/sites) and arcs connecting the nodes, the problem determines routes that depart from the depot, visit sites to collect profits, and return to the depot. There are multiple stakeholders interested in the mission and each site is associated with a vector whose kth element represents the profit value for the kth stakeholder. The objective of the problem is to maximize the profit sum for the least satisfied stakeholder, i.e. the stakeholder with the smallest total profit value. An approach based on linear programming relaxation and column-generation to solve this max–min type routing problem was developed. Two case studies—the planetary surface exploration and the Rome tour cases—were presented to demonstrate the effectiveness of the proposed problem formulation and solution methodology.     

Loading constraints for a multi-compartment vehicle routing problem

OR Spectrum - Multi-compartment vehicles (MCVs) can deliver several product segments jointly. Separate compartments are necessary as each product segment has its own specific characteristics and...     

Heuristic and exact algorithms for the multi-pile vehicle routing problem

The multi-pile vehicle routing problem is a particular combination of loading and routing problems, in which items have to be loaded into different piles within vehicles, and then delivered with minimum cost. The problem is motivated by a real-world timber distribution problem, and is of both theoretical and practical interest. In this paper, we first develop heuristic and exact methods to solve the loading problem. We then include these methods into a tailored combination of Variable Neighborhood Search and Branch-and-Cut, to solve the overall problem. Extensive computational results show how the resulting algorithms are capable of solving to optimality a large number of small-size instances, and of consistently outperforming previous algorithms from the literature on large-size and real-world instances.     

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.     

An optimization algorithm for a capacitated vehicle routing problem with time windows

In this paper, vehicle routing problem (VRP) with time windows and real world constraints are considered as a real-world application on google maps. Also, tabu search is used and Hopfield neural networks is utilized. Basic constraints consist of customer demands, time windows, vehicle speed, vehicle capacity and working hours. Recently, cost and on-time delivery are the most important factors in logistics. Thus, the logistic applications attract attention of companies. In logistic management, determining the locations of delivery points and deciding the path are the vital components that should be considered. Deciding the paths of vehicles provides companies to use their vehicles efficiently. And with utilizing optimized paths, big amounts of cost and time savings will be gained. The main aim of the work is providing the best path according to the needs of the customers, minimizing the costs with utilizing the VRP and presenting an application for companies that need logistic management. To compare the results, simulated annealing is used on special scenarios. And t-test is performed in the study for the visited path in km with p-value of 0.05.     

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.     

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 mathematical model for vehicle routing problem under endogenous uncertainty

In this study, a multistage stochastic programming (SP) model is presented for a variant of single-vehicle routing problem with stochastic demands from a dynamic viewpoint. It is assumed that the actual demand of a customer becomes known only when the customer is visited. This problem falls into the category of SP with endogenous uncertainty and hence, the scenario tree is decision-dependent. Therefore, nonanticipativity of decisions is ensured by conditional constraints making up a large portion of total constraints. Thus, a novel approach is proposed that considerably reduces the problem size without any effect on the solution space. Computational results on some test problems are reported.     

改进蚁群算法在物流配送路径中的应用

针对物流配送路径优化问题的特点,分析了基本蚁群算法的不足之处,并对原有蚁群算法进行改进.同时引入"扰动因子"和"奖惩"机制,建立数学模型,进而对物流配送车辆路径问题进行了实验仿真.结果表明,改进后的蚁群算法提高了全局寻优能力与收敛速度,取得了较好的效果.     

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.     

Vehicle routing with compartments: applications, modelling and heuristics

Despite the vast amount of literature about vehicle routing problems, only very little attention has been paid to vehicles with compartments that allow transportation of inhomogeneous products on the same vehicle, but in different compartments. We motivate a general vehicle routing problem with compartments that is essential for several industries, like the distribution of food or petrol. We introduce a formal model, an integer program formulation and a benchmark suite of 200 instances. A solver suite of heuristic components is presented, which covers a broad range of alternative approaches for construction, local search, large neighbourhood search and meta-heuristics. The empirical results for the benchmark instances identify effective algorithmic setups as well as essential components for achieving high solution quality. In a comparison on 23 specific and combinatorially less complex instances taken from literature, our algorithm showed to be competitive.     

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.