The Two-Echelon Capacitated Vehicle Routing Problem: Models and Math-Based Heuristics

Perboli, Guido; Tadei, Roberto; Vigo, Daniele
August 2011
Transportation Science;Aug2011, Vol. 45 Issue 3, p364
Academic Journal
Multiechelon distribution systems are quite common in supply-chain and logistics. They are used by public administrations in their transportation and traffic planning strategies, as well as by companies, to model own distribution systems. In the literature, most of the studies address issues relating to the movement of flows throughout the system from their origins to their final destinations. Another recent trend is to focus on the management of the vehicle fleets required to provide transportation among different echelons. The aim of this paper is twofold. First, it introduces the family of two-echelon vehicle routing problems (VRPs), a term that broadly covers such settings, where the delivery from one or more depots to customers is managed by routing and consolidating freight through intermediate depots. Second, it considers in detail the basic version of two-echelon VRPs, the two-echelon capacitated VRP, which is an extension of the classical VRP in which the delivery is compulsorily delivered through intermediate depots, named satellites. A mathematical model for two-echelon capacitated VRP, some valid inequalities, and two math-heuristics based on the model are presented. Computational results of up to 50 customers and four satellites show the effectiveness of the methods developed.


Related Articles

  • Science Applications International Corp. [SAI]: TSA Seeks EDS Maintenance Services for Reveal EDS.  // TR2: Terror Response Technology Report;1/5/2011, Vol. 7 Issue 1, p17 

    The article focuses on a pre-solicitation notice issued by the U.S. Transportation Security Administration for performance-based logistics services to the government-owned Reveal Imaging Technologies explosive detection systems.

  • Routing in Point-to-Point Delivery Systems: Formulations and Solution Heuristics. Leung, Janny M. Y.; Magnanti, Thomas L.; Singhal, Vijay // Transportation Science;Nov90, Vol. 24 Issue 4, p245 

    We develop an optimization-based approach for a point-to-point route planning problem that arises in many large scale delivery systems (for example, less-than-truckload freight, rail, mail and package delivery, communications). In these settings, a firm which must ship goods between many origin...

  • Policies News.  // Logistics & Transport Focus;Apr2004, Vol. 6 Issue 3, p49 

    This section presents updates on transportation and business logistics policies in Great Britain as of April 2004. The Department for Transport has announced its contract with congestion data specialist IT IS to provide the Department, the Highways Agency, Transport Direct and local authorities...

  • Generation of Primary Input Blocking Pattern for Power Minimization during Scan Testing. Wang-Dauh Tseng // Journal of Electronic Testing;Feb2007, Vol. 23 Issue 1, p75 

    Abstract??In this paper we propose a new approach to generate aprimary input blocking patternfor applying to the primary inputs during shift cycle such that the switching activity occurred in the combinational part of the circuit under test can be suppressed as much as possible. The primary...

  • Newsvendor Bounds and Heuristic for Optimal Policies in Serial Supply Chains. Shang, Kevin H.; Jing-Sheng Song // Management Science;May2003, Vol. 49 Issue 5, p618 

    We consider the classic N-stage serial supply systems with linear costs and stationary random demands. There are deterministic transportation leadtimes between stages, and unsatisfied demands are backlogged. The optimal inventory policy for this system is known to be an echelon base-stock...

  • Probabilistic analysis of a combined aggregation and math programming heuristic for a general... Federgruen, Awi; Ryzin, Garrett van // Management Science;Aug1997, Vol. 43 Issue 8, p1060 

    We propose and analyze a heuristic that uses region partitioning and an aggregation scheme for customer attributes (load size, time windows, etc.) to create a finite number of customer types. A math program is solved based on these aggregated customer types to generate a feasible solution to the...

  • CILT launches Food Logistics Forum.  // Logistics & Transport Focus;Mar2011, Vol. 13 Issue 3, p6 

    The article focuses on the Food Logistics Forum launched by the Chartered Institute of Logistics and Transport (CILT) at the Food & Drink Logistics Show in Great Britain in 2011.

  • RADAR SCREEN.  // JoC Week;8/26/2002, Vol. 3 Issue 34, p6 

    Reports on developments related to business logistics and transportation in the United States as of August 26, 2002. Contract negotiations between the International Longshore Warehouse Union and the Pacific Maritime Association; Retirement of senior staff of the U.S. Custom Service.

  • The Week.  // JoC Week;8/26/2002, Vol. 3 Issue 34, p8 

    Presents news items related to business logistics and transportation in the United States for the week ending August 26, 2002. National Customs Brokers and Forwarders Association of America's opposition to a U.S. Senate proposal to fund port security by introducing a container fee; Opening of a...


Other Topics