The min-max multi-depot vehicle routing problem: heuristics and computational results

In the multi-depot vehicle routing problem (MDVRP), there are several depots where vehicles can start and end their routes. The objective is to minimize the total distance travelled by all vehicles across all depots. The min-max multi-depot vehicle routing problem (Min-Max MDVRP) is a variant of the standard MDVRP. The primary objective is to minimize the length of the longest route. We develop a heuristic (denoted by MD) for the Min-Max MDVRP that has three stages: (1) simplify the multi-depot problem into a single depot problem and solve the simplified problem; (2) improve the maximal route; (3) improve all routes by exchanging customers between routes. MD is compared with two alternative heuristics that we also develop and an existing method from the literature on a set of 20 test instances. MD produces 15 best solutions and is the top performer. Additional computational experiments on instances with uniform and non-uniform distributions of customers and varying customer-to-vehicle ratios and with real-world data further demonstrate MD’s effectiveness in producing high-quality results.     

A new tabu search algorithm for the vehicle routing problem with backhauls

In the distribution of goods from a central depot to geographically dispersed customers happens quite frequently that some customers, called linehauls, receive goods from that depot while others, named backhauls, send goods to it. This situation is described and studied by the vehicle routing problem with backhauls. In this paper we present a new tabu search algorithm that starting from pseudo-lower bounds was able to match almost all the best published solutions and to find many new best solutions, for a large set of benchmark problems.     

A variable neighbourhood search algorithm for the open vehicle routing problem

In the open vehicle routing problem (OVRP), the objective is to minimise the number of vehicles and then minimise the total distance (or time) travelled. Each route starts at the depot and ends at a customer, visiting a number of customers, each once, en route, without returning to the depot. The demand of each customer must be completely fulfilled by a single vehicle. The total demand serviced by each vehicle must not exceed vehicle capacity. Additionally, in one variant of the problem, the travel time of each vehicle should not exceed an upper limit.     

A deterministic iterated local search algorithm for the vehicle routing problem with backhauls

The vehicle routing problem with backhauls is a variant of the classical capacitated vehicle routing problem. The difference is that it contains two distinct sets of customers: those who receive goods from the depot, who are called linehauls, and those who send goods to the depot, who are referred to as backhauls. In this paper, we describe a new deterministic iterated local search algorithm, which is tested using a large number of benchmark problems chosen from the literature. These computational tests have proven that this algorithm competes with the best known algorithms in terms of the quality of the solutions and at the same time, it is simpler and faster.     

An approximation algorithm for the pickup and delivery vehicle routing problem on trees

This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery.Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., at any time the sum of goods to be delivered and that of goods that have been picked up is not allowed to exceed the vehicle capacity. We propose a 2-approximation algorithm for the problem.     

Open vehicle routing problem with driver nodes and time deadlines

In this paper, we consider a variant of the open vehicle routing problem in which vehicles depart from the depot, visit a set of customers, and end their routes at special nodes called driver nodes. A driver node can be the home of the driver or a parking lot where the vehicle will stay overnight. The resulting problem is referred to as the open vehicle routing problem with driver nodes (OVRP-d). We consider three classes of OVRP-d: with no time constraints, with a maximum route duration, and with both a maximum route duration as well as time deadlines for visiting customers. For the solution of these problems, which are not addressed previously in the literature, we develop a new tabu search heuristic. Computational results on randomly generated instances indicate that the new heuristic exhibits a good performance both in terms of the solution quality and computation time.     

考虑客户满意度的同时收发车辆路径问题

当客户要求车辆一次性完成发送以及收集货物的任务时, 只需考虑车辆的路径安排即可.但若客户进一步提出在时间窗内完成的话,就必须考虑客户的等待时间--客户的满意度的衡量标准,等待时间越短满意度越高.因此问题的目标为最小化车辆路径总长度、最小化所有客户等待时间之和.本文通过加权转变为单目标函数,由最邻近法及最廉价插入法得到初始解后经过禁忌搜索算法可得到改进算法,解并通过实例对不同权参数的情况进行了比较.     

Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows

The Vehicle Routing Problem with Time Windows (VRPTW) is a combinatorial optimization problem. It deals with route planning and the distribution of goods from a depot to geographically dispersed customers by a fleet of vehicles with constrained capacities. The customers’ demands are known and each customer has a time window in which it has to be supplied. The time windows are assumed to be soft, that means, violations of the time windows are allowed, but associated with penalties. The problem is to organize the vehicle routes optimally, i.e. to minimize the total costs, consisting of the number of used vehicles and the total distance, and the penalties simultaneously. Thus, the problem is formulated as a bicriterion minimization problem and heuristic methods are used to calculate approximations of the Pareto optimal solutions. Experimental results show that in certain cases the allowance of penalties leads to significant savings of the total costs.     

Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints

In this paper, we extend the multiple traveling repairman problem by considering a limitation on the total distance that a vehicle can travel; the resulting problem is called the multiple traveling repairmen problem with distance constraints (MTRPD). In the MTRPD, a fleet of identical vehicles is dispatched to serve a set of customers. Each vehicle that starts from and ends at the depot is not allowed to travel a distance longer than a predetermined limit and each customer must be visited exactly once. The objective is to minimize the total waiting time of all customers after the vehicles leave the depot. To optimally solve the MTRPD, we propose a new exact branch-and-price-and-cut algorithm, where the column generation pricing subproblem is a resource-constrained elementary shortest-path problem with cumulative costs. An ad hoc label-setting algorithm armed with bidirectional search strategy is developed to solve the pricing subproblem. Computational results show the effectiveness of the proposed method. The optimal solutions to 179 out of 180 test instances are reported in this paper. Our computational results serve as benchmarks for future researchers on the problem.     

Creating lasso-solutions for the traveling salesman problem with pickup and delivery by Tabu search

We consider the Traveling Salesman Problem with Pickup and Delivery (TSPPD) where the same costumers might require both deloverie of goods and pickup of other goods. All the goods should be transported from/to the same depot. A vehicle on a TSPPD-tour could often get some practical problems when arranging the load. Even if the vehicle has enough space for all the pickups, one has to consider that they are stored in a way that doesn't block the delivery for the next customer. In real life problems this occurs for instance for breweries when they deliver bottles of beer or mineral water and collects empty bottles from the same customers on the same tour. In these situations we could relax the constraints of only checking Hamiltonian tours, and also try solutions that can visit customers in a way giving rise to a ‘alsso’ model. A solution which first only delivers bottles until the vehicle is partly unloaded, then do both delivery and pickup at the remaining customers and at last picks up the empty bottle from the first visited customers, could in these situations be better than a pure Hamiltonian tour, at least in a practical setting. To find such solutions, we will use the metaheuristic Tabu Search on some well known TSPPD-problems, and compare them to other kinds of solutions on the same problems.     

计及客户满意度的电动汽车物流配送路径规划与充放电管理

物流配送作为一种盈利型社会服务性行业,配送服务时间对客户满意度具有重要影响。论文考虑电动汽车(electric vehicle, EV)在配送途中和回到配送中心两个阶段,以物流配送成本最低和客户平均满意度最高为目标,构建了一种EV在换电模式下计及客户满意度的物流配送路径规划与充放电管理多目标优化模型,其中物流配送成本包括换电成本、车辆损耗成本以及慢速充放电成本。最后,以A-n29节点VRP基准测试系统插入四座换电站节点为例进行数值仿真,采用非支配排序遗传算法(Non-dominated sorting genetic algorithm, NSGA-II)对所提多目标优化模型进行求解,结果验证了所提方法的可行性和有效性。此外,论文进一步考查了EV慢速充放电管理对配电系统的影响,并对EV发车时间作了参数灵敏度分析,为管理者提供一些参考。     

The Supply Pattern for a Fleet of Vehicles Regularly Operating on a Fixed Route

In studying the supply pattern of goods delivered to a depot by a fleet of vehicles all operating from a common source of supply on an identical route, it is necessary to assess the statistical properties of the times between the arrivals of the vehicles at the depot. This would seem to depend critically on the journey-time distribution, i.e. the distribution of times taken from the depot to collect the goods and return to the depot. This paper demonstrates, however, that this is not necessarily true, and that very often the interarrival-time distribution is essentially independent of the detailed form of the journey-time distribution. The only knowledge required in such situations is the mean, and minimum possible, journey-time; two quantities which are usually quite well known.     

Heuristics for the lexicographic max-ordering vehicle routing problem

In this paper, we propose fast heuristics for the vehicle routing problem (VRP) with lexicographic max-order objective. A fixed number of vehicles, which are based at a depot, are to serve customers with known demands. The lexicographic max-order objective is introduced by asking to minimize lexicographically the sorted route lengths. Based on a model for this problem, several approaches are studied and new heuristic solution procedures are discussed resulting in the development of a sequential insertion heuristic and a modified savings algorithm in several variants. Comparisons between the algorithms are performed on instances of the VRP library VRPLIB. Finally, based on the results from the computational experiments, conclusions about the applicability and efficiency of the presented algorithms are drawn.     

A goal programming approach to vehicle routing problems with soft time windows

The classical vehicle routing problem involves designing a set of routes for a fleet of vehicles based at one central depot that is required to serve a number of geographically dispersed customers, while minimizing the total travel distance or the total distribution cost. Each route originates and terminates at the central depot and customers demands are known. In many practical distribution problems, besides a hard time window associated with each customer, defining a time interval in which the customer should be served, managers establish multiple objectives to be considered, like avoiding underutilization of labor and vehicle capacity, while meeting the preferences of customers regarding the time of the day in which they would like to be served (soft time windows). This work investigates the use of goal programming to model these problems. To solve the model, an enumeration-followed-by-optimization approach is proposed which first computes feasible routes and then selects the set of best ones. Computational results show that this approach is adequate for medium-sized delivery problems.     

A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers

The purpose of this article is to propose a perturbation metaheuristic for the vehicle routing problem with private fleet and common carrier (VRPPC). This problem consists of serving all customers in such a way that (1) each customer is served exactly once either by a private fleet vehicle or by a common carrier vehicle, (2) all routes associated with the private fleet start and end at the depot, (3) each private fleet vehicle performs only one route, (4) the total demand of any route does not exceed the capacity of the vehicle assigned to it, and (5) the total cost is minimized. This article describes a new metaheuristic for the VRPPC, which uses a perturbation procedure in the construction and improvement phases and also performs exchanges between the sets of customers served by the private fleet and the common carrier. Extensive computational results show the superiority of the proposed metaheuristic over previous methods.     

A greedy look-ahead heuristic for the vehicle routing problem with time windows

In this paper we consider the problem of physically distributing finished goods from a central facility to geographically dispersed customers, which pose daily demands for items produced in the facility and act as sales points for consumers. The management of the facility is responsible for satisfying all demand, and promises deliveries to the customers within fixed time intervals that represent the earliest and latest times during the day that a delivery can take place. We formulate a comprehensive mathematical model to capture all aspects of the problem, and incorporate in the model all critical practical concerns such as vehicle capacity, delivery time intervals and all relevant costs. The model, which is a case of the vehicle routing problem with time windows, is solved using a new heuristic technique. Our solution method, which is based upon Atkinson's greedy look-ahead heuristic, enhances traditional vehicle routing approaches, and provides surprisingly good performance results with respect to a set of standard test problems from the literature. The approach is used to determine the vehicle fleet size and the daily route of each vehicle in an industrial example from the food industry. This actual problem, with approximately two thousand customers, is presented and solved by our heuristic, using an interface to a Geographical Information System to determine inter-customer and depot–customer distances. The results indicate that the method is well suited for determining the required number of vehicles and the delivery schedules on a daily basis, in real life applications.     

A hybrid tabu search based heuristic for the periodic distribution inventory problem with perishable goods

Most of the research on integrated inventory and routing problems ignores the case when products are perishable. However, considering the integrated problem with perishable goods is crucial since any discrepancy between the routing and inventory cost can double down the risk of higher obsolescence costs due to the limited shelf-life of the products. In this paper, we consider a distribution problem involving a depot, a set of customers and a homogeneous fleet of capacitated vehicles. Perishable goods are transported from the depot to customers in such a way that out-of-stock situations never occur. The objective is to simultaneously determine the inventory and routing decisions over a given time horizon such that total transportation cost is minimized. We present a new “arc-based formulation” for the problem which is deemed more suitable for our new tabu search based approach for solving the problem. We perform a thorough sensitivity analysis for each of the tabu search parameters individually and use the obtained gaps to fine-tune the parameter values that are used in solving larger sized instances of the problem. We solve different sizes of randomly generated instances and compare the results obtained using the tabu search algorithm to those obtained by solving the problem using CPLEX and a recently published column generation algorithm. Our computational experiments demonstrate that the tabu search algorithm is capable of obtaining a near-optimal solution in less computational time than the time required to solve the problem to optimality using CPLEX, and outperforms the column generation algorithm for solving the “path flow formulation” of the problem in terms of solution quality in almost all of the considered instances.     

An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles

The vehicle routing problem with multiple use of vehicles is a variant of the classical vehicle routing problem. It arises when each vehicle performs several routes during the workday due to strict time limits on route duration (e.g., when perishable goods are transported). The routes are defined over customers with a revenue, a demand and a time window. Given a fixed-size fleet of vehicles, it might not be possible to serve all customers. Thus, the customers must be chosen based on their associated revenue minus the traveling cost to reach them. We introduce a branch-and-price approach to address this problem where lower bounds are computed by solving the linear programming relaxation of a set packing formulation, using column generation. The pricing subproblems are elementary shortest path problems with resource constraints. Computational results are reported on euclidean problems derived from well-known benchmark instances for the vehicle routing problem with time windows.     

Exact algorithms for routing problems under vehicle capacity constraints

The solution of a vehicle routing problem calls for the determination of a set of routes, each performed by a single vehicle which starts and ends at its own depot, such that all the requirements of the customers are fulfilled and the global transportation cost is minimized. The routes have to satisfy several operational constraints which depend on the nature of the transported goods, on the quality of the service level, and on the characteristics of the customers and of the vehicles. One of the most common operational constraint addressed in the scientific literature is that the vehicle fleet is capacitated and the total load transported by a vehicle cannot exceed its capacity.     

A multi-shift vehicle routing problem with windows and cycle times

In many applications of the vehicle routing problem with time windows (VRPTW), goods must be picked up within desired time frames. In addition, they have some limitations on their arrival time to the central depot. In this paper, we present a new version of VRPTW that minimizes the total cycle time of the goods. In order to meet the time windows and also minimize the cycle time, the courier’s schedule is allowed to vary. An algorithm, named VeRSA, is proposed to solve this problem. VeRSA employs concepts of scheduling theorems and algorithms to determine feasible routes and schedules of the available couriers. We prove a theoretical lower bound that provides a useful bound on the optimality gap. We also conduct a set of numerical experiments. VeRSA obtains a feasible solution faster than solving the MIP. The optimality gap using our proposed lower bound is smaller than the gap found with the standard LP relaxation.