Search

The aim of this erratum is to correct an error in the computer implementation of the algorithm proposed by Dabia, Ropke, and van Woensel [Dabia S, Ropke S, van Woensel T (2013) Branch and price for the time-dependent vehicle routing problem with time windows. Transportation Sci. 47(3):295–454]. Section 6, "Computational Results," from the original paper is rewritten to reflect the corrected implementation, the new computational setup, and the updated results. [ABSTRACT FROM AUTHOR]

This paper introduces the vehicle routing problem with time windows and shifts (VRPTWS). At the depot, several shifts with nonoverlapping operating periods are available to load the planned trucks. Each shift has a limited loading capacity. We solve the VRPTWS exactly by a branch-and-cut-and-price algorithm. The master problem is a set partitioning with an additional constraint for every shift. Each constraint requires the total quantity loaded in a shift to be less than its loading capacity. For every shift, a pricing subproblem is solved by a label-setting algorithm. Shift capacity constraints define knapsack inequalities; hence we use valid inequalities inspired from knapsack inequalities to strengthen the linear programming relaxation of the master problem when solved by column generation. In particular, we use a family of tailored robust cover inequalities and a family of new nonrobust cover inequalities. Numerical results show that nonrobust cover inequalities significantly improve the algorithm. [ABSTRACT FROM AUTHOR]

This paper presents a branch-and-price algorithm for the time-dependent vehicle routing problem with time windows (TDVRPTW).We capture road congestion by considering time-dependent travel times, i.e., depending on the departure time to a customer, a different travel time is incurred. We consider the variant of the TDVRPTW where the objective is to minimize total route duration and denote this variant the duration minimizing TDVRPTW (DM-TDVRPTW). Because of time dependency, vehicles' dispatch times at the depot are crucial as road congestion might be avoided. Because of its complexity, all known solution methods to the DM-TDVRPTW are based on (meta-)heuristics. The decomposition of an arc-based formulation leads to a set-partitioning problem as the master problem, and a time-dependent shortest path problem with resource constraints as the pricing problem. The master problem is solved by means of column generation, and a tailored labeling algorithm is used to solve the pricing problem. We introduce new dominance criteria that allow more label dominance. For our numerical results, we modified Solomon's data sets by adding time dependency. Our algorithm is able to solve about 63% of the instances with 25 customers, 38% of the instances with 50 customers, and 15% of the instances with 100 customers. [ABSTRACT FROM AUTHOR]

This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality, surpassing previous exact algorithms. [ABSTRACT FROM AUTHOR]

Highlights • New optimization problem for delivery activities using drones in collaboration with trucks. • Fleet of delivery trucks, each of them equipped with a single drone. • Focus on cost-minimization objective function with maximum duration time for all routes. • Noteworthy cost-savings with respect to the case of only using trucks. • Efficient metaheuristic is proposed to solve this problem. Abstract Unmanned Aerial Vehicles, commonly known as drones, have attained considerable interest in recent years due to the potential of revolutionizing transport and logistics. Amazon were among the first to introduce the idea of using drones to deliver goods, followed by several other distribution companies working on similar services. The Traveling Salesman Problem , frequently used for planning last-mile delivery operations, can easily be modified to incorporate drones, resulting in a routing problem involving both the truck and aircraft. Introduced by Murray and Chu (2015) , the Flying Sidekick Traveling Salesman Problem considers a drone and truck collaborating. The drone can be launched and recovered at certain visits on the truck route, making it possible for both vehicles to deliver goods to customers in parallel. This generalization considerably decreases the operational cost of the routes, by reducing the total fuel consumption for the truck, as customers on the routes can be serviced by drones without covering additional miles for the trucks, and hence increase productivity. In this paper a mathematical model is formulated, defining a problem similar to the Flying Sidekick Traveling Salesman Problem , but for the capacitated multiple-truck case with time limit constraints and minimizing cost as objective function. The corresponding problem is denoted the Vehicle Routing Problem with Drones. Due to the difficulty of solving large instances to optimality, an Adaptive Large Neighborhood Search metaheuristic is proposed. Finally, extensive computational experiments are carried out. The tests investigate, among other things, how beneficial the inclusion of the drone-delivery option is compared to delivering all items using exclusively trucks. Moreover, a detailed sensitivity analysis is performed on several drone-parameters of interest. [ABSTRACT FROM AUTHOR]