TITLE

# Solving a Practical Pickup and Delivery Problem

AUTHOR(S)
Hang Xu; Zhi-Long Chen; Rajagopal, Srinivas; Arunapuram, Sundar
PUB. DATE
August 2003
SOURCE
Transportation Science;Aug2003, Vol. 37 Issue 3, p347
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
We consider a pickup and delivery vehicle routing problem commonly encountered in real-world logistics operations. The problem involves a set of practical complications that have received little attention in the vehicle routing literature. In this problem, there are multiple carriers and multiple vehicle types available to cover a set of pickup and delivery orders, each of which has multiple pickup time windows and multiple delivery time windows. Orders and carrier/vehicle types must satisfy a set of compatibility constraints that specify which orders cannot be covered by which carrier/vehicle types and which orders cannot be shipped together. Order loading and unloading sequence must satisfy the nested precedence constraint that requires that an order cannot be unloaded until all the orders loaded into the truck later than this order are unloaded. Each vehicle trip must satisfy the driver's work rules prescribed by the Department of Transportation which specify legal working hours of a driver. The cost of a trip is determined by several factors including a fixed charge, total mileage, total waiting time, and total layover time of the driver. We propose column generation based solution approaches to this complex problem. The problem is formulated as a set partitioning type formulation containing an exponential number of columns. We apply the standard column generation procedure to solve the linear relaxation of this set partitioning type formulation in which the resulting master problem is a linear program and solved very efficiently by an LP solver, while the resulting subproblems are computationally intractable and solved by fast heuristics. An integer solution is obtained by using an IP solver to solve a restricted version of the original set partitioning type formulation that only contains the columns generated in solving the linear relaxation. The approaches are evaluated based on lower bounds obtained by solving the linear relaxation to optimality by using an exact dynamic programming algorithm to solve the subproblems exactly. It is shown that the approaches are capable of generating near-optimal solutions quickly for randomly generated instances with up to 200 orders. For larger randomly generated instances with up to 500 orders, it is shown that computational times required by these approaches are acceptable.
ACCESSION #
17685653

## Related Articles

• GatorTE utility vehicle.  // Landscape & Irrigation;Dec2005, Vol. 29 Issue 12, p11

The article introduces the John Deere Traditional Series Gator utility vehicles, the new Gator TE replaces the E-Gator with improved safety, convenience and performance features. It includes information about the performance application of the product.

• Spartan Strongbox.  // Landscape & Irrigation;Dec2005, Vol. 29 Issue 12, p11

The article introduces the Spartan Strongbox truck body, with cab chassis, which offers a wide selection of compartments and shelves, plus five body lengths. It offers information about the physical description, performance application and capability of the product.

• Powered trolley.  // RoSPA Occupational Safety & Health Journal;Jul2004, Vol. 34 Issue 7, p44

Evaluates the Power Pusher trolley from Nu-Star Material Handling Ltd. Functions of the product; Dimensions.

• Measures Would Be Taken By the Courts in Deciding Whether to Trigger the Off-hire Clause. Zheng Xia // Cross-Cultural Communication;2009, Vol. 5 Issue 1, p44

In the scope of carriage of goods by sea, the central issue is the vessel. Obviously, the efficiency of the vessel is of utmost importance not only to the shipowner who render the vessel to earn hire but also the charterer who pay the hire in the purpose to utilize the vessel. Sometimes, the...

• Police probe coach crash.  // Travel Weekly: The Choice of Travel Professionals;2/25/2005, Issue 1758, p2

This article reports that the Cantabrica Coaches is awaiting the results of a German police inquiry following a crash which killed one person and left a further seven injured. The police interviewed the driver on Wednesday and are now preparing a report, although they have not said when it will...

• TAÅžINMA EÅžYASI TAÅžIMALARINDA TAÅžIYICININ Ã–ZEL YÃœKÃœMLÃœLÃœKLERÄ°. TOPSOY, Fevzi // Ankara Barosu Dergileri;2014, Vol. 72 Issue 2, p21

Turkish Commercial Code (TCC) No. 6102 has made significant changes in the field of carriage law as well as in many areas. One of these changes regulates with carriage of household goods. The household goods are goods that are removed from a house or office or similar area and are carried to a...

• Construction/Maintenance Carts. Sockel, Tom // New Equipment Digest;Jun2006, Vol. 71 Issue 6, p18

The article evaluates the Trade Titan work carts from Milwaukee Electric Tool Corp., and offers information regarding its features and capabilities.

• Their Favorite Vehicle. Baugher, Jennifer // Canter Magazine;Winter2003, Vol. 2 Issue 1, p26

Suggests that horses and horse-drawn vehicles are more important than ever to the survival of countries like Cuba. Weakened economy that cannot support a fuel-dependent society; Background on the introduction and uses of horses and horse-drawn carts in Cuba; Class division; Cuban omnibus;...

• FOR HEATING & SELLING: Food and beverage carts. Chater, Amanda // FoodService Director;07/15/2000, Vol. 13 Issue 7, p118

Provides information on food service carts. Types of cart used at Newark Public Schools in New Jersey; Features of carts at Middlebury College in Vermont; Four essential points to consider when implementing a cart; Advantage and disadvantage of carts.

Share