An analytical bound on the fleet size in vehicle routing problems: A dynamic programming approach

We present an analytical upper bound on the number of required vehicles for vehicle routing problems with split deliveries and any number of capacitated depots. We show that a fleet size greater than the proposed bound is not achievable based on a set of common assumptions. This property of the upper bound is proved through a dynamic programming approach. We also discuss the validity of the bound for a wide variety of routing problems with or without split deliveries.     

Arc routing problems with time-dependent service costs

This paper studies an arc routing problem with capacity constraints and time-dependent service costs. This problem is motivated by winter gritting applications where the “timing” of each intervention is crucial. The exact problem-solving approach reported here first transforms the arc routing problem into an equivalent node routing problem. Then, a column generation scheme is used to solve the latter. The master problem is a classical set covering problem, while the subproblems are time-dependent shortest path problems with resource constraints. These subproblems are solved using an extension of a previously developed algorithm. Computational results are reported on problems derived from a set of classical instances of the vehicle routing problem with time windows.     

Hybrid metaheuristics for the profitable arc tour problem

The profitable arc tour problem is a variant in the vehicle routing problems. It is included in the family of the vehicle routing with profit problems in which a set of vehicle tours are constructed. The objective is to find a set of cycles in the vehicle tours that maximize the collection of profits minus travel costs, subject to constraints limiting the length of cycles that profit is available on arcs. To solve this variant we adopted two metaheuristics based on adaptive memory. We show that our algorithms provide good results in terms of solution quality and running times.     

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains challenging. In this work we provide an explanation to such challenge, by proving that when demands are given as a finite set of scenarios, solving the LP relaxation of such formulation is strongly NP-Hard. We also prove a hardness result for the case of independent normal demands.     

Using Experimental Design to Find Effective Parameter Settings for Heuristics

In this paper, we propose a procedure, based on statistical design of experiments and gradient descent, that finds effective settings for parameters found in heuristics. We develop our procedure using four experiments. We use our procedure and a small subset of problems to find parameter settings for two new vehicle routing heuristics. We then set the parameters of each heuristic and solve 19 capacity-constrained and 15 capacity-constrained and route-length-constrained vehicle routing problems ranging in size from 50 to 483 customers. We conclude that our procedure is an effective method that deserves serious consideration by both researchers and operations research practitioners.     

An improved algorithm for solving biobjective integer programs

A parametric algorithm for identifying the Pareto set of a biobjective integer program is proposed. The algorithm is based on the weighted Chebyshev (Tchebycheff) scalarization, and its running time is asymptotically optimal. A number of extensions are described, including: a technique for handling weakly dominated outcomes, a Pareto set approximation scheme, and an interactive version that provides access to all Pareto outcomes. Extensive computational tests on instances of the biobjective knapsack problem and a capacitated network routing problem are presented.     

Designing routes for WEEE collection: the vehicle routing problem with split loads and date windows

This paper presents an integer programming model and describes a GRASP based algorithm to solve a vehicle routing and scheduling problem for the collection of Waste of Electric and Electronic Equipment (WEEE). The difficulty of this problem arises from the fact that it is characterized by four variants of the vehicle routing problem that have been studied independently in the literature, but not together. The experimental analysis on a large set of randomly-generated instances shows the good performance of the proposed algorithm. Moreover, computational results using real data show that the method outperforms real existing approaches to reverse logistics.     

Using clustering analysis in a capacitated location-routing problem

The location routing problem (LRP) appears as a combination of two difficult problems: the facility location problem (FLP) and the vehicle routing problem (VRP). In this work, we consider a discrete LRP with two levels: a set of potential capacitated distribution centres (DC) and a set of ordered customers. In our problem we intend to determine the set of installed DCs as well as the distribution routes (starting and ending at the DC). The problem is also constrained with capacities on the vehicles. Moreover, there is a homogeneous fleet of vehicles, carrying a single product and each customer is visited just once. As an objective we intend to minimize the routing and location costs.     

Exact and hybrid methods for the multiperiod field service routing problem

This article deals with a particular class of routing problem, consisting of the planning and routing of technicians in the field. This problem has been identified as a multiperiod, multidepot uncapacitated vehicle routing problem with specific constraints that we call the multiperiod field service routing problem (MPFSRP). We propose a set covering formulation of the problem for the column generation technique and we develop an exact branch and price solution method for small-sized instances. We also propose several heuristic versions for larger instances. We present the results of experiments on realistic data adapted from an industrial application.     

Gossip algorithms for heterogeneous multi-vehicle routing problems

In this paper we address a class of heterogeneous multi-vehicle task assignment and routing problems. We propose two distributed algorithms based on gossip communication: the first algorithm is based on a local exact optimization and the second is based on a local approximate greedy heuristic. We consider the case where a set of heterogeneous tasks arbitrarily distributed in a plane has to be serviced by a set of mobile robots, each with a given movement speed and task execution speed. Our goal is to minimize the maximum execution time of robots.     

A computational comparison of algorithms for the inventory routing problem

The inventory routing problem is a distribution problem in which each customer maintains a local inventory of a product such as heating oil and consumes a certain amount of that product each day. Each day a fleet of trucks is dispatched over a set of routes to resupply a subset of the customers. In this paper, we describe and compare algorithms for this problem defined over a short planning period, e.g. one week. These algorithms define the set of customers to be serviced each day and produce routes for a fleet of vehicles to service those customers. Two algorithms are compared in detail, one which first allocates deliveries to days and then solves a vehicle routing problem and a second which treats the multi-day problem as a modified vehicle routing problem. The comparison is based on a set of real data obtained from a propane distribution firm in Pennsylvania. The solutions obtained by both procedures compare quite favorably with those in use by the firm.Part of this work was performed while this author was visiting the University of Waterloo.     

一种带时间窗和容量约束的车辆路线问题及其Tabu Search算法

本文提出一种带时间窗和容量约束的车辆路线问题（CVRPTW），并利用Tabu Search快速启式算法，针对Solomon提出的几个标准问题，快捷地得到了优良的数值结果。     

An evolutionary algorithm for the vehicle routing problem with route balancing

In this paper, we address a bi-objective vehicle routing problem in which the total length of routes is minimized as well as the balance of routes, i.e. the difference between the maximal route length and the minimal route length. We propose a meta-heuristic method based on an evolutionary algorithm involving classical multi-objective operators. To improve its efficiency, two mechanisms, which favor the diversification of the search, have been added. First, an elitist diversification mechanism is used in cooperation with classical diversification methodologies. Second, a parallel model designed to take into account the elitist diversification is proposed. Our method is tested on standard benchmarks for the vehicle routing problem. The contribution of the introduced mechanisms is evaluated by different performance metrics. All the experimentations indicate a strict improvement of the generated Pareto set.     

A memetic algorithm for the multiperiod vehicle routing problem with profit

In this paper, we extend upon current research in the vehicle routing problem whereby labour regulations affect planning horizons, and therefore, profitability. We call this extension the multiperiod vehicle routing problem with profit (mVRPP). The goal is to determine routes for a set of vehicles that maximizes profitability from visited locations, based on the conditions that vehicles can only travel during stipulated working hours within each period in a given planning horizon and that the vehicles are only required to return to the depot at the end of the last period. We propose an effective memetic algorithm with a giant-tour representation to solve the mVRPP. To efficiently evaluate a chromosome, we develop a greedy procedure to partition a given giant-tour into individual routes, and prove that the resultant partition is optimal. We evaluate the effectiveness of our memetic algorithm with extensive experiments based on a set of modified benchmark instances. The results indicate that our approach generates high-quality solutions that are reasonably close to the best known solutions or proven optima, and significantly better than the solutions obtained using heuristics employed by professional schedulers.     

A matheuristic approach for solving a home health care problem

We deal with a Home Health Care Problem (HHCP) which objective consists in constructing the optimal routes and rosters for the health care staffs. The challenge lies in combining aspects of vehicle routing and staff rostering which are two well known hard combinatorial optimization problems. To solve this problem, we initially propose an integer linear programming formulation (ILP) and we tested this model on small instances. To deal with larger instances we develop a matheuristic based on the decomposition of the ILP formulation into two problems. The first one is a set partitioning like problem and it represents the rostering part. The second problem consists in the routing part. This latter is equivalent to a Multi-depot Traveling Salesman Problem with Time Windows (MTSPTW).     

An adaptive memory algorithm for the split delivery vehicle routing problem

The split delivery vehicle routing problem (SDVRP) relaxes routing restrictions forcing unique deliveries to customers and allows multiple vehicles to satisfy customer demand. Split deliveries are used to reduce total fleet cost to meet those customer demands. We provide a detailed survey of the SDVRP literature and define a new constructive algorithm for the SDVRP based on a novel concept called the route angle control measure. We extend this constructive approach to an iterative approach using adaptive memory concepts, and then add a variable neighborhood descent process. These three new approaches are compared to exact and heuristic approaches by solving the available SDVRP benchmark problem sets. Our approaches are found to compare favorably with existing approaches and we find 16 new best solutions for a recent 21 problem benchmark set.     

GRASP-ASP: An algorithm for the CVRP with route balancing

An extension of the capacitated vehicle routing problem is studied in this paper. In this version the difference between the individual route lengths is minimized simultaneously with the total length. The drivers’ workload and perhaps, income, may be affected by the route lengths; so adding this objective makes the problem closer to real-life than the original, single-objective problem. A heuristic based on GRASP is used to obtain an approximation of the Pareto set. The proposed heuristic is tested on instances from the literature, obtaining good approximations of the Pareto set.     

m-aryn-cube网络的最优路由

基于可选邻接点的概念,在m-ary n-cube网络中提出一种新的最优寻径算法.这种算法始终在当前结点的可选邻接点中选取最空闲邻接点作为下一个信息传输点.该算法使得从源结点到达目的结点路由是最短路由也是最快速路由,而且在多项式时间内可以完成.     

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.     

Local search for the undirected capacitated arc routing problem with profits

This paper deals with a recently introduced routing problem variant called the undirected capacitated arc routing problem with profits (UCARPP). The UCARPP model considered in the present study is primarily aimed at generating the route set which maximizes the profit collected from a set of potential customers, represented by edges of the examined transportation network. The secondary objective is to minimize the total route travel time. The generated routes are subject both to capacity and travel time constraints. To tackle the examined problem, we propose a local search metaheuristic development which explores two solution neighborhood structures. The conducted search is effectively diversified by means of the promises concept which is based on the aspiration criteria used in tabu search approaches. The proposed algorithm was tested on UCARPP benchmark instances taken from the literature. It efficiently produced high-quality results, improving several previously best known solutions.