This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Sigurd, M. Articles by Sig, M. Search for Related Content

Scheduling Transportation of Live Animals to Avoid the Spread of Diseases

Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen, Denmark
sigurd{at}diku.dk
pisinger{at}diku.dk
michael{at}sig-post.dk

In the classical vehicle-routing problem (VRP) the objective is to service some geographically scattered customers with a given number of vehicles at the minimal cost. In the present paper, we consider a variant of the VRP where the vehicles should deliver some goods between groups of customers. The customers have an associated time window, a precedence number, and a quantity. Each vehicle should visit the customers within their time windows, in nondecreasing order of precedence respecting the capacity of the vehicle. The problem will be denoted the pickup-and-delivery problem with time windows and precedence constraints (PDPTWP). The PDPTWP has applications in the transportation of live animals where veterinary rules demand that the livestocks are visited in a given sequence in order not to spread specific diseases. We propose a tighter formulation of the PDPTWP based on Dantzig-Wolfe decomposition. The formulation splits the problem into a master problem, which is a kind of set-covering problem, and a subproblem that generates legal routes for a single vehicle. The LP-relaxation of the decomposed problem is solved through delayed column generation. Computational experiments show that the obtained bounds are less than 0.24% from optimum for the considered problems. As solving the pricing problems takes up the majority of the solution time, a reformulation of the problem is proposed that makes use of the precedence constraints. By merging customers having the same precedence number into "super nodes," the pricing problem may be reformulated as a shortest-path problem defined on an acyclic layered graph. This makes it possible to solve the pricing problem in pseudopolynomial time through dynamic programming. The paper concludes with a comprehensive computational study involving real-life instances from the transportation of live pigs. It is demonstrated that instances with up to 580 nodes can be solved to optimality.

Key Words: freight transportation; precedence constraints; column generation; layered graph; dynamic programming
History: Received: August 2001; revised: June 2002; revised: November 2002; accepted: November 2002.

This article has been cited by other articles:

				S. Ropke and D. Pisinger An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows Transportation Science, November 1, 2006; 40(4): 455 - 472. [Abstract] [PDF]