An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints

Iori, Manuel; Salazar-González, Juan-José; Vigo, Daniele
May 2007
Transportation Science;May2007, Vol. 41 Issue 2, p253
Academic Journal
We consider a special case of the symmetric capacitated vehicle routing problem, in which a fleet of K identical vehicles must serve n customers, each with a given demand consisting in a set of rectangular two-dimensional weighted items. The vehicles have a two-dimensional loading surface and a maximum weight capacity. The aim is to find a partition of the customers into routes of minimum total cost such that, for each vehicle, the weight capacity is taken into account and a feasible two-dimensional allocation of the items into the loading surface exists. The problem has several practical applications in freight transportation, and it is NP-hard in the strong sense. We propose an exact approach, based on a branch-and-cut algorithm, for the minimization of the routing cost that iteratively calls a branch-and-bound algorithm for checking the feasibility of the loadings. Heuristics are also used to improve the overall performance of the algorithm. The effectiveness of the approach is shown by means of computational results.


Related Articles

  • A Hybrid Tabu Search/Branch-and-Bound Algorithm for the Direct Flight Network Design Problem. Büdenbender, Klaus; Grünert, Tore; Sebastian, Hans-Jürgen // Transportation Science;Nov2000, Vol. 34 Issue 4, p364 

    This paper introduces a network design problem with a structure that is encountered in many transportation processes. The general organization of these systems is as follows. Freight has to be transported between a large number of origins and destinations. To consolidate the freight, it is first...

  • Steps to Transportation Management Excellence. Sykes, Scott; Menner, Matthew; Chiodo, Vincent // Outsourced Logistics;Jun2008, Vol. 1 Issue 1, p30 

    The article provides some steps in managing transportation function. It is said that for many firms, current capabilities in transportation management are incomplete and are spending more money on freight transportation than necessary. It is further said that taking the steps provided in the...

  • best practices in transportation Freight data management: which elements are essential to capture. Goodwill, Dan // Canadian Transportation & Logistics;Jan2011, Vol. 114 Issue 1, p38 

    The article presents ways on how to have a better freight data management. It notes the need of shipper to be certain to the data elements including the shipment number, pickup date, shipment weight and unit of loading in order to know the type of container to be used, space occupied and loading...

  • A branch and bound algorithm for the strip packing problem. Alvarez-Valdes, R.; Parre�o, F.; Tamarit, J. // OR Spectrum;Apr2009, Vol. 31 Issue 2, p431 

    We propose a new branch and bound algorithm for the two dimensional strip packing problem, in which a given set of rectangular pieces have to be packed into a strip of given width and infinite length so as to minimize the required height of the packing. We develop lower bounds based on integer...

  • Optimal Solutions for the Closest-String Problem via Integer Programming. Meneses, Cl�udio N.; Zhaosong Lu; Oliveira, Carlos A.S.; Pardalos, Panos M. // INFORMS Journal on Computing;Fall2004, Vol. 16 Issue 4, p419 

    In this paper we study the closest-string problem (CSP), which can be defined as follows: Given a finite set T = {s�, s�,&hellip,sn} of strings, each string with length m, find a center string t of length m minimizing d, such that for every string sI ϵ T, dH(t, si) = d....

  • Design of planar articulated mechanisms using branch and bound. Stolpe, Mathias; Kawamoto, Atsushi // Mathematical Programming;Jun2005, Vol. 103 Issue 2, p357 

    This paper considers an optimization model and a solution method for the design of two-dimensional mechanical mechanisms. The mechanism design problem is modeled as a nonconvex mixed integer program which allows the optimal topology and geometry of the mechanism to be determined simultaneously....

  • Multi-Way Distance Join Queries in Spatial Databases. Corral, Antonio; Manolopoulos, Yannis; Theodoridis, Yannis; Vassilakopoulos, Michael // GeoInformatica;Dec2004, Vol. 8 Issue 4, p373 

    Let a tuple of n objects obeying a query graph (QG) be called the n-tuple. The �D_distance-value� of this n-tuple is the value of a linear function of distances of the n objects that make up this n-tuple, according to the edges of the QG. This paper addresses the problem of finding the...

  • Improved Generation of Minimal Addition Chains. Bahig, Hatem // Computing;Oct2006, Vol. 78 Issue 2, p161 

    An addition chain for a natural number n is a sequence 1= a 0< a 1< . . . < a r = n of numbers such that for each 0< i= r, a i = a j + a k for some 0= k= j< i. An improvement by a factor of 2 in the generation of all minimal (or one) addition chains is achieved by finding sufficient...

  • A Dual-Bounded Algorithm for the p-Median Problem. Galv�o, Roberto O. // Operations Research;Sep/Oct80, Vol. 28 Issue 5, p1112 

    The p-median problem consists of locating p facilities on a network, so that the sum of shortest distances from each of the nodes of the network to its nearest facility is minimized. A dual bound, based on the dual of the LP relaxation of the integer programming formulation of the problem, is...


Read the Article


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

Try another library?
Sign out of this library

Other Topics