TITLE

An Exact Method for the Vehicle Routing Problem with Backhauls

AUTHOR(S)
Mingozzi, Aristide; Giorgi, Simone; Baldacci, Roberto
PUB. DATE
August 1999
SOURCE
Transportation Science;Aug99, Vol. 33 Issue 3, p315
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
We consider the problem in which a fleet of vehicles located at a central depot is to be optimally used to serve a set of customers partitioned into two subsets of linehaul and backhaul customers. Each route starts and ends at the depot and the backhaul customers must be visited after the linehaul customers. A new (0-1) integer programming formulation of this problem is presented. We describe a procedure that computes a valid lower bound to the optimal solution cost by combining different heuristic methods for solving the dual of the LP-relaxation of the exact formulation. An algorithm for the exact solution of the problem is presented. Computational tests on problems proposed in the literature show the effectiveness of the proposed algorithms in solving problems up to 100 customers.
ACCESSION #
4292826

 

Related Articles

  • Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs. Binyuan Chen; Küçükyavuz, Simge; Sen, Suvrajeet // Operations Research;Jan2011, Vol. 59 Issue 1, p202 

    In this paper, we give a finite disjunctive programming procedure to obtain the convex hull of general mixed-integer linear programs (MILP) with bounded integer variables. We propose a finitely convergent convex hull tree algorithm that constructs a linear program that has the same optimal...

  • Reformulations in mathematical programming: automatic symmetry detection and exploitation. Liberti, Leo // Mathematical Programming;Feb2012, Vol. 131 Issue 1/2, p273 

    If a mathematical program has many symmetric optima, solving it via Branch-and-Bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for automatically finding the formulation group of any given...

  • Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms. Malandraki, Chryssi; Daskin, Mark S. // Transportation Science;Aug92, Vol. 26 Issue 3, p185 

    The time dependent vehicle routing problem (TDVRP) is defined as follows. A vehicle fleet of fixed capacities serves customers of fixed demands from a central depot. Customers are assigned to vehicles and the vehicles routed so that the total time of the routes is minimized. The travel time...

  • A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem. Hadjar, Ahmed; Marcotte, Odile; Soumis, François // Operations Research;Jan/Feb2006, Vol. 54 Issue 1, p130 

    We consider the multiple depot vehicle scheduling problem (MDVSP) and propose a branch-and-bound algorithm for solving it that combines column generation, variable fixing, and cutting planes. We show that the solutions of the linear relaxation of the MDVSP contain many "odd cycles." We derive a...

  • FROM VALID INEQUALITIES TO HEURISTICS: A UNIFIED VIEW OF PRIMAL-DUAL APPROXIMATION ALGORITHMS IN COVERING PROBLEMS. Bertsimas, Dimitris; Chung-Piaw Teo // Operations Research;Jul/Aug98, Vol. 46 Issue 4, p503 

    In recent years approximation algorithms based on primal-dual methods have been successfully applied to a broad class of discrete optimization problems. In this paper, we propose a generic primal-dual framework to design and analyze approximation algorithms for integer programming problems of...

  • Optimal volume subintervals with k points and star discrepancy via integer programming. Thi�mard, Eric // Mathematical Methods of Operations Research;2001, Vol. 54 Issue 1, p21 

    Given n points in the s-dimensional unit cube, we consider the problem of finding a subinterval of minimum or maximum volume that contains exactly k of the n points. We give integer programming formulations of these problems and techniques to tackle their resolution. These optimal volume...

  • Parallel branch-and-branch algorithms: Survey and synthesis. Gendron, Bernard; Crainic, Teodor Gabriel // Operations Research;Nov/Dec94, Vol. 42 Issue 6, p1042 

    We present a detailed and up-to-date survey of the literature on parallel branch-and-bound algorithms. We synthesize previous work in this area and propose a new classification of parallel branch-and-bound algorithms. This classification is used to analyze the methods proposed in the literature....

  • Column enumeration based decomposition techniques for a class of non-convex MINLP problems. Rebennack, Steffen; Kallrath, Josef; Pardalos, Panos M. // Journal of Global Optimization;Feb2009, Vol. 43 Issue 2/3, p277 

    We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration...

  • Mixed-Integer Cuts from Cyclic Groups. Fischetti, Matteo; Saturni, Cristiano // Mathematical Programming;Jan2007, Vol. 109 Issue 1, p27 

    We analyze a separation procedure for Mixed-Integer Programs related to the work of Gomory and Johnson on interpolated subadditive functions. This approach has its roots in the Gomory-Johnson characterization on the master cyclic group polyhedron. To our knowledge, the practical benefit that can...

Share

Read the Article

Courtesy of VIRGINIA BEACH PUBLIC LIBRARY AND SYSTEM

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics