TITLE

An Improved Branch-and-Cut Algorithm for the Capacitated Vehicle Routing Problem

AUTHOR(S)
Achuthan, N.R.; Caccetta, L.; Hill, S.P.
PUB. DATE
May 2003
SOURCE
Transportation Science;May2003, Vol. 37 Issue 2, p153
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
The capacitated vehicle routing problem (CVRP) deals with the distribution of a single commodity from a centralized depot to a number of specified customer locations with known demands. The CVRP considered in this paper assumes common vehicle capacity, fixed or variable number of vehicles, and an objective to minimize the total distance traveled by all the vehicles. This paper develops several new cutting planes for this problem, and uses them in an exact branch-and-cut algorithm. Two of the new cutting planes are based on a specified structure of an optimal solution and its existence. Computational results are reported for 1,650 simulated Euclidean problems as well as 24 standard literature test problems; solved problems range in size from 15-100 customers. A comparative analysis demonstrates the significant computational benefit of the proposed method.
ACCESSION #
9909022

 

Related Articles

  • Outsourcing Across Borders In Europe.  // Logistics & Transport Focus;Jan/Feb2001, Vol. 3 Issue 1, p54 

    The Institute of Logistics and Transport responded to the invitation of the government of Great Britain to comment on the proposals submitted by the European Commission for access to community port services and for other policy initiatives. The institute confined its response to the broader...

  • Vehicle Routing and Scheduling with Full Truckloads. Arunapuram, Sundararajan; Mathur, Kamlesh; Solow, Daniel // Transportation Science;May2003, Vol. 37 Issue 2, p170 

    Truckload carriers are constantly faced with the problem of shipping full truckloads of goods at minimum cost between pairs of cities or customers, using a fleet of trucks located at one or more depots. In this paper, a new branch-and-bound algorithm for solving an integer-programming...

  • Future Warehouses.  // Logistics & Transport Focus;Mar2000, Vol. 2 Issue 2, p62 

    The response of the Institute of Logistics and Transport to the consultation document on the aviation industry which was published by the government of Great Britain in 2000 is the main focus of this article. A consideration of the views of the institute and other interested organizations, can...

  • Members of the Move.  // Logistics & Transport Focus;Jan/Feb2001, Vol. 3 Issue 1, p81 

    The Institute of Logistics and Transport has made submissions in respect of government consultations on logistics- and transportation-related issues, as of 2001. The House of Commons Transport Sub-Committee of the Transport, Local Government and the Regions Committee has decided to investigate...

  • Quick-fire cable.  // Management Services;May2000, Vol. 44 Issue 5, p25 

    This article focuses on the problems encountered by local authorities in Wales, after they first published their first local Transport Plans in 2000. In particular, this article considers the process and content of the local transport plans and examines some of the innovatory measures and...

  • Transport Planning &mdas; Skills Remain a High Priority.  // Logistics & Transport Focus;Jun2002, Vol. 4 Issue 5, p72 

    Reports that the Institute of Logistics and Transport is continuing to support the Transport Planning Skills Initiative.

  • Detecting Dynamic Traffic Assignment Capacity Paradoxes in Saturated Networks. Akamatsu, Takashi; Heydecker, Benjamin // Transportation Science;May2003, Vol. 37 Issue 2, p123 

    Creation of a new link or increase in capacity of an existing link can reduce the efficiency of a congested network as measured by the total travel cost. This phenomenon, of which an extreme example is given by Braess paradox, has been examined in conventional studies within the framework of...

  • Interchain Plan Board.  // Software World;Sep2003, Vol. 34 Issue 5, p21 

    Reports on Interchain's development of an intuitive multi-user electronic plan board functionality in response to the industry's need for an instand overview and control of a changing daily transportation resource planning environment. Offer of quick access to shipments and resource...

  • CILT(UK) Road Capacity and Road Charging Forum.  // Logistics & Transport Focus;Jan2009, Vol. 11 Issue 1, p8 

    This article presents the results of the Chartered Institute of Logistics and Transport Road Capacity and Road Charging Forum which asked members for responses to the Green Light group research on road charging. An estimated 4,000 members were presented with the document with a particular...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

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

Try another library?
Sign out of this library

Other Topics