The Experts below are selected from a list of 44109 Experts worldwide ranked by ideXlab platform

Claudia Archetti - One of the best experts on this subject based on the ideXlab platform.

  • a column generation approach for the split Delivery Vehicle routing problem
    Networks, 2011
    Co-Authors: Claudia Archetti, Nicola Bianchessi, Maria Grazia Speranza
    Abstract:

    In this article we present a branch-and-price-and-cut method for the solution of the split Delivery Vehicle routing problem (SDVRP). The SDVRP is the problem to serve customers with a fleet of capacitated Vehicles at minimum traveling cost. With respect to the classical Vehicle routing problem, where each customer is visited exactly once, in the SDVRP a customer may be visited any number of times. The exact method we propose is based on a decomposition of the problem where the possible routes, with the Delivery quantities, are generated in the subproblem. The generated routes are also used to find a heuristic solution to the problem. We consider both the case where the fleet of Vehicles is unlimited and the case where the fleet is limited to the minimum possible number of Vehicles. We solve to optimality instances with larger size with respect to previous approaches, find new best solutions to several benchmark instances and reduce the optimality gap on most of the benchmark instances. © 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 58(4), 241–254 2011 © 2011 Wiley Periodicals, Inc.

  • an optimization based heuristic for the split Delivery Vehicle routing problem
    Transportation Science, 2008
    Co-Authors: Claudia Archetti, Grazia M Speranza, Martin W P Savelsbergh
    Abstract:

    The split Delivery Vehicle routing problem is concerned with serving the demand of a set of customers with a fleet of capacitated Vehicles at minimum cost. Contrary to what is assumed in the classical Vehicle routing problem, a customer can be served by more than one Vehicle, if convenient. We present a solution approach that integrates heuristic search with optimization by using an integer program to explore promising parts of the search space identified by a tabu search heuristic. Computational results show that the method improves the solution of the tabu search in all but one instance of a large test set.

  • worst case analysis for split Delivery Vehicle routing problems
    Transportation Science, 2006
    Co-Authors: Claudia Archetti, Martin W P Savelsbergh, Grazia M Speranza
    Abstract:

    In the Vehicle routing problem (VRP) the objective is to construct a minimum cost set of routes serving all customers where the demand of each customer is less than or equal to the Vehicle capacity and where each customer is visited once. In the split Delivery Vehicle routing problem (SDVRP) the restriction that each customer is visited once is removed. We show that the cost savings that can be realized by allowing split deliveries is at most 50. We also study the variant of the VRP in which the demand of a customer may be larger than the Vehicle capacity, but where each customer has to be visited a minimum number of times. We show that the cost savings that can be realized by allowing more than the minimum number of required visits is again at most 50. Furthermore, we analyze the performance of simple heuristics that handle customers with demands larger than the Vehicle capacity by employing full load out-and-back trips to these customers until the demands become less than or equal to the Vehicle capacity. Finally, we investigate situations in which demands are discrete and Vehicle capacities are small.

  • The Split Delivery Vehicle Routing Problem: A Survey
    Operations Research Computer Science Interfaces, 1
    Co-Authors: Claudia Archetti, Maria Grazia Speranza
    Abstract:

    In the classical Vehicle Routing Problem (VRP) a fleet of capacitated Vehicles is available to serve a set of customers with known demand. Each customer is required to be visited by exactly one Vehicle and the objective is to minimize the total distance traveled. In the Split Delivery Vehicle Routing Problem (SDVRP) the restriction that each customer has to be visited exactly once is removed, i.e., split deliveries are allowed. In this chapter we present a survey of the state-of-the-art on the SDVRP.

  • OR - An Overview on the Split Delivery Vehicle Routing Problem
    Operations Research Proceedings, 1
    Co-Authors: Claudia Archetti, Maria Grazia Speranza
    Abstract:

    In the classical Vehicle Routing Problem (VRP) a fleet of capacitated Vehicles is available to serve a set of customers with known demand. Each customer is required to be visited by exactly one Vehicle and the objective is to minimize the total distance traveled. In the Split Delivery Vehicle Routing Problem (SDVRP) the restriction that each customer has to be visited exactly once is removed, i.e., split deliveries are allowed. In this paper we present a survey of the state-of-the-art on this important problem.

Martin W P Savelsbergh - One of the best experts on this subject based on the ideXlab platform.

  • an optimization based heuristic for the split Delivery Vehicle routing problem
    Transportation Science, 2008
    Co-Authors: Claudia Archetti, Grazia M Speranza, Martin W P Savelsbergh
    Abstract:

    The split Delivery Vehicle routing problem is concerned with serving the demand of a set of customers with a fleet of capacitated Vehicles at minimum cost. Contrary to what is assumed in the classical Vehicle routing problem, a customer can be served by more than one Vehicle, if convenient. We present a solution approach that integrates heuristic search with optimization by using an integer program to explore promising parts of the search space identified by a tabu search heuristic. Computational results show that the method improves the solution of the tabu search in all but one instance of a large test set.

  • worst case analysis for split Delivery Vehicle routing problems
    Transportation Science, 2006
    Co-Authors: Claudia Archetti, Martin W P Savelsbergh, Grazia M Speranza
    Abstract:

    In the Vehicle routing problem (VRP) the objective is to construct a minimum cost set of routes serving all customers where the demand of each customer is less than or equal to the Vehicle capacity and where each customer is visited once. In the split Delivery Vehicle routing problem (SDVRP) the restriction that each customer is visited once is removed. We show that the cost savings that can be realized by allowing split deliveries is at most 50. We also study the variant of the VRP in which the demand of a customer may be larger than the Vehicle capacity, but where each customer has to be visited a minimum number of times. We show that the cost savings that can be realized by allowing more than the minimum number of required visits is again at most 50. Furthermore, we analyze the performance of simple heuristics that handle customers with demands larger than the Vehicle capacity by employing full load out-and-back trips to these customers until the demands become less than or equal to the Vehicle capacity. Finally, we investigate situations in which demands are discrete and Vehicle capacities are small.

Grazia M Speranza - One of the best experts on this subject based on the ideXlab platform.

  • an optimization based heuristic for the split Delivery Vehicle routing problem
    Transportation Science, 2008
    Co-Authors: Claudia Archetti, Grazia M Speranza, Martin W P Savelsbergh
    Abstract:

    The split Delivery Vehicle routing problem is concerned with serving the demand of a set of customers with a fleet of capacitated Vehicles at minimum cost. Contrary to what is assumed in the classical Vehicle routing problem, a customer can be served by more than one Vehicle, if convenient. We present a solution approach that integrates heuristic search with optimization by using an integer program to explore promising parts of the search space identified by a tabu search heuristic. Computational results show that the method improves the solution of the tabu search in all but one instance of a large test set.

  • worst case analysis for split Delivery Vehicle routing problems
    Transportation Science, 2006
    Co-Authors: Claudia Archetti, Martin W P Savelsbergh, Grazia M Speranza
    Abstract:

    In the Vehicle routing problem (VRP) the objective is to construct a minimum cost set of routes serving all customers where the demand of each customer is less than or equal to the Vehicle capacity and where each customer is visited once. In the split Delivery Vehicle routing problem (SDVRP) the restriction that each customer is visited once is removed. We show that the cost savings that can be realized by allowing split deliveries is at most 50. We also study the variant of the VRP in which the demand of a customer may be larger than the Vehicle capacity, but where each customer has to be visited a minimum number of times. We show that the cost savings that can be realized by allowing more than the minimum number of required visits is again at most 50. Furthermore, we analyze the performance of simple heuristics that handle customers with demands larger than the Vehicle capacity by employing full load out-and-back trips to these customers until the demands become less than or equal to the Vehicle capacity. Finally, we investigate situations in which demands are discrete and Vehicle capacities are small.

Guy Desaulniers - One of the best experts on this subject based on the ideXlab platform.

  • branch and price and cut for the split Delivery Vehicle routing problem with time windows
    Operations Research, 2010
    Co-Authors: Guy Desaulniers
    Abstract:

    This paper addresses the split-Delivery Vehicle routing problem with time windows (SDVRPTW) that consists of determining least-cost Vehicle routes to service a set of customer demands while respecting Vehicle capacity and customer time windows. The demand of each customer can be fulfilled by several Vehicles. For solving this problem, we propose a new exact branch-and-price-and-cut method, where the column generation subproblem is a resource-constrained elementary shortest-path problem combined with the linear relaxation of a bounded knapsack problem. Each generated column is associated with a feasible route and a compatible Delivery pattern. As opposed to existing branch-and-price methods for the SDVRPTW or its variant without time windows, integrality requirements in the integer master problem are not imposed on the variables generated dynamically, but rather on additional variables. An ad hoc label-setting algorithm is developed for solving the subproblem. Computational results show the effectiveness of the proposed method.

Edward Wasil - One of the best experts on this subject based on the ideXlab platform.

  • a novel approach to solve the split Delivery Vehicle routing problem
    International Transactions in Operational Research, 2017
    Co-Authors: Ping Chen, Bruce L. Golden, Xingyin Wang, Edward Wasil
    Abstract:

    The split Delivery Vehicle routing problem (SDVRP) is a relaxed version of the classic capacitated Vehicle routing problem (CVRP). Customer demands are allowed to split among Vehicles. This problem is computationally challenging and the state-of-the-art heuristics are often complicated to describe and difficult to implement, and usually have long computing times. All these hinder their application by practitioners to solve real-world problems. We propose a novel, efficient, and easily implemented approach to solve the SDVRP using an a priori split strategy, that is, each customer demand is split into small pieces in advance. Our computational experiments on 82 benchmark instances show that our algorithm is overall much more efficient and produces results that are comparable to those from the state-of-the-art approaches.

  • A worst-case analysis for the split Delivery Vehicle routing problem with minimum Delivery amounts
    Optimization Letters, 2012
    Co-Authors: Yupei Xiong, Damon Gulczynski, Daniel J. Kleitman, Bruce L. Golden, Edward Wasil
    Abstract:

    In the Vehicle routing problem (VRP), a fleet of Vehicles must service the demands of customers in a least-cost way. In the split Delivery Vehicle routing problem (SDVRP), multiple Vehicles can service the same customer by splitting the deliveries. By allowing split deliveries, savings in travel costs of up to 50 % are possible, and this bound is tight. Recently, a variant of the SDVRP, the split Delivery Vehicle routing problem with minimum Delivery amounts (SDVRP-MDA), has been introduced. In the SDVRP-MDA, split deliveries are allowed only if at least a minimum fraction of a customer’s demand is delivered by each visiting Vehicle. We perform a worst-case analysis on the SDVRP-MDA to determine tight bounds on the maximum possible savings.

  • the multi depot split Delivery Vehicle routing problem an integer programming based heuristic new test problems and computational results
    Computers & Industrial Engineering, 2011
    Co-Authors: Damon Gulczynski, Bruce L. Golden, Edward Wasil
    Abstract:

    The multi-depot split Delivery Vehicle routing problem combines the split Delivery Vehicle routing problem and the multiple depot Vehicle routing problem. We define this new problem and develop an integer programming-based heuristic for it. We apply our heuristic to 30 instances to determine the reduction in distance traveled that can be achieved by allowing split deliveries among Vehicles based at the same depot and Vehicles based at different depots. We generate new test instances with high-quality, visually estimated solutions and report results on these instances.

  • the split Delivery Vehicle routing problem applications algorithms test problems and computational results
    Networks, 2007
    Co-Authors: Si Chen, Bruce L. Golden, Edward Wasil
    Abstract:

    In the split Delivery Vehicle routing problem (SDVRP), a customer's demand can be split among several Vehicles. In this article, we review applications of the SDVRP including the routing of helicopters in the North Sea and solution methods such as integer programming and tabu search. We develop a new heuristic that combines a mixed integer program and a record-to-record travel algorithm. Our heuristic produces high-quality solutions to six benchmark problems that have 50–199 customers and generally performs much better than tabu search. On five other problems for which lower bounds exist, our heuristic obtains solutions within 5.85p, on average. Finally, we generate 21 new test problems that have 8–288 customers. A near-optimal solution can be visually estimated for each problem. We apply our heuristic to these new problems and report our computational results. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 318–329 2007