An Exact Algorithm for the Vehicle Routing Problem with Backhauls

Toth, Paolo; Vigo, Daniele
November 1997
Transportation Science;Nov97, Vol. 31 Issue 4, p372
Academic Journal
The Vehicle Routing Problem with Back hauls is an extension of the capacitated Vehicle Routing Problem where the customers' set is partitioned into two subsets. The first is the set of Linehaul, or Delivery, customers, while the second is the set of Backhaul, or Pickup, customers. The problem is known to be NP-hard in the strong sense and finds many practical applications in distribution planning. In this paper we consider, in a unified framework, both the symmetric and the asymmetric versions of the vehicle routing problem with backhauls, for which we present a new integer linear programming model and a Lagrangian lower bound which is strengthened in a cutting plane fashion. The Lagrangian lower bound is then combined, according to�the additive approach, with a lower bound obtained by dropping the capacity constraints, thus obtaining an effective overall bounding procedure. A branch-and-bound algorithm, reduction procedures and dominance criteria are also described. Computational tests on symmetric and asymmetric instances from the literature, involving up to 100 customers, are given, showing the effectiveness of the proposed approach.


Related Articles

  • Building Better Nurse Scheduling Algorithms. Aickelin, Uwe; White, Paul // Annals of Operations Research;Apr2004, Vol. 128 Issue 1-4, p159 

    The aim of this research is twofold: Firstly, to model and solve a complex nurse scheduling problem with an integer programming formulation and evolutionary algorithms. Secondly, to detail a novel statistical method of comparing and hence build better scheduling algorithms by identifying...

  • Solving the Teacher Assignment-Course Scheduling Problem by a Hybrid Algorithm. Gunawan, Aldy; Kien Ming Ng; Kim Leng Poh // International Journal of Computer, Information & Systems Science;2007, Vol. 1 Issue 2, p136 

    This paper presents a hybrid algorithm for solving a timetabling problem, which is commonly encountered in many universities. The problem combines both teacher assignment and course scheduling problems simultaneously, and is presented as a mathematical programming model. However, this problem...

  • Controlled rounding and cell perturbation: statistical disclosure limitation methods for tabular data. Salazar-González, Juan-José // Mathematical Programming;Feb2006, Vol. 105 Issue 2/3, p583 

    Rounding methods are common techniques in many statistical offices to protect sensitive information when publishing data in tabular form. Classical versions of these methods do not consider protection levels while searching patterns with minimum information loss, and therefore typically the...

  • A linear programming formulation for the maximum complete multipartite subgraph problem. Cornaz, Denis // Mathematical Programming;Feb2006, Vol. 105 Issue 2/3, p329 

    Let G be a simple undirected graph with node set V( G) and edge set E( G). We call a subset [InlineMediaObject not available: see fulltext.] independent if F is contained in the edge set of a complete multipartite (not necessarily induced) subgraph of G, F is dependent otherwise. In this paper...

  • A COMPUTER CODE FOR INTEGER SOLUTIONS TO LINEAR PROGRAMS. Haldi, John; Isaacson, Leonard M. // Operations Research;Nov/Dec65, Vol. 13 Issue 6, p946 

    This paper reports on a new computer code (called "LIP1") for solving integer programming problems, which will be distributed for general use through SHARE. LIP1 was written as an experimental program for the purpose of reexamining and further testing the efficiency of GOMORY's original...

  • A Multivehicle Tanker Scheduling Problem. Bellmore, M.; Bennigton, G.; Lubore, S. // Transportation Science;Feb71, Vol. 5 Issue 1, p36 

    The Dantzig and Fulkerson Tanker Scheduling Problem is concerned with the determination of the minimum size and optimal routing of a fleet of homogeneous tankers needed to meet a prescribed schedule of deliveries. This problem has been formulated as a network flow problem. Later formulations...

  • A Column Generation Algorithm for a Ship Scheduling Problem. Appelgren, Leif H. // Transportation Science;Feb69, Vol. 3 Issue 1, p53 

    This paper describes an algorithm for a ship scheduling problem, obtained from a Swedish ship-owning company. The algorithm uses the Dantzig-Wolfe decomposition method for linear programming. The subprograms are simple network flow problems that are solved by dynamic programming. The master...

  • A Branch-and-Cut Procedure for the Multimode Resource-Constrained Project-Scheduling Problem. Guidong Zhu; Bard, Jonathan F.; Gang Yu // INFORMS Journal on Computing;Summer2006, Vol. 18 Issue 3, p377 

    This paper considers the multimode resource-constrained project-scheduling problem (MRCPSP) with a minimum-makespan objective. An exact branch and cut algorithm is presented based on the integer linear programming (ILP) formulation of the problem. In the preprocessing stage, lower bounds on the...

  • Variable Neighborhood Search for Parallel Machines Scheduling Problem with Step Deteriorating Jobs. Wenming Cheng; Peng Guo; Zeqiang Zhang; Ming Zeng; Jian Liang // Mathematical Problems in Engineering;2012, Vol. 2012, Special section p1 

    In many real scheduling environments, a job processed later needs longer time than the same job when it starts earlier. This phenomenon is known as scheduling with deteriorating jobs to many industrial applications. In this paper, we study a scheduling problem of minimizing the total completion...


Read the Article


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

Try another library?
Sign out of this library

Other Topics